MIT Discrete Applied Mathematics
LovisMind · 阅读与思考MIT Discrete Applied Mathematics
MIT 18.200 的课程笔记，从鸽巢原理、条件概率与期望、容斥原理这些基础工具出发，逐步进入概率方法与编码理论，每节都保留完整的证明写法与直觉来源。
目录
- 01鸽巢原理：抽屉、碰撞与证明的写法中 / EN从一个袜子问题出发，把鸽巢原理写成可证明的命题，再用它解决聚会中的度数碰撞、20 个四位数的同和子集、Erdős–Szekeres 最长子序列定理与家谱中的近亲问题，最后给出概率论的基本形式化。
- 02条件概率、独立性与期望：从贝叶斯到骰子悖论中 / EN用飞镖盘重新理解条件概率，用掷两次骰子的四个事件区分「看起来独立」与「真的独立」，推出全概率公式与贝叶斯公式，并用真实医学数据与 Mossel 骰子悖论说明直觉为何失效；最后引入随机变量、期望与指示函数。
- 03容斥原理：从错排到 1/e中 / EN用随机发还作业的问题引出容斥原理，在 n=2、n=3 的韦恩图上逐步修正过计与欠计，得到一般公式并归纳证明；代回原问题后得到错排概率趋于 1/e，再用期望线性性一行算出「拿到自己作业的人数期望为 1」，最后用它解决优惠券收集问题并引入随机变量独立性、方差与方差可加性。
- 04计数：二项式系数、双射与卡特兰数中 / EN从「从 n 个里选 k 个」出发，用除以 k! 修正顺序，用双重计数证明帕斯卡恒等式，推广到多项式系数；再用双射与星线法给球染色计数，最后用反射双射导出卡特兰数 c_n=C(2n,n)/(n+1)，并建立它与 Dyck 路径、二叉树之间的对应。
- 05生成函数：从凯莱树定理到求和的机械化中 / EN先用「同一种对象数两次」证明凯莱树定理：n 个顶点的标号树有 n^(n-2) 棵；再把序列打包成幂级数，定义生成函数，说明不交并对应相加、笛卡尔积对应相乘，用骰子与找零两个例子演示，最后用求导技巧算出 Σ k·C(n,k)=n·2^(n-1)。
- 06生成函数、Fibonacci 数与 Pascal 三角形中 / EN用「并、积、序列」三条操作把组合结构翻译成生成函数；从点划电报码推出 Fibonacci 递推，用部分分式求出 Binet 公式与信息率，再沿 Pascal 三角形对角线与组合计数两种方式验证同一个恒等式。
- 07Catalan 数的生成函数中 / EN从满二叉树的递推 C_n=ΣC_jC_{n−j−1} 得到 C(x)=1+xC(x)²，解二次方程并取舍根，再用二项式定理展开出 C_n=(1/(n+1))C(2n,n)；最后用 Dyck 路径的首次回零分解给出同一条方程的第二种来源。
- 08尾界、大数定律与概率方法中 / EN从 Markov 不等式出发，用平方技巧证明 Chebyshev 不等式，再由它推出弱大数定律；随后把尾界用于随机算法的错误率与赌博破产，并用「期望小于 1 就有正概率成功」证明 van der Waerden 数的下界。
- 09Chernoff 界：用指数矩控制偏差中 / EN通过指数变换把「偏离」变成非负随机变量，再用 Markov 与相互独立把矩母函数拆成乘积，逐步推出独立 Bernoulli 和的上尾、下尾与合并界，得到随样本量指数衰减的失败概率。
- 10同余、欧几里得算法与中国剩余定理中 / EN从带余除法建立同余的语言，证明「同余等价于余数相等」；用欧几里得算法快速求最大公因数，再用扩展算法得到 Bézout 等式，从而判定并计算模逆元；最后证明中国剩余定理并给出构造解法。
- 11群、Lagrange 定理与费马小定理中 / EN从模运算中的可逆元素抽象出群，用左陪集把群切成等大的块，证明子群的阶整除群的阶，并用它推出费马小定理与欧拉定理。
- 12线性规划入门：建模、标准形与对偶中 / EN用饮食与烘焙两个问题写出线性规划，说明标准形与规范形之间如何互相转换，再从「把约束加权相加」推出对偶规划，并证明弱对偶。
- 13一般线性规划的对偶与互补松弛中 / EN把对偶从规范形推广到任意线性规划，证明互补松弛定理并用它从原问题最优解反推对偶解，再用力学类比证明强对偶，最后以 König 定理收尾。
- 14零和博弈、混合策略与极小极大定理中 / EN用支付矩阵描述零和博弈，说明纯策略纳什均衡可能不存在，引入混合策略并把「无人愿意偏离」写成线性不等式，再用线性规划对偶证明 von Neumann 极小极大定理。
- 15最大流最小割：对偶与增广路径中 / EN把网络流写成线性规划，取对偶得到一个以顶点标号为变量的程序，说明对偶最优解可以取 0/1 从而对应一个割，于是强对偶给出最大流等于最小割；再用残量网络与增广路径说明整数流的存在性。
- 16数据压缩与 Shannon 无噪声编码定理中 / EN把压缩定义成「把消息映射成二进制串」，用熵衡量理论极限；先证下界（任何编码都不能低于 nH），再用典型序列构造一个达到 nH + o(n) 的编码，从而证明熵就是一阶信源的每符号最优码长。
- 17Huffman 编码：交换论证与最优前缀码中 / EN前缀码让逐符号解码成为可能。用三次交换论证推出最优树的结构（最小与次小概率符号是兄弟），把问题收缩成规模更小的子问题，得到贪心算法；再用 Kraft 不等式证明最优码长夹在熵与熵加一之间。
- 18噪声信道与 Shannon 编码定理中 / EN二元对称信道以概率 p 翻转每一位。重复码能把错误率压到零，但速率趋于零。Shannon 定理说明存在恒定的正速率 1−H(p)：随机码本加「环」解码给出可达性证明，计数与并集界给出逆定理。
- 19线性码与 Hamming 码：从维恩图到综合解码中 / EN随机码本不可实现，需要结构化的码。从 4 位消息加 3 个校验位的维恩图构造出发，抽象出线性码、生成矩阵与校验矩阵；用最小距离刻画纠错能力，最后用综合（syndrome）完成单比特纠错，并说明 Hamming 码为何是完美码。
- 20Reed–Solomon 码：多项式求值与错误定位中 / EN把消息写成次数小于 k 的多项式，在 n 个不同点上求值得到码字。多项式根数界立刻给出最小距离 n−k+1，可纠 (n−k)/2 个错误。解码化为解线性方程组：引入错误定位多项式 f 与 q=pf，解出后相除即可恢复消息。串接内码后，RS 码在 10% 误码率下把失败概率压到 10⁻⁶⁰ 量级。