了得網計算機/網絡_算法設計英文版

編輯推薦

- 眾多名校采用的算法設計課程教材
- 用實際示例闡明枯燥的算法理論
- 更注重算法設計思路而非算法復雜度分析
本書采用新穎的方法來講算法課程，通過激發算法思想的真實世界問題，引入了算法思想。兩位作者以一種清晰、直接的方式，指導學生自己分析和定義問題，並從中找出哪些設計原則適用於給定的場景。本書鼓勵更深入地理解算法設計過程，以及算法在計算機科學的更廣闊的領域中的應用。
本書有以下幾個特色：
1.強調分析和設計方法；
2.遵循結構化教學方法，引導學生學習問題形式化、算法設計和算法分析的全過程；
3.通過一繫列帶解答的問題，展示計算機科學家設計和應用算法的過程；
4.包含200多道作業題，其中一些題目來自Yahoo！和Oracle這樣的公司；
5.提供廣泛用於處理NP困難問題和隨機應用的算法，這些是非常重要的算法主題。

內容簡介

這是一本關於算法設計和分析的教材。本書圍繞算法設計進行組織，對每種算法技術選擇了多個典型範例進行分析，把算法的理論跟實際存在的問題結合起來，具有很大的啟發性。本書側重算法設計思路，不再贅述算法復雜度的分析，每章都從實際問題出發，經過深入的具體分析引出相應的算法的設計思想，並對算法的正確性和復雜性進行合理的分析和論證。本書覆蓋面很寬，且含有200多道精彩的習題，還擴展了PSPACE問題、參數復雜性等內容。

作者簡介

Jon Kleinberg是美國國家科學院（NAS）、美國國家工程院（NAE）、美國人文與科學院（AAAS）三料院士。在計算機科學領域是“傳說級”的人物，而且還獲得過國際數學家大會頒發“奈望林納獎”，該獎是數學家大會為了表彰信息科學方面的重要數學貢獻而設的。

目錄

1Introduction: Some Representative Problems / 引言：某些有代表性的問題1

1.1A First Problem: Stable Matching / 第一個問題：穩定匹配1

1.2Five Representative Problems / 五個有代表性的問題12

SolvedExercises / 帶解答的練習19

Exercises/ 練習22

Notesand Further Reading / 注釋和進一步閱讀28
目錄

1Introduction: Some Representative Problems / 引言：某些有代表性的問題1

1.1A First Problem: Stable Matching / 第一個問題：穩定匹配1

1.2Five Representative Problems / 五個有代表性的問題12

SolvedExercises / 帶解答的練習19

Exercises/ 練習22

Notesand Further Reading / 注釋和進一步閱讀28

2Basics of Algorithm Analysis / 算法分析基礎29

2.1Computational Tractability / 計算可解性29

2.2Asymptotic Order of Growth / 增長的漸近階35

2.3Implementing the Stable Matching Algorithm Using Lists and Arrays / 用列表和數組實現穩定匹配算法42

2.4A Survey of Common Running Times / 常用運行時間概述47

2.5A More Complex Data Structure: Priority Queues / 更復雜的數據結構：優先隊列57

SolvedExercises / 帶解答的練習65

Exercises/ 練習67

Notesand Further Reading / 注釋和進一步閱讀70

3Graphs / 圖73

3.1Basic Definitions and Applications / 基本定義與應用73

3.2Graph Connectivity and Graph Traversal / 圖的連通性與圖的遍歷78

3.3Implementing Graph Traversal Using Queues and Stacks / 用優先隊列與棧實現圖的遍歷87

3.4Testing Bipartiteness: An Application of Breadth-First Search / 二分性測試：寬度優先搜索的應用94

3.5Connectivity in Directed Graphs / 有向圖中的連通性97

3.6Directed Acyclic Graphs and Topological Ordering / 有向無環圖與拓撲排序99

SolvedExercises / 帶解答的練習104

Exercises/ 練習107

Notesand Further Reading / 注釋和進一步閱讀112

4Greedy Algorithms / 貪心算法115

4.1Interval Scheduling: The Greedy Algorithm Stays Ahead / 區間調度：貪心算法領先116

4.2Scheduling to Minimize Lateness: An Exchange Argument / 小延遲調度：交換論證125

4.3Optimal Caching: A More Complex Exchange Argument / 高速緩存：更復雜的交換論證131

4.4Shortest Paths in a Graph / 圖的短路徑137

