华中科技大学博士研究生入学考试
《计算机数学》（离散数学、形式语言自动机）
第一部分 考试大纲
一、考试性质
计算机数学是计算机科学的重要理论基础。博士研究生《计算机数学》考试是为华中科技大学计算机科学和技术及其相关专业招收博士研究生而设置的。它的评价标准是高等学校计算机及相关学科优秀硕士生能达到的及格或及格以上水平，以保证被录取者具有继续深造的必要的数学基础和素质，并有利于各相关专业在招生工作上的择优选拔。
二、考试范围
集合论，包括集合、关系、函数；代数系统的一般概念、群、格和布尔代数；图论；命题逻辑和谓词逻辑；形式语言与自动机。
三、评价目标
在考查基本概念、基本理论的基础上，注意考查学生运用基本知识分析和解决问题的能力。具体要求：
1． 正确理解各基本概念；
2． 熟练掌握研究对象的基本性质；
3． 深入理解各研究对象之间的内在联系；
4． 熟练掌握计算机数学中的几种典型的论证方法；
5． 能运用所学的知识对未知的问题进行分析、推理而加以解决。
四、考试形式与试卷结构
1．答卷方式：闭卷，笔试
2．答题时间：180分钟
3．考查内容及其考查比例：
①基本概念：30%
②论证推理：70%
第二部分 考查要点
一、集合论
1． 集合，幂集，分划等概念
2． 集合间的各种关系和运算，运算定律
3． 笛卡尔积，关系，复合关系，逆关系等概念
4． 关系的集合表示，矩阵表示和关系图表示
5． 关系的复合运算，闭包运算
6． 关系的性质，等价关系和偏序关系
7． 函数，复合函数，逆函数
8． 内射，满射和双射
二、代数系统
1． 集合A上运算的概念，二元运算的一些特殊元素
2． 运算的封闭性和代数系统的概念
3． 同态，满同态以及同构的概念和性质
4． 群的定义和性质
5． 子群及其判别
6． 陪集和正规子群
7． 格的定义和性质
8． 有补格，分配格和布尔代数的定义及有关性质
三、图论
1． 图的定义及有关的各个概念，完全图、连通图、子图、分图等。欧拉图，哈米尔顿图，图的连通性
2． 树的定义及性质，有向树的定义，二元树及二元树的周游，有向树中的一些数量关系，有向树的应用
3． 二部图的定义及其判别
4． 平面图的定义及其判别
四、数理逻辑
1．命题逻辑
命题，命题联结词，命题变元，命题公式，永真公式，永假公式及可满足公式，命题
公式的等值关系和蕴含关系，命题演算的推理理论
2．谓词逻辑
谓词、个体词和量词，谓词演算公式，谓词演算的永真公式，永假公式和可满足公式，谓词演算公式的等值和蕴含，谓词演算的推理理论
五、形式语言与自动机
1、语言及文法
语言的定义与运算、文法、文法的分类。
2、有限自动机和右线性文法
有限自动机、不确定的有限自动机、DFA与NFA的等效、有ε转换的不确定的有限自动机、正则集与正则式、右线性文法和正则集、右线性语言与有限自动机、右线性语言的性质。
