《算法基础(第5版)/图灵计算机科学丛书》((美)那不勒坦|译者:贾洪峰)-图书推荐
内容提要
那不勒坦著的《算法基础(第5版)》通过大量示例介绍了算法设计、算法的复杂度分析以及计算复杂度。主要内容有:算法设计与分析、分而治之方法、动态规划方法、贪婪方法、回溯算法、分支定界算法、计算复杂度、难解性NP理论、遗传算法和遗传编程、数论算法、并行算法等。此外,本书在每章末尾都提供了大量练习,而且还提供了全面的教辅材料及答案,是教授和学本书适合高等院校学生、程序员及算法分析和设计人员。
目录
第1章 算法:效率、分析和阶
1.1 算法
1.2 开发高效算法的重要性
1.2.1 顺序查找与二分查找的对比
1.2.2 斐波那契序列
1.3 算法分析
1.3.1 复杂度分析
1.3.2 理论应用
1.3.3 正确性分析
1.4 阶
1.4.1 阶的直观介绍
1.4.2 阶数的严谨介绍
1.4.3 利用极限计算阶
1.5 本书概要
1.6 习题
第2章 分而治之
2.1 二分查找
2.2 合并排序
2.3 分而治之方法
2.4 快速排序(分割交换排序)
2.5 Strassen矩阵乘法算法
2.6 大整数的算术运算
2.6.1 大整数的表示:加法和其他线性时间运算
2.6.2 大整数的乘法
2.7 确定阈值
2.8 不应使用分而治之方法的情况
2.9 习题
第3章 动态规划
3.1 二项式系数
3.2 Floyd短路径算法
3.3 动态规划与优化问题
3.4 矩阵链乘法
3.5 优二叉查找树
3.6 旅行推销员问题
3.7 序列对准
3.8 习题
第4章 贪婪方法
4.1 小生成树
4.1.1 Prim算法
4.1.2 Kruskal算法
4.1.3 Prim算法与Kruskal算法的比较
4.1.4 终讨论
4.2 单源短路径的Dijkstra算法
4.3 调度计划
4.3.1 使系统内总时间短
4.3.2 带有终期限的调度安排
4.4 霍夫曼编码
4.4.1 前缀码
4.4.2 霍夫曼算法
4.5 贪婪方法与动态规划的比较:背包问题
4.5.1 0-1背包问题的一种贪婪方法
4.5.2 部分背包问题的贪婪方法
4.5.3 0-1背包问题的动态规划方法
4.5.4 0-1背包问题动态规划算法的改进
4.6 习题
第5章 回溯
5.1 回溯方法
5.2 n皇后问题
5.3 用蒙特卡洛算法估计回溯算法的效率
5.4 “子集之和”问题
5.5 图的着色
5.6 哈密顿回路问题
5.7 0-1背包问题
5.7.1 0-1背包问题的回溯算法
5.7.2 比较0-1背包问题的动态规划算法与回溯算法
5.8 习题
第6章 分支定界
6.1 用0-1背包问题说明分支定界
6.1.1 带有分支定界修剪的宽度优先查找
6.1.2 带有分支定界修剪的佳优先查找
6.2 旅行推销员问题
6.3 溯因推理(诊断)
6.4 习题
第7章 计算复杂度介绍:排序问题
7.1 计算复杂度
7.2 插入排序和选择排序
7.3 每次比较多减少一个倒置的算法的下限
7.4 再谈合并排序
7.5 再谈快速排序
7.6 堆排序
7.6.1 堆和基本堆例程
7.6.2 堆排序的一种实现
7.7 合并排序、快速排序和堆排序的比较
7.8 仅通过键的比较进行排序的下限
7.8.1 排序算法的决策树
7.8.2 差情况下的下限
7.8.3 平均情况下的下限
7.9 分配排序(基数排序)
7.10 习题
第8章 再谈计算复杂度:查找问题
8.1 仅通过键的比较进行查找的下限
8.1.1 差表现的下限
8.1.2 平均情况下的下限
8.2 插值查找
8.3 树中的查找
8.3.1 二叉查找树
8.3.2 B树
8.4 散列
8.5 选择问题:对手论证
8.5.1 找出大键
8.5.2 同时找出大键和小键
8.5.3 找出第二大的键
8.5.4 查找第k小的键
8.5.5 选择问题的一种概率算法
8.6 习题
第9章 计算复杂度和难解性:NP理论简介
9.1 难解性
9.2 再谈输入规模
9.3 三类一般问题
9.3.1 已经找到多项式时间算法的问题
9.3.2 已经证明难解的问题
9.3.3 未被证明是难解的,但也从来没有找到多项式时间算法的问题
9.4 NP理论
9.4.1 集合P和
9.4.2 NP 问题
9.4.3 NP困难、NP容易和NP等价问题
9.5 处理NP困难问题
9.5.1 旅行推销员问题的近似算法
9.5.2 装箱问题的近似算法
9.6 习题
0章 遗传算法和遗传编程
10.1 遗传知识复习
10.2 遗传算法
10.2.1 算法
10.2.2 说明范例
10.2.3 旅行推销员问题
10.3 遗传编程
10.3.1 说明范例
10.3.2 人造蚂蚁
10.3.3 在金融贸易中的应用
10.4 讨论及扩展阅读
10.5 习题
1章 数论算法
11.1 数论回顾
11.1.1 合数与质数
11.1.2 大公约数
11.1.3 质因数分解
11.1.4 小公倍数
11.2 计算大公约数
11.2.1 欧氏算法
11.2.2 欧氏算法的扩展
11.3 模运算回顾
11.3.1 群论
11.3.2 关于n同余
11.3.3 子群
11.4 模线性方程的求解
11.5 计算模的幂
11.6 寻找大质数
11.6.1 寻找大质数
11.6.2 检查一个数字是否为质数
11.7 RSA公钥密码系统
11.7.1 公钥加密系统
11.7.2 RSA加密系统
11.8 习题
2章 并行算法简介
12.1 并行体系结构
12.1.1 控制机制
12.1.2 地址空间的组织
12.1.3 互联网络
12.2 PRAM模型
12.2.1 为CREWPRAM模型设计算法
12.2.2 为CRCWPRAM模型设计算法
12.3 习题
附录A 数学知识回顾
附录B求解递归方程:在递归算法分析
中的应用
附录C不交集的数据结构
参考文献