教学大纲-哈尔滨工业大学

《集合论与图论》课程教学大纲

一、课程基本信息

课程编号：13SD03100400 课程名称：集合论与图论

英文名称：SET THEORY AND GRAPH THEORY 课程类别：专业基础课

总学时： 64； 授课：48； 习题课：16 ； 总学分：4 先修课程：工科数学分析、线性代数

适用专业：计算机大类专业（包括计算机科学与技术、物联网工程、生物信息学、信息安全）。

开课学期：1春季学期

开课单位：计算机科学与技术学院 课程要求：必修课

二、课程目标

《集合论与图论》是计算机/软件工程大类的一门专业基础课程。本课程为后继的专业基础课及专业课提供必要的数学工具，为描述离散模型提供数学语言。该课程的设置主要是为了培养学生的抽象思维和逻辑推理能力，提高学生分析问题和解决问题的能力，提高学生的数学修养及计算机科学素质。

要想用计算机解决问题就要为它建立数学模型，即描述研究对象及对象与对象之间的联系，并通过事物之间的联系找出事物的运动规律。集合论与图论为此提供了强有力的描述工具与推理理论。

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

课程具体目标如下：

课程目标1：掌握集合论与图论的基本概念、基本原理、基本方法等基本知识，培养形式化、模型化的抽象思维能力，使学生能够利用集合论与图论的概念、理论与方法识别、表达计算相关的复杂工程问题，逐步学会为计算类复杂工程问题建立数学模型；

课程目标2：掌握直接证明法、反证法、数学归纳法、构造法等常用的证明方法，培养机械化、自动化的逻辑推理能力，使学生能够利用集合论与图论的概念、理论与方法并通过文献研究分析复杂工程问题，并能获得有效的结论，理解并逐步设计求解这些问题的算法基本思想；

课程目标3：培养自学能力，自学能力的关键是习惯的养成与资料的获取。通过布置思考题训练学生学会获取扩展阅读资料，并引导学生阅读一些经典图书、电子资源（相关的会议与刊物）、相关研究群体的个人主页等。此外，该课程的每一章都会布置大量的作业题，而且不提供参考答案，这也可以大大提升学生的自学能力。

课程目标4：培养学生的独立思考与创新能力，人类知识的创造、科学的进展都有前因后果，来龙去脉。因此勤奋学习，全面掌握文献，积累深厚基础，加上追根到底，万事必问为什么的好奇心，就是创新的源泉。本课程利用习题课等环节，通过引导与鼓励学生敢于怀疑与发问来促进独立思考与创新能力的培养。

表1. 课程对专业培养要求的支撑 专业培养要求 (本课程可覆盖的)专业培养要求指标点 （1）具有良好的包括计算思维在内的科学思维能力。（2）具有研究素质 运用数学和自然科学解决复杂工程问题的能力。（3）能够应用数学和自然科学和工程科学的基本原理，识别、表达并通过文献研究分析复杂工程问题，以获得有效结论。 掌握如形式化、模型化、自动化等包括抽象思维与逻辑思维在计算思维能力 内的计算思维能力，能够运用计算思维分析和解决复杂的工程问题。 算法设计与分析能力 （1）能够运用算法设计与分析相关的知识，并针对复杂的工程问题，设计求解问题相关的算法。 （1）能够就复杂工程问题与业界同行及社会公众进行有效沟通表达与沟通能力 和交流。（2）能够熟练运用合适的模型表达与沟通复杂工程问题求解方案。（3）能够跨学科进行交流，理解他人所表述的内容，发表自己的见解或提出建设性意见。 自学、独立思考与创新能力 （1）具有终身学习意识，善于独立思考，具有提出问题、分析问题和解决问题的能力。（4）具有创新意识、创新思维和创新能力。 课程目标3 课程目标4 课程目标1 课程目标2 课程目标1 课程目标2 课程目标1 课程目标2 (支撑指标点的)课程目标 课程目标2 三、课程教学内容

