算法设计 英文版 = ALGORITHM DESIGNPDF电子书下载

1引言：一些典型问题 1

1.1第一个问题：稳定匹配 1

1.2五个典型问题 12

带解答的练习 19

练习 22

注释和进一步阅读 28

2算法分析基础 29

2.1计算可解性 29

2.2增长的渐近阶 35

2.3用列表和数组实现稳定匹配算法 42

2.4常见运行时间综述 47

2.5更复杂的数据结构：优先队列 57

带解答的练习 65

练习 67

注释和进一步阅读 70

3图 73

3.1基本定义与应用 73

3.2图连通性与图遍历 78

3.3用优先队列与栈实现图遍历 87

3.4二分性测试：广度优先搜索的应用 94

3.5有向图中的连通性 97

3.6有向无环图和拓扑排序 99

带解答的练习 104

练习 107

注释和进一步阅读 112

4贪心算法 115

4.1区间调度：贪心算法保持领先 116

4.2最小延迟的调度：交换论证 125

4.3最优缓存：更复杂的交换论证 131

4.4图的最短路径 137

4.5最小生成树问题 142

4.6实现Kruskal算法：Union-Find数据结构 151

4.7聚类 157

4.8哈夫曼码和数据压缩 161

4.9最小费用有向树：多阶段贪心算法 177

带解答的练习 183

练习 188

注释和进一步阅读 205

5分治 209

5.1第一个递推式：归并排序算法 210

5.2进一步的递推关系 214

5.3计数逆序 221

5.4寻找最近点对 225

5.5整数乘法 231

5.6卷积和快速傅里叶变换 234

带解答的练习 242

练习 246

注释和进一步阅读 249

6动态规划 251

6.1加权区间调度：递归过程 252

6.2动态规划原理：备忘录或子问题迭代 258

6.3分段最小二乘：多重选择 261

6.4子集和与背包：加一个变量 266

6.5RNA二级结构：区间上的动态规划 272

6.6序列比对 278

6.7通过分治在线性空间中的序列比对 284

6.8图中的最短路径 290

6.9最短路径和距离向量协议 297

6.10图中的负环 301

带解答的练习 307

练习 312

注释和进一步阅读 335

7网络流 337

7.1最大流问题和Ford-Fulkerson算法 338

7.2网络中的最大流和最小割 346

7.3选择好的增广路径 352

7.4预流推动最大流算法 357

7.5第一个应用：二分匹配问题 367

7.6有向图和无向图中的不相交路径 373

7.7最大流问题的推广 378

7.8调查设计 384

7.9航线调度 387

7.10图像分割 391

7.11项目选择 396

7.12棒球排除 400

7.13进一步的方向：对匹配问题增加费用 404

带解答的练习 411

练习 415

注释和进一步阅读 448

8 NP和计算难解性 451

8.1多项式时间归约 452

8.2通过“小配件”归约：可满足性问题 459

8.3有效证书和NP的定义 463

8.4NP完全问题 466

8.5排序问题 473

8.6划分问题 481

8.7图着色 485

8.8数值问题 490

8.9Co-NP和NP的不对称性 495

8.10困难问题的部分分类 497

带解答的练习 500

练习 505

注释和进一步阅读 529

9PSPACE：NP之外的一类问题 531

9.1 PSPACE 531

9.2 PSPACE中的一些难题 533

9.3在多项式空间中求解量化问题和博弈 536

9.4在多项式空间中求解规划问题 538

9.5证明问题是PSPACE完全的 543

带解答的练习 547

练习 550

注释和进一步阅读 551

10扩展易解性的界限 553

10.1寻找小的顶点覆盖 554

10.2求解树上的NP难问题 558

10.3圆弧集着色 563

10.4图的树分解 572

10.5构造树分解 584

带解答的练习 591

练习 594

注释和进一步阅读 598

11近似算法 599

11.1贪心算法和最优值的界限：负载均衡问题 600

11.2中心选址问题 606

11.3集合覆盖：一般贪心启发式 612

11.4定价方法：顶点覆盖 618

11.5用定价方法最大化：不相交路径问题 624

11.6线性规划和舍入：顶点覆盖的应用 630

11.7再论负载均衡：更高级的LP应用 637

11.8任意好的近似：背包问题 644

带解答的练习 649

练习 651

注释和进一步阅读 659

12局部搜索 661

12.1优化问题的地形 662

12.2Metropolis算法和模拟退火算法 666

12.3局部搜索在Hopfield神经网络中的应用 671

12.4通过局部搜索进行最大割近似 676

12.5选择邻居关系 679

12.6用局部搜索分类 681

12.7最佳响应动态和纳什均衡 690

带解答的练习 700

练习 702

注释和进一步阅读 705

13随机算法 707

13.1第一个应用：消除争用 708

13.2寻找全局最小割 714

13.3随机变量及其期望 719

13.4MAX 3-SAT的随机近似算法 724

13.5随机分治：找中位数和快速排序 727

13.6散列：字典的随机实现 734

13.7寻找最近点对：随机方法 741

13.8随机缓存 750

13.9切尔诺夫界 758

13.10负载均衡 760

13.11分组路由 762

13.12背景知识：一些基本概率定义 769

带解答的练习 776

练习 782

注释和进一步阅读 793

后记：永远运行的算法 795

参考文献 805