计算机科学中的数学
这门课学什么
这是给计算机学生的离散数学课。内容包括证明与归纳、数论与 RSA、图论、计数、生成函数、概率和随机变量。课程配套同名免费教材（Lehman、Leighton、Meyer 著）。
内容摘要
这门课讲计算机科学最常用的离散数学，主讲人是莱顿（Tom Leighton）。课程主线是严格证明：先学会写证明，再把证明技巧用在数论、图论、计数和概率上。
课程分 4 个单元。第 1 单元（第 1–5 讲）讲命题、证明方法、归纳法和数论，最后推导 RSA 加密。第 2 单元（第 6–11 讲）讲图论：着色、匹配、最小生成树、通信网络、有向图和偏序。第 3 单元（第 12–17 讲）讲求和、渐近记号、递归式和计数规则。第 4 单元（第 18–25 讲）讲概率：条件概率、独立性、随机变量、期望、大偏差和随机游走。
作业是 12 份习题集，一般一周一份。课程还有 1 次 2 小时的期中考试和 1 次 3 小时的期末考试。教材是免费的 Mathematics for Computer Science，作者是 Lehman、莱顿和 Meyer。
学完以后，你能写清楚归纳证明，能分析递归算法的运行时间，能解计数问题，能用期望和概率不等式估计随机算法的表现。这些是算法课和机器学习课的数学基础。
莱顿讲课用大量实例和小游戏，比如稳定婚姻问题和赌徒破产问题。他常先让学生猜答案，再给出反直觉的结果，让人记住结论背后的道理。
为什么值得学
Leighton 是 Akamai 联合创始人。课程把严谨证明和计算机实际应用结合，配套教材在 MIT 以外也用得很广。
课程信息
- 学校
- 麻省理工（MIT）
- 课程号
- 6.042J
- 讲师
- 汤姆·莱顿（Tom Leighton）、Marten van Dijk
- 学期
- Fall 2010
- 平台
- MIT OpenCourseWare
- 费用
- 免费
- 难度
- 入门
- 学时
- 25 讲
- 先修
- 学过微积分。
- 材料
- 视频、作业、考试、教材
- 许可证
- CC BY-NC-SA 4.0
课程大纲 · 共 25 节
大纲依据：Fall 2010 OCW 讲座视频列表（25 讲）（查看原始页面 ↗）
- 1导论与证明Introduction and Proofs
介绍命题和谓词，讲直接证明和反证法，说明“看起来成立”不等于证明。
- 2归纳法Induction
讲普通归纳法和良序原理，并分析错误的归纳证明错在哪里。
- 3强归纳法Strong Induction
用强归纳法和不变量证明游戏和谜题中的结论。
- 4数论（上）Number Theory I
讲整除、最大公因数和欧几里得算法。
- 5数论（下）Number Theory II
讲模运算、费马小定理和欧拉定理，并推导 RSA 加密。
- 6图论与着色Graph Theory and Coloring
介绍图的基本概念，用图着色解决排期这类冲突问题。
- 7匹配问题Matching Problems
讲二分匹配和稳定婚姻问题，证明配对算法的正确性。
- 8图论（2）：最小生成树Graph Theory II: Minimum Spanning Trees
讲树的性质，证明贪心算法能求出最小生成树。
- 9通信网络Communication Networks
比较几种互连网络结构的直径、拥塞和交换机数量。
- 10图论（3）Graph Theory III
讲有向图中的路径和环路，以及欧拉回路。
- 11关系、偏序与调度Relations, Partial Orders, and Scheduling
用偏序描述任务之间的先后约束，分析并行调度需要的时间和处理器数。
- 12求和Sums
讲求和的闭式解法，用几何级数和年金问题做例子。
- 13求和与渐近Sums and Asymptotics
用积分估计求和，介绍调和数、Stirling 公式和大 O 记号。
- 14分治递归式Divide and Conquer Recurrences
求解汉诺塔和归并排序的递归式，介绍求解分治递归式的通用方法。
- 15线性递归式Linear Recurrences
用特征方程求解线性递归式，比如斐波那契数列。
- 16计数规则（上）Counting Rules I
讲乘法规则、加法规则、双射规则和除法规则。
- 17计数规则（下）Counting Rules II
讲二项式定理、鸽巢原理和容斥原理。
- 18概率导论Probability Introduction
用树图和四步法分析概率问题，例如 Monty Hall 问题。
- 19条件概率Conditional Probability
讲条件概率和全概率公式，分析医学检测中的反直觉结果。
- 20独立性Independence
区分两两独立和相互独立，并用生日问题估计碰撞概率。
- 21随机变量Random Variables
定义随机变量和概率分布，介绍二项分布这类常见分布。
- 22期望（上）Expectation I
讲期望的定义和期望的线性性，用它简化复杂的计算。
- 23期望（下）Expectation II
讲乘积的期望和条件期望，并计算“平均要等多久”这类问题。
- 24大偏差Large Deviations
讲 Markov 不等式、Chebyshev 不等式和 Chernoff 界，估计随机变量偏离期望的概率。
- 25随机游走Random Walks
用赌徒破产问题分析随机游走，并介绍图上的随机游走。