算法基礎(chǔ)：英文版

定　價(jià)：￥35.00

作　者：	Gilles Brassard，Paul Bratly著
出版社：	清華大學(xué)出版社
叢編項(xiàng)：	大學(xué)計(jì)算機(jī)教育國(guó)外著名教材系列
標(biāo)　簽：	算法

購(gòu)買(mǎi)這本書(shū)可以去

ISBN：	9787302111559	出版時(shí)間：	2005-07-01	包裝：	平裝
開(kāi)本：	21cm	頁(yè)數(shù)：	515	字?jǐn)?shù)：

內(nèi)容簡(jiǎn)介

　　本書(shū)足關(guān)于算法導(dǎo)論的經(jīng)典教材，書(shū)中包括大量例題解答與命題證明。本書(shū)是按照算法類(lèi)型而不是按照應(yīng)用類(lèi)型對(duì)算法進(jìn)行介紹，以其清晰的概念講解贏得專(zhuān)家們的廣泛贊譽(yù)。本書(shū)適用對(duì)象廣泛。對(duì)于學(xué)習(xí)算法設(shè)計(jì)與分析的本科生和研究生，本書(shū)足優(yōu)選教材。對(duì)于從事算法計(jì)算研究和工程應(yīng)用的科研人員和工程技術(shù)人員，本書(shū)也是一本優(yōu)秀的基礎(chǔ)性讀物。本書(shū)翻譯版已出版，書(shū)號(hào)為7-302一10609-6。

作者簡(jiǎn)介

暫缺《算法基礎(chǔ)：英文版》作者簡(jiǎn)介

圖書(shū)目錄

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