4.5The Minimum Spanning Tree Problem / 小生成樹問題142

4.6Implementing Kruskal’s Algorithm: The Union-Find Data Structure / 實現Kruskal算法：Union-Find數據結構151

4.7Clustering / 聚類157

4.8Huffman Codes and Data Compression / 赫夫曼碼與數據壓縮161

4.9 Minimum-Cost Arborescences: A Multi-Phase Greedy Algorithm / 小費用有向樹：多階段貪心算法177

SolvedExercises / 帶解答的練習183

Exercises/ 練習188

Notesand Further Reading / 注釋和進一步閱讀205

5Divide and Conquer / 分治策略209

5.1A First Recurrence: The Mergesort Algorithm / 第一個遞推式：歸並排序算法210

5.2Further Recurrence Relations / 更多的遞推關繫214

5.3Counting Inversions / 計數逆序221

5.4Finding the Closest Pair of Points / 找接鄰近的點對225

5.5Integer Multiplication / 整數乘法231

5.6Convolutions and the Fast Fourier Transform / 卷積與快速傅裡葉變換234

SolvedExercises / 帶解答的練習242

Exercises/ 練習246

Notesand Further Reading / 注釋和進一步閱讀249

6Dynamic Programming / 動態規劃251

6.1Weighted Interval Scheduling: A Recursive Procedure / 帶權的區間調度：遞歸過程252

6.2Principles of Dynamic Programming: Memoization or Iteration over Subproblems / 動態規劃原理：備忘錄或者子問題迭代258

6.3Segmented Least Squares: Multi-way Choices / 分段的小二乘：多重選擇261

6.4Subset Sums and Knapsacks: Adding a Variable / 子集和與背包：加一個變量266

6.5RNA Secondary Structure: Dynamic Programming over Intervals / RNA二級結構：在區間上的動態規劃272

6.6Sequence Alignment / 序列比對278

6.7Sequence Alignment in Linear Space via Divide and Conquer / 通過分治策略在線性空間的序列比對284

6.8Shortest Paths in a Graph / 圖中的短路徑290

6.9Shortest Paths and Distance Vector Protocols / 短路徑和距離向量協議297

6.10 Negative Cycles in a Graph / 圖中的負圈301

SolvedExercises / 帶解答的練習307

Exercises/ 練習312

Notesand Further Reading / 注釋和進一步閱讀335

7Network Flow / 網絡流337

7.1The Maximum-Flow Problem and the Ford-Fulkerson Algorithm / 流問題與Ford-Fulkerson算法338

7.2Maximum Flows and Minimum Cuts in a Network / 網絡中的流與小割346

7.3Choosing Good Augmenting Paths / 選擇好的增廣路徑352

7.4 The Preflow-Push Maximum-Flow Algorithm / 前向流推動流算法357

7.5A First Application: The Bipartite Matching Problem / 第一個應用：二分匹配問題367

7.6Disjoint Paths in Directed and Undirected Graphs / 有向與無向圖中的不交路徑373

7.7Extensions to the Maximum-Flow Problem / 對流問題的推廣378

7.8Survey Design / 調查設計384

7.9Airline Scheduling / 航線調度387

7.10Image Segmentation / 圖像分割391

7.11Project Selection / 項目選擇396

7.12Baseball Elimination / 棒球排除400

7.13 A Further Direction: Adding Costs to the Matching Problem / 進一步的方向：對匹配問題增加費用404

SolvedExercises / 帶解答的練習411

Exercises/ 練習415

Notesand Further Reading / 注釋和進一步閱讀448

8NP and Computational Intractability / NP與計算的難解性451

8.1Polynomial-Time Reductions / 多項式時間歸約452

8.2Reductions via “Gadgets”: The Satisfiability Problem / 使用“零件”的歸約：可滿足性問題459

8.3Efficient Certification and the Definition of NP / 有效證書和NP的定義463

8.4NP-Complete Problems / NP完全問題466

8.5Sequencing Problems / 排序問題473

8.6Partitioning Problems / 劃分問題481

8.7Graph Coloring / 圖著色485

8.8Numerical Problems / 數值問題490

8.9Co-NP and the Asymmetry of NP / Co-NP及NP的不對稱性495

8.10A Partial Taxonomy of Hard Problems / 難問題的部分分類497

SolvedExercises / 帶解答的練習500

Exercises/ 練習505

