算法之道：从无有 到无穷

图书标准信息

• 作者 邹恒明 著
• 出版社 机械工业出版社
• 出版时间 2010-02
• 版次 1
• ISBN 9787111294948
• 定价 39.00元
• 装帧 平装
• 开本 16开
• 纸张 胶版纸
• 页数 292页
• 正文语种 简体中文

【内容简介】

　　《算法之道》追求的目标是算法背后的逻辑，是一本启示书，而不是一本包罗万象的算法大全。因此，《算法之道》甄选了那些最能够展现算法思想、战略和精华，并能够有效训练算法思维的内容。《算法之道》将算法的讨论分为五大部分：算法基础篇、算法设计篇、算法分析篇、经典算法篇、难解与无解篇。每一个部分分别讨论算法的一大方面：基础、设计、分析、经典和难解问题。
　　《算法之道》既可以作为大学本科或研究生的算法教材或参考书，也可以作为对算法有兴趣的读者提升认知深度的读物。

【目录】

前言
第一篇算法基础篇
第1章从无有到无穷2
1.1意念与现实3
1.2什么是算法4
1.3算法的表示6
1.4算法之魂7
1.5如何比较速度8
1.6算法与计算机的关系9
1.7算法的范畴10
1.8为什么学习算法10
思考题11

第2章计数与渐近12
2.1算法的分析12
2.1.1正确性分析13
2.1.2时空效率分析14
2.1.3时空特性分析14
2.2计数：算法分析的核心14
2.3算法设计15
2.4算法效率表示16
2.5渐近分析17
2.6O表示18
2.7最好、最坏、平均19
2.8O的另一类定义21
2.9O的性质22
2.10要更快的计算机还是要更快的算法22
思考题23

第3章分治与递归25
3.1分而治之为上策26
3.2分治策略28
3.3递归表达式求解29
3.3.1递归树法29
3.3.2替换解法30
3.3.3大师解法32
3.4分治策略举例1：乘方运算35
3.5生命不能承受之重：矩阵乘法36
3.6魔鬼序列：斐波那契序列38
3.7VLSI布线41
3.8多项式乘法43
3.9分治就在潜意识深处43
思考题43

第二篇算法设计篇
第4章动态规划思想46
4.1什么是动态规划47
4.2流水装配线问题48
4.3最长公共子序列52
4.3.1第一种解法：蛮力策略52
4.3.2第二种解法：动态规划53
4.4最长公共子序列变种55
4.5记忆递归法55
4.6空间效率改善56
4.7最优二叉搜索树56
4.7.1递归解法59
4.7.2计算最优答案59
4.8最优子结构与重叠子问题62
4.8.1最优子结构62
4.8.2重叠子问题63
4.9动态规划与静态规划的关系63
4.10动态规划与静态规划的相互转换64
思考题65

第5章贪婪选择思想67
5.1仅有动态规划是不够的67
5.2什么是贪婪68
5.3背包问题68
5.4贪婪选择属性71
5.5教室规划问题72
5.6最小生成树76
5.6.1Kruskal算法的正确性79
5.6.2Kruskal算法的时间分析80
5.7Prim算法80
5.8霍夫曼树和霍夫曼编码83
5.8.1霍夫曼树85
5.8.2霍夫曼编码86
5.8.3霍夫曼编码的无前缀编码性质87
5.9贪婪选择属性88
5.10标准分治、动态规划和贪婪选择的比较89
思考题90

第6章随机化思想92
6.1为什么要随机化93
6.2随机的平方94
6.3什么是随机化算法95
6.4拉斯维加斯算法96
6.5蒙特卡罗算法97
6.6素性测试97
6.7矩阵乘积验证器100
6.8随机化最小生成树算法102
6.8.1Karger-Klein-Tarjan算法103
6.8.2节点降低算法103
6.8.3线性时间最小生成树算法104
6.8.4线性时间最小生成树算法的时间成本分析104
6.9随机数的生成105
6.10随机化算法的应用105
思考题106

第三篇算法分析篇
第7章概率分析108
7.1一切都在概率中109
7.2什么是概率分析109
7.3梦幻情人的代价110
7.3.1直接分析112
7.3.2最坏情况分析113
7.3.3最好情况分析113
7.3.4平均情况分析113
7.3.5平均情况下成本的概率分析113
7.4概率分析结果的有效性114
7.5正确概率分析的保障115
7.6梦幻情人的概率115
7.7随机排列问题117
7.8南柯一梦：从无穷到无有119
7.9概率分析的其他应用120
思考题121

第8章摊销分析122
8.1什么是摊销分析123
8.2摊销分析与数据结构124
8.3摊销分析的几种方法124
8.4聚类分析125
8.4.1栈操作的聚类分析125
8.4.2二进制计数器的聚类分析126
8.5会计分析128
8.6势能分析130
8.6.1栈操作的势能分析130
8.6.2二进制计数器的势能分析131
8.7摊销分析应用：表格扩展的代价131
8.7.1动态表插入操作的聚类分析134
8.7.2动态表插入操作的会计分析134
8.7.3动态表插入操作的势能分析136
8.8运气不好就摊销137
思考题138

