由迈克尔T.古德里奇、罗伯托·塔马西亚著的《算法设计与应用/计算机科学丛书》全面系统地介绍算法设计和算法应用的各个领域，内容涵盖经典数据结构、经典算法、算法分析方法、算法设计方法以及算法在各个领域的应用，还包含一些高级主题。本书采用应用驱动的方法引入各章内容，内容编排清晰合理，讲解由浅入深。此外，各章都附有巩固练习、创新练习和应用练习三种类型的题目，为读者理解和掌握算法设计和应用提供了很好的素材。
本书可作为高等院校计算机及相关专业“数据结构和算法”课程的本科生、研究生教材，也可作为算法理论和实践工作者的参考手册。
出版者的话
译者序
前言
第1章 算法分析
1.1 分析算法
1.1.1 伪代码
1.1.2 随机存取机模型
1.1.3 基本操作数目的计算
1.1.4 递归算法的分析
1.1.5 渐近表示法
1.1.6 渐近表示法的重要性
1.2 相关数学知识复习
1.2.1 求和
1.2.2 对数和幂
1.2.3 简单的证明技术
1.2.4 概率基础
1.3 算法分析案例
1.3.1 大子数组问题的第一个解
1.3.2 一种改进的求大子数组算法
1.3.3 线性时间的大子数组算法
1.4 平摊分析
1.4.1 平摊技术
1.4.2 对一个可扩展数组实现的分析
1.5 练习
本章注记
第一部分 数据结构
第2章 基本数据结构
2.1 栈和队列
2.1.1 栈
2.1.2 队列
2.2 列表
2.2.1 基于索引的列表
2.2.2 链表
2.3 树
2.3.1 树的定义
2.3.2 树的遍历
2.3.3 二叉树
2.3.4 表示树的数据结构
2.4 练习
本章注记
第3章 二叉搜索树
3.1 搜索和更新
3.1.1 二叉搜索树的定义
3.1.2 二叉搜索树中的搜索
3.1.3 二叉搜索树中的插入
3.1.4 二叉搜索树中的删除
3.1.5 二叉搜索树的性能
3.2 范围查询
3.3 基于索引的搜索
3.4 随机构造二叉搜索树
3.5 练习
本章注记
第4章 平衡二叉搜索树
4.1 秩和旋转
4.2 AVL树
4.3 红黑树
4.4 弱AVL树
4.5 伸展树
4.6 练习
本章注记
第5章 优先队列和堆
5.1 优先队列
5.2 PQ排序、选择排序和插入排序
5.2.1 选择排序
5.2.2 插入排序
5.3 堆
5.3.1 基于数组结构的二叉树
5.3.2 堆中的插入
5.3.3 堆中的删除
5.4 堆排序
5.5 扩展优先队列
5.6 练习
本章注记
第6章 散列表
6.1 映射
6.1.1 映射的定义
6.1.2 查找表
6.2 散列函数
6.2.1 分量求和
6.2.2 多项式求值函数
6.2.3 基于表格的散列
6.2.4 取模
6.2.5 随机线性和多项式函数
6.3 碰撞处理与再散列
6.3.1 拉链法
6.3.2 开放寻址法
6.3.3 线性探测
6.3.4 平方探测
6.3.5 双重散列
6.3.6 再散列
6.4 布谷鸟散列
6.5 通用散列
6.6 练习
本章注记
第7章 并查集结构
7.1 并查集及其应用
7.1.1 连通分支
7.1.2 迷宫建筑和渗透理论
7.2 基于列表的实现
7.3 基于树的实现
7.4 练习
本章注记
第二部分 排序和选择
第8章 归并排序和快速排序
8.1 归并排序
8.1.1 分而治之
8.1.2 归并排序和递推方程
8.2 快速排序
8.2.1 随机快速排序
8.2.2 原地快速排序
8.3 基于比较的排序的下界
8.4 练习
本章注记
第9章 快速排序和选择
9.1 桶排序和基数排序
9.1.1 桶排序
9.1.2 基数排序
9.2 选择
9.2.1 随机快速选择
9.2.2 确定性选择
9.3 加权中位数
9.4 练习
本章注记
第三部分 基本技术
第10章 贪心法
10.1 分份背包问题
10.2 任务调度
10.3 文本压缩和哈夫曼编码
10.4 练习
本章注记
第11章 分治法
11.1 递推与主定理
11.2 整数乘法
11.3 矩阵乘法
11.4 极大点集问题
11.5 练习
本章注记
第12章 动态规划
12.1 矩阵连乘
12.2 通用技术
12.3 望远镜调度
12.4 博弈策略
12.4.1 硬币行
12.4.2 概率博弈策略与逆向归纳法
12.5 长公共子序列问题
12.5.1 问题定义
12.5.2 应用动态规划解LCS问题
12.6 0-1背包问题
12.7 练习
本章注记
第13章 图及遍历
13.1 图的术语和表示方法
13.1.1 图的一些术语
13.1.2 图的操作
13.1.3 表示图的数据结构
13.2 深度优先搜索
13.3 广度优先搜索
13.4 有向图
13.4.1 遍历有向图
13.4.2 传递闭包
13.4.3 有向DFS和垃圾回收
13.4.4 有向无环图
13.5 双连通分量
13.6 练习
本章注记
第四部分 图算法
第14章 短路径
14.1 单源短路径
14.2 Dijkstra算法
14.3 BellmanFord 算法
14.4 有向无环图中的短路径
14.5 所有顶点对之间的短路径
14.5.1 动态规划短路径算法
14.5.2 通过矩阵乘法计算短路径
14.6 练习
本章注记
第15章 小生成树
15.1 小生成树的性质
15.2 Kruskal算法
15.3 PrimJarník算法
15.4 Baruvka算法
15.5 练习
本章注记
第16章 网络流和匹配
16.1 流与割
16.1.1 割
16.1.2 剩余容量和增流路径
16.2 大流算法
16.2.1 FordFulkerson算法
16.2.2 EdmondsKarp算法
16.3 大二分图匹配
16.4 棒球赛的淘汰
16.5 低成本流
16.6 练习
本章注记
第五部分 计算困难问题
第17章 NP完全性
17.1 P和NP
17.1.1 定义复杂类P和NP
17.1.2 一些有趣的NP问题
17.2 NP完全性
17.2.1 多项式时间归约和NP难度
17.2.2 CookLevin 定理
17.2.3 如何证明一个问题是NP完全问题
17.3 合取范式可满足问题和3可满足问题
17.4 顶点覆盖、团和集合覆盖
17.5 子集和与背包问题
17.6 哈密顿回路和TSP
17.7 练习
本章注记
第18章 近似算法
18.1 几何旅行商问题
18.1.1 MetricTSP的一个2近似算法
18.1.2 Christofides近似算法
18.2 覆盖问题的近似
18.2.1 顶点覆盖的2近似算法
18.2.2 集合覆盖的对数近似
18.3 多项式时间近似方法
18.4 回溯和分支定界
18.4.1 回溯法
18.4.2 分支定界法
18.5 练习
本章注记
第六部分 高级主题
第19章 随机算法
19.1 随机排列的生成
19.2 稳定婚姻和优惠券收集
19.2.1 优惠券收集问题分析
19.2.2 稳定婚姻问题
19.3 小割
19.3.1 收缩边
19.3.2 计算小割
19.3.3 更快的算法
19.4 寻找素数
19.5 切尔诺夫界
19.5.1 马尔可夫不等式
19.5.2 示性随机变量之和
19.5.3 几何型随机变量之和
19.6 跳跃表
19.6.1 搜索
19.6.2 更新操作
19.6.3 跳跃表的概率分析
19.7 练习
本章注记
第20章 B树和外部存储器
20.1 外部存储器
20.2 (2,4)树和B树
20.2.1 多叉搜索树
20.2.2 (2,4)树
20.2.3 (a,b)树和B树
20.3 外部存储器排序
20.4 在线缓存算法
20.5 练习
本章注记
第21章 多维搜索
21.1 范围树
21.2 优先搜索树
21.2.1 构造优先搜索树
21.2.2 在优先搜索树中搜索
21.2.3 优先范围树
21.3 四叉树和kd树
21.3.1 四叉树
21.3.2 kd树
21.4 练习
本章注记
第22章 计算几何
22.1 几何对象上的操作
22.2 凸壳
22.2.1 礼品包装算法
22.2.2 Graham扫描算法
22.3 线段相交
22.4 求近点对
22.5 练习
本章注记
第23章 字符串算法
23.1 字符串操作
23.2 BoyerMoore 算法
23.3 KnuthMorrisPratt算法
23.4 基于散列的词典匹配
23.5 字典树
23.5.1 标准字典树
23.5.2 压缩字典树
23.5.3 后缀字典树
23.5.4 搜索引擎
23.6 练习
本章注记
第24章 密码学
24.1 大公约数
24.1.1 一些初等数论知识
24.1.2 欧几里得GCD算法
24.2 模运算
24.2.1 模幂运算
24.2.2 模乘法逆
24.3 加密操作
24.4 RSA密码系统
24.5 El Gamal密码系统
24.6 练习
本章注记
第25章 快速傅里叶变换
25.1 卷积
25.2 原始单位根
25.3 离散傅里叶变换
25.4 快速傅里叶变换算法
25.5 练习
本章注记
第26章 线性规划
26.1 定义问题
26.2 单纯形法
26.2.1 松弛型
26.2.2 扩展的例子
26.2.3 单纯形算法
26.3 对偶
26.4 线性规划的应用
26.5 练习
本章注记
附录 A一些有用的数学知识
参考文献
[
我的消息
购物车
