离散数学(Discrete Mathematics)
教材与参考书:
教材:讲义。
参考书:
课外阅读(与作业和考试无关,仅供兴趣拓展和娱乐):
课程内容:
- 第1、2课: 课程介绍 ,二项式系数,子集个数,可重复子集个数,星号竖杠方法.
lec1&2
- 第3、4课: 证明方法:直接证明,分类讨论,反证法,归纳法,Ramsey(拉姆齐数),涌现现象。
lec3&4
- 第5、6课: 计数方法:函数、等价关系、偏序关系,容斥原理,双计数,映射方法,无穷集的计数,对角线方法。
lec5&6
- 第7课: 鸽笼原理,扩展鸽笼原理,概率鸽笼原理(生日悖论)。
lec7
- 第8课: 整数与矩阵的快速乘法,递归式求解,主定理,生成函数方法,组合方法,Catalan数(明安图)。
lec8
- 第9、10、12课: 离散几何:凸多边形的对角线交点数,区域数,组合方法,Caratheodory定理,线性代数方法,Happy Ending定理,几何数据中的涌现现象,Fano平面等有限几何及其应用,纠错码。
lec9&12