算法设计

作者: [美] 克莱因伯格（Jon Kleinberg）著 , [美] 塔多斯（Eva Tardos）著

出版社: 清华大学出版社

出版时间: 2006-01

版次: 1

ISBN: 9787302122609

定价: 89.00

装帧: 平装

开本: 16开

纸张: 胶版纸

页数: 838页

正文语种: 简体中文

原版书名: Algorithm Design

分类: 教材教辅考试>教材>大学教材>计算机与互联网

1 张插图图片

129人买过

　　《大学计算机教育国外著名教材系列：算法设计（影印版）》是近年来关于算法设计和分析的不可多得的优秀教材。《大学计算机教育国外著名教材系列：算法设计（影印版）》围绕算法设计技术组织素材，对每种算法技术选择了多个典型范例进行分析。本书将直观性与严谨性完美地结合起来。每章从实际问题出发，经过具体、深入、细致的分析，自然且富有启发性地引出相应的算法设计思想，并对算法的正确性、复杂性进行恰当的分析、论证。本书覆盖的面较宽，凡属串行算法的经典论题都有涉及，并且论述深入有新意。全书共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
内容简介:
　　《大学计算机教育国外著名教材系列：算法设计（影印版）》是近年来关于算法设计和分析的不可多得的优秀教材。《大学计算机教育国外著名教材系列：算法设计（影印版）》围绕算法设计技术组织素材，对每种算法技术选择了多个典型范例进行分析。本书将直观性与严谨性完美地结合起来。每章从实际问题出发，经过具体、深入、细致的分析，自然且富有启发性地引出相应的算法设计思想，并对算法的正确性、复杂性进行恰当的分析、论证。本书覆盖的面较宽，凡属串行算法的经典论题都有涉及，并且论述深入有新意。全书共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