北京邮电大学博士考试大纲之离散数学

　　一、 考试要求

　　要求考生系统地掌握离散数学的基本概念、基本定理和方法，具有较强的逻辑思维和抽象思维能力，能够灵活运用所学的内容和方法解决计算机科学中的实际问题。

　　二、 考试内容

　　1、 数理逻辑

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

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

　　3) 证明方法

　　4) 数学归纳法

　　2、 集合论

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

　　2) 等价关系，划分

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

　　3、 计数

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

　　2) 离散概率

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

　　4、 图论

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

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

　　3) 最短路经，最大流量

　　5、 形式语言与自动机

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

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

　　6、 代数系统

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

　　2) 群与编码

　　3) 格与布尔代数，环与域

　　三、 试卷结构

　　1、 考试时间为3小时，满分100分。

　　2、 题目类型：计算题、简答题和证明题。