算法基础（第5版）

图书标准信息

• 作者 [美]那不勒坦（Richard E.Neapolitan） 著；贾洪峰 译
• 出版社 人民邮电出版社
• 出版时间 2016-03
• 版次 1
• ISBN 9787115416575
• 定价 99.00元
• 装帧 平装
• 开本 16开
• 纸张 胶版纸
• 页数 398页
• 字数 775千字
• 正文语种 简体中文
• 原版书名 Foundations of Algorithms
• 丛书 图灵计算机科学丛书

【内容简介】

本书通过大量示例介绍了算法设计、算法的复杂度分析以及计算复杂度。主要内容有：算法设计与分析、分而治之方法、动态规划方法、贪婪方法、回溯算法、分支定界算法、计算复杂度、难解性和NP理论、遗传算法和遗传编程、数论算法、并行算法等。此外，本书在每章末尾都提供了大量练习，而且还提供了全面的教辅材料及答案，是教授和学习算法设计与分析的理想教材。

【作者简介】

RichardE.Neapolitan，美国东北伊利诺伊大学计算机科学教授，CSuiteConsultingGroup贝叶斯网络和统计学研究员。研究方向包括：概率与统计、人工智能、认知科学，以及贝叶斯网络和概率建模在医学、生物和金融领域的应用。他是国际知名的理论家和实践者，并受邀在世界各地发表讲演、举办研讨会。Neapolitan还是一位多产的作家，另著有《专家系统的概率推理》《学习贝叶斯网络》《当代人工智能》等专著。

【目录】

第1章算法：效率、分析和阶1
1．1算法1
1．2开发高效算法的重要性5
1．2．1顺序查找与二分查找的对比6
1．2．2斐波那契序列7
1．3算法分析10
1．3．1复杂度分析10
1．3．2理论应用14
1．3．3正确性分析15
1．4阶15
1．4．1阶的直观介绍15
1．4．2阶数的严谨介绍17
1．4．3利用极限计算阶23
1．5本书概要25
1．6习题25
第2章分而治之30
2．1二分查找30
2．2合并排序33
2．3分而治之方法38
2．4快速排序（分割交换排序）38
2．5Strassen矩阵乘法算法42
2．6大整数的算术运算46
2．6．1大整数的表示：加法和其他线性时间运算46
2．6．2大整数的乘法46
2．7确定阈值50
2．8不应使用分而治之方法的情况53
2．9习题53
第3章动态规划58
3．1二项式系数58
3．2Floyd最短路径算法61
3．3动态规划与最优化问题66
3．4矩阵链乘法67
3．5最优二叉查找树73
3．6旅行推销员问题79
3．7序列对准84
3．8习题88
第4章贪婪方法92
4．1最小生成树94
4．1．1Prim算法96
4．1．2Kruskal算法100
4．1．3Prim算法与Kruskal算法的比较103
4．1．4最终讨论103
4．2单源最短路径的Dijkstra算法104
4．3调度计划106
4．3．1使系统内总时间最短106
4．3．2带有最终期限的调度安排108
4．4霍夫曼编码112
4．4．1前缀码113
4．4．2霍夫曼算法114
4．5贪婪方法与动态规划的比较：背包问题116
4．5．10-1背包问题的一种贪婪方法116
4．5．2部分背包问题的贪婪方法118
4．5．30-1背包问题的动态规划方法118
4．5．40-1背包问题动态规划算法的改进118
4．6习题120
第5章回溯124
5．1回溯方法124
5．2n皇后问题129
5．3用蒙特卡洛算法估计回溯算法的效率132
5．4“子集之和”问题134
5．5图的着色138
5．6哈密顿回路问题141
5．70-1背包问题143
5．7．10-1背包问题的回溯算法143
5．7．2比较0-1背包问题的动态规划算法与回溯算法149
5．8习题150
第6章分支定界153
6．1用0-1背包问题说明分支定界154
6．1．1带有分支定界修剪的宽度优先查找154
6．1．2带有分支定界修剪的最佳优先查找158
6．2旅行推销员问题161
6．3溯因推理（诊断）167
6．4习题173
第7章计算复杂度介绍：排序问题175
7．1计算复杂度175
7．2插入排序和选择排序176
7．3每次比较最多减少一个倒置的算法的下限179
7．4再谈合并排序181
7．5再谈快速排序185
7．6堆排序186
7．6．1堆和基本堆例程186
7．6．2堆排序的一种实现189
7．7合并排序、快速排序和堆排序的比较193
7．8仅通过键的比较进行排序的下限194
7．8．1排序算法的决策树194
7．8．2最差情况下的下限196
7．8．3平均情况下的下限197
7．9分配排序（基数排序）200
7．10习题203
第8章再谈计算复杂度：查找问题207
8．1仅通过键的比较进行查找的下限207
8．1．1最差表现的下限209
8．1．2平均情况下的下限210
8．2插值查找213
8．3树中的查找215
8．3．1二叉查找树215
8．3．2B树218
8．4散列219
8．5选择问题：对手论证222
8．5．1找出最大键222
8．5．2同时找出最大键和最小键223
8．5．3找出第二大的键227
8．5．4查找第k小的键230
8．5．5选择问题的一种概率算法236
8．6习题238
第9章计算复杂度和难解性：NP理论简介241
9．1难解性241
9．2再谈输入规模242
9．3三类一般问题244
9．3．1已经找到多项式时间算法的问题244
9．3．2已经证明难解的问题245
9．3．3未被证明是难解的，但也从来没有找到多项式时间算法的问题245
9．4NP理论245
9．4．1集合P和NP247
9．4．2NP完全问题250
9．4．3NP困难、NP容易和NP等价问题256
9．5处理NP困难问题259
9．5．1旅行推销员问题的近似算法259
9．5．2装箱问题的近似算法263
9．6习题266
第10章遗传算法和遗传编程268
10．1遗传知识复习268
10．2遗传算法270
10．2．1算法270
10．2．2说明范例270
10．2．3旅行推销员问题272
10．3遗传编程278
10．3．1说明范例279
10．3．2人造蚂蚁281
10．3．3在金融贸易中的应用283
10．4讨论及扩展阅读284
10．5习题284
第11章数论算法286
11．1数论回顾286
11．1．1合数与质数286
11．1．2最大公约数286
11．1．3质因数分解288
11．1．4最小公倍数289
11．2计算最大公约数290
11．2．1欧氏算法290
11．2．2欧氏算法的扩展292
11．3模运算回顾294
11．3．1群论294
11．3．2关于n同余295
11．3．3子群299
11．4模线性方程的求解302
11．5计算模的幂305
11．6寻找大质数307
11．6．1寻找大质数307
11．6．2检查一个数字是否为质数307
11．7RSA公钥密码系统318
11．7．1公钥加密系统318
11．7．2RSA加密系统319
11．8习题321
第12章并行算法简介324
12．1并行体系结构325
12．1．1控制机制326
12．1．2地址空间的组织326
12．1．3互联网络328
12．2PRAM模型330
12．2．1为CREWPRAM模型设计算法332
12．2．2为CRCWPRAM模型设计算法337
12．3习题339
附录A必备数学知识回顾340
附录B求解递归方程：在递归算法分析
中的应用363
附录C不交集的数据结构388
参考文献395