algorithms and complexity - wilf

《algorithms and complexity - wilf》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、AlgorithmsandComplexityHerbertS.WilfUniversityofPennsylvaniaPhiladelphia,PA19104-6395CopyrightNoticeCopyright1994byHerbertS.Wilf.Thismaterialmaybereproducedforanyeducationalpurpose,multiplecopiesmaybemadeforclasses,etc.Charges,ifany,forreproducedcopiesmustbejustenoughtorecoverreasonablecostsof

2、reproduction.Reproductionforcommercialpurposesisprohibited.Thiscoverpagemustbeincludedinalldistributedcopies.InternetEdition,Summer,1994ThiseditionofAlgorithmsandComplexityisthe¯lepub/wilf/AlgComp.ps.Z"attheanonymousftpsiteftp.cis.upenn.edu".Itmaybetakenatnochargebyallinterestedpersons.Comme

3、ntsandcorrectionsarewelcome,andshouldbesenttowilf@central.cis.upenn.eduCONTENTSChapter0:WhatThisBookIsAbout0.1Background......................................10.2Hardvs.easyproblems.................................20.3Apreview.......................................4Chapter1:MathematicalPrelimi

4、naries1.1Ordersofmagnitude..................................51.2Positionalnumbersystems...............................111.3Manipulationswithseries...............................141.4Recurrencerelations..................................161.5Counting......................................211.6Gra

5、phs.......................................24Chapter2:RecursiveAlgorithms2.1Introduction.....................................302.2Quicksort......................................312.3Recursivegraphalgorithms...............................382.4Fastmatrixmultiplication.............................

6、..472.5ThediscreteFouriertransform.............................502.6ApplicationsoftheFFT................................562.7Areview.......................................60Chapter3:TheNetworkFlowProblem3.1Introduction.....................................633.2Algorithmsforthenetwork°owproblem.

7、........................643.3ThealgorithmofFordandFulkerson..........................653.4Themax-°owmin-cuttheorem.............................693.5ThecomplexityoftheFord-Fulkersonalgorithm.....................703.6Layerednetworks......