中山大学 中山大学

离散数学基础

所属微专业:

图片
课程概述

   本课程不提供教学服务、作业批改及证书发放。

   离散数学是计算机专业的核心基础课程。计算机只能处理离散结构的数据,连续的、复杂的应用结构只能通过适当的离散化,分解抽象出离散的计算模型,才能由计算机进行处理。离散数学是计算机科学技术与工程的理论基础,而且随着计算机科学技术的发展不断形成新的应用体系。学生通过离散数学的学习,能够在数学推理、组合分析、离散结构构造、算法设计以及应用与建模等方面形成基本的离散思维方法提高抽象思维和逻辑推理能力。离散数学也是后续专业课程(数据结构、编译系统、操作系统、数据库原理、人工智能、计算机网络等)的数学基础。离散数学的应用体系十分广泛,例如数字逻辑理论、逻辑电路设计、程序正确性证明、信息编码理论以及大量的图的实际应用模型。

   离散数学课程的主要内容包括:数理逻辑、集合与关系代数、图论以及代数结构等。通过本课程的学习,学生应该熟练掌握有关集合、关系、图、树等离散结构的基本知识,掌握有关逻辑和证明的基本技巧和方法,理解并能初步运用离散结构进行问题建模和求解。


证书要求

本课程不提供证书服务。

预备知识

授课大纲


第1周 命题逻辑的基本概念

数理逻辑的发展:逻辑、经典逻辑与非经典逻辑,公理系统

命题及其符号化

命题合式公式及其真值

命题等值公式与联结词的完备集


第2周 命题逻辑的等值演算和自然推理

命题公式的范式

命题推理基本定律

举例及应用


第3周 命题逻辑的自然演绎系统和归结推理

命题逻辑的自然演绎系统

命题逻辑的归结推理方法


第4周 一阶逻辑的基本概念和等值演算

个体、谓词与量词

谓词公式及其解释

谓词逻辑的自然语言形式化

基本的谓词等值式


第5周 一阶逻辑推理基础

谓词逻辑的推理结构

谓词逻辑的归结推理和归结反演


第6周 集合

集合与元素

集合的相等与蕴含

集合的基本运算


第7周 关系的概念

序偶与笛卡尔乘积

关系的定义及性质

等价关系与集合的划分


第8周 关系的运算

关系的一般运算

关系的逆运算、复合运算

关系的闭包


第9周 偏序关系和格

偏序关系和 Hasse 图

格的定义及实例


第10周 函数

函数的概念

集合的基数

有穷布尔代数


第11周 期中假期


第12周 图的基本定义

图论的起源

有向图和无向图

子图

图的度


第13周 道路与回路

道路的概念

Euler 回路和 de Bruijn 序列

Hamilton 回路和 Ore 条件


第14周 图的矩阵和树结构

图的邻接矩阵、道路矩阵和 Warshall 算法

树的基本概念

图的关联矩阵及生成树数目


第15周 二元树

二元树

最优二元树

Huffman 树与 Huffman 编码


第16周 最优路径问题

最短路径与 Dijstra 算法

最短树与 Prim 算法和 Kruskal 算法

作业网络与关键路径问题


第17周 平面图

平面图

极大平面图及性质

图的可平面性及 Kuratowski 定理


第18周 图的染色

图的K-可着色

图的色数

图的色数多项式

图的独立集、支配集与覆盖


第19周 图的匹配

图的匹配理论

Hall 婚姻定理

最大匹配的匈牙利算法


第20周 网络模型

运输网络

割切

最大流最小割定理

求最大流的 Ford-Fulkerson 算法


参考资料

1.Kenneth H. Rosen. Descrete Mathematics and its Applications (Seventh Edition, 影印版). 机械工业出版社,2012.

2.B. Kolman, R. C. Busby, S. C. Ross. Discrete Mathematical Structures (Fifth Edition). Prentice Hall. 罗平译,离散数学结构(第五版),高等教育出版社,2005

3.D. S. Malik, Discrete Mathematical Structures – Theory and Applications, 高等教育出版社, 2005.

4.耿素云、屈婉玲, 《离散数学》(修订版), 高等教育出版社, 2004.

5.左孝凌等,《离散数学》, 上海科技文献出版社, 2002.

6.李盘林等,《离散数学》, 高等教育出版社, 1999.

授课老师
蔡国扬

蔡国扬

所属微专业

所属系列课程

分享