算法设计

图书标准信息

• 作者 [美]克莱因伯格（Jon Kleinberg）、[美]塔多斯（Eva Tardos） 著
• 出版社 清华大学出版社
• 出版时间 2006-01
• 版次 1
• ISBN 9787302122609
• 定价 89.00元
• 装帧 平装
• 开本 16开
• 纸张 胶版纸
• 页数 838页
• 正文语种 简体中文
• 原版书名 Algorithm Design

【内容简介】

　　《大学计算机教育国外著名教材系列：算法设计（影印版）》是近年来关于算法设计和分析的不可多得的优秀教材。《大学计算机教育国外著名教材系列：算法设计（影印版）》围绕算法设计技术组织素材，对每种算法技术选择了多个典型范例进行分析。本书将直观性与严谨性完美地结合起来。每章从实际问题出发，经过具体、深入、细致的分析，自然且富有启发性地引出相应的算法设计思想，并对算法的正确性、复杂性进行恰当的分析、论证。本书覆盖的面较宽，凡属串行算法的经典论题都有涉及，并且论述深入有新意。全书共200多道丰富而精彩的习题是本书的重要组成部分，也是本书的突出特色之一。
　　本书适用于本科高年级学生以及研究生算法课的教材，也很适于具有计算机或相近专业本科水平的人自学算法的需要。

【作者简介】

　　JonKleinbergisaprofessorofComputerScienceatCornellUniversity.HereceivedhisPh.D.fromM.I.T.in1996.HeistherecipientofanNSFCareerAward，anONRYoungInvestigatorAward，anIBMOutstand-ingInnovationAward，theNationalAcademyofSci-encesAwardforInitiativesinResearch，researchfel-lowshipsfromthePackardandSloanFoundations，andteachingawardsfromtheCornellEngineeringCollegeandComputerScienceDepartment.
　　Kleinberg'sresearchiscenteredaroundalgorithms，particularlythosecon-cernedwiththestructureofnetworksandinformation，andwithapplicationstoinformationscience，optimization，datamining，andcomputationalbiol-ogy.HisworkonnetworkanalysisusinghubsandauthoritieshelpedformthefoundationforthecurrentgenerationofInternetsearchengines.EvaTardosisaprofessorofComputerScienceatCor-nellUniversity.ShereceivedherPh.D.fromEotvosUniversityinBudapest，Hungaryin1984.SheisamemberoftheAmericanAcademyofArtsandSci-ences，andanACMFellow;sheistherecipientofanNSFPresidentialYoungInvestigatorAward，theFulk-ersonPrize，researchfellowshipsfromtheGuggen-heim，Packard，andSloanFoundations，andteach-ingawardsfromtheCornellEngineenngCollegeandComputerScienceDepartment.Tardos'sresearchinterestsarefocusedonthedesignandanalysisofalgorithmsforproblemsongraphsornetworks.Sheismostknownforherworkonnetwork-flowalgorithmsandapproximationalgorithmsfornetworkproblems.Herrecentworkfocusesonalgorithmicgametheory，anemergingareaconcernedwithdesigningsystemsandalgorithmsforselfishusers.

【目录】

AbouttheAuthors
Preface
1Introduction：SomeRepresentativeProblems
1.1AFirstProblem：StableMatching
1.2FiveRepresentativeProblems
SolvedExercises
Exercises
NotesandFurtherReading

2BasicsofAlgorithmAnalysis
2.1ComputationalTractability
2.2AsymptoticOrderofGrowth
2.3ImplementingtheStableMatchingAlgorithmUsingListsandArrays
2.4ASurveyofCommonRunningTimes
2.5AMoreComplexDataStructure：PriorityQueues
SolvedExercises
Exercises
NotesandFurtherReading

3Graphs
3.1BasicDefinitionsandApplications
3.2GraphConnectivityandGraphTraversal
3.3ImplementingGraphTraversalUsingQueuesandStacks
3.4TestingBipaniteness：AnApplicationofBreadth-FirstSearch
3.5ConnectivityinDirectedGraphs
3.6DirectedAcyclicGraphsandTopologicalOrdering
SolvedExercises
Exercises
NotesandFurtherReading

4GreedyAlgorithms
4.1IntervalScheduling：TheGreedyAlgorithmStaysAhead
4.2SchedulingtoMinimizeLateness：AnExchangeArgument
4.3OptimalCaching：AMoreComplexExchangeArgument
4.4ShortestPathsinaGraph
4.5TheMinimumSpanningTreeProblem
4.6ImplementingKruskal'sAlgorithm：TheUnion-FindDataStructure
4.7Clustering
4.8HuffmanCodesandDataCompression
*4.9Minimum-CostArborescences：AMulti-PhaseGreedyAlgorithm
SolvedExercises
Exercises
NotesandFurtherReading

5DivideandCornquer
5.1AFirstRecurrence：TheMergesortAlgorithm
5.2FurtherRecurrenceRelations
5.3CountingInversions
5.4FindingtheClosestPairofPoints
5.5IntegerMultiplication
5.6ConvolutionsandtheFastFourierTransform
SolvedExercises
Exercises
NotesandFurtherReading

6DynamicProgramming
6.1WeightedIntervalScheduling：ARecursiveProcedure
6.2PrinciplesofDynamicProgramming：MemoizationorIterationoverSubproblems
6.3SegmentedLeastSquares：Multi-wayChoices
……

7NetworkFlow
8NPandComputationalIntractability
9PSPACE：AClassofProblemsbeyondNP
10ExtendingtheLimitsofTractability
11ApproximationAlgorithms
12LocalSearch
13RandomizedAlgorithms
Epilogue：AlgorithmsThatRunForever
References
Index