Notesand Further Reading / 注釋和進一步閱讀529

9PSPACE: A Class of Problems beyond NP / PSPACE：一類超出NP的問題531

9.1PSPACE / PSPACE531

9.2Some Hard Problems in PSPACE / PSPACE中的難問題533

9.3Solving Quantified Problems and Games in Polynomial Space / 在多項式空間中解量化問題和博弈問題536

9.4Solving the Planning Problem in Polynomial Space / 在多項式空間內求解規劃問題538

9.5Proving Problems PSPACE-Complete / 證明問題是PSPACE完全的543

SolvedExercises / 帶解答的練習547

Exercises/ 練習550

Notesand Further Reading / 注釋和進一步閱讀551

10Extending the Limits of Tractability / 擴展易解性的界限553

10.1Finding Small Vertex Covers / 找小的頂點覆蓋554

10.2Solving NP-Hard Problems on Trees / 在樹上解NP難問題558

10.3Coloring a Set of Circular Arcs / 圓弧集著色563

10.4 Tree Decompositions of Graphs / 圖的樹分解572

10.5 Constructing a Tree Decomposition / 構造樹分解584

SolvedExercises / 帶解答的練習591

Exercises/ 練習594

Notesand Further Reading / 注釋和進一步閱讀598

11Approximation Algorithms / 近似算法599

11.1Greedy Algorithms and Bounds on the Optimum: A Load Balancing Problem / 貪心算法與值的界限：負載均衡問題600

11.2The Center Selection Problem / 中心選址問題606

11.3Set Cover: A General Greedy Heuristic / 集合覆蓋：一般的貪心啟發式方法612

11.4The Pricing Method: Vertex Cover / 定價法：頂點覆蓋618

11.5Maximization via the Pricing Method: The Disjoint Paths Problem / 用定價法化：不交路徑問題624

11.6Linear Programming and Rounding: An Application to Vertex Cover / 線性規劃與舍入：對頂點覆蓋的應用630

11.7 Load Balancing Revisited: A More Advanced LP Application / 再論負載均衡：更高級的LP應用637

11.8Arbitrarily Good Approximations: The Knapsack Problem / 任意好的近似：背包問題644

SolvedExercises / 帶解答的練習649

Exercises/ 練習651

Notesand Further Reading / 注釋和進一步閱讀659

12Local Search / 局部搜索661

12.1The Landscape of an Optimization Problem / 化問題的地形圖662

12.2The Metropolis Algorithm and Simulated Annealing / Metropolis算法與模擬退火算法666

12.3An Application of Local Search to Hopfield Neural Networks / 局部搜索在Hopfield神經網絡中的應用671

12.4Maximum-Cut Approximation via Local Search / 局部搜索對割近似的應用676

12.5Choosing a Neighbor Relation / 選擇鄰居關繫679

12.6 Classification via Local Search / 用局部搜索分類681

12.7Best-Response Dynamics and Nash Equilibria / 響應動態過程與納什均衡690

SolvedExercises / 帶解答的練習700

Exercises/ 練習702

Notesand Further Reading / 注釋和進一步閱讀705

13Randomized Algorithms / 隨機算法707

13.1A First Application: Contention Resolution / 第一個應用：消除爭用708

13.2Finding the Global Minimum Cut / 求完全小割714

13.3Random Variables and Their Expectations / 隨機變量及其期望719

13.4A Randomized Approximation Algorithm for MAX 3-SAT / 關於MAX 3-SAT的隨機近似算法724

13.5Randomized Divide and Conquer: Median-Finding and Quicksort / 隨機分治策略：求中位數與快速排序727

13.6Hashing: A Randomized Implementation of Dictionaries / 散列法：字典的隨機實現734

13.7Finding the Closest Pair of Points: A Randomized Approach / 求鄰近點對：隨機方法741

13.8Randomized Caching / 隨機超高速緩存750

13.9Chernoff Bounds / 切爾諾夫界758

13.10Load Balancing / 負載均衡760

13.11Packet Routing / 包路由選擇762

13.12Background: Some Basic Probability Definitions / 背景：某些基本概率定義769

SolvedExercises / 帶解答的練習776

Exercises/ 練習782

Notesand Further Reading / 注釋和進一步閱讀793

Epilogue:Algorithms That Run Forever / 後記：永不停止運行的算法795

References/ 參考文獻805

商品搜索

商品分类

【醫學】

【各大出版社】