Ex nihilo: algorithmica logos

前言

第一篇  算法基础篇

第1章  从无有到无穷

1.1  意念与现实

1.2  什么是算法

1.3  算法的表示

1.4  算法之魂

1.5  如何比较速度

1.6  算法与计算机的关系

1.7  算法的范畴

1.8  为什么学习算法

思考题

第2章  计数与渐近

2.1  算法的分析

2.1.1  正确性分析

2.1.2  时空效率分析

2.1.3  时空特性分析

2.2  计数：算法分析的核心

2.3  算法设计

2.4  算法效率表示

2.5  渐近分析

2.6  表示

2.7  最好、最坏、平均

2.8  另一类定义

2.9  性质

2.10  要更快的计算机还是要更快的算法

思考题

第3章  分治与递归

3.1  分而治之为上策

3.2  分治策略

3.3  递归表达式求解

3.3.1  递归树法

3.3.2  替换解法

3.3.3  大师解法

3.4  分治策略举例1：乘方运算

3.5  生命中不能承受之重：矩阵乘法

3.6  魔鬼序列：斐波那契序列

3.6.1  由底至上

3.6.2  使用通式

3.6.3  使用矩阵乘方

3.7  VLSI 布线

3.8  多项式乘法

3.9  分治就在潜意识

思考题

第二篇  算法设计篇

第4章  动态规划思想

4.1  什么是动态规划

4.2  流水线问题

4.3  最长公共子序列

4.3.1  第一种解法：蛮力策略

4.3.2  第二种解法：动态规划

4.4  最长公共子序列变种

4.5  记忆递归法

4.6  空间效率改善

4.7  最优二叉搜索树

4.7.1  递归解法

4.7.2  计算最优答案

4.8  最优子结构与重叠子问题

4.8.1  最优子结构

4.8.2  重叠子问题

4.9  动态规划与静态规划的关系

4.10  动态规划与静态规划的相互转换

思考题

第5章  贪婪选择思想

5.1  仅有动态规划是不够的

5.2  什么是贪婪

5.3  背包问题

5.4  贪婪选择属性

5.5  教室规划问题

5.6  最小生成树

5.6.1  Kruskal算法的正确性

5.6.2  Kruskal算法的时间分析

5.7  Prim算法

5.8  霍夫曼树和霍夫曼编码

5.8.1  霍夫曼树

5.8.2  霍夫曼编码

5.8.3  霍夫曼编码的无前缀编码性质

5.9  进程调度问题

5.10  贪婪选择属性

5.11  标准分治、动态规划和贪婪选择的比较

思考题

第6章  随机化思想

6.1  为什么要随机化

6.2  随机的平方

6.3  什么是随机化算法

6.4  拉斯维加斯算法

6.5  蒙特卡罗算法

6.6  素性测试

6.7  矩阵乘积验证器

6.8  随机化最小生成树算法

6.8.1  Karger-Klein-Tarjan算法

6.8.2  结点降低算法

6.8.3  线性时间最小生成树算法

6.8.4  线性时间最小生成树算法的时间成本分析

6.9  随机数的生成

6.10  随机化算法的应用

思考题

第三篇  算法分析篇

第7章  概率分析

7.1  一切都在概率中

7.2  什么是概率分析

7.3  梦幻情人的代价

7.3.1  直接分析

7.3.2  最坏情况分析

7.3.3  最好情况分析

7.3.4  平均情况分析

7.3.5  平均情况下成本的概率分析

7.3.6  概率分析结果的有效性

7.3.7  正确概率分析的保障

7.4  梦幻情人的概率

7.5  随机排列问题

7.6  跳转表问题

7.6.1  跳转表插入操作

7.6.2  随机化跳转表构建算法

7.7  南柯一梦：从无穷到无有

7.8  概率分析的其他应用

思考题

第8章  摊销分析

8.1  什么是摊销分析

8.2  摊销分析与数据结构

8.3  摊销分析的几种方法

8.4  聚类分析

8.4.1  栈操作的聚类分析

8.4.2  二进制计数器的聚类分析

8.5  会计分析

8.6  势能分析

8.6.1  栈操作的势能分析

8.6.2  二进制计数器的势能分析

8.7  摊销分析应用：表格扩展的代价

8.7.1  动态表插入操作的聚类分析

8.7.2  动态表插入操作的会计分析

8.7.3  动态表插入操作的势能分析

8.8  运气不好就摊销

思考题

第9章  竞争分析

9.1  什么是竞争分析

9.2  在线算法和离线算法

9.3  竞争力

9.4  健忘对手和优良对手

9.5  线性表更新问题

9.6  前置移动算法的竞争分析

9.7  聚类问题

9.7.1  聚类问题的次优解算法

9.7.2  CLUSTERING-ALGORITHM算法的竞争分析

