微信扫码下载

编辑推荐

-众多名校采用的算法设计课程教材
-用实际示例阐明枯燥的算法理论
-更注重算法设计思路而非算法复杂度分析

算法设计 英文版》采用新颖的方法来讲算法课程,通过激发算法思想的真实世界问题,引入了算法思想。两位作者以一种清晰、直接的方式,指导学生自己分析和定义问题,并从中找出哪些设计原则适用于给定的场景。《算法设计 英文版》鼓励更深入地理解算法设计过程,以及算法在计算机科学的更广阔的领域中的应用。

算法设计 英文版》有以下几个特色:
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

其他推荐