集合论与图论课程

离散数学教程（集合论与图论）离散数学：计算机科学与技术的数学基础课内容：集合论，图论，组合数学，代数结构，数理逻辑集合论:（第1-4章）组合数学初步:（第5-7章）图论:（第8-11章）教师介绍⏹教师：吴永辉博士副教授⏹简历：⏹1984-1988 上海科技大学计算机系本科⏹1988-1991 复旦大学计算机系硕士⏹1991-2003 华东师范大学计算机系工作⏹1998-2001 复旦大学计算机系博士⏹2003-复旦大学计算机系工作⏹答疑E-mail: yhwu@《集合论与图论》课件制作软件⏹Microsoft PowerPoint⏹MathType Equation《集合论与图论》课程大纲⏹课程性质与目的⏹教学内容与要求⏹使用教材、参考书籍⏹命题说明和题型课程性质、目的与基本要求⏹课程性质本课程讲授计算机科学与技术的数学基础课《离散数学》的部分主要内容：集合论、图论与组合数学初步，是计算机专业的主干课程之一。

本课程前行课程为线性代数，数学分析(上)。

⏹课程目的使学生掌握集合论、图论与组合数学初步的基本内容，并对证明的思想和方法深入理解和体会，初步培养学生的思维过程的数学化。

⏹基本要求：⏹掌握集合论、组合学和图论的基本概念，清楚了解引入基本概念的实际背景、各概念间相互关系；掌握基本定理以及有关理论题的证明技巧；掌握解决计数问题的基本方法和技巧；掌握图论中各算法设计的思想、正确性证明以及算法的应用。

为进一步学习计算机其他课程打下坚实的基础。

教学方式本课程以课堂讲授为主。

考核方式⏹平时作业；⏹集合论、组合数学和图论3次课堂练习；⏹期中，期末的两次笔试考试。

教学内容与要求----集合论⏹第一章集合的基本概念掌握：集合的基本概念，集合的运算。

了解：集合论的悖论。

掌握证明两个集合相等的基本法和公式法。

⏹第二章关系掌握：关系的性质、运算和关系的闭包，以及等价关系和偏序关系。

了解：关系在关系数据库中的应用。

掌握证明的类型。

《集合论与图论》课程示范性教学设计1 本课程教学方法（一）教学方法在这里，仅总结一下我的教学方法，不细展开，因此不涉及专业术语和与专业有关的例子。

以下仅是一些指导思想：（1 ）启发式、由浅入深、从直观到抽象。

要用些生动的例子帮助学生理解抽象概念的含义，但要做到生动而有趣又不失概念的准确性和推理的严格性，使学生易于接受，又了解直观背景。

（2 ）突出基本思想及方法，强调规律性，提高学生的抽象能力。

要从哲学的高度强调概念是第一位的，引导学生思考问题时必须清楚理解所涉及的概念，使问题有一个明确的提法，引导学生掌握从问题到建立数学模型这一抽象过程的方法。

（3 ）利用集合论某些概念和理论与方法总结已学过的知识（如微积分、线性代数）找出本质的规律或主线，使学生认识事物内部的深刻规律。

其次，随时指出在后继课如何应用这些知识、在科技论文中将怎样出现这些知识的应用。

这不仅提高了学习的积极性，也使学生增强了学习的目的性。

（4 ）只要有可能就要以建立数学模型组织教学，讲习题也不例外。

这样，能使学生加深印象—任何时候都要抓住事物的本质与事物之间的联系。

（5 ）鼓励学生多问为什么，为什么会是这样子而不是那个样子。

不是教会学生怎样去使用工具、去模仿或复制，而是要教会学生独立思考，发现问题，提出问题和解决问题的思考，否则思维会退化。

（5 ）适当地提出一些未解决的问题。

尚无答案的问题是摆在我们及学生面前的有无限价值的东西，因为支持大学的最高准则是探究未知领域。

事实上，在每年教此课时，提一些问题确实有学生在思考。

（6 ）注意每个学科（内部）的美。

如果某部分很丑或太复杂，人们倾向于认为是不清楚的和暂时的，它没有真正反映客观规律，因为我们相信，越接近终极真理，我们的解释中的不自然的东西就越少。

科学是以越来越完美、有力的理论向终极真理发展的。

（二）关于素质教育、培养创新精神的人才的思考素质教育应该是各类教育的核心，而培养创新人才则是高等教育的任务（见高等教育法，第五条）。

“什么是教育？教育就是当你把所学的东西都忘掉后，最终剩下的东西！”“最终剩下的东西就是一个人的创新意识和学习能力。

”把教学的着眼点集中在掌握科学基础知识和训练创新能力上，着重培养科学的思维方法，把知识传授与科学探索融为一体，激发学生的好奇心和创造性。

教学质量是“教育水平高低和效果优劣的程度”（教育大词典）前言0.1集合论与图论是数学的一部分“对于大自然这本奥秘无穷的书，我读不懂”。

──莎士比亚：《安东尼和克里奥帕特拉》（1564—1616）“如果不理解它的语言，没有人能读懂宇宙这本伟大的书，它的语言就是数学”。

──伽里略（1564—1642）“在任何特定的理论中，只有其中包含数学的部分才是真正的科学”。

──康德（1724—1804）数学不专属自然科学，也不专属社会科学，更不专属于文学艺术。

它是一种宇宙语言，为一切文明生物共有、共享。

0.2 主要内容“我想知道上帝是如何创造这个世界的。

对这个或那个现象、这个或那个元素的谱我并不感兴趣。

