《算法之道》介绍
为了方便C/C++版面CUer对新技术和新知识的追求，我们会不定期的提供一些大家喜欢的和版本相关的技术类图书，采取拍卖的方式进行，欢迎本讨论区爱好技术的各位CUer参与竞拍。同时,也欢迎大家提议更多大家喜好的技术图书,我们后期会尽量的去提供，给大家更多更好的选择。
本次的书籍是提供给本版的技术爱好者和相关从业人员的(至少本版发帖20贴以上)，所以非本版人员请勿扰乱拍卖活动，欢迎大家监督！
算法之道
http://images.china-pub.com/ebook195001-200000/196344/zcover.jpg?2010-2-5%200:13:34
[*]作者：邹恒明[*]出版社：机械工业出版社[*]ISBN：9787111294948[*]上架时间：2010-1-29[*]出版日期：2010 年2月[*]开本：16开[*]页码：292[*]版次：1-1
图书简介：
本书追求的目标是算法背后的逻辑，是一本启示书，而不是一本包罗万象的算法大全。因此，本书甄选了那些最能够展现算法思想、战略和精华，并能够有效训练算法思维的内容。本书将算法的讨论分为五大部分：算法基础篇、算法设计篇、算法分析篇、经典算法篇、难解与无解篇。每一个部分分别讨论算法的一大方面：基础、设计、分析、经典和难解问题。
本书既可以作为大学本科或研究生的算法教材或参考书，也可以作为对算法有兴趣的读者提升认知深度的读物。
图书目录：
前言
第一篇算法基础篇
第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和NP 252
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
页:
[1]