一、  考试要求

通过本科目考试，检验学生对离散数学的基本概念、基本定理和方法的掌握程度，考察学生逻辑思维、抽象思维以及灵活运用所学的内容和方法解决计算机科学中的实际问题的能力。

二、  考试内容

 

1、  数理逻辑

 

1)  命题和联结词，谓词与量词，合式公式，赋值，解释与指派，范式

 

2)  命题形式化，等价式与对偶式，蕴含式，推理与证明

 

3)  证明方法

 

4)  数学归纳法

 

2、  集合论

 

1)  集合代数，笛卡尔乘积，关系与函数，关系的性质与运算

 

2)  等价关系，划分

 

3)  偏序关系与偏序集，格

 

3、  计数

 

1)  排列与组合，容斥原理，鸽巢原理

 

2)  离散概率

 

3)  函数的增长与递推关系

 

4、  图论

 

1)  欧拉图与哈密顿图，平面图与对偶图，二部图与匹配，图的着色

 

2)  树，树的遍历，最小生成树

 

3)  最短路径，最大流量

 

5、  代数系统

 

1)  二元运算，群与半群，积群与商群，同态与同构

 

2)  群与编码

 

3)  格与布尔代数

 

6、 形式语言与自动机

 

1) 语言与文法，正则表达式与正则集

 

2）有限状态自动机，有限状态自动机与正则语言