第9章竞争分析139
9.1什么是竞争分析139
9.2在线算法和离线算法141
9.3竞争力142
9.4健忘对手和优良对手142
9.5线性表更新问题143
9.6前置移动算法的竞争分析145
9.7聚类问题147
9.7.1聚类问题的次优解算法148
9.7.2CLUSTERING-ALGORITHM算法的竞争分析148
9.8竞争分析与普通算法分析149
思考题149

第四篇经典算法篇
第10章排序和次序152
10.1排序无处不在152
10.2插入排序153
10.2.1插入排序的效率分析154
10.2.2折半插入排序155
10.3归并排序156
10.4快速排序158
10.4.1快速排序的过程158
10.4.2快速排序的时间复杂性分析159
10.4.3最坏情况分析160
10.4.4最好情况分析160
10.4.5平均情况分析161
10.5随机化快速排序162
10.6排序的下限164
10.7线性排序165
10.8计数排序166
10.9基数排序168
10.9.1基数排序的正确性169
10.9.2基数排序的时间效率分析170
10.10桶排序171
10.10.1桶排序的定义172
10.10.2桶排序的正确性173
10.10.3桶排序的时间复杂性分析173
10.11次序选择175
10.12快速次序选择算法176
10.13随机快速次序选择算法178
10.14最坏情况下的线性选择算法179
10.14.1杠杆点好坏分析180
10.14.2算法的时间复杂性分析181
思考题181

第11章搜索与哈希183
11.1搜索问题184
11.2顺序搜索184
11.3折半搜索185
11.4常数搜索186
11.5哈希搜索187
11.6哈希函数选择189
11.6.1直接哈希189
11.6.2除法（模除法）哈希190
11.6.3乘法哈希191
11.6.4乘法哈希的赌徒原理192
11.6.5乘方取中法193
11.7哈希算法的碰撞问题193
11.7.1开放寻址哈希193
11.7.2开放寻址哈希的时间成本194
11.7.3开放寻址下成功搜索的时间成本195
11.7.4封闭寻址哈希196
11.7.5探寻序列的设计197
11.7.6封闭寻址哈希的效率分析199
11.7.7搜索不成功的时间成本199
11.7.8成功搜索的效率分析201
11.8哈希表元素删除201
11.9随机化哈希202
11.10全域哈希203
11.11全域哈希构造204
11.12完美哈希206
思考题208

第12章最短路径211
12.1剑指罗马211
12.2最短路径问题213
12.3单源单点最短路径问题215
12.3.1深度优先搜索与广度优先搜索215
12.3.2深度优先解法217
12.4单源多点最短路径问题218
12.4.1最短路径的性质219
12.4.2Dijkstra最短路径算法220
12.4.3Dijkstra算法举例221
12.4.4Dijkstra算法与洪水泛滥222
12.4.5Dijkstra算法的正确性223
12.4.6Dijkstra算法的时间复杂性224
12.5Bellman-Ford算法226
12.5.1负权重的应对方式227
12.5.2Bellman-Ford算法的正确性230
12.5.3负循环检查问题231
12.5.4Bellman-Ford算法的时间复杂性231
12.6多源多点最短路径问题232
12.6.1多源多点最短路径问题解决思路232
12.6.2直接动态规划解法233
12.6.3矩阵乘法解法234
12.6.4Floyd-Warshall算法235
12.6.5Johnson算法236
12.6.6Johnson等效变换237
12.6.7差限问题解决238
12.7天意难违240
思考题240

第五篇难解与无解篇
第13章可解与不可解244
13.1我们战无不胜吗245
13.2易解与难解245
13.3决策问题和优化问题246
13.4决策问题247
13.5P类问题247
13.6NP类问题248
13.7（确定性）图灵机249
13.8非确定性图灵机249
13.9非确定性算法250
13.10回到NP类问题251
13.11P和NP252
13.12搜索问题、决策问题和优化问题253
13.13有没有解和是否可决定253
思考题254

第14章NP完全问题256
14.1玉龙雪山下的审判256
14.2NP完全问题的定义257
14.3NP完全的重要性258
14.4多项式时间规约259
14.5如何证明一个问题S是NP完全259
14.6第1个NP完全问题的证明260
14.7库克定理260
14.83-SAT问题263
14.9证明NP难的技巧264
14.10整数规划265
14.11独立集问题266
14.12汉密尔顿回路问题268
14.13讨论：弱NP完全、强NP完全和中NP完全271
思考题272

第15章无解与近似273
15.1难解问题274
15.2不可决定问题274
15.3程序终结的判断275
15.4难解之题的求解276
15.5智能穷举、近似算法和本地搜索277
15.6智能穷举之回溯策略279
15.7智能穷举之分支限界280
15.8贪婪近似策略280
15.9启发式搜索策略281
15.10模拟淬火算法282
15.10.1模拟淬火算法的思想284
15.10.2模拟淬火算法的基本循环284
15.10.3淬火算法描述284
思考题286
结语算法之道288
附录算法随想290
参考文献293