9.8  竞争分析与普通算法分析

思考题

第四篇  经典算法篇

第10章  排序与次序

10.1  排序无处不在

10.2  插入排序

10.2.1  插入排序的效率分析

10.2.2  折半插入排序

10.3  归并排序

10.4  快速排序

10.4.1  快速排序的过程

10.4.2  快速排序的时间复杂性分析

10.4.3  最坏情况分析

10.4.4  最好情况分析

10.4.5  平均情况分析

10.5  随机化快速排序

10.6  排序的下限

10.7  线性排序

10.8  计数排序

10.9  基数排序

10.9.1  基数排序的正确性

10.9.2  基数排序的时间效率分析

10.10  桶排序

10.10.1  桶排序的定义

10.10.2  桶排序的正确性

10.10.3  桶排序的时间复杂性分析

10.11  次序选择

10.12  快速次序选择算法

10.13  随机快速次序选择算法

10.14  最坏情况下的线性选择算法

10.14.1  杠杆点好坏分析

10.14.2  算法时间复杂性分析

思考题

第11章  搜索与散列

11.1  搜索问题

11.2  顺序搜索

11.3  折半搜索

11.4  常数搜索

11.5  散列搜索

11.6  散列函数选择

11.6.1  直接散列

11.6.2  除法（模除法）散列

11.6.3  乘法散列

11.6.4  乘法散列的赌徒原理

11.6.5  乘方取中法

11.7  散列算法的碰撞问题

11.7.1  开放寻址散列

11.7.2  开放寻址散列的时间成本

11.7.3  开放寻址下成功搜索的时间成本

11.7.4  封闭寻址散列

11.7.5  探寻序列的设计

11.7.6  封闭寻址散列的效率分析

11.7.7  搜索不成功的时间成本

11.7.8  成功搜索的效率分析

11.8  散列表元素删除

11.9  随机化散列

11.10  全域散列

11.11  完美散列

思考题

第12章  最短路径

12.1  剑指罗马

12.2  最短路径问题

12.3  单源单点最短路径问题

12.3.1  深度优先与广度优先搜索

12.3.2  深度优先解法

12.4  单源多点最短路径问题

12.4.1  最短路径的性质

12.4.2  Dijkstra最短路径算法

12.4.3  Dijkstra算法举例

12.4.4  Dijkstra算法与洪水泛滥

12.4.5  Dijkstra算法的正确性

12.4.6  Dijkstra算法的时间复杂性

12.5  Bellman-Ford算法

12.5.1  负权重的应对方式

12.5.2  Bellman-Ford算法的正确性

12.5.3  负循环检查问题

12.5.4  Bellman-Ford算法的时间复杂性

12.6  多源多点最短路径问题

12.6.1  多源多点最短路径问题解决思路

12.6.2  直接动态规划解法

12.6.3  矩阵乘法解法

12.6.4  Floyd-Warshall算法

12.6.5  Johnson算法

12.6.6  Johnson等效变换

12.6.7  差限问题解决

12.7  天意难违

思考题

第五篇  难解与无解篇

第13章  易解与难解

13.1  我们战无不胜吗

13.2  易解与难解

13.3  决策问题和优化问题

13.4  决策问题

13.5  P类问题

13.6  NP类问题

13.7  （确定性）图灵机

13.8  非确定性图灵机

13.9  非确定性算法

13.10  回到NP类问题

13.11  P和NP

13.12  搜索问题、决策问题和优化问题

13.13  有没有解和是否可决定

思考题

第14章  NP完全问题

14.1  玉龙雪山下的审判

14.2  NP完全问题的定义

14.3  NP完全的重要性

14.4  多项式时间规约

14.5  如何证明一个问题S是NP完全问题

14.6  第1个NP完全问题的证明

14.7  库克定理

14.8  3-SAT问题

14.9  证明NP难的技巧

14.10  整数规划

14.11  独立集问题

14.12  汉密尔顿回路问题

14.13  讨论：弱NP完全、强NP完全和中NP完全

思考题

第15章  无解与近似

15.1  难解问题

15.2  不可决定问题

15.3  程序终结的判断

15.4  难解之题的求解

15.5  智能穷举、近似算法和本地搜索

15.6  智能穷举之回溯策略

15.7  智能穷举之分支限界

15.8  贪婪近似策略

15.9  启发式搜索策略

15.10  模拟退火算法

15.10.1  模拟退火算法的思想

15.10.2  模拟退火算法的基本循环

15.10.3  退火算法描述

15.11  基因／遗传算法

15.11.1  生物进化与遗传

15.11.2  遗传算法的基本要义

15.11.3  遗传算法的实现

15.11.4  遗传算法的基本运算过程

15.11.5  遗传算法的现状

15.12  概率尽在一切中

思考题

结语  算法之道

附录  算法随想

参考文献