算法导论

先行条件

6.1200/6.042 计算机数学

课程描述

介绍计算问题的数学模型，常见算法、算法范式，和用来解决这些问题的数据结构
强调算法与编程之间的关系
介绍这些算法问题的基本性能度量和分析技术

参考书

《算法导论》，也称CLRS（可选）

适合人群

初学者（非快餐式进食目的，事实性的知识刻板接受，不在乎底层的设计思想）
想学《算法导论》遇到瓶颈的学习者

主题

模块一： Lec 1~8 数据结构与排序 ----- Q1

模块二： Lec 9-14 最短路径，图算法 --- Q2

模块三：Lec 15-19 动态规划 ---- Q3

搜索问题（数据结构）	排序算法	最短路径算法
静态数组 (L01)	插入排序 (L03)	广度优先搜索 (L09)
链表 (L02)	选择排序 (L03)	有向无环图松弛 (L11)
动态数组 (L02)	归并排序 (L03)	深度优先搜索 (L10)
有序数组 (L03)	计数排序 (L05)	拓扑排序 (L10)
直接访问数组 (L04)	基数排序 (L05)	Bellman-Ford算法 (L12)
哈希表 (L04)	AVL排序 (L07)	Dijkstra算法 (L13)
平衡二叉树 (L06-L07)	堆排序 (L08)	Johnson算法 (L14)
二叉堆 (L08)		Floyd-Warshall算法 (L18)

参考书

CLRS

测试

Lec 1~8 数据结构与排序 ----- Q1

Lec 9-14 最短路径，图算法 --- Q2

Lec 15-19 动态规划 ---- Q3

Quiz Review	Quiz
Quiz 1 Review (PDF)Quiz 1 Review Solutions (PDF)	Quiz 1 (PDF)Quiz 1 Solutions (PDF)
Quiz 2 Review (PDF)Quiz 2 Review Solutions (PDF)	Quiz 2 (PDF)Quiz 2 Solutions (PDF)
Quiz 3 Review (PDF)Quiz 3 Review Solutions (PDF)	Quiz 3 (PDF)Quiz 3 Solutions (PDF)
No reviews	Final Exam (PDF)Final Exam Solutions (PDF)

练习题

Problems	Solutions
Problem Session 1 questions (PDF)	Problem Session 1 solutions (PDF)
Problem Session 2 questions (PDF)	Problem Session 2 solutions (PDF)
Problem Session 3 questions (PDF)	Problem Session 3 solutions (PDF)
Problem Session 4 questions (PDF)	Problem Session 4 solutions (PDF)
Problem Session 5 questions (PDF)	Problem Session 5 solutions (PDF)
Problem Session 6 questions (PDF)	Problem Session 6 solutions (PDF)
Problem Session 7 questions (PDF)	Problem Session 7 solutions (PDF)
Problem Session 8 questions (PDF)	Problem Session 8 solutions (PDF)
Problem Session 9 questions (PDF)	Problem Session 9 solutions (PDF)

Lec 1 介绍

算法定义
渐进表示法
计算模型
数据结构
练习题

lec1.md

Lec 2 数据结构

序列接口
序列接口的实现
集合接口
集合接口的实现

数据结构 是用于存储数据的方式，并提供对数据的操作的算法。

接口（interface），也称ADT（抽象数据类型，API是一组操作的集合。接口定义了哪些操作是支持的（或者说适合什么问题），而数据结构则是如何支持这些操作的表示方式（即解决方案）

这节课主要关注两个接口：序列（Sequence）和集合（Set)

lec2.md

Lec 3 排序

在Lec2 的练习题上，我们提前用序列接口实现了集合接口，发现时间复杂度比较高

排序
递归

lec3.md

Lec 4 哈希

今天的目标是关注静态查找

比较模型
直接访问数组
哈希
通用哈希
练习题

两个目标

证明你不能实现比O(log n) 还快的find(k)
展示如何find(k)比O(log n)还要快

lec4.md

Lec 5 线性排序

比较排序下界
直接访问数组排序
元祖排序
计数排序
基数排序

lec5.md

Lec 6 二叉树

一种几乎优于所有目前我们所了解的数据结构——二叉树

二叉树
应用：集合
应用：序列

lec6.md

Lec 7 AVL树

我们这节课的终极目标是实现树的平衡：n个节点的树如果它的高度是 $O (\log n)$ ，那么它是平衡的。

高度平衡
树的旋转
- 局部重平衡
- 全局重平衡
计算高度
应用：序列
应用：排序
练习题

lec7.md

Lec 8 优先队列 & 二叉堆

介绍另外一种类似树的数据结构称为二叉堆，他给了我们排序的另外一种思路

优先队列接口
优先队列的排序
二叉堆
堆排序

lec8.md

Lec 9 广度优先搜索

图的定义
图的表示
图的路径问题
练习题

lec9.md

Lec 10 深度优先搜索

DFS
全量BFS/DFS
图的连通性
拓扑排序
循环检测

lec10.md

Lec 11 加权最短路径

