机械工业现代算法设计与分析桑迪普森计算机科学丛书黑皮书

  内容简介

本书不仅讲解传统的算法设计策略和技巧，而且关注算法领域不断涌现的新概念、新方法和新应用，帮助读者把握技术热点及发展趋势。书中引入了降维技术、并行算法、随机算法、层次化存储结构算法和流算法等新内容，大量使用概率分析和随机化技术，并包含众多新颖的示例，特别是强调计算模型和计算环境，不再局限于理想化的随机存取机模型。全书内容简洁明快，并配有丰富的习题和拓展阅读资料，适合作为高等院校计算机相关专业的教材，也适合业界技术人员阅读参考。

  目录

  出版者的话
译者序
前言
致谢
*1章 模型与分析1
1.1 计算斐波那契数1
1.2 快速乘法3
1.3 计算模型3
1.4 随机算法简介4
1.4.1 另一种随机算法6
1.5 其他计算模型8
1.5.1 外部存储器模型8
1.5.2 并行模型8
拓展阅读10
习题10
*2章 概率基础与尾部不等式13
2.1 概率基础13
2.2 尾部不等式17
2.3 生成随机数20
2.3.1 生成具有任意分布的随机变量21
2.3.2 由顺序文件生成随机变量21
2.3.3 生成随机置换23
拓展阅读25
习题25
第3章 热身问题27
3.1 计算*大公因子的欧几里得算法27
3.1.1 扩展欧几里得算法27
3.1.2 在密码学中的应用28
3.2 寻找第k小的元素28
3.2.1 选择随机的划分元29
3.2.2 中位数的中位数30
3.3 词的排序32
3.4 可归并的堆34
3.4.1 归并二项堆35
3.5 一个简单的半动态词典35
3.5.1 势能法与平摊分析36
3.6 下界37
拓展阅读39
习题39
第4章 优化Ⅰ：蛮力法与贪婪策略42
4.1 启发式搜索方法42
4.1.1 博弈树44
4.2 贪婪算法的框架46
4.2.1 *大支撑树49
4.2.2 寻找*小权值子集49
4.2.3 一个调度问题50
4.3 *小支撑树算法的高效数据结构51
4.3.1 并查集的一种简单数据结构52
4.3.2 更快的方案53
4.3.3 增长*慢的函数54
4.3.4 整合55
4.3.5 仅做道路压缩56
4.4 其他不同形式的贪婪策略57
4.5 与贪婪策略的折中58
4.6 梯度下降59
4.6.1 应用63
拓展阅读65
习题66
第5章 优化Ⅱ：动态规划69
5.1 背包问题70
5.2 上下文无关文法的解析71
5.3 *长单调子序列72
5.4 函数逼近74
5.5 *大似然估计的Viterbi算法75
5.6 树中的*大权独立集76
拓展阅读76
习题77
第6章 查找80
6.1 跳表——一个简单的字典80
6.1.1 跳表的构造80
6.1.2 分析81
6.1.3 更强的尾部估计82
6.2 树堆：随机查找树83
6.3 全域哈希86
6.3.1 全域哈希函数的存在性88
6.4 *美哈希函数88
6.4.1 将期望界转换为*差情况的界89
6.5 一个复杂度为log log N的优先级队列89
拓展阅读91
习题92
第7章 多维查找与几何算法94
7.1 区间树与范围树94
7.1.1 一维范围查找94
7.1.2 二维范围查找96
7.2 k*d树97
7.3 优先级查找树99
7.4 平面凸包101
7.4.1 Jarvis March算法102
7.4.2 Graham扫描算法102
7.4.3 排序与凸包103
7.5 快速凸包算法104
7.5.1 分析105
7.5.2 期望运行时间106
7.6 使用持久化数据结构的点定位107
7.7 增量构造法109
拓展阅读111
习题111
第8章 字符串匹配与指纹函数114
8.1 Rabin*Karp指纹字符串查找算法114
8.2 KMP算法117
8.2.1 KMP算法的分析120
8.2.2 模式分析120
8.3 字典树及其应用121
拓展阅读123
习题123
第9章 快速傅里叶变换及其应用125
9.1 多项式求值与插值125
9.1.1 多项式相乘126
9.2 Cooley*Tukey算法126
9.3 蝶形网络128
9.4 Schonage*Strassen快速乘法算法129
9.5 广义字符串匹配131
9.5.1 基于卷积的方法131
拓展阅读133
习题133
*10章 图算法135
10.1 深度优先搜索135
10.2 深度优先搜索的应用138
10.2.1 强连通分支138
10.2.2 双连通分支140
10.3 道路问题142
10.3.1 Bellman*Ford单源*短道路算法143
10.3.2 Dijkstra单源*短道路算法143
10.3.3 任意两点之间的*短道路算法145
10.4 计算赋权图中的支撑子145
10.5 全局*小割148
10.5.1 收缩算法149
10.5.2 *小割的概率149
拓展阅读150
习题151
*11章 *大流及其应用153
11.1 *大流的性质与算法155
11.1.1 *大流与*小割155
11.1.2 Ford*Fulkerson算法156
11.1.3 Edmond*Karp可增广道路策略157
11.1.4 单调性引理及迭代次数的界158
11.2 *大流的应用159
11.2.1 边不相交的道路159
11.2.2 二部图的匹配159
11.2.3 环流问题162
11.2.4 项目规划164
拓展阅读165
习题165
*12章 NP完全性与近似算法168
12.1 分类与可归约性170
12.2 Cook*Levin定理172
12.3 常见的NP完全问题173
12.4 NP完全性的证明175
12.4.1 顶点覆盖及相关问题175
12.4.2 图的3着色问题176
12.4.3 背包问题及相关问题177
12.5 其他重要的复杂度类179
12.6 使用近似算法处理困难性181
12.6.1 *大背包问题182
12.6.2 *小集合覆盖183
12.6.3 几何旅行商问题184
12.6.4 3着色问题185
12.6.5 *大割问题185
拓展阅读186
习题186
*13章 降维188
13.1 随机投影与Johnson*Lindenstrauss引理188
13.2 高斯消元法191
13.3 奇异值分解及其应用192
13.3.1 矩阵代数与SVD定理192
13.3.2 使用SVD的低秩近似194
13.3.3 低秩近似的应用196
13.3.4 聚类问题197
13.3.5 SVD定理的证明199
拓展阅读200
习题200
*14章 并行算法201
14.1 并行计算模型201
14.2 排序和比较问题202
14.2.1 寻找*大值202
14.2.2 排序204
14.3 并行前缀208
14.4 基本的图算法212
14.4.1 列表排名212
14.4.2 连通分支214
14.5 基本的几何算法216
14.6 并行模型之间的关系217
14.6.1 网格上的路由218
拓展阅读220
习题220
*15章 层次化存储结构及高速缓存223
15.1 层次化存储模型223
15.2 矩阵转置224
15.2.1 矩阵乘法225
15.3 在外部存储器中进行排序226
15.3.1 我们可以改进这个算法吗227
15.4 高速缓存参数无关的算法设计228
15.4.1 参数无关的矩阵转置229
拓展阅读231
习题232
*16章 流数据模型233
16.1 引言233
16.2 查找流中的频繁元素233
16.3 流中的相异元素236
16.4 频数矩问题及其应用238
16.4.1 均值的中位数241
16.4.2 二阶频数矩的特例241
16.5 流模型下界的证明243
拓展阅读244
习题245
附录A 递推关系与生成函数247
参考文献253