《算法設計（英文版）》是2020年4月人民郵電出版社出版的圖書，作者是[美]喬恩·克萊因伯格（Jon Kleinberg）、伊娃·塔多斯（éva Tardos）。
基本介紹
- 書名：算法設計（英文版）
- 作者：[美]喬恩·克萊因伯格（Jon Kleinberg）、伊娃·塔多斯（éva Tardos）
- 出版社：人民郵電出版社
- 出版時間：2020年4月
- 頁數：814 頁
- 定價：138 元
- 開本：16 開
- 裝幀：平裝
- ISBN：9787115495921
內容簡介,圖書目錄,
內容簡介
這是一本關於算法設計和分析的教材。本書圍繞算法設計進行組織，對每種算法技術選擇了多個典型範例進行分析，把算法的理論跟實際存在的問題結合起來，具有很大的啟發性。本書側重算法設計思路，不再贅述算法複雜度的分析，每章都從實際問題出發，經過深入的具體分析引出相應的算法的設計思想，並對算法的正確性和複雜性進行合理的分析和論證。本書覆蓋面很寬，且含有200多道精彩的習題，還擴展了PSPACE問題、參數複雜性等內容。
圖書目錄
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
