×
超值优惠券
¥50
100可用 有效期2天

全场图书通用(淘书团除外)

关闭
暂无评论
图文详情
  • ISBN:9787115495921
  • 装帧:一般胶版纸
  • 册数:暂无
  • 重量:暂无
  • 开本:其他
  • 页数:814
  • 出版时间:2018-07-01
  • 条形码:9787115495921 ; 978-7-115-49592-1

本书特色

这是一本关于算法设计和分析的教材。本书围绕算法设计进行组织,对每种算法技术选择了多个典型范例进行分析,把算法的理论跟实际存在的问题结合起来,具有很大的启发性。本书侧重算法设计思路,不再赘述算法复杂度的分析,每章都从实际问题出发,经过深入的具体分析引出相应的算法的设计思想,并对算法的正确性和复杂性进行合理的分析和论证。本书覆盖面很宽,且含有200多道精彩的习题,还扩展了PSPACE问题、参数复杂性等内容。

内容简介

这是一本关于算法设计和分析的教材。本书围绕算法设计进行组织,对每种算法技术选择了多个典型范例进行分析,把算法的理论跟实际存在的问题结合起来,具有很大的启发性。本书侧重算法设计思路,不再赘述算法复杂度的分析,每章都从实际问题出发,经过深入的具体分析引出相应的算法的设计思想,并对算法的正确性和复杂性进行合理的分析和论证。本书覆盖面很宽,且含有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





展开全部

作者简介

Jon Kleinberg是美国国家科学院(NAS)、美国国家工程院(NAE)、美国人文与科学院(AAAS)三料院士。在计算机科学领域是“传说级”的人物,而且还获得过国际数学家大会颁发“奈望林纳奖”,该奖是数学家大会为了表彰信息科学方面的重要数学贡献而设的。

预估到手价 ×

预估到手价是按参与促销活动、以最优惠的购买方案计算出的价格(不含优惠券部分),仅供参考,未必等同于实际到手价。

确定
快速
导航