《算法之道》介绍

send_linux

为了方便C/C++版面CUer对新技术和新知识的追求，我们会不定期的提供一些大家喜欢的和版本相关的技术类图书，采取拍卖的方式进行，欢迎本讨论区爱好技术的各位CUer参与竞拍。

    同时,也欢迎大家提议更多大家喜好的技术图书,我们后期会尽量的去提供，给大家更多更好的选择。

    本次的书籍是提供给本版的技术爱好者和相关从业人员的(至少本版发帖20贴以上)，所以非本版人员请勿扰乱拍卖活动，欢迎大家监督！

算法之道

• 作者：邹恒明
• 出版社：机械工业出版社
• 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.6  O、(、(表示        18
    2.7  最好、最坏、平均        19
    2.8  O、(、(的另一类定义        21
    2.9  O、(、(的性质        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.7  VLSI 布线        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.1  Kruskal算法的正确性        79
    5.6.2  Kruskal算法的时间分析        80
    5.7  Prim算法        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.1  Karger-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.2  CLUSTERING-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.2  Dijkstra最短路径算法        220
    12.4.3  Dijkstra算法举例        221
    12.4.4  Dijkstra算法与洪水泛滥        222
    12.4.5  Dijkstra算法的正确性        223
    12.4.6  Dijkstra算法的时间复杂性        224
    12.5  Bellman-Ford算法        226
    12.5.1  负权重的应对方式        227
    12.5.2  Bellman-Ford算法的正确性        230
    12.5.3  负循环检查问题        231
    12.5.4  Bellman-Ford算法的时间复杂性        231
    12.6  多源多点最短路径问题        232
    12.6.1  多源多点最短路径问题解决思路        232
    12.6.2  直接动态规划解法        233
    12.6.3  矩阵乘法解法        234
    12.6.4  Floyd-Warshall 算法        235
    12.6.5  Johnson 算法        236
    12.6.6  Johnson等效变换        237
    12.6.7  差限问题解决        238
    12.7  天意难违        240
    思考题        240
    第五篇  难解与无解篇
    第13章  可解与不可解        244
    13.1  我们战无不胜吗        245
    13.2  易解与难解        245
    13.3  决策问题和优化问题        246
    13.4  决策问题        247
    13.5  P类问题        247
    13.6  NP类问题        248
    13.7 （确定性）图灵机        249
    13.8  非确定性图灵机        249
    13.9  非确定性算法        250
    13.10  回到NP类问题        251
    13.11  P和NP        252
    13.12  搜索问题、决策问题和优化问题        253
    13.13  有没有解和是否可决定        253
    思考题        254
    第14章  NP完全问题        256
    14.1  玉龙雪山下的审判        256
    14.2  NP完全问题的定义        257
    14.3  NP完全的重要性        258
    14.4  多项式时间规约        259
    14.5  如何证明一个问题S是NP完全        259
    14.6  第1个NP完全问题的证明        260
    14.7  库克定理        260
    14.8  3-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