首页 算法导论 第三版.pdf

算法导论 第三版.pdf

算法导论 第三版.pdf

上传者: 流血浆 2013-03-26 评分1 评论0 下载57 收藏0 阅读量805 暂无简介 简介 举报

简介:本文档为《算法导论 第三版pdf》,可适用于专题技术领域,主题内容包含ALGORITHMSINTRODUCTIONTOTHIRDEDITIONTHOMASHCHARLESERONALDLCLIFFORDSTEINRIV符等。

ALGORITHMSINTRODUCTIONTOTHIRDEDITIONTHOMASHCHARLESERONALDLCLIFFORDSTEINRIVESTLEISERSONCORMENIntroductiontoAlgorithmsThirdEditionThomasHCormenCharlesELeisersonRonaldLRivestCliffordSteinIntroductiontoAlgorithmsThirdEditionTheMITPressCambridge,MassachusettsLondon,EnglandcMassachusettsInstituteofTechnologyAllrightsreservedNopartofthisbookmaybereproducedinanyformorbyanyelectronicormechanicalmeans(includingphotocopying,recording,orinformationstorageandretrieval)withoutpermissioninwritingfromthepublisherForinformationaboutspecialquantitydiscounts,pleaseemailspecialsalesmitpressmiteduThisbookwassetinTimesRomanandMathtimeProbytheauthorsPrintedandboundintheUnitedStatesofAmericaLibraryofCongressCataloginginPublicationDataIntroductiontoalgorithmsThomasHCormenetalrdedpcmIncludesbibliographicalreferencesandindexISBN(hardcover:alkpaper)ISBN(pbk:alkpaper)ComputerprogrammingComputeralgorithmsICormen,ThomasHQAIdcContentsPrefacexiiiIFoundationsIntroductionTheRoleofAlgorithmsinComputingAlgorithmsAlgorithmsasatechnologyGettingStartedInsertionsortAnalyzingalgorithmsDesigningalgorithmsGrowthofFunctionsAsymptoticnotationStandardnotationsandcommonfunctionsDivideandConquerThemaximumsubarrayproblemStrassen’salgorithmformatrixmultiplicationThesubstitutionmethodforsolvingrecurrencesTherecursiontreemethodforsolvingrecurrencesThemastermethodforsolvingrecurrencesProofofthemastertheoremProbabilisticAnalysisandRandomizedAlgorithmsThehiringproblemIndicatorrandomvariablesRandomizedalgorithmsProbabilisticanalysisandfurtherusesofindicatorrandomvariablesviContentsIISortingandOrderStatisticsIntroductionHeapsortHeapsMaintainingtheheappropertyBuildingaheapTheheapsortalgorithmPriorityqueuesQuicksortDescriptionofquicksortPerformanceofquicksortArandomizedversionofquicksortAnalysisofquicksortSortinginLinearTimeLowerboundsforsortingCountingsortRadixsortBucketsortMediansandOrderStatisticsMinimumandmaximumSelectioninexpectedlineartimeSelectioninworstcaselineartimeIIIDataStructuresIntroductionElementaryDataStructuresStacksandqueuesLinkedlistsImplementingpointersandobjectsRepresentingrootedtreesHashTablesDirectaddresstablesHashtablesHashfunctionsOpenaddressingPerfecthashingContentsviiBinarySearchTreesWhatisabinarysearchtreeQueryingabinarysearchtreeInsertionanddeletionRandomlybuiltbinarysearchtreesRedBlackTreesPropertiesofredblacktreesRotationsInsertionDeletionAugmentingDataStructuresDynamicorderstatisticsHowtoaugmentadatastructureIntervaltreesIVAdvancedDesignandAnalysisTechniquesIntroductionDynamicProgrammingRodcuttingMatrixchainmultiplicationElementsofdynamicprogrammingLongestcommonsubsequenceOptimalbinarysearchtreesGreedyAlgorithmsAnactivityselectionproblemElementsofthegreedystrategyHuffmancodesMatroidsandgreedymethodsAtaskschedulingproblemasamatroidAmortizedAnalysisAggregateanalysisTheaccountingmethodThepotentialmethodDynamictablesviiiContentsVAdvancedDataStructuresIntroductionBTreesDefinitionofBtreesBasicoperationsonBtreesDeletingakeyfromaBtreeFibonacciHeapsStructureofFibonacciheapsMergeableheapoperationsDecreasingakeyanddeletinganodeBoundingthemaximumdegreevanEmdeBoasTreesPreliminaryapproachesArecursivestructureThevanEmdeBoastreeDataStructuresforDisjointSetsDisjointsetoperationsLinkedlistrepresentationofdisjointsetsDisjointsetforestsAnalysisofunionbyrankwithpathcompressionVIGraphAlgorithmsIntroductionElementaryGraphAlgorithmsRepresentationsofgraphsBreadthfirstsearchDepthfirstsearchTopologicalsortStronglyconnectedcomponentsMinimumSpanningTreesGrowingaminimumspanningtreeThealgorithmsofKruskalandPrimContentsixSingleSourceShortestPathsTheBellmanFordalgorithmSinglesourceshortestpathsindirectedacyclicgraphsDijkstra’salgorithmDifferenceconstraintsandshortestpathsProofsofshortestpathspropertiesAllPairsShortestPathsShortestpathsandmatrixmultiplicationTheFloydWarshallalgorithmJohnson’salgorithmforsparsegraphsMaximumFlowFlownetworksTheFordFulkersonmethodMaximumbipartitematchingPushrelabelalgorithmsTherelabeltofrontalgorithmVIISelectedTopicsIntroductionMultithreadedAlgorithmsThebasicsofdynamicmultithreadingMultithreadedmatrixmultiplicationMultithreadedmergesortMatrixOperationsSolvingsystemsoflinearequationsInvertingmatricesSymmetricpositivedefinitematricesandleastsquaresapproximationLinearProgrammingStandardandslackformsFormulatingproblemsaslinearprogramsThesimplexalgorithmDualityTheinitialbasicfeasiblesolutionxContentsPolynomialsandtheFFTRepresentingpolynomialsTheDFTandFFTEfficientFFTimplementationsNumberTheoreticAlgorithmsElementarynumbertheoreticnotionsGreatestcommondivisorModulararithmeticSolvingmodularlinearequationsTheChineseremaindertheoremPowersofanelementTheRSApublickeycryptosystemPrimalitytestingIntegerfactorizationStringMatchingThenaivestringmatchingalgorithmTheRabinKarpalgorithmStringmatchingwithfiniteautomataTheKnuthMorrisPrattalgorithmComputationalGeometryLinesegmentpropertiesDeterminingwhetheranypairofsegmentsintersectsFindingtheconvexhullFindingtheclosestpairofpointsNPCompletenessPolynomialtimePolynomialtimeverificationNPcompletenessandreducibilityNPcompletenessproofsNPcompleteproblemsApproximationAlgorithmsThevertexcoverproblemThetravelingsalesmanproblemThesetcoveringproblemRandomizationandlinearprogrammingThesubsetsumproblemContentsxiVIIIAppendix:MathematicalBackgroundIntroductionASummationsASummationformulasandpropertiesABoundingsummationsBSets,EtcBSetsBRelationsBFunctionsBGraphsBTreesCCountingandProbabilityCCountingCProbabilityCDiscreterandomvariablesCThegeometricandbinomialdistributionsCThetailsofthebinomialdistributionDMatricesDMatricesandmatrixoperationsDBasicmatrixpropertiesBibliographyIndexPrefaceBeforetherewerecomputers,therewerealgorithmsButnowthattherearecomputers,thereareevenmorealgorithms,andalgorithmslieattheheartofcomputingThisbookprovidesacomprehensiveintroductiontothemodernstudyofcomputeralgorithmsItpresentsmanyalgorithmsandcoverstheminconsiderabledepth,yetmakestheirdesignandanalysisaccessibletoalllevelsofreadersWehavetriedtokeepexplanationselementarywithoutsacrificingdepthofcoverageormathematicalrigorEachchapterpresentsanalgorithm,adesigntechnique,anapplicationarea,orarelatedtopicAlgorithmsaredescribedinEnglishandinapseudocodedesignedtobereadablebyanyonewhohasdonealittleprogrammingThebookcontainsfiguresmanywithmultiplepartsillustratinghowthealgorithmsworkSinceweemphasizeefficiencyasadesigncriterion,weincludecarefulanalysesoftherunningtimesofallouralgorithmsThetextisintendedprimarilyforuseinundergraduateorgraduatecoursesinalgorithmsordatastructuresBecauseitdiscussesengineeringissuesinalgorithmdesign,aswellasmathematicalaspects,itisequallywellsuitedforselfstudybytechnicalprofessionalsInthis,thethirdedition,wehaveonceagainupdatedtheentirebookThechangescoverabroadspectrum,includingnewchapters,revisedpseudocode,andamoreactivewritingstyleTotheteacherWehavedesignedthisbooktobebothversatileandcompleteYoushouldfinditusefulforavarietyofcourses,fromanundergraduatecourseindatastructuresupthroughagraduatecourseinalgorithmsBecausewehaveprovidedconsiderablymorematerialthancanfitinatypicalonetermcourse,youcanconsiderthisbooktobea“buffet”or“smorgasbord”fromwhichyoucanpickandchoosethematerialthatbestsupportsthecourseyouwishtoteachxivPrefaceYoushouldfinditeasytoorganizeyourcoursearoundjustthechaptersyouneedWehavemadechaptersrelativelyselfcontained,sothatyouneednotworryaboutanunexpectedandunnecessarydependenceofonechapteronanotherEachchapterpresentstheeasiermaterialfirstandthemoredifficultmateriallater,withsectionboundariesmarkingnaturalstoppingpointsInanundergraduatecourse,youmightuseonlytheearliersectionsfromachapterinagraduatecourse,youmightcovertheentirechapterWehaveincludedexercisesandproblemsEachsectionendswithexercises,andeachchapterendswithproblemsTheexercisesaregenerallyshortquestionsthattestbasicmasteryofthematerialSomearesimpleselfcheckthoughtexercises,whereasothersaremoresubstantialandaresuitableasassignedhomeworkTheproblemsaremoreelaboratecasestudiesthatoftenintroducenewmaterialtheyoftenconsistofseveralquestionsthatleadthestudentthroughthestepsrequiredtoarriveatasolutionDepartingfromourpracticeinpreviouseditionsofthisbook,wehavemadepubliclyavailablesolutionstosome,butbynomeansall,oftheproblemsandexercisesOurWebsite,http:mitpressmitedualgorithms,linkstothesesolutionsYouwillwanttocheckthissitetomakesurethatitdoesnotcontainthesolutiontoanexerciseorproblemthatyouplantoassignWeexpectthesetofsolutionsthatweposttogrowslowlyovertime,soyouwillneedtocheckiteachtimeyouteachthecourseWehavestarred()thesectionsandexercisesthataremoresuitableforgraduatestudentsthanforundergraduatesAstarredsectionisnotnecessarilymoredifficultthananunstarredone,butitmayrequireanunderstandingofmoreadvancedmathematicsLikewise,starredexercisesmayrequireanadvancedbackgroundormorethanaveragecreativityTothestudentWehopethatthistextbookprovidesyouwithanenjoyableintroductiontothefieldofalgorithmsWehaveattemptedtomakeeveryalgorithmaccessibleandinterestingTohelpyouwhenyouencounterunfamiliarordifficultalgorithms,wedescribeeachoneinastepbystepmannerWealsoprovidecarefulexplanationsofthemathematicsneededtounderstandtheanalysisofthealgorithmsIfyoualreadyhavesomefamiliaritywithatopic,youwillfindthechaptersorganizedsothatyoucanskimintroductorysectionsandproceedquicklytothemoreadvancedmaterialThisisalargebook,andyourclasswillprobablycoveronlyaportionofitsmaterialWehavetried,however,tomakethisabookthatwillbeusefultoyounowasacoursetextbookandalsolaterinyourcareerasamathematicaldeskreferenceoranengineeringhandbookPrefacexvWhataretheprerequisitesforreadingthisbookYoushouldhavesomeprogrammingexperienceInparticular,youshouldunderstandrecursiveproceduresandsimpledatastructuressuchasarraysandlinkedlistsYoushouldhavesomefacilitywithmathematicalproofs,andespeciallyproofsbymathematicalinductionAfewportionsofthebookrelyonsomeknowledgeofelementarycalculusBeyondthat,PartsIandVIIIofthisbookteachyouallthemathematicaltechniquesyouwillneedWehaveheard,loudandclear,thecalltosupplysolutionstoproblemsandexercisesOurWebsite,http:mitpressmitedualgorithms,linkstosolutionsforafewoftheproblemsandexercisesFeelfreetocheckyoursolutionsagainstoursWeask,however,thatyoudonotsendyoursolutionstousTotheprofessionalThewiderangeoftopicsinthisbookmakesitanexcellenthandbookonalgorithmsBecauseeachchapterisrelativelyselfcontained,youcanfocusinonthetopicsthatmostinterestyouMostofthealgorithmswediscusshavegreatpracticalutilityWethereforeaddressimplementationconcernsandotherengineeringissuesWeoftenprovidepracticalalternativestothefewalgorithmsthatareprimarilyoftheoreticalinterestIfyouwishtoimplementanyofthealgorithms,youshouldfindthetranslationofourpseudocodeintoyourfavoriteprogramminglanguagetobeafairlystraightforwardtaskWehavedesignedthepseudocodetopresenteachalgorithmclearlyandsuccinctlyConsequently,wedonotaddresserrorhandlingandothersoftwareengineeringissuesthatrequirespecificassumptionsaboutyourprogrammingenvironmentWeattempttopresenteachalgorithmsimplyanddirectlywithoutallowingtheidiosyncrasiesofaparticularprogramminglanguagetoobscureitsessenceWeunderstandthatifyouareusingthisbookoutsideofacourse,thenyoumightbeunabletocheckyoursolutionstoproblemsandexercisesagainstsolutionsprovidedbyaninstructorOurWebsite,http:mitpressmitedualgorithms,linkstosolutionsforsomeoftheproblemsandexercisessothatyoucancheckyourworkPleasedonotsendyoursolutionstousToourcolleaguesWehavesuppliedanextensivebibliographyandpointerstothecurrentliteratureEachchapterendswithasetofchapternotesthatgivehistoricaldetailsandreferencesThechapternotesdonotprovideacompletereferencetothewholefieldxviPrefaceofalgorithms,howeverThoughitmaybehardtobelieveforabookofthissize,spaceconstraintspreventedusfromincludingmanyinterestingalgorithmsDespitemyriadrequestsfromstudentsforsolutionstoproblemsandexercises,wehavechosenasamatterofpolicynottosupplyreferencesforproblemsandexercises,toremovethetemptationforstudentstolookupasolutionratherthantofinditthemselvesChangesforthethirdeditionWhathaschangedbetweenthesecondandthirdeditionsofthisbookThemagnitudeofthechangesisonaparwiththechangesbetweenthefirstandsecondeditionsAswesaidaboutthesecondeditionchanges,dependingonhowyoulookatit,thebookchangedeithernotmuchorquiteabitAquicklookatthetableofcontentsshowsthatmostofthesecondeditionchaptersandsectionsappearinthethirdeditionWeremovedtwochaptersandonesection,butwehaveaddedthreenewchaptersandtwonewsectionsapartfromthesenewchaptersWekeptthehybridorganizationfromthefirsttwoeditionsRatherthanorganizingchaptersbyonlyproblemdomainsoraccordingonlytotechniques,thisbookhaselementsofbothItcontainstechniquebasedchaptersondivideandconquer,dynamicprogramming,greedyalgorithms,amortizedanalysis,NPCompleteness,andapproximationalgorithmsButitalsohasentirepartsonsorting,ondatastructuresfordynamicsets,andonalgorithmsforgraphproblemsWefindthatalthoughyouneedtoknowhowtoapplytechniquesfordesigningandanalyzingalgorithms,problemsseldomannouncetoyouwhichtechniquesaremostamenabletosolvingthemHereisasummaryofthemostsignificantchangesforthethirdedition:WeaddednewchaptersonvanEmdeBoastreesandmultithreadedalgorithms,andwehavebrokenoutmaterialonmatrixbasicsintoitsownappendixchapterWerevisedthechapteronrecurrencestomorebroadlycoverthedivideandconquertechnique,anditsfirsttwosectionsapplydivideandconquertosolvetwoproblemsThesecondsectionofthischapterpresentsStrassen’salgorithmformatrixmultiplication,whichwehavemovedfromthechapteronmatrixoperationsWeremovedtwochaptersthatwererarelytaught:binomialheapsandsortingnetworksOnekeyideainthesortingnetworkschapter,theprinciple,appearsinthiseditionwithinProblemasthesortinglemmaforcompareexchangealgorithmsThetreatmentofFibonacciheapsnolongerreliesonbinomialheapsasaprecursorPrefacexviiWerevisedourtreatmentofdynamicprogrammingandgreedyalgorithmsDynamicprogrammingnowleadsoffwithamoreinterestingproblem,rodcutting,thantheassemblylineschedulingproblemfromthesecondeditionFurthermore,weemphasizememoizationabitmorethanwedidinthesecondedition,andweintroducethenotionofthesubproblemgraphasawaytounderstandtherunningtimeofadynamicprogrammingalgorithmInouropeningexampleofgreedyalgorithms,theactivityselectionproblem,wegettothegreedyalgorithmmoredirectlythanwedidinthesecondeditionThewaywedeleteanodefrombinarysearchtrees(whichincludesredblacktrees)nowguaranteesthatthenoderequestedfordeletionisthenodethatisactuallydeletedInthefirsttwoeditions,incertaincases,someothernodewouldbedeleted,withitscontentsmovingintothenodepassedtothedeletionprocedureWithournewwaytodeletenodes,ifothercomponentsofaprogrammaintainpointerstonodesinthetree,theywillnotmistakenlyendupwithstalepointerstonodesthathavebeendeletedThematerialonflownetworksnowbasesflowsentirelyonedgesThisapproachismoreintuitivethanthenetflowusedinthefirsttwoeditionsWiththematerialonmatrixbasicsandStrassen’salgorithmmovedtootherchapters,thechapteronmatrixoperationsissmallerthaninthesecondeditionWehavemodifiedourtreatmentoftheKnuthMorrisPrattstringmatchingalgorithmWecorrectedseveralerrorsMostoftheseerrorswerepostedonourWebsiteofsecondeditionerrata,butafewwerenotBasedonmanyrequests,wechangedthesyntax(asitwere)ofourpseudocodeWenowuse“D”toindicateassi

职业精品

分销渠道选择.ppt

辞职申请书(优质范文).doc

公司年检申请书doc.doc

厂家和经销商代理合同.doc

用户评论

0/200
    暂无评论
上传我的资料

精彩专题

相关资料换一换

资料评价:

/ 1313
所需积分:0 立即下载

意见
反馈

返回
顶部