书籍详情
算法基础：英文版
作者：Gilles Brassard，Paul Bratly著
出版社：清华大学出版社
出版时间：2005-07-01
ISBN：9787302111559
定价：¥35.00
购买这本书可以去
内容简介
本书足关于算法导论的经典教材，书中包括大量例题解答与命题证明。本书是按照算法类型而不是按照应用类型对算法进行介绍，以其清晰的概念讲解赢得专家们的广泛赞誉。本书适用对象广泛。对于学习算法设计与分析的本科生和研究生，本书足优选教材。对于从事算法计算研究和工程应用的科研人员和工程技术人员，本书也是一本优秀的基础性读物。本书翻译版已出版，书号为7-302一10609-6。
作者简介
暂缺《算法基础：英文版》作者简介
目录
PREFACE
1PRELIMINARIES
1.1Introduction1
1.2Whatisanalgorithm?1
1.3Notationforprograms6
1.4Mathematicalnotation7
1.4.1Propositionalcalculus7
1.4.2Settheory8
1.4.3Integers,realsandintervals8
1.4.4Functionsandrelations9
1.4.5Quantifiers10
1.4.6Sumsandproducts11
1.4.7Miscellaneous12
1.5Prooftechnique1--Contradiction13
1.6Prooftechnique2--Mathematicalinduction16
1.6.1Theprincipleofmathematicalinduction18
1.6.2Ahorseofadifferentcolour23
1.6.3Generalizedmathematicalinduction24
1.6.4Constructiveinduction27
1.7Somereminders31
1.7.1Limits31
1.7.2Simpleseries34
1.7.3Basiccombinatorics38
1.7.4Elementaryprobability41
1.8Problems48
1.9Referencesandfurtherreading55
2ELEMENTARYALGORITHMICS
2.1Introduction57
2.2Problemsandinstances58
2.3Theefficiencyofalgorithms59
2.4Averageandworst-caseanalyses61
2.5Whatisanelementaryoperation?64
2.6Whylookforefficiency?66
2.7Someexamples67
2.7.1Calculatingdeterminants68
2.7.2Sorting68
2.7.3Multiplicationoflargeintegers70
2.7.4Calculatingthegreatestcommondivisor71
2.7.5CalculatingtheFibonaccisequence72
2.7.6Fouriertransforms73
2.8Whenisanalgorithmspecified?74
2.9Problems74
2.10Referencesandfurtherreading78
3ASYMPTOTICNOTATION
3.1Introduction79
3.2Anotationfor"theorderof"79
3.3Otherasymptoticnotation85
3.4Conditionalasymptoticnotation88
3.5Asymptoticnotationwithseveralparameters91
3.6Operationsonasymptoticnotation91
3.7Problems92
3.8Referencesandfurtherreading97
4ANALYSISOFALGORITHMS
4.1Introduction98
4.2Analysingcontrolstructures98
4.2.1Sequencing98
4.2.2"For"loops99
4.2.3Recursivecalls101
4.2.4"While"and"repeat"loops102
4.3Usingabarometer104
4.4Supplementaryexamples106
4.5Average-caseanalysis111
4.6Amortizedanalysis112
4.7Solvingrecurrences116
4.7.1Intelligentguesswork116
4.7.2Homogeneousrecurrences118
4.7.3Inhomogeneousrecurrences123
4.7.4Changeofvariable130
4.7.5Rangetransformations136
4.7.6Asymptoticrecurrences137
4.8Problems139
4.9Referencesandfurtherreading146
5SOMEDATASTRUCTURES
5.1Arrays,stacksandqueues147
5.2Recordsandpointers150
5.3Lists151
5.4Graphs152
5.5Trees154
5.6Associativetables159
5.7Heaps162
5.8Binomialheaps170
5.9Disjointsetstructures175
5.10Problems181
5.11Referencesandfurtherreading186
6GREEDYALGORITHMS
6.1Makingchange(1)187
6.2Generalcharacteristicsofgreedyalgorithms188
6.3Graphs:Minimumspanningtrees190
6.3.1Kruskal'salgorithm193
6.3.2Prim'salgorithm196
6.4Graphs:Shortestpaths198
6.5Theknapsackproblem(1)202
6.6Scheduling205
6.6.1Minimizingtimeinthesystem205
6.6.2Schedulingwithdeadlines207
6.7Problems214
6.8Referencesandfurtherreading217
7DIVIDE-AND-CONQUER
7.1Introduction:Multiplyinglargeintegers219
7.2Thegeneraltemplate223
7.3Binarysearch226
7.4Sorting228
7.4.1Sortingbymerging228
7.4.2Quicksort231
7.5Findingthemedian237
7.6Matrixmultiplication242
7.7Exponentiation243
7.8Puttingitalltogether:Introductiontocryptography247
7.9Problems250
7.10Referencesandfurtherreading257
8DYNAMICPROGRAMMING
8.1Twosimpleexamples260
8.1.1Calculatingthebinomialcoefficient260
8.1.2TheWorldSeries261
8.2Makingchange(2)263
8.3Theprincipleofoptimality265
8.4Theknapsackproblem(2)266
8.5Shortestpaths268
8.6Chainedmatrixmultiplication271
8.7Approachesusingrecursion274
8.8Memoryfunctions276
8.9Problems278
8.10Referencesandfurtherreading283
9EXPLORINGGRAPHS
9.1Graphsandgames:Anintroduction285
9.2Traversingtrees291
9.2.1Preconditioning292
9.3Depth-firstsearch:Undirectedgraphs294
9.3.1Articulationpoints296
9.4Depth-firstsearch:Directedgraphs298
9.4.1Acyclicgraphs:Topologicalsorting300
9.5Breadth-firstsearch302
9.6Backtracking305
9.6.1Theknapsackproblem(3)306
9.6.2Theeightqueensproblem308
9.6.3Thegeneraltemplate311
9.7Branch-and-bound312
9.7.1Theassignmentproblem312
9.7.2Theknapsackproblem(4)315
9.7.3Generalconsiderations316
9.8Theminimaxprinciple317
9.9Problems319
9.10Referencesandfurtherreading326
I0PROBABILISTICALGORITHMS
10.1Introduction328
102Probabilisticdoesnotimplyuncertain329
10.3Expectedversusaveragetime331
10.4Pseudorandomgeneration331
10.5Numericalprobabilisticalgorithms333
10.5.1Buffon'sneedle333
10.5.2Numericalintegration336
10.5.3Probabilisticcounting338
10.6MonteCarloalgorithms341
10.6.1Verifyingmatrixmultiplication341
10.6.2Primalitytesting343
10.6.3Cananumberbeprobablyprime?348
10.6.4Amplificationofstochasticadvantage350
10.7LasVegasalgorithms353
10.7.1Theeightqueensproblemrevisited355
10.7.2Probabilisticselectionandsorting358
10.7.3Universalhashing360
10.7.4Factorizinglargeintegers362
10.8Problems366
10.9Referencesandfurtherreading373
11PARALLELALGORITHMS
11.1Amodelforparallelcomputation376
11.2Somebasictechniques379
11.2.1Computingwithacompletebinarytree379
11.2.2Pointerdoubling380
11.3Workandefficiency383
11.4Twoexamplesfromgraphtheory386
11.4.1Shortestpaths386
11.4.2Connectedcomponen,ts387
11.5Parallelevaluationofexpressions392
11.6Parallelsortingnetworks397
11.6.1Thezero-oneprinciple399
11.6.2Parallelmergingnetworks400
11.6.3Improvedsortingnetworks402
11.7Parallelsorting402
11.7.1Preliminaries403
11.7.2Thekeyidea404
11.7.3Thealgorithm405
11.7.4Asketchofthedetails406
11.8SomeremarksonEREWandcrcwp-rams406
11.9Distributedcomputation408
11.10Problems409
11.11Referencesandfurtherreading412
12COMPUTATIONALCOMPLEXITY
12.1Introduction:Asimpleexample414
12.2Information-theoreticarguments414
12.2.1Thecomplexityofsorting418
12.2.2Complexitytotherescueofalgorithmics421
12.3Adversaryarguments423
12.3.1Findingthemaximumofanarray424
12.3.2Testinggraphconnectivity425
12.3.3Themedianrevisited426
12.4Linearreductions427
12.4.1Formaldefinitions430
12.4.2Reductionsamongmatrixproblems433
12.4.3Reductionsamongshortestpathproblems438
12.5IntroductiontoNP-completeness441
12.5.1TheclassesPandNp441
12.5.2Polynomialreductions445
12.5.3NP-completeproblems450
12.5.4AfewNP-completenessproofs453
12.5.5Np-hardproblems457
12.5.6Nondeterministicalgorithms458
12.6Amenagerieofcomplexityclasses460
12.7Problems464
12.8Referencesandfurtherreading471
13HEURISTICANDAPPROXIMATEALGORITHMS
13.1Heuristicalgorithms475
13.1.1Colouringagraph475
13.1.2Thetravellingsalesperson477
13.2Approximatealgorithms478
13.2.1Themetrictravellingsalesperson478
13.2.2Theknapsackproblem(5)480
13.2.3Binpacking482
13.3NP-hardapproximationproblems484
13.3.1Hardabsoluteapproximationproblems486
13.3.2Hardrelativeapproximationproblems487
13.4Thesame,onlydifferent489
13.5Approximationschemes492
13.5.1Binpackingrevisited493
13.5.2Theknapsackproblem(6)493
13.6Problems496
13.7Referencesandfurtherreading500
REFERENCES
INDEX
1PRELIMINARIES
1.1Introduction1
1.2Whatisanalgorithm?1
1.3Notationforprograms6
1.4Mathematicalnotation7
1.4.1Propositionalcalculus7
1.4.2Settheory8
1.4.3Integers,realsandintervals8
1.4.4Functionsandrelations9
1.4.5Quantifiers10
1.4.6Sumsandproducts11
1.4.7Miscellaneous12
1.5Prooftechnique1--Contradiction13
1.6Prooftechnique2--Mathematicalinduction16
1.6.1Theprincipleofmathematicalinduction18
1.6.2Ahorseofadifferentcolour23
1.6.3Generalizedmathematicalinduction24
1.6.4Constructiveinduction27
1.7Somereminders31
1.7.1Limits31
1.7.2Simpleseries34
1.7.3Basiccombinatorics38
1.7.4Elementaryprobability41
1.8Problems48
1.9Referencesandfurtherreading55
2ELEMENTARYALGORITHMICS
2.1Introduction57
2.2Problemsandinstances58
2.3Theefficiencyofalgorithms59
2.4Averageandworst-caseanalyses61
2.5Whatisanelementaryoperation?64
2.6Whylookforefficiency?66
2.7Someexamples67
2.7.1Calculatingdeterminants68
2.7.2Sorting68
2.7.3Multiplicationoflargeintegers70
2.7.4Calculatingthegreatestcommondivisor71
2.7.5CalculatingtheFibonaccisequence72
2.7.6Fouriertransforms73
2.8Whenisanalgorithmspecified?74
2.9Problems74
2.10Referencesandfurtherreading78
3ASYMPTOTICNOTATION
3.1Introduction79
3.2Anotationfor"theorderof"79
3.3Otherasymptoticnotation85
3.4Conditionalasymptoticnotation88
3.5Asymptoticnotationwithseveralparameters91
3.6Operationsonasymptoticnotation91
3.7Problems92
3.8Referencesandfurtherreading97
4ANALYSISOFALGORITHMS
4.1Introduction98
4.2Analysingcontrolstructures98
4.2.1Sequencing98
4.2.2"For"loops99
4.2.3Recursivecalls101
4.2.4"While"and"repeat"loops102
4.3Usingabarometer104
4.4Supplementaryexamples106
4.5Average-caseanalysis111
4.6Amortizedanalysis112
4.7Solvingrecurrences116
4.7.1Intelligentguesswork116
4.7.2Homogeneousrecurrences118
4.7.3Inhomogeneousrecurrences123
4.7.4Changeofvariable130
4.7.5Rangetransformations136
4.7.6Asymptoticrecurrences137
4.8Problems139
4.9Referencesandfurtherreading146
5SOMEDATASTRUCTURES
5.1Arrays,stacksandqueues147
5.2Recordsandpointers150
5.3Lists151
5.4Graphs152
5.5Trees154
5.6Associativetables159
5.7Heaps162
5.8Binomialheaps170
5.9Disjointsetstructures175
5.10Problems181
5.11Referencesandfurtherreading186
6GREEDYALGORITHMS
6.1Makingchange(1)187
6.2Generalcharacteristicsofgreedyalgorithms188
6.3Graphs:Minimumspanningtrees190
6.3.1Kruskal'salgorithm193
6.3.2Prim'salgorithm196
6.4Graphs:Shortestpaths198
6.5Theknapsackproblem(1)202
6.6Scheduling205
6.6.1Minimizingtimeinthesystem205
6.6.2Schedulingwithdeadlines207
6.7Problems214
6.8Referencesandfurtherreading217
7DIVIDE-AND-CONQUER
7.1Introduction:Multiplyinglargeintegers219
7.2Thegeneraltemplate223
7.3Binarysearch226
7.4Sorting228
7.4.1Sortingbymerging228
7.4.2Quicksort231
7.5Findingthemedian237
7.6Matrixmultiplication242
7.7Exponentiation243
7.8Puttingitalltogether:Introductiontocryptography247
7.9Problems250
7.10Referencesandfurtherreading257
8DYNAMICPROGRAMMING
8.1Twosimpleexamples260
8.1.1Calculatingthebinomialcoefficient260
8.1.2TheWorldSeries261
8.2Makingchange(2)263
8.3Theprincipleofoptimality265
8.4Theknapsackproblem(2)266
8.5Shortestpaths268
8.6Chainedmatrixmultiplication271
8.7Approachesusingrecursion274
8.8Memoryfunctions276
8.9Problems278
8.10Referencesandfurtherreading283
9EXPLORINGGRAPHS
9.1Graphsandgames:Anintroduction285
9.2Traversingtrees291
9.2.1Preconditioning292
9.3Depth-firstsearch:Undirectedgraphs294
9.3.1Articulationpoints296
9.4Depth-firstsearch:Directedgraphs298
9.4.1Acyclicgraphs:Topologicalsorting300
9.5Breadth-firstsearch302
9.6Backtracking305
9.6.1Theknapsackproblem(3)306
9.6.2Theeightqueensproblem308
9.6.3Thegeneraltemplate311
9.7Branch-and-bound312
9.7.1Theassignmentproblem312
9.7.2Theknapsackproblem(4)315
9.7.3Generalconsiderations316
9.8Theminimaxprinciple317
9.9Problems319
9.10Referencesandfurtherreading326
I0PROBABILISTICALGORITHMS
10.1Introduction328
102Probabilisticdoesnotimplyuncertain329
10.3Expectedversusaveragetime331
10.4Pseudorandomgeneration331
10.5Numericalprobabilisticalgorithms333
10.5.1Buffon'sneedle333
10.5.2Numericalintegration336
10.5.3Probabilisticcounting338
10.6MonteCarloalgorithms341
10.6.1Verifyingmatrixmultiplication341
10.6.2Primalitytesting343
10.6.3Cananumberbeprobablyprime?348
10.6.4Amplificationofstochasticadvantage350
10.7LasVegasalgorithms353
10.7.1Theeightqueensproblemrevisited355
10.7.2Probabilisticselectionandsorting358
10.7.3Universalhashing360
10.7.4Factorizinglargeintegers362
10.8Problems366
10.9Referencesandfurtherreading373
11PARALLELALGORITHMS
11.1Amodelforparallelcomputation376
11.2Somebasictechniques379
11.2.1Computingwithacompletebinarytree379
11.2.2Pointerdoubling380
11.3Workandefficiency383
11.4Twoexamplesfromgraphtheory386
11.4.1Shortestpaths386
11.4.2Connectedcomponen,ts387
11.5Parallelevaluationofexpressions392
11.6Parallelsortingnetworks397
11.6.1Thezero-oneprinciple399
11.6.2Parallelmergingnetworks400
11.6.3Improvedsortingnetworks402
11.7Parallelsorting402
11.7.1Preliminaries403
11.7.2Thekeyidea404
11.7.3Thealgorithm405
11.7.4Asketchofthedetails406
11.8SomeremarksonEREWandcrcwp-rams406
11.9Distributedcomputation408
11.10Problems409
11.11Referencesandfurtherreading412
12COMPUTATIONALCOMPLEXITY
12.1Introduction:Asimpleexample414
12.2Information-theoreticarguments414
12.2.1Thecomplexityofsorting418
12.2.2Complexitytotherescueofalgorithmics421
12.3Adversaryarguments423
12.3.1Findingthemaximumofanarray424
12.3.2Testinggraphconnectivity425
12.3.3Themedianrevisited426
12.4Linearreductions427
12.4.1Formaldefinitions430
12.4.2Reductionsamongmatrixproblems433
12.4.3Reductionsamongshortestpathproblems438
12.5IntroductiontoNP-completeness441
12.5.1TheclassesPandNp441
12.5.2Polynomialreductions445
12.5.3NP-completeproblems450
12.5.4AfewNP-completenessproofs453
12.5.5Np-hardproblems457
12.5.6Nondeterministicalgorithms458
12.6Amenagerieofcomplexityclasses460
12.7Problems464
12.8Referencesandfurtherreading471
13HEURISTICANDAPPROXIMATEALGORITHMS
13.1Heuristicalgorithms475
13.1.1Colouringagraph475
13.1.2Thetravellingsalesperson477
13.2Approximatealgorithms478
13.2.1Themetrictravellingsalesperson478
13.2.2Theknapsackproblem(5)480
13.2.3Binpacking482
13.3NP-hardapproximationproblems484
13.3.1Hardabsoluteapproximationproblems486
13.3.2Hardrelativeapproximationproblems487
13.4Thesame,onlydifferent489
13.5Approximationschemes492
13.5.1Binpackingrevisited493
13.5.2Theknapsackproblem(6)493
13.6Problems496
13.7Referencesandfurtherreading500
REFERENCES
INDEX
猜您喜欢
