离散数学

课程编码：B2511001H 英文名称：Discrete Mathematics 课时：60 学分：3.00 课程属性：专业必修课 主讲教师：吴凌云

本课程主要针对人工智能专业的本科生，讲授离散数学中的数理逻辑、集合论、代数结构、算法、数论、组合数学和图论等内容，培养学生掌握离散数学的基本概念、结论、算法、推理与证明方法，了解数学中的抽象思维与人工智能技术实践之间的内在联系，并能够用离散数学中的理论和方法解决本专业的实际问题，为后续课程的学习及将来从事人工智能相关工作奠定必要的理论基础。

This course is primarily designed for undergraduate students majoring in artificial intelligence. It covers topics in discrete mathematics such as mathematical logic, set theory, algebraic structures, algorithms, number theory, combinatorics, and graph theory. The course aims to help students master the basic concepts, conclusions, algorithms, reasoning, and proof methods of discrete mathematics. It also enables them to understand the intrinsic connections between abstract mathematical thinking and the practical applications of artificial intelligence techniques. Furthermore, students will learn to apply the theories and methods from discrete mathematics to solve practical problems in their field of study. This course lays the necessary theoretical foundation for subsequent courses and future work related to artificial intelligence.

本课程属于人工智能专业的专业必修课，教学目的是使学生获得离散数学的基础知识，熟练掌握离散数学的基本概念、结论、算法、推理与证明方法，了解数学中的抽象思维与人工智能技术实践之间的内在联系，并能够用离散数学中的理论和方法解决本专业的实际问题，培养学生的抽象思维、逻辑推理、分析证明、概括分析等综合解决问题的能力。
通过本课程的学习，要求学生了解离散数学的主要组成部分及各部分所涉及的基本内容，包括数理逻辑、集合论、代数结构、算法、数论、组合数学和图论等，及其在人工智能技术领域中的应用；理解离散数学的基本概念、结论、算法、应用方法及适用范围；了解主要模型的应用；掌握离散数学的推理与证明过程、基本算法及应用方法；掌握处理离散量的一些数学方法，并具有较好的逻辑推理和抽象思维的能力，为后续课程的学习及将来从事解决本专业实际问题的工作做好必要的理论储备。

《微积分》、《线性代数》、《计算机科学导论》

离散数学是研究离散量的结构及其相互关系的数学学科，是现代数学的一个重要分支。本课程主要讲授离散数学中的主要基础知识，包括数理逻辑、集合论、代数结构、算法、数论、组合数学和图论等。本课程的授课方式以课堂讲授为主。

 

第1章  基础：逻辑和证明

1.1 命题逻辑

1.2 命题逻辑的应用

1.3 命题等价式

1.4 谓词和量词

1.5 嵌套量词

1.6 推理规则

1.7 证明导论

1.8 证明的方法和策略

本章学习要求：理解命题和逻辑运算的相关概念，熟练掌握使用逻辑运算符描述复合命题，了解命题逻辑的应用；理解命题公式的相关概念，熟练掌握常见的逻辑恒等式；理解命题等价性、范式（析取范式与合取范式）的定义，熟练掌握范式之间的相互转换；理解命题公式的可满足性问题，了解可满足性问题解决方法与相关应用；理解谓词、量词的概念，熟练掌握使用谓词、量词的方法；理解量词的嵌套，掌握自然语言与逻辑表达式之间的相互翻译；理解命题逻辑推演系统，熟练掌握运用推理规则证明一般命题公式；理解定理的概念和常见定理证明方法，熟练掌握运用直接证明、反证法、枚举证明等方法证明一般定理；理解并掌握常见证明技巧和策略；理解存在性证明和唯一性证明的概念。

 

第2章  基本结构：集合、函数、序列、求和与矩阵

2.1 集合

2.2 集合运算

2.3 函数

2.4 序列与求和

2.5 集合的基数

2.6 矩阵

本章学习要求：理解集合的概念与运算，熟练掌握集合运算；理解函数的定义，以及单射、满射、双射的定义，熟练掌握双射函数证明方法；理解逆函数、复合函数的定义，熟练掌握函数求逆和复合运算；理解序列的定义，了解常见的特殊序列及其性质；理解集合基数的定义，熟练掌握可数集与不可数集的证明方法。

 

第3章  算法基础

3.1 算法

3.2 函数的增长

3.3 算法的复杂度

本章学习要求：理解算法的定义，熟练掌握常见的搜索算法、排序算法、贪心算法等；理解停机问题的定义，掌握其证明方法；理解函数增长趋势的表示方法，熟练掌握使用大O表示法、大Omega和Theta表示法描述函数；理解算法复杂度的定义，熟练掌握常见算法的复杂度计算。

 

第4章  数论基础

4.1 整除性和模算术

4.2 整数表示和算法

4.3 素数和最大公约数

4.4 求解同余方程

4.5 同余的应用

本章学习要求：理解整除性的定义和表示，了解整数整除性的一些基本性质，熟练掌握整除算法的表示；理解模算术、同余的定义和表示，熟练掌握同余的性质和相关应用；理解模m算术的定义和表示，熟练掌握模m算术的相关性质；理解有关进制的定义，熟练掌握整数的各种进制表示和各种进制之间的相互转换；熟练掌握不同进制下的整数运算的加法算法和乘法算法；理解模指数运算的定义，熟练掌握模指数运算的算法；理解素数的定义、算术基本定理的意义及作用；掌握证明素数的方法，掌握求解素因子分解式的方法以及分解的唯一性原理；理解 Eratosthenes筛法造素数表的原理，了解一些特殊素数以及相关的重要猜想和开放问题；理解最大公约数、最小公倍数、互质、两两互素的概念和性质，掌握并能应用欧几里得算法求最大公约数、最小公倍数；理解线性同余方程的定义，掌握求解线性同余方程的方法，理解中国剩余定理的意义及作用；掌握大整数做算术运算的方法；理解并掌握费马小定理及相关应用；理解模素数的原根和离散对数的定义以及表示。

 