加权图定义和表示
加权最短路径问题
加权最短路径算法
松弛算法
最短路径树
DAG松弛
练习题

lec11.md

Lec 12 Bellman-Ford

这节课介绍一个基于图复制和DAG松弛Bellman-Ford版本算法，这个算法能够以 $O (| V | | E |)$ 的时间复杂度和空间复杂度下解决SSSP问题的，并且能够返回从 s 到 v 的路径上可达的负权环，对于任何满足 $δ (s, v) = - \infty$ 都适用

简单最短路径
负权重环见证者
Bellman-Ford算法

lec12.md

Lec 13 Dijkstra's 算法

非负权重边
Dijkstra's 算法

lec13.md

Lec 14 Johnson's 算法

全源最短路径
Johnson's 算法

lec14.md

模块复习课：图结构及其算法

主要是针对Lec9~Lec14的复习

Lec 15-18 动态规划专题

lec15.md

Lec 19 复杂度

总览

决策问题
P， NP, EXP, R问题
非确定性多项式时间
规约

lec19.md

Q3: 动态规划复习

Lec 20 课程复习

三大目标

解决计算问题
与人交流，battle正确性问题
- 递归和归纳证明
与人交流，battle 性能效率
- 模型+分析

并不总是能用“Good”的算法解决问题。

大多数问题无法有效解决，但我们想到的许多问题是可以的！
多项式时间指的是相对于输入大小的多项式时间。
伪多项式时间指的是相对于输入大小和输入中数字大小的多项式时间。
但是很多问题都可以在多项式时间内进行检查（NP问题），或者通过暴力方法解决（EXP问题）。（当你沿着这条轨道前进时，可以在后续的进阶课程里面将其解决）
- NP（非确定性多项式时间）：多项式时间内可验证的证书。
- NP-hard（NP困难）：一组可以用来在多项式时间内解决 NP 中任何问题的问题
- NP-complete（NP完全）：NP-hard 和 NP 的交集问题

课程结构

Q1：用于查找的数据结构，以及排序问题
- 序列（外在的顺序）
- 集合（内在的查询顺序）
Q2：图问题
- 通过BFS或者DFS在O(|E|）时间实现可达性验证
- 通过Full-BFS或者Full-DFS实现连通性验证
- 通过DFS实现拓扑排序、循环检测
- 通过Bellman-Ford实现负权重环检测
- SSSP
- ASSP
Q3：动态规划——递归框架（SRTBOT)

6.046

看作是6.006的扩展

数据结构：Union-Find，摊销分析
图：MST，网络流问题
设计范式：分治，动态规划，弹性
复杂性问题：规约

松弛问题（更改正确性和效率的定义）

随机算法
- 6.006 课程中大多使用确定性算法（如哈希）
- 拉斯维加斯算法：总是正确，可能快速（比如哈希）
- 蒙特卡罗算法：总是快速，可能正确
- 通常可以在结构化数据上得到更快的随机算法
数值算法/连续优化
- 6.006 只处理整数
- 近似实数！为精度付出时间代价
近似算法
- 输入一个优化问题（在加权输出中寻找最小/最大值）
- 许多优化问题是 NP 难的
- 我们能在多项式时间内多接近最优解？

改变计算模型

缓存模型（内存层次结构成本模型）
量子计算机（利用量子特性）
并行处理器（使用多个 CPU 而不是只用一个）
- 多核，大共享内存
- 分布式核心，消息传递

未来课程

模型

6.045, 6.840, 6.841 计算/复杂性
6.842 随机过程
6.845 量子
6.852 分布式/消息传递
6.816, 6.846 多核/共享内存
6.890 图和矩阵
6.172 性能工程

应用

6.875 加密
6.853 Game Theory
6.047 生物学
6.850 地理学
6.837 图形学
6.819 视觉
6.849 折纸

6.851 高级数据结构

我们唯一接触的模型是Word RAM，还有其他不同的模型

O(lg n) via AVL
O(lg w) via van Emde Boas
O(lg n / lg w) via fusion tree

算法导论 ​

先行条件 ​

课程描述 ​

参考书 ​

适合人群 ​

主题 ​

参考书 ​

测试 ​

练习题 ​

Lec 1 介绍 ​

Lec 2 数据结构 ​

Lec 3 排序 ​

Lec 4 哈希 ​

Lec 5 线性排序 ​

Lec 6 二叉树 ​

Lec 7 AVL树 ​

Lec 8 优先队列 & 二叉堆 ​

Lec 9 广度优先搜索 ​

Lec 10 深度优先搜索 ​

Lec 11 加权最短路径 ​

Lec 12 Bellman-Ford ​

Lec 13 Dijkstra's 算法 ​

Lec 14 Johnson's 算法 ​

模块复习课： 图结构及其算法 ​

Lec 15-18 动态规划专题 ​

Lec 19 复杂度 ​

Q3: 动态规划复习 ​

Lec 20 课程复习 ​

三大目标 ​

课程结构 ​

6.046 ​

未来课程 ​