考研复习专业课#2021年山东大学<<离散数学>>考研大纲

考研复习>>专业课>>正文2021年山东大学<<离散数学>>考研大纲

更新时间：2020/11/1010:43:20

2021年山东大学考研大纲

826-离散数学

考试要求

要求考生系统地理解与掌握离散数学的基本概念
、计算和证明方法
，以及应用概念和方法进行应用问题离散建模、计算求解和逻辑推理的能力
。要求考生具有抽象思维能力，逻辑推理能力 ，和综合运用所学的知识分析问题和解决问题的能力。

考试内容

1.逻辑和证明基础：命题逻辑及其应用 、命题等价式
、命题逻辑等价演算、谓词 、量词
、嵌套量词、推理规则 、证明方法和策略

2.基本结构：集合基本概念及其运算
、函数、序列及求和 、集合的基数

3.算法：算法的基本概念
、搜索算法、排序问题 、贪婪算法、函数的增长
、算法的复杂度

4.初等数论：整除性和模算术、整数进制表示和运算算法 、素数
、最大公约数、最小公倍数 、欧几里得算法
、最大公约数的线性组合表示、线性同余方程 、中国剩余定理
、费马小定理、原根 、离散对数问题

5.归纳与递归：数学归纳法原理及其运用
、强归纳法及其运用、良序性质 、递归定义与结构归纳法、递归算法
、程序正确性

6.计数：计数基础、鸽巢原理 、排列与组合及其推广
、二项式系数与恒等式、生成排列和组合

7.关系：二元关系基本概念及其性质 、n元关系及其应用
、关系的表示（关系矩阵、关系图） 、关系的闭包
、等价关系、偏序

8.图：图的基本概念 、图模型
、图的基本术语、几种特殊类型图 、二部图和匹配、图的表示与图的同构
、图的连通性、欧拉通路 、哈密顿通路
、最短通路算法、平面图及其应用 、图的着色问题 。

9.树：树的基本概念
、树的基本性质及其应用、树的遍历算法 、树的编码
、生成树、最小生成树
。

10.布尔代数：布尔函数及其表示 、逻辑门电路
、电路极小化。

考试形式

考试形式为闭卷、笔试
，考试时间为180分钟，满分为150分 。

参考教材

离散数学及其应用（原书第7版） ，KennethH.Rosen
，机械工业出版社

原作名:DiscreteMathematicsandItsApplications，译者:徐六通 、杨娟、吴斌