第5章  归纳与递归

5.1 数学归纳法

5.2 强归纳法与良序性

5.3 递归定义与结构归纳法

5.4 递归算法

本章学习要求：理解数学归纳法的定义，熟练掌握数学归纳法的证明原理和技巧；理解强归纳法的定义、原理和证明方法；熟练掌握良序性的定义和公理；理解有关递归、迭代的定义，熟练掌握结构归纳法；理解拉梅定理及其证明方法；了解广义归纳法；理解递归和迭代算法的定义，掌握求解一些问题的递归和迭代算法设计。

 

第6章  计数

6.1 计数基础

6.2 鸽巢原理

6.3 排列与组合

6.4 二项式系数与恒等式

6.5 排列与组合的推广

6.6 生成排列与组合

本章学习要求：理解并掌握基本的计数原则（乘法原理和加法原理），并能够应用求解较为复杂的计数问题；理解并掌握鸽巢原理和广义鸽巢原理及其应用；理解在无重复和有重复元素情形下的排列与组合的定义，熟练掌握相关的排列与组合的计数公式及其应用；掌握二项式定理，掌握一些特殊组合恒等式的证明；掌握一些生成排列与组合的算法。

 

第7章  高级计数技术

7.1 递推关系的应用

7.2 求解递推关系

7.3 分而治之算法与递推关系

7.4 生成函数

7.5 容斥原理

7.6 容斥原理的应用

本章学习要求：理解递推关系的定义，掌握利用递推关系构造模型；理解普通生成函数、指数型生成函数的定义；掌握广义二项式定理及其应用；熟练掌握求解常系数线性齐次递推关系的特征根方法、生成函数法；熟练掌握求解常系数线性非齐次递推关系的特殊方法；理解分治递推关系及相关应用；了解一些特殊的计数序列；熟练掌握容斥原理及其应用。

 

第8章  关系

8.1 关系及其性质

8.2 n元关系及其应用

8.3 关系的表示

8.4 关系的闭包

8.5 等价关系

8.6 偏序关系

本章学习要求：理解关系的定义，理解并掌握关系的性质和组合（运算），熟练掌握关系的表示方法；熟练掌握关系的闭包及相关性质；理解等价关系、等价类的定义和性质，掌握等价类划分的方法；理解偏序的定义和性质，掌握偏序的哈斯图表示，掌握判定偏序的方法；理解与偏序相关的若干概念，如：极大元、极小元、最大元、最小元、最大上界、最小下界等；理解格的定义；理解并掌握拓扑排序的算法。

 

第9章  图论基础

9.1 图和图模型

9.2 图的术语和特殊的图

9.3 图的表示和图的同构

9.4 图的连通性

9.5 欧拉路径与哈密顿路径

9.6 最短路问题

9.7 平面图

9.8 图染色问题

本章学习要求：理解图的定义和表示，了解常用的图模型和分类，熟练掌握图的常用表示；理解图同构的定义，了解相关问题和应用；理解图的连通性，了解相关问题和应用；理解欧拉通路、欧拉回路，熟练掌握欧拉通路和欧拉回路的充要条件和算法；理解中国邮递员问题及其意义；理解哈密顿通路与哈密顿回路，了解旅行商问题及其应用；理解最短路问题，熟练掌握最短路的Dijkstra算法；理解平面图的定义，熟练掌握使用欧拉公式，熟练掌握证明平面图的方法；理解图着色的定义，了解相关问题和应用。

 

第10章  树

10.1 树的概述

10.2 树的应用

10.3 树的遍历

10.4 生成树

10.5 最小生成树

本章学习要求：理解树的定义，熟练掌握树的性质；理解二叉搜索树、决策树、博弈树，熟练掌握应用决策树证明问题复杂度下界，熟练掌握哈夫曼编码；熟练掌握树的三种遍历方法；理解生成树的定义，了解深度优先搜索和宽度优先搜索，熟练掌握最小生成树的Prim算法和Kruskal算法。

章节/学时分配	讲课	习题课	实验课	上机课	讨论课	其它
第1章	8
第2章	4
第3章	4
第4章	6	2
第5章	4
第6章	6
第7章	6
第8章	6
第9章	8	2
第10章	4

在课程教学内容的实施过程中，教学团队坚持“教书育人”的理念，在传授知识的同时，也注重立德树人，弘扬社会主义核心价值观，培养科学情怀。例如，在课堂上相关知识点上，如：杨辉三角形（与二项式定理相关）、中国邮递员问题等，讲解中国古代和现代科学家做出重要贡献和刻苦研究的事例，也向学生们展示与授课内容相关的我国相关数学家的故事和最新进展，让青年学子缅怀老一辈科学家，致敬新一代离散数学工作者，学习他们勇攀科技高峰的科研奋斗精神与爱国主义情怀。

离散数学及其应用（原书第8版），作者：Kenneth H.Rosen，译者：徐六通、杨娟、吴斌，机械工业出版社，2019年。

吴凌云，研究员，博士生导师。现任中国科学院数学与系统科学研究院生物信息中心主任，中国运筹学会常务副秘书长、常务理事，中国工业与应用数学学会副秘书长。主要从事运筹学与信息科学的交叉研究，在国内外重要学术期刊和会议发表论文一百余篇，主持过多项国家自然科学基金项目和国家重点研发计划课题，获中国运筹学会青年科技奖。