算法设计 | PDF下载|ePub下载
类别: 计算机
作者:[美] Gayle Laakmann McDowell
出版社: 人民邮电出版社
原作名: Cracking the coding interview:150 programming questions and solutions,fifth edition
译者:李琳骁/漆犇
出版年: 2013-11
页数: 372
定价: 59.00元
装帧: 平装
ISBN: 9787115332912
出版社: 人民邮电出版社
原作名: Cracking the coding interview:150 programming questions and solutions,fifth edition
译者:李琳骁/漆犇
出版年: 2013-11
页数: 372
定价: 59.00元
装帧: 平装
ISBN: 9787115332912
内容简介 · · · · · ·
这是一本关于算法设计和分析的经典教材。本书围绕算法设计进行组织，对每种算法技术用多个典型范例进行分析，把算法的理论跟实际问题结合起来，具有很大的启发性。本书侧重算法设计思路，每章都从实际问题出发，经过深入具体的分析引出相应算法的设计思想，并对算法的正确性和复杂性进行合理的分析和论证。本书覆盖面广，且含有200多道精彩的习题，最后还扩展了PSPACE问题、参数复杂性等内容。
作者简介 · · · · · ·
Jon Kleinberg，康奈尔大学计算机科学教授。于1996年从麻省理工学院获得博士学位。荣获过美国国家科学基金会事业奖、海军研究局青年研究员奖、IBM杰出创新奖和美国国家科学院创新研究奖等众多奖项。其研究集中在算法上，特别是与网络结构和信息相关的算法，以及这些算法在信息科学、优化、数据挖掘以及计算生物学等方面的应用。
Éva Tardos，康奈尔大学计算机科学教授。美国艺术与科学学院院士、ACM会士。荣获过美国国家科学基金会总统青年研究员奖和富尔克森奖等众多奖项。其研究主要集中在图和网络问题的算法设计和分析上，因在网络流算法和网络问题的近似算法方面的工作而闻名。她最近的工作重点是算法博弈论。
目录 · · · · · ·
第1章 引言：一些典型问题 1
1.1 第一个问题：稳定匹配 1
1.2 5个典型问题 8
带解答的练习 12
练习 14
注释和进一步阅读 17
第2章 算法分析基础 18
2.1 计算可解性 18
2.2 增长的渐近阶 21
2.3 用列表和数组实现稳定匹配算法 26
2.4 常见运行时间综述 29
2.5 更复杂的数据结构：优先队列 35
带解答的练习 40
练习 41
注释和进一步阅读 44
第3章 图 45
3.1 基本定义和应用 45
3.2 图连通性和图遍历 48
3.3 用队列和栈实现图遍历 53
3.4 二分性测试：广度优先搜索的应用 58
3.5 有向图中的连通性 59
3.6 有向无环图和拓扑排序 61
带解答的练习 64
练习 66
注释和进一步阅读 69
第4章 贪心算法 70
4.1 区间调度：贪心算法保持领先 70
4.2 最小化延迟的调度：交换论证 76
4.3 最优缓存：更复杂的交换论证 80
4.4 图的最短路径 83
4.5 最小生成树问题 87
4.6 实现Kruskal算法：Union-Find数据结构 92
4.7 聚类 97
4.8 哈夫曼码和数据压缩 99
*4.9 最小开销树形图：多阶段贪心算法 109
带解答的练习 113
练习 116
注释和进一步阅读 125
第5章 分治 127
5.1 第一个递推式：归并排序算法 127
5.2 进一步的递推关系 130
5.3 计数逆序 134
5.4 寻找最近点对 137
5.5 整数乘法 141
5.6 卷积和快速傅里叶变换 142
带解答的练习 148
练习 150
注释和进一步阅读 152
第6章 动态规划 153
6.1 加权区间调度：递归过程 153
6.2 动态规划原理：备忘录或子问题迭代 157
6.3 分段最小二乘：多重选择 159
6.4 子集和与背包：加一个变量 162
6.5 RNA二级结构：区间上的动态规划 166
6.6 序列比对 169
6.7 通过分治在线性空间中序列比对 173
6.8 图中的最短路径 177
6.9 最短路径和距离向量协议 182
*6.10 图中的负环 184
带解答的练习 187
练习 190
注释和进一步阅读 204
第7章 网络流 205
7.1 最大流问题和Ford-Fulkerson算法 205
7.2 网络中的最大流和最小割 211
7.3 选择好的增广路径 214
*7.4 预流推进最大流算法 218
7.5 第一个应用：二分匹配问题 225
7.6 有向图和无向图中的不相交路径 228
7.7 最大流问题的扩展 232
7.8 调查设计 236
7.9 航空公司调度 237
7.10 图像分割 240
7.11 项目选择 243
7.12 棒球排除 246
*7.13 进一步的方向：为匹配问题增加开销 249
带解答的练习 253
练习 255
注释和进一步阅读 274
第8章 NP和计算难解性 276
8.1 多项式时间归约 276
8.2 通过“小配件”归约：可满足性问题 280
8.3 有效证书和NP的定义 283
8.4 NP完全问题 285
8.5 排序问题 289
8.6 划分问题 294
8.7 图着色 297
8.8 数值问题 300
8.9 co-NP和NP的不对称性 303
8.10 困难问题的部分分类 305
带解答的练习 307
练习 309
注释和进一步阅读 323
第9章 PSPACE：NP之外的一类问题 324
9.1 PSPACE 324
9.2 PSPACE中的一些难题 325
9.3 在多项式空间中求解量化问题和博弈 327
9.4 在多项式空间中求解规划问题 328
9.5 证明问题是PSPACE完全的 331
带解答的练习 334
练习 335
注释和进一步阅读 336
第10章 扩展易解性的界限 337
10.1 寻找小的顶点覆盖 338
10.2 求解树上的NP困难问题 340
10.3 圆弧集着色 343
*10.4 图的树分解 349
*10.5 构造树分解 356
带解答的练习 361
练习 363
注释和进一步阅读 365
第11章 近似算法 366
11.1 贪心算法和最优值的界限：负载均衡问题 366
11.2 中心选址问题 370
11.3 集合覆盖：一般贪心启发式 374
11.4 定价方法：顶点覆盖 378
11.5 用定价方法最大化：不相交路径问题 382
11.6 线性规划和舍入：顶点覆盖的应用 386
*11.7 再论负载均衡：更高级的LP应用 390
11.8 任意好的近似：背包问题 394
带解答的练习 398
练习 399
注释和进一步阅读 404
第12章 局部搜索 406
12.1 优化问题的地形 406
12.2 Metropolis算法和模拟退火算法 409
12.3 局部搜索在Hopfield神经网络中的应用 412
12.4 通过局部搜索的最大割近似 415
12.5 选择邻居关系 417
*12.6 用局部搜索分类 418
12.7 最优响应动态和纳什均衡 423
带解答的练习 430
练习 431
注释和进一步阅读 433
第13章 随机算法 434
13.1 第一个应用：消除争用 435
13.2 寻找全局最小割 438
13.3 随机变量及其期望 442
13.4 MAX 3-SAT的随机近似算法 445
13.5 随机分治：找中位数和Quicksort 447
13.6 哈希：字典的随机实现 452
13.7 寻找最近点对：随机方法 457
13.8 随机缓存 462
13.9 切尔诺夫界 467
13.10 负载均衡 468
13.11 分组路由 470
13.12 背景知识：一些基本概率定义 474
带解答的练习 479
练习 483
注释和进一步阅读 489
后记：永远运行的算法 491
参考文献 497
· · · · · ·
1.1 第一个问题：稳定匹配 1
1.2 5个典型问题 8
带解答的练习 12
练习 14
注释和进一步阅读 17
第2章 算法分析基础 18
2.1 计算可解性 18
2.2 增长的渐近阶 21
2.3 用列表和数组实现稳定匹配算法 26
2.4 常见运行时间综述 29
2.5 更复杂的数据结构：优先队列 35
带解答的练习 40
练习 41
注释和进一步阅读 44
第3章 图 45
3.1 基本定义和应用 45
3.2 图连通性和图遍历 48
3.3 用队列和栈实现图遍历 53
3.4 二分性测试：广度优先搜索的应用 58
3.5 有向图中的连通性 59
3.6 有向无环图和拓扑排序 61
带解答的练习 64
练习 66
注释和进一步阅读 69
第4章 贪心算法 70
4.1 区间调度：贪心算法保持领先 70
4.2 最小化延迟的调度：交换论证 76
4.3 最优缓存：更复杂的交换论证 80
4.4 图的最短路径 83
4.5 最小生成树问题 87
4.6 实现Kruskal算法：Union-Find数据结构 92
4.7 聚类 97
4.8 哈夫曼码和数据压缩 99
*4.9 最小开销树形图：多阶段贪心算法 109
带解答的练习 113
练习 116
注释和进一步阅读 125
第5章 分治 127
5.1 第一个递推式：归并排序算法 127
5.2 进一步的递推关系 130
5.3 计数逆序 134
5.4 寻找最近点对 137
5.5 整数乘法 141
5.6 卷积和快速傅里叶变换 142
带解答的练习 148
练习 150
注释和进一步阅读 152
第6章 动态规划 153
6.1 加权区间调度：递归过程 153
6.2 动态规划原理：备忘录或子问题迭代 157
6.3 分段最小二乘：多重选择 159
6.4 子集和与背包：加一个变量 162
6.5 RNA二级结构：区间上的动态规划 166
6.6 序列比对 169
6.7 通过分治在线性空间中序列比对 173
6.8 图中的最短路径 177
6.9 最短路径和距离向量协议 182
*6.10 图中的负环 184
带解答的练习 187
练习 190
注释和进一步阅读 204
第7章 网络流 205
7.1 最大流问题和Ford-Fulkerson算法 205
7.2 网络中的最大流和最小割 211
7.3 选择好的增广路径 214
*7.4 预流推进最大流算法 218
7.5 第一个应用：二分匹配问题 225
7.6 有向图和无向图中的不相交路径 228
7.7 最大流问题的扩展 232
7.8 调查设计 236
7.9 航空公司调度 237
7.10 图像分割 240
7.11 项目选择 243
7.12 棒球排除 246
*7.13 进一步的方向：为匹配问题增加开销 249
带解答的练习 253
练习 255
注释和进一步阅读 274
第8章 NP和计算难解性 276
8.1 多项式时间归约 276
8.2 通过“小配件”归约：可满足性问题 280
8.3 有效证书和NP的定义 283
8.4 NP完全问题 285
8.5 排序问题 289
8.6 划分问题 294
8.7 图着色 297
8.8 数值问题 300
8.9 co-NP和NP的不对称性 303
8.10 困难问题的部分分类 305
带解答的练习 307
练习 309
注释和进一步阅读 323
第9章 PSPACE：NP之外的一类问题 324
9.1 PSPACE 324
9.2 PSPACE中的一些难题 325
9.3 在多项式空间中求解量化问题和博弈 327
9.4 在多项式空间中求解规划问题 328
9.5 证明问题是PSPACE完全的 331
带解答的练习 334
练习 335
注释和进一步阅读 336
第10章 扩展易解性的界限 337
10.1 寻找小的顶点覆盖 338
10.2 求解树上的NP困难问题 340
10.3 圆弧集着色 343
*10.4 图的树分解 349
*10.5 构造树分解 356
带解答的练习 361
练习 363
注释和进一步阅读 365
第11章 近似算法 366
11.1 贪心算法和最优值的界限：负载均衡问题 366
11.2 中心选址问题 370
11.3 集合覆盖：一般贪心启发式 374
11.4 定价方法：顶点覆盖 378
11.5 用定价方法最大化：不相交路径问题 382
11.6 线性规划和舍入：顶点覆盖的应用 386
*11.7 再论负载均衡：更高级的LP应用 390
11.8 任意好的近似：背包问题 394
带解答的练习 398
练习 399
注释和进一步阅读 404
第12章 局部搜索 406
12.1 优化问题的地形 406
12.2 Metropolis算法和模拟退火算法 409
12.3 局部搜索在Hopfield神经网络中的应用 412
12.4 通过局部搜索的最大割近似 415
12.5 选择邻居关系 417
*12.6 用局部搜索分类 418
12.7 最优响应动态和纳什均衡 423
带解答的练习 430
练习 431
注释和进一步阅读 433
第13章 随机算法 434
13.1 第一个应用：消除争用 435
13.2 寻找全局最小割 438
13.3 随机变量及其期望 442
13.4 MAX 3-SAT的随机近似算法 445
13.5 随机分治：找中位数和Quicksort 447
13.6 哈希：字典的随机实现 452
13.7 寻找最近点对：随机方法 457
13.8 随机缓存 462
13.9 切尔诺夫界 467
13.10 负载均衡 468
13.11 分组路由 470
13.12 背景知识：一些基本概率定义 474
带解答的练习 479
练习 483
注释和进一步阅读 489
后记：永远运行的算法 491
参考文献 497
· · · · · ·
发表回复
要发表评论，您必须先登录。