微信扫码下载
编辑推荐
-众多名校采用的算法设计课程教材-用实际示例阐明枯燥的算法理论
-更注重算法设计思路而非算法复杂度分析
《算法设计 英文版》采用新颖的方法来讲算法课程，通过激发算法思想的真实世界问题，引入了算法思想。两位作者以一种清晰、直接的方式，指导学生自己分析和定义问题，并从中找出哪些设计原则适用于给定的场景。《算法设计 英文版》鼓励更深入地理解算法设计过程，以及算法在计算机科学的更广阔的领域中的应用。
《算法设计 英文版》有以下几个特色：
1.强调分析和设计方法；
2.遵循结构化教学方法，引导学生学习问题形式化、算法设计和算法分析的全过程；
3.通过一系列带解答的问题，展示计算机科学家设计和应用算法的过程；
4.包含200多道作业题，其中一些题目来自Yahoo！和Oracle这样的公司；
5.提供广泛用于处理NP困难问题和随机应用的算法，这些是非常重要的算法主题。
内容简介
这是一本关于算法设计和分析的教材。《算法设计 英文版》围绕算法设计进行组织，对每种算法技术选择了多个典型范例进行分析，把算法的理论跟实际存在的问题结合起来，具有很大的启发性。《算法设计 英文版》侧重算法设计思路，不再赘述算法复杂度的分析，每章都从实际问题出发，经过深入的具体分析引出相应的算法的设计思想，并对算法的正确性和复杂性进行合理的分析和论证。《算法设计 英文版》覆盖面很宽，且含有200多道精彩的习题，还扩展了PSPACE问题、参数复杂性等内容。作者简介
JonKleinberg是美国国家科学院（NAS）、美国国家工程院（NAE）、美国人文与科学院（AAAS）三料院士。在计算机科学领域是“传说级”的人物，而且还获得过国际数学家大会颁发“奈望林纳奖”，该奖是数学家大会为了表彰信息科学方面的重要数学贡献而设的。目录
目录1 Introduction：SomeRepresentativeProblems/引言：某些有代表性的问题 1
1．1 AFirstProblem：StableMatching/第一个问题：稳定匹配 1
1．2 FiveRepresentativeProblems/五个有代表性的问题 12
Solved Exercises/带解答的练习 19
Exercises /练习 22
Notes andFurtherReading/注释和进一步阅读 28
2 BasicsofAlgorithmAnalysis/算法分析基础 29
2．1 ComputationalTractability/计算可解性 29
2．2 AsymptoticOrderofGrowth/增长的渐近阶 35
2．3 ImplementingtheStableMatchingAlgorithmUsingListsandArrays/用列表和数组实现稳定匹配算法42
2．4 ASurveyofCommonRunningTimes/常用运行时间概述 47
2．5 AMoreComplexDataStructure：PriorityQueues/更复杂的数据结构：优先队列 57
Solved Exercises/带解答的练习 65
Exercises /练习 67
Notes andFurtherReading/注释和进一步阅读 70
3 Graphs/图 73
3．1 BasicDefinitionsandApplications/基本定义与应用 73
3．2 GraphConnectivityandGraphTraversal/图的连通性与图的遍历 78
3．3 ImplementingGraphTraversalUsingQueuesandStacks/用优先队列与栈实现图的遍历 87
3．4 TestingBipartiteness：AnApplicationofBreadth-FirstSearch/二分性测试：宽度优先搜索的应用 94
3．5 ConnectivityinDirectedGraphs/有向图中的连通性 97
3．6 DirectedAcyclicGraphsandTopologicalOrdering/有向无环图与拓扑排序 99
Solved Exercises/带解答的练习 104
Exercises /练习 107
Notes andFurtherReading/注释和进一步阅读 112
4 GreedyAlgorithms/贪心算法 115
4．1 IntervalScheduling：TheGreedyAlgorithmStaysAhead/区间调度：贪心算法领先 116
4．2 SchedulingtoMinimizeLateness：AnExchangeArgument/最小延迟调度：交换论证 125
4．3 OptimalCaching：AMoreComplexExchangeArgument/最优高速缓存：更复杂的交换论证131
4．4 ShortestPathsinaGraph/图的最短路径 137
4．5 TheMinimumSpanningTreeProblem/最小生成树问题 142
4．6 ImplementingKruskal’sAlgorithm：TheUnion-FindDataStructure/实现Kruskal算法：Union-Find数据结构 151
4．7 Clustering/聚类 157
4．8 HuffmanCodesandDataCompression/赫夫曼码与数据压缩 161
4．9Minimum-CostArborescences：AMulti-PhaseGreedyAlgorithm/最小费用有向树：多阶段贪心算法 177
Solved Exercises/带解答的练习 183
Exercises /练习 188
Notes andFurtherReading/注释和进一步阅读 205
5 DivideandConquer/分治策略 209
5．1 AFirstRecurrence：TheMergesortAlgorithm/第一个递推式：归并排序算法 210
5．2 FurtherRecurrenceRelations/更多的递推关系 214
5．3 CountingInversions/计数逆序 221
5．4 FindingtheClosestPairofPoints/找最接邻近的点对 225
5．5 IntegerMultiplication/整数乘法 231
5．6 ConvolutionsandtheFastFourierTransform/卷积与快速傅里叶变换 234
Solved Exercises/带解答的练习 242
Exercises /练习 246
Notes andFurtherReading/注释和进一步阅读 249
6 DynamicProgramming/动态规划 251
6．1 WeightedIntervalScheduling：ARecursiveProcedure/带权的区间调度：递归过程 252
6．2 PrinciplesofDynamicProgramming：MemoizationorIterationoverSubproblems/动态规划原理：备忘录或者子问题迭代 258
6．3 SegmentedLeastSquares：Multi-wayChoices/分段的最小二乘：多重选择 261
6．4 SubsetSumsandKnapsacks：AddingaVariable/子集和与背包：加一个变量 266
6．5 RNASecondaryStructure：DynamicProgrammingoverIntervals/RNA二级结构：在区间上的动态规划 272
6．6 SequenceAlignment/序列比对 278
6．7 SequenceAlignmentinLinearSpaceviaDivideandConquer/通过分治策略在线性空间的序列比对 284
6．8 ShortestPathsinaGraph/图中的最短路径 290
6．9 ShortestPathsandDistanceVectorProtocols/最短路径和距离向量协议 297
6．10NegativeCyclesinaGraph/图中的负圈 301
Solved Exercises/带解答的练习 307
Exercises /练习 312
Notes andFurtherReading/注释和进一步阅读 335
7 NetworkFlow/网络流 337
7．1 TheMaximum-FlowProblemandtheFord-FulkersonAlgorithm/最大流问题与Ford-Fulkerson算法 338
7．2 MaximumFlowsandMinimumCutsinaNetwork/网络中的最大流与最小割 346
7．3 ChoosingGoodAugmentingPaths/选择好的增广路径352
7．4ThePreflow-PushMaximum-FlowAlgorithm/前向流推动最大流算法 357
7．5 AFirstApplication：TheBipartiteMatchingProblem/第一个应用：二分匹配问题 367
7．6 DisjointPathsinDirectedandUndirectedGraphs/有向与无向图中的不交路径 373
7．7 ExtensionstotheMaximum-FlowProblem/对最大流问题的推广 378
7．8 SurveyDesign/调查设计384
7．9 AirlineScheduling/航线调度 387
7．10 ImageSegmentation/图像分割 391
7．11 ProjectSelection/项目选择 396
7．12 BaseballElimination/棒球排除 400
7．13AFurtherDirection：AddingCoststotheMatchingProblem/进一步的方向：对匹配问题增加费用 404
Solved Exercises/带解答的练习 411
Exercises /练习 415
Notes andFurtherReading/注释和进一步阅读 448
8 NPandComputationalIntractability/NP与计算的难解性 451
8．1 Polynomial-TimeReductions/多项式时间归约 452
8．2 Reductionsvia“Gadgets”：TheSatisfiabilityProblem/使用“零件”的归约：可满足性问题 459
8．3 EfficientCertificationandtheDefinitionofNP/有效证书和NP的定义 463
8．4 NP-CompleteProblems/NP完全问题 466
8．5 SequencingProblems/排序问题 473
8．6 PartitioningProblems/划分问题 481
8．7 GraphColoring/图着色 485
8．8 NumericalProblems/数值问题 490
8．9 Co-NPandtheAsymmetryofNP/Co-NP及NP的不对称性 495
8．10 APartialTaxonomyofHardProblems/难问题的部分分类 497
Solved Exercises/带解答的练习 500
Exercises /练习 505
Notes andFurtherReading/注释和进一步阅读 529
9 PSPACE：AClassofProblemsbeyondNP/PSPACE：一类超出NP的问题 531
9．1 PSPACE/PSPACE 531
9．2 SomeHardProblemsinPSPACE/PSPACE中的难问题 533
9．3 SolvingQuantifiedProblemsandGamesinPolynomialSpace/在多项式空间中解量化问题和博弈问题 536
9．4 SolvingthePlanningProbleminPolynomialSpace/在多项式空间内求解规划问题 538
9．5 ProvingProblemsPSPACE-Complete/证明问题是PSPACE完全的 543
Solved Exercises/带解答的练习 547
Exercises /练习 550
Notes andFurtherReading/注释和进一步阅读 551
10 ExtendingtheLimitsofTractability/扩展易解性的界限 553
10．1 FindingSmallVertexCovers/找小的顶点覆盖 554
10．2 SolvingNP-HardProblemsonTrees/在树上解NP难问题 558
10．3 ColoringaSetofCircularArcs/圆弧集着色 563
10．4TreeDecompositionsofGraphs/图的树分解 572
10．5ConstructingaTreeDecomposition/构造树分解 584
Solved Exercises/带解答的练习 591
Exercises /练习 594
Notes andFurtherReading/注释和进一步阅读 598
11 ApproximationAlgorithms/近似算法 599
11．1 GreedyAlgorithmsandBoundsontheOptimum：ALoadBalancingProblem/贪心算法与最优值的界限：负载均衡问题 600
11．2 TheCenterSelectionProblem/中心选址问题 606
11．3 SetCover：AGeneralGreedyHeuristic/集合覆盖：一般的贪心启发式方法 612
11．4 ThePricingMethod：VertexCover/定价法：顶点覆盖 618
11．5 MaximizationviathePricingMethod：TheDisjointPathsProblem/用定价法最大化：不交路径问题 624
11．6 LinearProgrammingandRounding：AnApplicationtoVertexCover/线性规划与舍入：对顶点覆盖的应用 630
11．7LoadBalancingRevisited：AMoreAdvancedLPApplication/再论负载均衡：更高级的LP应用 637
11．8 ArbitrarilyGoodApproximations：TheKnapsackProblem/任意好的近似：背包问题 644
Solved Exercises/带解答的练习 649
Exercises /练习 651
Notes andFurtherReading/注释和进一步阅读 659
12 LocalSearch/局部搜索 661
12．1 TheLandscapeofanOptimizationProblem/最优化问题的地形图 662
12．2 TheMetropolisAlgorithmandSimulatedAnnealing/Metropolis算法与模拟退火算法 666
12．3 AnApplicationofLocalSearchtoHopfieldNeuralNetworks/局部搜索在Hopfield神经网络中的应用 671
12．4 Maximum-CutApproximationviaLocalSearch/局部搜索对最大割近似的应用 676
12．5 ChoosingaNeighborRelation/选择邻居关系 679
12．6ClassificationviaLocalSearch/用局部搜索分类 681
12．7 Best-ResponseDynamicsandNashEquilibria/最佳响应动态过程与纳什均衡 690
Solved Exercises/带解答的练习 700
Exercises /练习 702
Notes andFurtherReading/注释和进一步阅读 705
13 RandomizedAlgorithms/随机算法 707
13．1 AFirstApplication：ContentionResolution/第一个应用：消除争用 708
13．2 FindingtheGlobalMinimumCut/求完全最小割 714
13．3 RandomVariablesandTheirExpectations/随机变量及其期望 719
13．4 ARandomizedApproximationAlgorithmforMAX3-SAT/关于MAX3-SAT的随机近似算法 724
13．5 RandomizedDivideandConquer：Median-FindingandQuicksort/随机分治策略：求中位数与快速排序 727
13．6 Hashing：ARandomizedImplementationofDictionaries/散列法：字典的随机实现 734
13．7 FindingtheClosestPairofPoints：ARandomizedApproach/求最邻近点对：随机方法 741
13．8 RandomizedCaching/随机超高速缓存 750
13．9 ChernoffBounds/切尔诺夫界 758
13．10 LoadBalancing/负载均衡 760
13．11 PacketRouting/包路由选择 762
13．12 Background：SomeBasicProbabilityDefinitions/背景：某些基本概率定义 769
Solved Exercises/带解答的练习 776
Exercises /练习 782
Notes andFurtherReading/注释和进一步阅读 793
Epilogue： AlgorithmsThatRunForever/后记：永不停止运行的算法 795
References /参考文献 805
