1. Algorithms with numbers

设计 Hash 函数一般要考虑两个因素，一是它的随机性，即保证数据分布均匀；二是它的一致性，即对于同一份数据每次都要获得相同的结果。

2. Divide-and-conquer algorithms

多项式乘法

最普通的多项式乘法需要将两个多项式的不同系数一一相乘，算法复杂度是 \(O(n^2)\)。而如果采用点值表示法，即用多项式在 n + 1 个不同的点上的取值来唯一的表示这个多项式的话，计算它们的乘积只需要两个多项式在 2n + 1 个点的值就可以了（乘积的最高项次数为 2n），需要的时间是线性的。所以接下来的问题是如何在点值表示法和系数形式之间高效的转换。

首先是求值，即给出 n 个系数和 n + 1 组不同的取值，求出这些取值下的多项式的值。将奇数次幂的项的偶数次幂的项分开，则有 \(A(x) = A_e(x^2) + xA_o(x^2)\)，这里 \(A_e\) 代表偶数次幂的项，\(A_o\) 代表奇数次幂的项。同时，考虑到 \(A(x_i)\) 和 \(A(-x_i)\) 的计算： \[ \begin{align*} A(x_i) = A_e(x_{i}^{2}) + x_iA_o(x_{i}^{2}) \\ A(-x_i) = A_e(x_{i}^{2}) - x_iA_o(x_{i}^{2}) \end{align*} \]

把计算任务减少到了项数低一半的 \(A_e\) 和 \(A_o\)，计算量减少了一半。接着通过引入复数，可以进一步二分计算 \(A_e\) 和 \(A_o\)，从而在 \(O(log n)\) 的时间内得出结果。

3. Decompositions of graphs

强连通分量

DFS 其实并不需要从根节点开始搜素，因为当子节点先被遍历后，接下来自然会遍历它的父节点。

关于用 DFS 检测有向图中的强连通分量，关键的理论依据在于书上的性质 3：对于两个强连通分量 C 和 C’，如果有一条边从 C 上的点通向 C’ 上的点，则 C 中点的 post 值的最大值肯定比 C’ 中的最大值更大。证明：如果 DFS 先访问了 C，然后再访问 C’，那么在离开 C 中最后一个顶点前，C’ 的所有顶点都肯定已经被访问过了；如果 C’ 被先访问，那么在 C’ 中所有顶点访问完成之前，C 中的任一结点都不会被访问到，DFS 在遍历完 C 中结点后就会寻找下一个没有被访问过的连通分量，这里面包括 C。

性质 3 换句话说，就是可以根据顶点 post 值的最大值，将不同强连通分量由高到低排序后，得到的就是这些连通分量的拓扑序列，排在最前的强连通分量也就是源（source）所在的强连通分量。但是我们需要的是汇（sink）所在的强连通分量，为了得到这个结果，可以先在图 G 的逆向图上跑一遍 DFS，从而获得逆向图中源所在的强连通分量，亦即原图中汇所在的强连通分量。遍历汇所在的强连通分量后（遍历时不会访问到其他强连通分量），删除这一强连通分量，继续遍历下一个汇所在的分量，多次遍历后就能找出所有的强连通分量了。

4. Paths in graphs

单源最短路径

Dijkstra 算法其实是 BFS 针对这一类问题的一种改良，它没法检测图中是否存在负环。Bellman-Ford 算法把所有的边都更新（算法导论上这个过程被称为 relax） |V| - 1 次，如果要检测负环只要再多 relax 一次，看看最短路径的数据有没有变就知道了。

5. Greedy algorithms

最小生成树

Kruskal 算法和 Prim 算法都依赖于最小生成树的 cut property：假设边集 X 是图 G = (V, E) 的最小生成树的一部分，选取任意一组点集 S，使得 X 中不包含横跨 S 和 V-S 两个点集的边，另 e 为所有横跨 S 和 V-S 的边中最短的那条，则 \(X \cup \left \{ e \right \}\) 一定是某一棵最小生成树的一部分。

Kruskal 和 Prim 都利用了这个 cut property 扩大结果集，它们的区别在于 Kruskal 每次都把不会形成环的权值最小的边放到生成树 T 中，构建过程中的部分生成图是零散的，需要一个并查集高效的维护不同连通块之间的合并关系；而 Prim 则每次选择一条和当前的部分生成树相连、不会形成环、且权值最小的边，构建过程中始终形成一棵树的结构。换句话说，它们的区别在于切分 S 和 V-S 两个子集的策略不同。

哈夫曼编码

衡量一个系统的熵的方法之一是对取样后的数据进行哈夫曼编码，编码的总长度越短，系统的熵就越小，其随机程度也越低。对于一个长度为 m 的序列，每个取值的可能性分别为 \(p_1, p_2, ..., p_n\)，则由数学归纳法可证编码这一序列需要的位数为 \(\sum_{i=1}^{n}m p_i log(1/p_i)\)，平均每个字符需要的位数为 \[\sum_{i=1}^{n}m p_i log(1/p_i)\] 这就是这个分布的熵。

6. Dynamic programming

讲了几个经典的动态规划问题

  • 单源最短路径
  • 最短编辑距离（书上的例子应该是 Hamming distance）
  • 01 背包问题
  • 矩阵乘法链的优化
  • 全源最短路径

7. Linear programming and reductions

单纯形法（Simplex method）

单纯形法就是从任一一个顶点开始，寻找邻近的收益更高的顶点，直到找不到更高的顶点为止。由于图形是一个简单几何体，因此找到的局部最优解也必然是全局最优解。

网络流

