书籍详情
算法设计 英文版
作者：[美] 乔恩·克莱因伯格（Jon Kleinberg） 著
出版社：人民邮电出版社
出版时间：2019-05-01
ISBN：9787115495921
定价：¥138.00
购买这本书可以去
内容简介
这是一本关于算法设计和分析的教材。本书围绕算法设计进行组织，对每种算法技术选择了多个典型范例进行分析，把算法的理论跟实际存在的问题结合起来，具有很大的启发性。本书侧重算法设计思路，不再赘述算法复杂度的分析，每章都从实际问题出发，经过深入的具体分析引出相应的算法的设计思想，并对算法的正确性和复杂性进行合理的分析和论证。本书覆盖面很宽，且含有200多道精彩的习题，还扩展了PSPACE问题、参数复杂性等内容。
作者简介
Jon Kleinberg是美国国家科学院（NAS）、美国国家工程院（NAE）、美国人文与科学院（AAAS）三料院士。在计算机科学领域是“传说级”的人物，而且还获得过国际数学家大会颁发“奈望林纳奖”，该奖是数学家大会为了表彰信息科学方面的重要数学贡献而设的。
目录
目录
1 Introduction： Some Representative Problems / 引言：某些有代表性的问题 1
1．1 A First Problem： Stable Matching / 第 一个问题：稳定匹配 1
1．2 Five Representative Problems / 五个有代表性的问题 12
Solved Exercises / 带解答的练习 19
Exercises / 练习 22
Notes and Further Reading / 注释和进一步阅读 28
2 Basics of Algorithm Analysis / 算法分析基础 29
2．1 Computational Tractability / 计算可解性 29
2．2 Asymptotic Order of Growth / 增长的渐近阶 35
2．3 Implementing the Stable Matching Algorithm Using Lists and Arrays / 用列表和数组实现稳定匹配算法42
2．4 A Survey of Common Running Times / 常用运行时间概述 47
2．5 A More Complex Data Structure： Priority Queues / 更复杂的数据结构：优先队列 57
Solved Exercises / 带解答的练习 65
Exercises / 练习 67
Notes and Further Reading / 注释和进一步阅读 70
3 Graphs / 图 73
3．1 Basic Definitions and Applications / 基本定义与应用 73
3．2 Graph Connectivity and Graph Traversal / 图的连通性与图的遍历 78
3．3 Implementing Graph Traversal Using Queues and Stacks / 用优先队列与栈实现图的遍历 87
3．4 Testing Bipartiteness： An Application of Breadth-First Search / 二分性测试：宽度优先搜索的应用 94
3．5 Connectivity in Directed Graphs / 有向图中的连通性 97
3．6 Directed Acyclic Graphs and Topological Ordering / 有向无环图与拓扑排序 99
Solved Exercises / 带解答的练习 104
Exercises / 练习 107
Notes and Further Reading / 注释和进一步阅读 112
4 Greedy Algorithms / 贪心算法 115
4．1 Interval Scheduling： The Greedy Algorithm Stays Ahead / 区间调度：贪心算法领先 116
4．2 Scheduling to Minimize Lateness： An Exchange Argument / 最小延迟调度：交换论证 125
4．3 Optimal Caching： A More Complex Exchange Argument / 最优高速缓存：更复杂的交换论证131
4．4 Shortest Paths in a Graph / 图的最短路径 137
4．5 The Minimum Spanning Tree Problem / 最小生成树问题 142
4．6 Implementing Kruskal’s Algorithm： The Union-Find Data Structure / 实现Kruskal算法：Union-Find数据结构 151
4．7 Clustering / 聚类 157
4．8 Huffman Codes and Data Compression / 赫夫曼码与数据压缩 161
4．9 Minimum-Cost Arborescences： A Multi-Phase Greedy Algorithm / 最小费用有向树：多阶段贪心算法 177
Solved Exercises / 带解答的练习 183
Exercises / 练习 188
Notes and Further Reading / 注释和进一步阅读 205
5 Divide and Conquer / 分治策略 209
5．1 A First Recurrence： The Mergesort Algorithm / 第 一个递推式：归并排序算法 210
5．2 Further Recurrence Relations / 更多的递推关系 214
5．3 Counting Inversions / 计数逆序 221
5．4 Finding the Closest Pair of Points / 找最接邻近的点对 225
5．5 Integer Multiplication / 整数乘法 231
5．6 Convolutions and the Fast Fourier Transform / 卷积与快速傅里叶变换 234
Solved Exercises / 带解答的练习 242
Exercises / 练习 246
Notes and Further Reading / 注释和进一步阅读 249
6 Dynamic Programming / 动态规划 251
6．1 Weighted Interval Scheduling： A Recursive Procedure / 带权的区间调度：递归过程 252
6．2 Principles of Dynamic Programming： Memoization or Iteration over Subproblems / 动态规划原理：备忘录或者子问题迭代 258
6．3 Segmented Least Squares： Multi-way Choices / 分段的最小二乘：多重选择 261
6．4 Subset Sums and Knapsacks： Adding a Variable / 子集和与背包：加一个变量 266
6．5 RNA Secondary Structure： Dynamic Programming over Intervals / RNA二级结构：在区间上的动态规划 272
6．6 Sequence Alignment / 序列比对 278
6．7 Sequence Alignment in Linear Space via Divide and Conquer / 通过分治策略在线性空间的序列比对 284
6．8 Shortest Paths in a Graph / 图中的最短路径 290
6．9 Shortest Paths and Distance Vector Protocols / 最短路径和距离向量协议 297
6．10 Negative Cycles in a Graph / 图中的负圈 301
Solved Exercises / 带解答的练习 307
Exercises / 练习 312
Notes and Further Reading / 注释和进一步阅读 335
7 Network Flow / 网络流 337
7．1 The Maximum-Flow Problem and the Ford-Fulkerson Algorithm / 最大流问题与Ford-Fulkerson算法 338
7．2 Maximum Flows and Minimum Cuts in a Network / 网络中的最大流与最小割 346
7．3 Choosing Good Augmenting Paths / 选择好的增广路径352
7．4 The Preflow-Push Maximum-Flow Algorithm / 前向流推动最大流算法 357
7．5 A First Application： The Bipartite Matching Problem / 第 一个应用：二分匹配问题 367
7．6 Disjoint Paths in Directed and Undirected Graphs / 有向与无向图中的不交路径 373
7．7 Extensions to the Maximum-Flow Problem / 对最大流问题的推广 378
7．8 Survey Design / 调查设计384
7．9 Airline Scheduling / 航线调度 387
7．10 Image Segmentation / 图像分割 391
7．11 Project Selection / 项目选择 396
7．12 Baseball Elimination / 棒球排除 400
7．13 A Further Direction： Adding Costs to the Matching Problem / 进一步的方向：对匹配问题增加费用 404
Solved Exercises / 带解答的练习 411
Exercises / 练习 415
Notes and Further Reading / 注释和进一步阅读 448
8 NP and Computational Intractability / NP与计算的难解性 451
8．1 Polynomial-Time Reductions / 多项式时间归约 452
8．2 Reductions via “Gadgets”： The Satisfiability Problem / 使用“零件”的归约：可满足性问题 459
8．3 Efficient Certification and the Definition of NP / 有效证书和NP的定义 463
8．4 NP-Complete Problems / NP完全问题 466
8．5 Sequencing Problems / 排序问题 473
8．6 Partitioning Problems / 划分问题 481
8．7 Graph Coloring / 图着色 485
8．8 Numerical Problems / 数值问题 490
8．9 Co-NP and the Asymmetry of NP / Co-NP及NP的不对称性 495
8．10 A Partial Taxonomy of Hard Problems / 难问题的部分分类 497
Solved Exercises / 带解答的练习 500
Exercises / 练习 505
Notes and Further Reading / 注释和进一步阅读 529
9 PSPACE： A Class of Problems beyond NP / PSPACE：一类超出NP的问题 531
9．1 PSPACE / PSPACE 531
9．2 Some Hard Problems in PSPACE / PSPACE中的难问题 533
9．3 Solving Quantified Problems and Games in Polynomial Space / 在多项式空间中解量化问题和博弈问题 536
9．4 Solving the Planning Problem in Polynomial Space / 在多项式空间内求解规划问题 538
9．5 Proving Problems PSPACE-Complete / 证明问题是PSPACE完全的 543
Solved Exercises / 带解答的练习 547
Exercises / 练习 550
Notes and Further Reading / 注释和进一步阅读 551
10 Extending the Limits of Tractability / 扩展易解性的界限 553
10．1 Finding Small Vertex Covers / 找小的顶点覆盖 554
10．2 Solving NP-Hard Problems on Trees / 在树上解NP难问题 558
10．3 Coloring a Set of Circular Arcs / 圆弧集着色 563
10．4 Tree Decompositions of Graphs / 图的树分解 572
10．5 Constructing a Tree Decomposition / 构造树分解 584
Solved Exercises / 带解答的练习 591
Exercises / 练习 594
Notes and Further Reading / 注释和进一步阅读 598
11 Approximation Algorithms / 近似算法 599
11．1 Greedy Algorithms and Bounds on the Optimum： A Load Balancing Problem / 贪心算法与最优值的界限：负载均衡问题 600
11．2 The Center Selection Problem / 中心选址问题 606
11．3 Set Cover： A General Greedy Heuristic / 集合覆盖：一般的贪心启发式方法 612
11．4 The Pricing Method： Vertex Cover / 定价法：顶点覆盖 618
11．5 Maximization via the Pricing Method： The Disjoint Paths Problem / 用定价法最大化：不交路径问题 624
11．6 Linear Programming and Rounding： An Application to Vertex Cover / 线性规划与舍入：对顶点覆盖的应用 630
11．7 Load Balancing Revisited： A More Advanced LP Application / 再论负载均衡：更高级的LP应用 637
11．8 Arbitrarily Good Approximations： The Knapsack Problem / 任意好的近似：背包问题 644
Solved Exercises / 带解答的练习 649
Exercises / 练习 651
Notes and Further Reading / 注释和进一步阅读 659
12 Local Search / 局部搜索 661
12．1 The Landscape of an Optimization Problem / 最优化问题的地形图 662
12．2 The Metropolis Algorithm and Simulated Annealing / Metropolis算法与模拟退火算法 666
12．3 An Application of Local Search to Hopfield Neural Networks / 局部搜索在Hopfield神经网络中的应用 671
12．4 Maximum-Cut Approximation via Local Search / 局部搜索对最大割近似的应用 676
12．5 Choosing a Neighbor Relation / 选择邻居关系 679
12．6 Classification via Local Search / 用局部搜索分类 681
12．7 Best-Response Dynamics and Nash Equilibria / 最佳响应动态过程与纳什均衡 690
Solved Exercises / 带解答的练习 700
Exercises / 练习 702
Notes and Further Reading / 注释和进一步阅读 705
13 Randomized Algorithms / 随机算法 707
13．1 A First Application： Contention Resolution / 第 一个应用：消除争用 708
13．2 Finding the Global Minimum Cut / 求完全最小割 714
13．3 Random Variables and Their Expectations / 随机变量及其期望 719
13．4 A Randomized Approximation Algorithm for MAX 3-SAT / 关于MAX 3-SAT的随机近似算法 724
13．5 Randomized Divide and Conquer： Median-Finding and Quicksort / 随机分治策略：求中位数与快速排序 727
13．6 Hashing： A Randomized Implementation of Dictionaries / 散列法：字典的随机实现 734
13．7 Finding the Closest Pair of Points： A Randomized Approach / 求最邻近点对：随机方法 741
13．8 Randomized Caching / 随机超高速缓存 750
13．9 Chernoff Bounds / 切尔诺夫界 758
13．10 Load Balancing / 负载均衡 760
13．11 Packet Routing / 包路由选择 762
13．12 Background： Some Basic Probability Definitions / 背景：某些基本概率定义 769
Solved Exercises / 带解答的练习 776
Exercises / 练习 782
Notes and Further Reading / 注释和进一步阅读 793
Epilogue： Algorithms That Run Forever / 后记：永不停止运行的算法 795
References / 参考文献 805
1 Introduction： Some Representative Problems / 引言：某些有代表性的问题 1
1．1 A First Problem： Stable Matching / 第 一个问题：稳定匹配 1
1．2 Five Representative Problems / 五个有代表性的问题 12
Solved Exercises / 带解答的练习 19
Exercises / 练习 22
Notes and Further Reading / 注释和进一步阅读 28
2 Basics of Algorithm Analysis / 算法分析基础 29
2．1 Computational Tractability / 计算可解性 29
2．2 Asymptotic Order of Growth / 增长的渐近阶 35
2．3 Implementing the Stable Matching Algorithm Using Lists and Arrays / 用列表和数组实现稳定匹配算法42
2．4 A Survey of Common Running Times / 常用运行时间概述 47
2．5 A More Complex Data Structure： Priority Queues / 更复杂的数据结构：优先队列 57
Solved Exercises / 带解答的练习 65
Exercises / 练习 67
Notes and Further Reading / 注释和进一步阅读 70
3 Graphs / 图 73
3．1 Basic Definitions and Applications / 基本定义与应用 73
3．2 Graph Connectivity and Graph Traversal / 图的连通性与图的遍历 78
3．3 Implementing Graph Traversal Using Queues and Stacks / 用优先队列与栈实现图的遍历 87
3．4 Testing Bipartiteness： An Application of Breadth-First Search / 二分性测试：宽度优先搜索的应用 94
3．5 Connectivity in Directed Graphs / 有向图中的连通性 97
3．6 Directed Acyclic Graphs and Topological Ordering / 有向无环图与拓扑排序 99
Solved Exercises / 带解答的练习 104
Exercises / 练习 107
Notes and Further Reading / 注释和进一步阅读 112
4 Greedy Algorithms / 贪心算法 115
4．1 Interval Scheduling： The Greedy Algorithm Stays Ahead / 区间调度：贪心算法领先 116
4．2 Scheduling to Minimize Lateness： An Exchange Argument / 最小延迟调度：交换论证 125
4．3 Optimal Caching： A More Complex Exchange Argument / 最优高速缓存：更复杂的交换论证131
4．4 Shortest Paths in a Graph / 图的最短路径 137
4．5 The Minimum Spanning Tree Problem / 最小生成树问题 142
4．6 Implementing Kruskal’s Algorithm： The Union-Find Data Structure / 实现Kruskal算法：Union-Find数据结构 151
4．7 Clustering / 聚类 157
4．8 Huffman Codes and Data Compression / 赫夫曼码与数据压缩 161
4．9 Minimum-Cost Arborescences： A Multi-Phase Greedy Algorithm / 最小费用有向树：多阶段贪心算法 177
Solved Exercises / 带解答的练习 183
Exercises / 练习 188
Notes and Further Reading / 注释和进一步阅读 205
5 Divide and Conquer / 分治策略 209
5．1 A First Recurrence： The Mergesort Algorithm / 第 一个递推式：归并排序算法 210
5．2 Further Recurrence Relations / 更多的递推关系 214
5．3 Counting Inversions / 计数逆序 221
5．4 Finding the Closest Pair of Points / 找最接邻近的点对 225
5．5 Integer Multiplication / 整数乘法 231
5．6 Convolutions and the Fast Fourier Transform / 卷积与快速傅里叶变换 234
Solved Exercises / 带解答的练习 242
Exercises / 练习 246
Notes and Further Reading / 注释和进一步阅读 249
6 Dynamic Programming / 动态规划 251
6．1 Weighted Interval Scheduling： A Recursive Procedure / 带权的区间调度：递归过程 252
6．2 Principles of Dynamic Programming： Memoization or Iteration over Subproblems / 动态规划原理：备忘录或者子问题迭代 258
6．3 Segmented Least Squares： Multi-way Choices / 分段的最小二乘：多重选择 261
6．4 Subset Sums and Knapsacks： Adding a Variable / 子集和与背包：加一个变量 266
6．5 RNA Secondary Structure： Dynamic Programming over Intervals / RNA二级结构：在区间上的动态规划 272
6．6 Sequence Alignment / 序列比对 278
6．7 Sequence Alignment in Linear Space via Divide and Conquer / 通过分治策略在线性空间的序列比对 284
6．8 Shortest Paths in a Graph / 图中的最短路径 290
6．9 Shortest Paths and Distance Vector Protocols / 最短路径和距离向量协议 297
6．10 Negative Cycles in a Graph / 图中的负圈 301
Solved Exercises / 带解答的练习 307
Exercises / 练习 312
Notes and Further Reading / 注释和进一步阅读 335
7 Network Flow / 网络流 337
7．1 The Maximum-Flow Problem and the Ford-Fulkerson Algorithm / 最大流问题与Ford-Fulkerson算法 338
7．2 Maximum Flows and Minimum Cuts in a Network / 网络中的最大流与最小割 346
7．3 Choosing Good Augmenting Paths / 选择好的增广路径352
7．4 The Preflow-Push Maximum-Flow Algorithm / 前向流推动最大流算法 357
7．5 A First Application： The Bipartite Matching Problem / 第 一个应用：二分匹配问题 367
7．6 Disjoint Paths in Directed and Undirected Graphs / 有向与无向图中的不交路径 373
7．7 Extensions to the Maximum-Flow Problem / 对最大流问题的推广 378
7．8 Survey Design / 调查设计384
7．9 Airline Scheduling / 航线调度 387
7．10 Image Segmentation / 图像分割 391
7．11 Project Selection / 项目选择 396
7．12 Baseball Elimination / 棒球排除 400
7．13 A Further Direction： Adding Costs to the Matching Problem / 进一步的方向：对匹配问题增加费用 404
Solved Exercises / 带解答的练习 411
Exercises / 练习 415
Notes and Further Reading / 注释和进一步阅读 448
8 NP and Computational Intractability / NP与计算的难解性 451
8．1 Polynomial-Time Reductions / 多项式时间归约 452
8．2 Reductions via “Gadgets”： The Satisfiability Problem / 使用“零件”的归约：可满足性问题 459
8．3 Efficient Certification and the Definition of NP / 有效证书和NP的定义 463
8．4 NP-Complete Problems / NP完全问题 466
8．5 Sequencing Problems / 排序问题 473
8．6 Partitioning Problems / 划分问题 481
8．7 Graph Coloring / 图着色 485
8．8 Numerical Problems / 数值问题 490
8．9 Co-NP and the Asymmetry of NP / Co-NP及NP的不对称性 495
8．10 A Partial Taxonomy of Hard Problems / 难问题的部分分类 497
Solved Exercises / 带解答的练习 500
Exercises / 练习 505
Notes and Further Reading / 注释和进一步阅读 529
9 PSPACE： A Class of Problems beyond NP / PSPACE：一类超出NP的问题 531
9．1 PSPACE / PSPACE 531
9．2 Some Hard Problems in PSPACE / PSPACE中的难问题 533
9．3 Solving Quantified Problems and Games in Polynomial Space / 在多项式空间中解量化问题和博弈问题 536
9．4 Solving the Planning Problem in Polynomial Space / 在多项式空间内求解规划问题 538
9．5 Proving Problems PSPACE-Complete / 证明问题是PSPACE完全的 543
Solved Exercises / 带解答的练习 547
Exercises / 练习 550
Notes and Further Reading / 注释和进一步阅读 551
10 Extending the Limits of Tractability / 扩展易解性的界限 553
10．1 Finding Small Vertex Covers / 找小的顶点覆盖 554
10．2 Solving NP-Hard Problems on Trees / 在树上解NP难问题 558
10．3 Coloring a Set of Circular Arcs / 圆弧集着色 563
10．4 Tree Decompositions of Graphs / 图的树分解 572
10．5 Constructing a Tree Decomposition / 构造树分解 584
Solved Exercises / 带解答的练习 591
Exercises / 练习 594
Notes and Further Reading / 注释和进一步阅读 598
11 Approximation Algorithms / 近似算法 599
11．1 Greedy Algorithms and Bounds on the Optimum： A Load Balancing Problem / 贪心算法与最优值的界限：负载均衡问题 600
11．2 The Center Selection Problem / 中心选址问题 606
11．3 Set Cover： A General Greedy Heuristic / 集合覆盖：一般的贪心启发式方法 612
11．4 The Pricing Method： Vertex Cover / 定价法：顶点覆盖 618
11．5 Maximization via the Pricing Method： The Disjoint Paths Problem / 用定价法最大化：不交路径问题 624
11．6 Linear Programming and Rounding： An Application to Vertex Cover / 线性规划与舍入：对顶点覆盖的应用 630
11．7 Load Balancing Revisited： A More Advanced LP Application / 再论负载均衡：更高级的LP应用 637
11．8 Arbitrarily Good Approximations： The Knapsack Problem / 任意好的近似：背包问题 644
Solved Exercises / 带解答的练习 649
Exercises / 练习 651
Notes and Further Reading / 注释和进一步阅读 659
12 Local Search / 局部搜索 661
12．1 The Landscape of an Optimization Problem / 最优化问题的地形图 662
12．2 The Metropolis Algorithm and Simulated Annealing / Metropolis算法与模拟退火算法 666
12．3 An Application of Local Search to Hopfield Neural Networks / 局部搜索在Hopfield神经网络中的应用 671
12．4 Maximum-Cut Approximation via Local Search / 局部搜索对最大割近似的应用 676
12．5 Choosing a Neighbor Relation / 选择邻居关系 679
12．6 Classification via Local Search / 用局部搜索分类 681
12．7 Best-Response Dynamics and Nash Equilibria / 最佳响应动态过程与纳什均衡 690
Solved Exercises / 带解答的练习 700
Exercises / 练习 702
Notes and Further Reading / 注释和进一步阅读 705
13 Randomized Algorithms / 随机算法 707
13．1 A First Application： Contention Resolution / 第 一个应用：消除争用 708
13．2 Finding the Global Minimum Cut / 求完全最小割 714
13．3 Random Variables and Their Expectations / 随机变量及其期望 719
13．4 A Randomized Approximation Algorithm for MAX 3-SAT / 关于MAX 3-SAT的随机近似算法 724
13．5 Randomized Divide and Conquer： Median-Finding and Quicksort / 随机分治策略：求中位数与快速排序 727
13．6 Hashing： A Randomized Implementation of Dictionaries / 散列法：字典的随机实现 734
13．7 Finding the Closest Pair of Points： A Randomized Approach / 求最邻近点对：随机方法 741
13．8 Randomized Caching / 随机超高速缓存 750
13．9 Chernoff Bounds / 切尔诺夫界 758
13．10 Load Balancing / 负载均衡 760
13．11 Packet Routing / 包路由选择 762
13．12 Background： Some Basic Probability Definitions / 背景：某些基本概率定义 769
Solved Exercises / 带解答的练习 776
Exercises / 练习 782
Notes and Further Reading / 注释和进一步阅读 793
Epilogue： Algorithms That Run Forever / 后记：永不停止运行的算法 795
References / 参考文献 805
猜您喜欢
