课程名称：离散数学 II （全英）

课程类别：基础必修课

学分：2

考核方式：闭卷

授课老师：黄战

教学目标：

“离散数学”是计算机科学与技术的理论基础，是计算机科学与技术各专业的核心、骨干课程。教学目标着重于两个方面：一方面，它为后续课，如数据结构、编译原理、操作系统、数据库原理和人工智能等，提供必要的数学基础；另一方面，通过学习离散数学，可以培养和提高学生的抽象思维与逻辑推理能力，对提高独立分析问题及解决问题的能力是非常重要的。

教学要求：

通过本课程的学习，学生应达到下列基本要求：

1．熟练掌握离散概率、计数技术、关系、图论、布尔代数和计算建模的基本概念、基本术语、基本定理。

2．培养和提高抽象思维和逻辑推理能力，以及将学到的知识用以分析和解决实际问题的能力。

教学内容：

第8章 高级计数技术

应用的递推关系；求解线性递推关系

分而治之算法和递推关系

生成函数； 容斥原理及应用

第9章 关系

关系及其性质 

n元关系及其应用

关系表示

关系闭包；等价关系；偏序关系

第10章图论

图和图模型

图的术语和特殊类型的图

图表示和图同构；连通性

欧拉和哈密尔顿路径

最短路径问题；平面图；图着色；

第11章树

树及其应用；树的遍历

生成树；最小生成树

第12章布尔代数

布尔函数

代表布尔函数

逻辑门；最小化电路

第13章计算建模         

语言和文法

有输出的有限状态机；无输出的有限状态机

语言识别；图灵机

教材及主要参考书目

离散数学及其应用(英文版第7版)

原书名： Discrete Mathematics and Its Applications Seventh Edition

原出版社： McGraw-Hill Science/Engineering/Math

作者： (美)Kenneth H. Rosen

丛书名： 经典原版书库

出版社：机械工业出版社

ISBN：9787111385509