离散数学课程旨在引导学生掌握如何运用数学模型和方法去分析计算机科学中的问题。重点培养学生用严格的逻辑分析去建模和解决计算类问题。本课程将覆盖现代计算机科学中的若干重要且非常实用的知识点，包括序理论，组合，图论，网络算法等。每一章中都包含了若干有趣的定理、性质、它们的详细证明及一些相对更有挑战性的问题。本课程主要为计算机科学专业学生开设，也可为理工类其它专业学生提供参考。目的是通过本课程的学习给学生未来的学习和工作奠定必要的数学素质。

Mathematical foundations of computer science introduces to the students how to use mathematical models and methods to analyze problems that arise in computer science. It aims to enhance the logic and analytic abilities of the students to model and solve computational problems in a rigorous manner. The course is going to cover several important and useful topics in modern computer science, including ordering theory, combinatorics, graph theory, probabilistic methods, network etc.. At the end of each semester, some cutting-edge topics will be introduced to make the course more adaptable. This is one of the core courses for computer science major, offering them the mathematical sophistications necessary for further study.

课程大纲

01离散数学基础

基本准备知识，序理论入门。

课时

1.1 导引

1.2 基本关系

1.3 Mirsky定理及其应用

02组合计数

组合计数的基本问题、方法、技术。

课时

2.1 基本计数

2.2 计数的简单应用

2.3 二项式定理及推广

2.4 容斥原理

03函数估计

函数的渐进比较，较复杂函数的估计。

课时

3.1 函数的渐进比较

3.2 估值初步

04图论导引

图论入门，定义与简单性质。

课时

4.1 基本概念

4.2 基本性质

05特殊图

几类具有特殊性质的图，图相关性质的应用。

课时

5.1 欧拉图及其应用

5.2 哈密顿图

5.3 握手定理的应用

06树及算法

树同构的定义，树相关计数问题和算法。

课时

6.1 导引

6.2 树同构

6.3 生成树的计数

6.4 最小生成树

07网络流

网络流的定义及基本性质。

课时

7.1 导引

7.2 最大流最小割定理