离散数学

抱歉,您来晚了,本次开课已结束!
加入课程 54人 收藏
分享到

课程介绍

本课程研究不同背景下离散量的结构、规律及相互关系,在程序设计语言、数据结构、操作系统、数据库原理、计算机网络、人工智能等方面都有着广泛的应用,不仅强调对知识的理解和掌握,还强调方法论的学习。
本课程的目的是使学生接受现代数学关于离散数学的观点,掌握命题逻辑和谓词逻辑、集合、关系和函数、图、树等几类模型的有关概念、基本理论和一定的应用技巧,具备使用离散数学模型分析和解决实际应用问题的能力。
本课程可以培养、训练并提高学生的问题抽象能力、逻辑推理能力以及利用离散数学模型分析和解决问题的能力等。本课程亦可培养学生自主性学习能力,为学生进一步学习后续课程以及进行或参与创新性的研究和开发工作打下坚实基础。

课程大纲

1    基础知识    
        集合、子集、超集与幂集的概念
        有限集合的幂集元素的计数
        集合之间的关系:包含、相等、真包含
        集合包含/相等关系的证明方法
        空集与全集
        集合的运算:交、并、补、差、对称差
        文氏图
        容斥原理
        集合运算的性质
        序列的概念
        特征函数
        使用特征函数表示集合
        布尔矩阵及其运算
2    命题逻辑    
        命题的概念
        原子命题与复合命题
        逻辑连接符
        真值表
        合式公式的定义
        命题公式的分类
        自然语言形式化
        命题公式等值的定义
        命题逻辑的基本等值式
        命题逻辑的等值演算
        文字、互补对、析取式和合取式的概念
        析取范式和合取范式的概念
        析取范式和合取范式的计算方法
        极大项/极小项的概念
        极大项/极小项的性质
        主范式的概念
        求主范式的方法
        主范式与真值表的关系
        命题逻辑中正确推理的概念
        命题逻辑的推理演算
        命题逻辑推理的归结法
3    谓词逻辑    
        谓词
        全称量词/存在量词
        自然语言的形式化
        谓词公式等值的定义
        谓词逻辑的基本等值式
        谓词逻辑的等值演算
        前束范式的概念
        前束范式的转换方法
        谓词逻辑中正确推理的概念
        谓词逻辑的推理方法
        证明与反驳、证明方法
4    二元关系    
        有序对
        笛卡尔积
        二元关系的概念
        多元关系
        划分
        关系图表示
        关系矩阵表示
        关系的像
        关系相等的判断方法
        关系中的道路
        由道路定义的关系
        关系的性质
        关系的计数
        等价关系
        等价关系与划分的一一对应
        商集
        关系的运算
        关系运算对性质的保持
        关系运算满足的定律
        关系性质的判断
        闭包的概念和计算
        Warshall算法
5    函数    
        函数、自变量、像的定义
        处处定义、映上、一对一、双射、一一对应
        函数的复合
        逆函数的定义
        逆函数存在性的判定
        逆函数的性质
        函数的计数
        计算机科学中的常用函数
6    偏序关系    
        偏序关系
        拟序关系
        对偶偏序集
        积偏序、字典序
        哈斯图
        可比性、不可比性
        线性序
        极大元、极小元、最大元、最小元
        上界、下界、上确界、下确界
        拓扑排序
7    树    
        根树的概念
        根树的性质
        根、叶子的概念
        层数、高度的概念
        父亲、子顶点、兄弟顶点的概念
        m叉树、完全m叉树的概念
        子树的概念
        标号树的概念
        有序树的概念
        代数运算表达式的有序标号树表示
        树的遍历
        波兰式、逆波兰式
        使用波兰式计算运算式的结果
        使用逆波兰式计算运算式的结果
        前缀码的概念和判断
        霍夫曼树与霍夫曼编码
        无向树的等价定义
        支撑树的概念
        最小支撑树的概念
        Prim算法
        Kruskal算法
        破圈法
        Borůvka算法
8    图    
        无向图和有向图的定义
        顶点的度的定义
        握手定理
        道路、回路的概念
        孤立顶点、重边的概念
        连通性、连通分支、桥的概念
        特殊的图
        子图
        图的同构的概念
        简单图的概念
        欧拉道路/回路的概念
        欧拉道路/回路存在性判定
        Fleury算法
        有向图中的欧拉道路/回路
        哈密尔顿道路/回路的概念
        哈密尔顿道路/回路存在性判定
        平面图
        欧拉公式
        对偶图
        图的点着色、边着色、面着色
        韦尔奇-鲍威尔方法
        四色定理
        最短路径
        Dijkstra算法

考核标准

综合成绩总分100,各项占比:
[线上成绩]:__20___%
[线下成绩]:__60__%
[其他](翻转、论坛)]:___20__%
线上成绩总分100,各项占比:
[课件浏览]:__40___%
[客观练习]:__30___%
[主观练习]:__10___%
[课内讨论]:__20___%
【暂定,待更新】

教材教参

Bernard Kolman, Robert Busby, Sharon C. Ross. Discrete Mathematical Structures. 第6版(影印版). 北京. 高等教育出版社. 2010.