离散数学

计算机科学系本科生必修课, 厦门大学, 2022

该课程为厦门大学计算机科学系大二上学期必修课,是计算机和相关专业的专业基础课,为数据结构、算法设计与分析、操作系统、编译原理等后续课程的先修课。主要讲授数理逻辑、集合论、代数结构和图论的基本理论和方法,注重常用离散结构背景、算法和应用的讲述,引导学生应用离散数学的理论和方法解决实际问题。

教材

耿素云、屈婉玲编:《离散数学(第2版)》,北京大学出版社,2019年9月。

课程大纲

章节主要内容
第一章 命题逻辑命题,联结,命题符号化,等值演算,主析取/合取范式,命题逻辑推理理论
第二章 一阶逻辑量词,命题符号化,等值演算,前束范式,谓词逻辑推理理论
第三章 集合集合恒等式,有穷集合的计数
第四章 二元关系和函数二元关系的定义、表示、运算和性质,等价关系,偏序关系,函数
第五章 代数系统的一般概念运算,代数系统,运算律和特异元素,子代数和积代数,代数系统的同态
第六章 几个典型的代数系统半群与独异点,群,子群与子群判定定理,循环群,置换群,群的直积与同态,环与域,格与布尔代数
第七章 图的基本概念图的定义,(导出)子图,图的连通性,图的矩阵表示
第八章 树树的定义和性质,最小生成树,根树
第九章 二部图、欧拉图、哈密顿图二部图,匹配,欧拉图,哈密尔顿图
第十章 平面图及图的着色平面图,极大/极小平面图,平面图判定定理,图的点、边、面着色
第十一章 组合计数加法法则,乘法法则,计数公式,多重集的计数公式,二项式定理,多项式定理
第十二章 递推方程与生成函数递推方程,特征方程,生成函数,用生成函数求解组合计数

往年资料

2021 2020