关闭

关闭

封号提示

内容

首页 算法导论 第三版.pdf

算法导论 第三版.pdf

算法导论 第三版.pdf

上传者: 流血浆 2013-03-26 评分 5 0 177 24 805 暂无简介 简介 举报

简介:本文档为《算法导论 第三版pdf》,可适用于IT/计算机领域,主题内容包含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

类似资料

该用户的其他资料

白话c++.pdf

C程序设计语言_第2版新版.pdf

C专家编程.pdf

hadoop权威指南.pdf

Linux内核设计的艺术.pdf

职业精品

精彩专题

上传我的资料

精选资料

热门资料排行换一换

  • [Algebraic.Numbe…

  • 陈寅恪晚年诗文释证(余英时)19…

  • 《邓广铭宋史人物书系:韩世忠年谱…

  • ANSYS进阶培训(ANSYS驻…

  • 18.《电子计算机机房设计规范》…

  • [高质量程序设计指南.C.C语言…

  • “文革”时期知识分子抗争述论.p…

  • 人权研究(第5卷) 徐显明主编.…

  • 人权研究(第4卷) 徐显明主编.…

  • 资料评价:

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

    意见
    反馈

    返回
    顶部