序号 教学内容 推荐教学要求 学时 式 目标 推荐教学方对应的课程1．掌握集合、子集、全集、空集和幂集等概念。熟悉常用的表示集合的方法。能够判定元素与集集合、子集、集合的相等关系、幂集；集合并、交、差、对称差、补集、迪卡尔乘积运算，各运算的性质及相互联系；有穷集合的基数、基本计数法则、容斥原理及应用。 合、集合与集合之间的关系；熟练掌握两个集合相等关系和包含关系的定义和性质，能够利用定义证明两个集合相等。 2.熟练掌握集合之间的各种运算以及集合运算的基本等式，能够利用它们来证明更复杂的集合等式。 3.掌握余集与集合笛卡儿乘积的概念以及De Morgan公式。 4．掌握求解与有穷集合计数相关的实际问题。 映射的基本定义、鸽1.掌握映射的基本概念以及单射、满射、双射2 巢原理、映射的一般之间的区别。给定一个映射能够确定它是单射、性质、映射的合成、满射、双射等？ 逆映射、置换、二元2.掌握映射的合成和逆映射的定义以及他们存6 课堂讲授/慕课自学/翻转课堂 课程目标1 课程目标2 课堂讲授/6 慕课自学/翻转课堂 课程目标1 1 运算、应用。 在的条件。 3.掌握集合的象及原象的定义及相关性质；掌握给定一个映射，能确定一点的象、一个集合的象和原象以及映射的合成等。 4.掌握针对具体问题构造映射来解决问题。 5.掌握把映射和其他章节有机的结合起来。 1.掌握二元关系的形式定义及其各种表示方法：序对、矩阵、关系图等；能正确使用集合表达式、关系矩阵、关系图等给定的关系，并要求能够从一种形式写出另一种形式。 2.掌握关系的各种运算，包括集合运算及关系合成和关系的逆运算。 3.熟练掌握二元关系的各种特殊性质：自反、反自反、对称、反对称和传递等，并理解这些性质是如何反映在关系图上、关系矩阵上等。 4.掌握二元关系的闭包的意义和简单性质，能求出有限集合上的二元关系的闭包。 5.熟练掌握等价关系的概念，并掌握划分、等价类、商集的定义和基本性质，掌握等价关系与划分之间的关系。 6.熟练掌握偏序关系、偏序集、全序、良序等概念以及偏序集的极大元、极小元、最大元、最小元、上界、下界、上确界、下确界等概念；能画出有限偏序集的Hasse图，并根据图讨论偏序集的某些性质。 8 课堂讲授/慕课自学/翻转课堂 课程目标1 课程目标2 二（n）元关系、几个特殊二元关系、二元3 关系的表示、关系的合成运算、传递闭包、等价关系与集合的划分、偏序关系。 可数集及其性质、存1．掌握可数集，连续集和无穷集合基数的概念在不可数集—对角线及其性质。 4 法，基数及其比较、2．熟练掌握Cantor“对角线解法”的证明方法。 连续统、罗素悖论与3．掌握与无穷集合有关但与有穷集合不同的一数学危机。 图、路、圈、连通图、5 偶图、补图、欧拉图、哈密顿图、图的邻接矩阵、最短路径问题。 些性质，从而深刻体会无穷的特征。 1.熟练掌握图的基础知识中的概念和定理和连通图的问题及其证明。 2.掌握欧拉图和哈密顿图的概念及判断方法。 3.掌握最短路的算法及其邮路问题。 4.能够判断和证明图的有关结论 1.掌握树的基础概念和定理。 树及其性质、生成树、6 割点和桥及其特征性质，最小生成树问题。 2.掌握求连通图生成树的破圈法及求带权连通图的最小生成树的Kruskal算法和Prim算法。 3.掌握利用树的等价定义判断和证明树的有关理论。 4.掌握割点、桥和割集的定义、性质。 顶点连通度与边连通度1.掌握连通度的概念及其性质 7 及其关系、偶图的匹配、2.掌握匹配、最大匹配、完备匹配和完美匹配Hall定理。 等概念；能够利用相异性条件和t条件判定偶4 课堂讲授/慕课自学/翻转课堂 课程目标1 课程目标2 课堂讲授/4 慕课自学/翻转课堂 课程目标1 课程目标2 课堂讲授/8 慕课自学/翻转课堂 课程目标1 课程目标2 课堂讲授/4 慕课自学/翻转课堂 课程目标1 课程目标2 图是完全匹配？ 1.熟练掌握连通平面图的欧拉公式及其几个推论。 2.掌握并运用库拉托斯基（K.Kuratowski）定理判定一个图是否为平面图。 3.熟练掌握图的着色的概念及其有关性质。 1.熟练掌握有向图的基础知识中的概念和定理。 有向图、有向路、有向2．掌握有向图同构的概念，会判断结点数较少圈、有向图的连通、有的图之间的同构。 9 向图的邻接矩阵、可达3．掌握可达性及其各种连通性并能熟练地作出矩阵、关联矩阵、有向判断。 树、有根树、有序树、4．对于上述的全部内容都能够用矩阵熟练地加比赛图。 以判断。 5. 掌握根树和有序树的概念及其性质；有序树（森林）的二元树表示方法。 每部分内容对应1-2学时的习题课 复习课堂讲授的基本概念、基本理论、基本方法，深入理解相关的内容，并能运用所学知识解决相关问题。 16 课堂讲授/以练代讲/翻转课堂 课程目标3 课程目标4 平面图及其欧拉公8 式、图的着色、五色定理，介绍计算机证明四色猜想。 课堂讲授/4 慕课自学/翻转课堂 课程目标1 课程目标2 课堂讲授/4 慕课自学/翻转课堂 课程目标1 课程目标2 10 四、课程教学方法

（1）证明为主：作为一门数学课，与以往不同的是以证明为主而不是以计算为主。因此，要学会证明技术，学会分析问题和解决问题的思想方法。