网络流其实可以规约到线性规划问题，从而使用单纯形法解决。而使用单纯形法解决网络流问题的方法正是不断在当前图的 residual network 中找连通 source 和 sink 的流，直到找不到这样的流为止。在 residual network 中查找满足要求的流可以使用 BFS，使得找到的流的边数最少，从而保证在 \(O(|V| * |E^2|)\) 的时间内解决问题。

关于单纯形法解决网络流问题的正确性也很容易证明。在最终的 residual netwoking 中，必然不存在从 source 到 sink 的流。另 L 为 source 能够到达的顶点的集合，而 R 为图中除了 L 外的顶点的集合，则 (L, R) 是原图的一个最小割（可以用反证法证明），且它的容量等于当前流的流量。结合最大流最小割定理，就能证明单纯形法的正确性。

线性规划的对偶性

网络流中，流往往比割小，而最大流和最小割的相等性则证明了它们的最优性。回到线性规划的问题上，每一个线性最大化的问题也有一个对偶的最小化的问题，它们之前的关系和最大流最小割很像。转化的方法很简单，通过给线性最大化问题的不等式加上不同的系数，可以获得不同的解的限制。这些限制大多很宽松，比实际解的值大。因此问题可以转换为找到合理的系数，使得限制的值最小，从而转化为了一个线性最小化的问题。

如果一个线性规划的问题存在一个有限的最优解，那么它的对偶问题也存在最优解，且这两个最优值相同。

最短路径问题中的对偶性

这个举例也很有意思。我们把最短路径假象成一个现实中的物理模型：用绳子代表图中的边，绳子的长度即边的长度，绳子之间的关系和图中边的关系一样。找从 s 点到 t 点的最短路径的方法之一，便是手握 s 点和 t 点，并将这一模型拉紧，拉紧后它们的距离就是 s 点到 t 点的最短路径的距离。

这个例子中，「拉紧」这一过程不断的增加 s 和 t 之间的距离，是一个最大化的过程；而最短路径本身，则是一个求最小值的问题。于是这又是一对对偶的问题。

多维空间中的顶点

在多维空间里，顶点的定义是对于全部不等式的任意子集，如果存在一个唯一的点使它们的等号成立，且这个点在可行区间里，改点即为一个顶点。

对于有 n 个变量的线性规划问题，至少要 n 个方程才能确定一个顶点。而如果定义两个顶点的方程里有 n - 1 个是相同的，那么这两个顶点相邻。

多维空间中的单纯形法

大致过程主要是两步：

  1. 查看当前顶点是否已经最优；
  2. 如果不是，则往下一个顶点移动。

如果当前顶点就是原点，在判断如何往下一个顶点移动时会很方便，只要放开其中一个约束方程，让某个变量不断增加即可。而为了保证当前顶点是原点，需要在每次移动后使用平移、旋转等方法，使新的顶点成为当前坐标系的原点。

电路求值

电路求值的问题是指，给定一个由与、或、非构成的电路和它的输入，问最终的输出结果是真还是假。

这个问题可以规约到线性规划，每一个门都可以被若干个不等式表达，例如 c = OR(a, b) 就等价于 \(x_c \geq x_a, x_c \geq x_b, x_c \leq x_a = x_b\)。同时，任何一个 P 问题都可以规约到电路求值（计算机本身就是由电路实现的），因此所有的 P 问题都可以规约到线性规划问题。此外，如果给线性规划问题加一个限制，要求所有的变量都是整数，就成了整数规划问题，它是一个 NPC 问题。

8. NP-complete problems

证明一个问题是 NPC 问题通常分两个步骤，一是证明它是 NP 问题，这一点可以通过证明它是多项式时间内可证的就行；二是证明某一个 NPC 问题可以规约到它。这里有一个问题，第一个 NPC 问题是怎么来的呢？Cook’s theorem 证明了 SAT 是一个 NPC 问题，因为任何一个非确定性图灵机都能被编码成一个二进制的式子，而这个图灵机接收某一串输入当且仅当这个式子是可满足的。

NP 问题除了 NPC 和 P 问题之外，剩下的问题既不能被证明可以在多项式内解决，也无法从其他 NPC 问题规约而来。经典的例子就是图的同构判断和质因数分解问题。

这一章内容和之前看过的《Introduction to the Theory of Computation》的后半部分很像，主要介绍了几个 NPC 问题和它们之间相互规约的方法。

9. Coping with NP-completeness

这一章内容和 Stanford 公开课 Artificial Intelligence 的前面一半课程内容很接近，包括：

  • 搜索中的回溯
  • 分枝定界法
  • 近似算法
  • k-Cluster
  • 局部最优近似（restart、randomization、退火）

10. Quantum algorithms

量子

经典比特是由高电压和低电压表示的。而在量子世界中，一个量子除了基态(ground state) \(|0 \rangle\) 和激发态(excited state) \(|1 \rangle\) 外，还可以在这两种状态的组合，即叠加态(superposition) \(a_0 |0\rangle + a_1|1\rangle\)，这里 \(a_0\) 和 \(a_1\) 可以是任意复数，只要它们满足 \(a_0^2 + a_1^2 = 1\)。而 \(a_0 |0\rangle + a_1|1\rangle\) 便是量子计算机中描述信息的基本单元，被称为「量子比特」(qubit)。

对量子的测量会引起波函数坍塌，测量结果有 \(|a_0|^2\) 的概率成为 0，有 \(|a_1|^2\) 的概率成为 1，且测量后系统状态就会变成基态活激发态。注意这里的 \(a_0\) 和 \(a_1\) 可以是虚数，因此概率未必是非负实数。