算法设计与分析
这门课学什么
这是 6.006 的后续课。内容包括分治、均摊分析、随机算法、网络流、线性规划、NP 完全、近似算法、分布式算法和密码学算法。课程有讲座和习题课视频、讲义、作业和考试。
内容摘要
这门课是 6.006 的后续课，2015 年春季由德迈纳（Erik Demaine）、德瓦达斯（Srini Devadas）和林奇（Nancy Lynch）讲授。重点从“会用算法”转到“会设计和证明算法”。课程按设计范式组织：分治、均摊、随机化、动态规划、贪心、增量改进和线性规划。
课程分 3 段。第 1 段（第 1–9 讲）讲分治（凸包、中位数、FFT、van Emde Boas 树）、均摊分析、随机化算法（快速排序、跳表、全域哈希和完美哈希）和范围树。第 2 段（第 10–18 讲）讲高级动态规划、全源最短路径、最小生成树、最大流最小割、匹配和线性规划，再讲 NP 完全、近似算法和固定参数算法。第 3 段（第 19–24 讲）讲分布式算法、密码学中的哈希和加密，以及缓存无关算法。
课程有 10 份习题集，题目要求写出算法、证明正确性并分析运行时间。另有 2 次测验和 1 次期末考试。播放列表还收录了 10 段习题课录像，补充 B 树、主定理、网络流应用和旅行商近似这些例题。
学完以后，你能针对新问题选择设计范式，写出严格的正确性证明，并判断问题是否 NP 难。遇到 NP 难问题时，你知道近似算法和固定参数算法这两条退路。
三位老师各有侧重。德迈纳讲数据结构和复杂度，德瓦达斯讲随机化和密码学，林奇讲分布式算法。课程难度明显高于 6.006，适合打算深入算法理论的人。
为什么值得学
它讲进阶程序员必须掌握的算法思想。三位讲师都是一线研究者，Nancy Lynch 是分布式计算理论的奠基人之一。
课程信息
- 学校
- 麻省理工（MIT）
- 课程号
- 6.046J
- 讲师
- 埃里克·德迈纳（Erik Demaine）、斯里尼·德瓦达斯（Srini Devadas）、南希·林奇（Nancy Lynch）
- 学期
- Spring 2015
- 平台
- MIT OpenCourseWare
- 费用
- 免费
- 难度
- 中级
- 学时
- 34 段视频（讲座 + 习题课）
- 先修
- 学过 6.006 和 6.042J 或同等课程。
- 材料
- 视频、讲义、作业、考试
- 许可证
- CC BY-NC-SA 4.0
课程大纲 · 共 24 节
大纲依据：Spring 2015 OCW 课程日历（24 讲）（查看原始页面 ↗）
- 1课程概述与区间调度Course Overview, Interval Scheduling
介绍课程的设计范式，用区间调度问题对比贪心解法和带权版本的动态规划解法。
- 2分治：凸包与中位数查找Divide & Conquer: Convex Hull, Median Finding
用分治求平面点集的凸包，并讲线性时间的选择算法。
- 3分治：快速 Fourier 变换Divide & Conquer: FFT
用 FFT 在 O(n log n) 时间内完成多项式乘法。
- 4分治：van Emde Boas 树Divide & Conquer: van Emde Boas Trees
用递归分块的结构在 O(log log u) 时间内支持前驱和后继查询。
- 5均摊：均摊分析Amortization: Amortized Analysis
讲聚合法、记账法和势能法 3 种均摊分析方法。
- 6随机化：矩阵乘积验证与快速排序Randomization: Matrix Multiply, Quicksort
区分 Monte Carlo 算法和 Las Vegas 算法，用矩阵乘积验证和随机快速排序做例子。
- 7随机化：跳表Randomization: Skip Lists
用随机分层的链表实现期望 O(log n) 的搜索，并给出高概率界。
- 8随机化：全域哈希与完美哈希Randomization: Universal & Perfect Hashing
用全域哈希族保证期望性能，用两级结构实现静态完美哈希。
- 9增强：范围树Augmentation: Range Trees
增强平衡搜索树，回答一维和多维的范围查询。
- 10动态规划：高级动态规划Dynamic Programming: Advanced DP
用多个例题练习子问题的设计和状态转移的推导。
- 11动态规划：全源最短路径Dynamic Programming: All-Pairs Shortest Paths
用动态规划和 Floyd-Warshall 算法求全源最短路径，并讲 Johnson 算法。
- 12贪心算法：最小生成树Greedy Algorithms: Minimum Spanning Tree
证明最小生成树的贪心选择性质，讲 Prim 算法和 Kruskal 算法。
- 13增量改进：最大流与最小割Incremental Improvement: Max Flow, Min Cut
定义流网络，用增广路径求最大流，并证明最大流最小割定理。
- 14增量改进：匹配Incremental Improvement: Matching
把二分匹配和棒球淘汰问题归约成最大流问题。
- 15线性规划：建模、归约与单纯形法Linear Programming: LP, Reductions, Simplex
把优化问题写成线性规划，介绍对偶和单纯形法。
- 16复杂度：P、NP、NP 完全与归约Complexity: P, NP, NP-completeness, Reductions
用多项式时间归约证明问题是 NP 完全的。
- 17复杂度：近似算法Complexity: Approximation Algorithms
为 NP 难问题设计多项式时间的近似算法，并证明近似比。
- 18复杂度：固定参数算法Complexity: Fixed-Parameter Algorithms
让运行时间的指数部分只依赖一个小参数，以顶点覆盖为例演示这类算法。
- 19同步分布式算法：对称破缺与最短路径生成树Synchronous Distributed Algorithms: Symmetry-Breaking. Shortest-Paths Spanning Trees
在同步网络模型中讲怎样打破节点之间的对称，并构造最短路径生成树。
- 20异步分布式算法：最短路径生成树Asynchronous Distributed Algorithms: Shortest-Paths Spanning Trees
在消息延迟不确定的异步模型中构造最短路径生成树，并分析消息复杂度。
- 21密码学：哈希函数Cryptography: Hash Functions
介绍随机预言模型和密码学哈希函数应满足的性质，以及哈希函数的应用。
- 22密码学：加密Cryptography: Encryption
讲对称加密、Diffie-Hellman 密钥交换和 RSA 公钥加密。
- 23缓存无关算法：中位数与矩阵Cache-Oblivious Algorithms: Medians & Matrices
介绍外存模型和缓存无关模型，分析中位数查找和矩阵乘法的缓存效率。
- 24缓存无关算法：搜索与排序Cache-Oblivious Algorithms: Searching & Sorting
用 van Emde Boas 布局做搜索，并讲缓存无关的排序思路。