（2）强调抽象：本课程的特点是概念多，但都有实在的、具体的实物背景，最后要落实到抽象的定义上，概念是第一位的。讲清概念的背景，最好先从具体的实例出发，直观地给出实在的东西，然后推广或抽出本质得到抽象概念。没有抽象就没有科学，因此，基本概念必须抽象化，定义基本概念时不关注具体对象是什么，而是强调数学上“不加定义的对象”之间的相互关系以及它们所遵循的运算法。

（3）发现解法：已知的事物和要求的事、已知量和未知量、假设和结论，这些都是一些隔开的事物和想法，解题的过程就是要在这原先隔开的事物或想法之间找出联系。这种联系是由一条链来贯穿的：一个证明象是一串论据，象是一条由一系列结论组成的链，也许是一条长链。这条链的强度是由它最弱的一环来代表的。因为哪怕是只少了一环，就不会有连续推理的链，也就不会有有效的证明。

（4）瞻前顾后：站在新的概念、理论、方法和观点看已学过的知识（在这里是微积分、线性代数、概率论、C语言程序设计等）有时会更清楚，显得简单，理解会更深刻；我们还将随时指出本课的内容在计算机专业中的应用，特别是在后继课──数据结构与算法、形式语言与自动机、编译、数据库原理、计算复杂性理论等中的应用。但不能详述，目的是告诉你现在值得花点精力学它。

（5）基于问题：学习要以思考为基础，一般的学习只是一种模仿，而没有任何创用，思考由怀疑和答案组成，学习便是经常怀疑，经常随时发问。怀疑是智慧的大门，知道得越多，就越会发问，而问题就越多。所以，发问使人进步，发问和答案一样重要。但在独立思

考之前，必须先有基础知识，所谓“获得基础知识”并不是形式上读过某门课程，而是将学过的东西完全弄懂。本课程的学习中，概念是第一位的，概念的背景（直观原型）、抽象定义的内涵和外延要准确，应用时才能运用自如。

（6）敢于犯错：学习的一种方法，经常还是唯一的方法，就在于首先犯错误。我们在学习，多数时间在通过犯错误学习。教师在传授知识和技术的过程中，偶尔会传授教训，这种教训如果没有经过你的亲身体验，不会变成有用的经验。知识没有教训作为根基，只能是纸上谈兵。上课、读书、复习、做作业、讨论、做实验、自己编程序、上机调试排错…是绝对必要的。提倡学习中互相讨论、辩论、提出不同的方法。

（7）辅导答疑：这是任课教师与学生直接交流、沟通思想的时间。对学生一视同仁应当是教师的基本心理，而善待每个学生是教师应当坚持的教育原则。学生应该充分利用好答疑时间，是与老师交流的机会，会获得意想不到的东西。教师要为学生解答经过努力尚未弄懂的问题，没有经过思考的习题、问题最好暂时不问，否则收获不大。教师不要立即暴露你的全部秘密——让学生在你说出来之前先去猜——尽量让他们自己去找出来。你可以给一些提示，创造一个稍好的环境，让学生自己去发现，这样可以增强学生的信心。学生可以把老师看成朋友或者长者，这时除谈业务外，还可以谈理想、人生、道德、责任、如何做人…

五、课程考核方法

本课程成绩满分100分。由以下部分构成： 考核环节 建议分值 比例 10% 10% 考核/评价细则 对应的课程目标 课程目标3 课程目标4 课程目标3 课程目标4 课程目标1 课程目标2 课程目标3 课程目标4 1.随堂测试 2.作业 2-3周一次学生小测验（5-8分钟） 每章一次作业 考试题目要全面，符合大纲要求，同时要做到3.期末考试 80% 体现重点，题型多样化（包括单项选择题、判断对错、填空题、简答题、证明等），难度和题量的梯度应按照教学要求的不同层次安排。 课程最终成绩 = 1+2+3 期末考试以集合论与图论课程教学大纲的要求为准。考试题目要全面，符合大纲要求，同时要做到体现重点，题型多样化（包括单项选择题、判断对错、填空题、简答题、证明等），难度和题量的梯度应按照教学要求的不同层次安排。 本课程笔试，考卷中考核概念是否理解占40%，是否掌握基本理论和基本方法占30%，考核学生能否灵活应用基本概念、基本理论、基本方法占20%，较难题占10%。 期末考试卷面成绩满分为100分（占总分的80%）。 六、课程达成度评价方法

课程目标1至课程目标4的总达成度

= 课程最终成绩不低于60分的学生人数 / 应参与学生人数。

七、主要教材和参考书

1.《离散数学引论》（修订版），王义和编著，哈尔滨工业大学出版，2016. 2.《离散数学教程》，耿素云等编著，北京大学出版社，2015。 3.《离散数学》，左孝凌等编著，上海科技文献出版社，2016。

大纲撰写人：

姜守旭 大纲审核人：

本文来源：https://www.bwwdw.com/article/9i8.html