我想知道的是他的思想，其他的都是细节问题”。

──爱因斯坦（1879—1955）本课主要讲述集合论（Set Theory）：集合及其运算、映射及其合成、关系及其运算、无穷集合及其基数。

图论（Graph Theory）：图的一些基本概念、一些特殊的图、树及其性质、割点和桥、连通度、平面图、图的着色、有向图。

基本思想和意义我们从“集合”这个基本概念开始建立集合理论。

就某种观点来看，“集合”与“性质”是同义词，是基本概念之一。

这样，集合用来描述事物的性质——我们的研究对象，映射用来描述事物之间的联系——运算、关系，从而为集合建立了结构。

于是，为建立系统的数学模型提供了数学描述语言——工具，代数系统就是在集合上引入运算。

集合论又提供了研究数学模型的性质，发现新联系的推理方法，从而找出事物的运动规律。

而图论是上述思想的一个具体应用，事实上，图论为任何一个包含了一种二元关系的系统提供了一个数学模型；部分地，也因为使用了图解式表示方法，图就具有一种直观的和符合美学的外形。

离散数学教程（集合论与图论）离散数学：计算机科学与技术的数学基础课内容：集合论，图论，组合数学，代数结构，数理逻辑集合论:（第1-4章）组合数学初步:（第5-7章）图论:（第8-11章）教师介绍⏹教师：吴永辉博士副教授⏹简历：⏹1984-1988 上海科技大学计算机系本科⏹1988-1991 复旦大学计算机系硕士⏹1991-2003 华东师范大学计算机系工作⏹1998-2001 复旦大学计算机系博士⏹2003-复旦大学计算机系工作⏹答疑E-mail: yhwu@《集合论与图论》课件制作软件⏹Microsoft PowerPoint⏹MathType Equation《集合论与图论》课程大纲⏹课程性质与目的⏹教学内容与要求⏹使用教材、参考书籍⏹命题说明和题型课程性质、目的与基本要求⏹课程性质本课程讲授计算机科学与技术的数学基础课《离散数学》的部分主要内容：集合论、图论与组合数学初步，是计算机专业的主干课程之一。

本课程前行课程为线性代数，数学分析(上)。

⏹课程目的使学生掌握集合论、图论与组合数学初步的基本内容，并对证明的思想和方法深入理解和体会，初步培养学生的思维过程的数学化。

⏹基本要求：⏹掌握集合论、组合学和图论的基本概念，清楚了解引入基本概念的实际背景、各概念间相互关系；掌握基本定理以及有关理论题的证明技巧；掌握解决计数问题的基本方法和技巧；掌握图论中各算法设计的思想、正确性证明以及算法的应用。

为进一步学习计算机其他课程打下坚实的基础。

教学方式本课程以课堂讲授为主。

考核方式⏹平时作业；⏹集合论、组合数学和图论3次课堂练习；⏹期中，期末的两次笔试考试。

教学内容与要求----集合论⏹第一章集合的基本概念掌握：集合的基本概念，集合的运算。

了解：集合论的悖论。

掌握证明两个集合相等的基本法和公式法。

⏹第二章关系掌握：关系的性质、运算和关系的闭包，以及等价关系和偏序关系。

了解：关系在关系数据库中的应用。

掌握证明的类型。

《集合论与图论》课程教学大纲一、课程基本信息课程编号：CS31111课程名称：集合论与图论英文名称：SET THEORY AND GRAPH THEORY课程学时：64；讲课学时： 48；实验学时：上机学时：习题学时：16;课程学分：4.0开课单位：计算机科学与技术学院授课对象：计算机大类专业（包括计算机科学与技术、物联网工程、生物信息学、信息安全）、软件工程大类专业开课学期： 1春先修课程：工科数学分析、线性代数二、课程目标《集合论与图论》是计算机大类/软件工程大类专业的一门专业基础课程。

本课程为后继的专业基础课及专业课提供必要的数学工具，为描述离散模型提供数学语言。

该课程的设置主要是为了培养学生的抽象思维和逻辑推理能力，提高学生分析问题和解决问题的能力，提高学生的数学修养及计算机科学素质。

要想用计算机解决问题就要为它建立数学模型，即描述研究对象及对象与对象之间的联系，并通过事物之间的联系找出事物的运动规律。

集合论与图论为此提供了强有力的描述工具与推理理论。

本课程的目标是通过理论学习，为计算机科学与技术专业的后继课及将来的科学研究提供必要的相关数学知识，提供建立离散系统的数学模型的数学描述工具；使学生正确地理解概念，正确地使用概念进行推理，养成一个好的思维习惯，理解理论与实践的关系；引导学生观察生活、社会和大自然，分析事物间的联系，建立系统的模型，提出和解决其中的复杂工程问题。

课程具体目标如下：课程目标1：掌握集合论与图论的基本概念、基本原理、基本方法等基本知识，培养形式化、模型化的抽象思维能力，使学生能够利用集合论与图论的概念、理论与方法识别、表达计算相关的复杂工程问题，逐步学会为计算类复杂工程问题建立数学模型；课程目标2：掌握直接证明法、反证法、数学归纳法、构造法等常用的证明方法，培养机械化、自动化的逻辑推理能力，使学生能够利用集合论与图论的概念、理论与方法并通过文献研究分析复杂工程问题，并能获得有效的结论，理解并逐步设计求解这些问题的算法基本思想；课程目标3：掌握资料查阅方法，学会对课堂所学理论知识进行扩展，培养自学能力。