导语

  

内容提要

  

    这是一本关于算法设计和分析的教材。本书围绕算法设计进行组织，对每种算法技术选择了多个典型范例进行分析，把算法的理论跟实际存在的问题结合起来，具有很大的启发性。本书侧重算法设计思路，不再赘述算法复杂度的分析，每章都从实际问题出发，经过深入的具体分析引出相应的算法的设计思想，并对算法的正确性和复杂性进行合理的分析和论证。本书覆盖面很宽，且含有200多道精彩的习题，还扩展了PSPACE问题、参数复杂性等内容。
    本书适合作为计算机及相近专业本科高年级学生以及研究生算法课程的参考教材，也适合作为对信息学奥林匹克竞赛感兴趣的高中生的指导书籍。对算法分析和设计感兴趣的IT专业技术人员也可以将本书作为案头必备的参考书或工程实践手册。

1  Introduction: Some Representative Problems/引言：某些有代表性的问题
  1.1  A First Problem: Stable Matching/第 一个问题：稳定匹配
  1.2  Five Representative Problems/五个有代表性的问题
    Solved Exercises/带解答的练习
    Exercises /练习
    Notes  and Further Reading/注释和进一步阅读
2  Basics of Algorithm Analysis/算法分析基础
  2.1  Computational Tractability/计算可解性
  2.2  Asymptotic Order of Growth/增长的渐近阶
  2.3  Implementing the Stable Matching Algorithm Using Lists and Arrays/用列表和数组实现稳定匹配算法
  2.4  A Survey of Common Running Times/常用运行时间概述
  2.5  A More Complex Data Structure: Priority Queues/更复杂的数据结构：优先队列
    Solved Exercises/带解答的练习
    Exercises /练习
    Notes  and Further Reading/注释和进一步阅读
3  Graphs/图
  3.1  Basic Definitions and Applications/基本定义与应用
  3.2  Graph Connectivity and Graph Traversal/图的连通性与图的遍历
  3.3  Implementing Graph Traversal Using Queues and Stacks/用优先队列与栈实现图的遍历
  3.4  Testing Bipartiteness: An Application of Breadth-First Search/二分性测试：宽度优先搜索的应用
  3.5  Connectivity in Directed Graphs/有向图中的连通性
  3.6  Directed Acyclic Graphs and Topological Ordering/有向无环图与拓扑排序
    Solved Exercises/带解答的练习
    Exercises /练习
    Notes  and Further Reading/注释和进一步阅读
4  Greedy Algorithms/贪心算法
  4.1  Interval Scheduling: The Greedy Algorithm Stays Ahead/区间调度：贪心算法领先
  4.2  Scheduling to Minimize Lateness: An Exchange Argument/最小延迟调度：交换论证
  4.3  Optimal Caching: A More Complex Exchange Argument/最优高速缓存：更复杂的交换论证
  4.4  Shortest Paths in a Graph/图的最短路径
  4.5  The Minimum Spanning Tree Problem/最小生成树问题
  4.6  Implementing Kruskal’s Algorithm: The Union-Find Data Structure/实现Kruskal算法：Union-Find数据结构
  4.7  Clustering/聚类
  4.8  Huffman Codes and Data Compression/赫夫曼码与数据压缩
  4.9  Minimum-Cost Arborescences: A Multi-Phase Greedy Algorithm/最小费用有向树：多阶段贪心算法
    Solved Exercises/带解答的练习
    Exercises /练习
    Notes  and Further Reading/注释和进一步阅读
5  Divide and Conquer/分治策略
  5.1  A First Recurrence: The Mergesort Algorithm/第 一个递推式：归并排序算法
  5.2  Further Recurrence Relations/更多的递推关系
  5.3  Counting Inversions/计数逆序
  5.4  Finding the Closest Pair of Points/找最接邻近的点对
  5.5  Integer Multiplication/整数乘法
  5.6  Convolutions and the Fast Fourier Transform/卷积与快速傅里叶变换
    Solved Exercises/带解答的练习
    Exercises /练习
    Notes  and Further Reading/注释和进一步阅读
6  Dynamic Programming/动态规划
  6.1  Weighted Interval Scheduling: A Recursive Procedure/带权的区间调度：递归过程
  6.2  Principles of Dynamic Programming: Memoization or Iteration over Subproblems/动态规划原理：备忘录或者子问题迭代
  6.3  Segmented Least Squares: Multi-way Choices/分段的最小二乘：多重选择
  6.4  Subset Sums and Knapsacks: Adding a Variable/子集和与背包：加一个变量
  6.5  RNA Secondary Structure: Dynamic Programming over Intervals/RNA二级结构：在区间上的动态规划
  6.6  Sequence Alignment/序列比对
  6.7  Sequence Alignment in Linear Space via Divide and Conquer/通过分治策略在线性空间的序列比对
  6.8  Shortest Paths in a Graph/图中的最短路径
  6.9  Shortest Paths and Distance Vector Protocols/最短路径和距离向量协议
  6.10  Negative Cycles in a Graph/图中的负圈
    Solved Exercises/带解答的练习
    Exercises /练习
    Notes  and Further Reading/注释和进一步阅读
