courses.csail.mit.edu/6.042/spring18/mcs.pdf

MIT: Mathematics for Computer Science 包含:
1. 证明的概念
• 介绍数学证明的基本概念与形式，包括命题、谓词、证明方法（如反证法、情况证明）等。
2. 良序原理
• 讨论良序原理（Well Ordering Principle），其应用与证明模板，以及良序集与素数分解。
3. 逻辑公式
• 涉及命题逻辑与谓词逻辑的运算、等价性、有效性等，介绍如何在计算机程序中应用逻辑。
4. 数学数据类型
• 介绍集合、序列、函数、二元关系及其在计算机科学中的应用，特别是有限集的基数问题。
5. 归纳法
• 详细讲解普通归纳法与强归纳法，比较它们与良序原理的联系及应用。
6. 状态机
• 解释状态机的基本概念、状态转移以及不变性原则，应用于算法的部分正确性与终止性分析。
7. 递归数据类型
• 介绍递归定义、结构归纳法、递归函数及其在计算机科学中的应用，如搜索树与游戏建模。
8. 无限集合
• 探讨无限集的基数、停机问题及集合逻辑等问题，讨论集合论的工作原理。
9. 数论
• 介绍数论的基本概念，包括可整除性、最大公因数、素数、模运算与RSA加密等应用。
10. 有向图与偏序
• 讨论有向图的性质、顶点度、路径、偏序及其在调度问题中的应用。
11. 通信网络
• 介绍路由问题、网络设计与相关度量的理论基础。
12. 简单图论
• 探讨简单图的性质，包括图的同构、二部图、着色问题、连通性等。
13. 平面图
• 研究平面图的定义、欧拉公式、边界问题以及多面体的分类。
14. 求和与渐近分析
• 涉及求和、渐近符号及其在计算复杂度中的应用，包含近似方法和乘积的分析。
15. 基数法则
• 介绍计数规则，如乘法规则、除法规则、鸽巢原理及包含-排除原理，应用于组合数学问题。
16. 生成函数
• 探讨生成函数的应用，包括线性递推方程、形式幂级数和部分分式展开。
17. 事件与概率空间
• 涉及概率论的基础，包括事件、条件概率、独立性与蒙提霍尔问题等。
18. 随机变量
• 介绍随机变量及其分布、期望值、方差等统计性质，讨论随机抽样和随机变量的和。
19. 随机游走
• 探讨随机游走的理论及其在图论中的应用，讨论如赌徒破产问题等经典例子。
20. 递推关系
• 研究递推关系的解法，包括经典的汉诺塔问题、归并排序以及分治法的递推公式。