7  Network Flow/网络流
  7.1  The Maximum-Flow Problem and the Ford-Fulkerson Algorithm/最大流问题与Ford-Fulkerson算法
  7.2  Maximum Flows and Minimum Cuts in a Network/网络中的最大流与最小割
  7.3  Choosing Good Augmenting Paths/选择好的增广路径
  7.4  The Preflow-Push Maximum-Flow Algorithm/前向流推动最大流算法
  7.5  A First Application: The Bipartite Matching Problem/第 一个应用：二分匹配问题
  7.6  Disjoint Paths in Directed and Undirected Graphs/有向与无向图中的不交路径
  7.7  Extensions to the Maximum-Flow Problem/对最大流问题的推广
  7.8  Survey Design/调查设计
  7.9  Airline Scheduling/航线调度
  7.10  Image Segmentation/图像分割
  7.11  Project Selection/项目选择
  7.12  Baseball Elimination/棒球排除
  7.13  A Further Direction: Adding Costs to the Matching Problem/进一步的方向：对匹配问题增加费用
    Solved Exercises/带解答的练习
    Exercises /练习
    Notes  and Further Reading/注释和进一步阅读
8  NP and Computational Intractability/NP与计算的难解性
  8.1  Polynomial-Time Reductions/多项式时间归约
  8.2  Reductions via “Gadgets”: The Satisfiability Problem/使用“零件”的归约：可满足性问题
  8.3  Efficient Certification and the Definition of NP/有效证书和NP的定义
  8.4  NP-Complete Problems/NP完全问题
  8.5  Sequencing Problems/排序问题
  8.6  Partitioning Problems/划分问题
  8.7  Graph Coloring/图着色
  8.8  Numerical Problems/数值问题
  8.9  Co-NP and the Asymmetry of NP/Co-NP及NP的不对称性
  8.10  A Partial Taxonomy of Hard Problems/难问题的部分分类
    Solved Exercises/带解答的练习
    Exercises /练习
    Notes  and Further Reading/注释和进一步阅读
9  PSPACE: A Class of Problems beyond NP/PSPACE：一类超出NP的问题
  9.1  PSPACE/PSPACE
  9.2  Some Hard Problems in PSPACE/PSPACE中的难问题
  9.3  Solving Quantified Problems and Games in Polynomial Space/在多项式空间中解量化问题和博弈问题
  9.4  Solving the Planning Problem in Polynomial Space/在多项式空间内求解规划问题
  9.5  Proving Problems PSPACE-Complete/证明问题是PSPACE完全的
    Solved Exercises/带解答的练习
    Exercises /练习
    Notes  and Further Reading/注释和进一步阅读
10  Extending the Limits of Tractability/扩展易解性的界限
  10.1  Finding Small Vertex Covers/找小的顶点覆盖
  10.2  Solving NP-Hard Problems on Trees/在树上解NP难问题
  10.3  Coloring a Set of Circular Arcs/圆弧集着色
  10.4  Tree Decompositions of Graphs/图的树分解
  10.5  Constructing a Tree Decomposition/构造树分解
    Solved Exercises/带解答的练习
    Exercises /练习
    Notes  and Further Reading/注释和进一步阅读
11  Approximation Algorithms/近似算法
  11.1  Greedy Algorithms and Bounds on the Optimum: A Load Balancing Problem/贪心算法与最优值的界限：负载均衡问题
  11.2  The Center Selection Problem/中心选址问题
  11.3  Set Cover: A General Greedy Heuristic/集合覆盖：一般的贪心启发式方法
  11.4  The Pricing Method: Vertex Cover/定价法：顶点覆盖
  11.5  Maximization via the Pricing Method: The Disjoint Paths Problem/用定价法最大化：不交路径问题
  11.6  Linear Programming and Rounding: An Application to Vertex Cover/线性规划与舍入：对顶点覆盖的应用
  11.7  Load Balancing Revisited: A More Advanced LP Application/再论负载均衡：更高级的LP应用
  11.8  Arbitrarily Good Approximations: The Knapsack Problem/任意好的近似：背包问题
    Solved Exercises/带解答的练习
    Exercises /练习
    Notes  and Further Reading/注释和进一步阅读
12  Local Search/局部搜索
  12.1  The Landscape of an Optimization Problem/最优化问题的地形图
  12.2  The Metropolis Algorithm and Simulated Annealing/Metropolis算法与模拟退火算法
  12.3  An Application of Local Search to Hopfield Neural Networks/局部搜索在Hopfield神经网络中的应用
  12.4  Maximum-Cut Approximation via Local Search/局部搜索对最大割近似的应用
  12.5  Choosing a Neighbor Relation/选择邻居关系
  12.6  Classification via Local Search/用局部搜索分类
  12.7  Best-Response Dynamics and Nash Equilibria/最佳响应动态过程与纳什均衡
    Solved Exercises/带解答的练习
    Exercises /练习
    Notes  and Further Reading/注释和进一步阅读
13  Randomized Algorithms/随机算法
  13.1  A First Application: Contention Resolution/第 一个应用：消除争用
  13.2  Finding the Global Minimum Cut/求完全最小割
  13.3  Random Variables and Their Expectations/随机变量及其期望
  13.4  A Randomized Approximation Algorithm for MAX 3-SAT/关于MAX 3-SAT的随机近似算法
  13.5  Randomized Divide and Conquer: Median-Finding and Quicksort/随机分治策略：求中位数与快速排序
  13.6  Hashing: A Randomized Implementation of Dictionaries/散列法：字典的随机实现
  13.7  Finding the Closest Pair of Points: A Randomized Approach/求最邻近点对：随机方法
  13.8  Randomized Caching/随机超高速缓存
  13.9  Chernoff Bounds/切尔诺夫界
  13.10  Load Balancing/负载均衡
  13.11  Packet Routing/包路由选择
  13.12  Background: Some Basic Probability Definitions/背景：某些基本概率定义
    Solved Exercises/带解答的练习
    Exercises /练习
    Notes  and Further Reading/注释和进一步阅读
Epilogue:  Algorithms That Run Forever/后记：永不停止运行的算法
References /参考文献