加入VIP
  • 专属下载特权
  • 现金文档折扣购买
  • VIP免费专区
  • 千万文档免费下载

上传资料

关闭

关闭

关闭

封号提示

内容

首页 算法导论_中文版_第三版

算法导论_中文版_第三版.pdf

算法导论_中文版_第三版

横天liang
2012-07-29 0人阅读 举报 0 0 暂无简介

简介:本文档为《算法导论_中文版_第三版pdf》,可适用于工程科技领域

ALGORITHMSINTRODUCTIONTOTHIRDEDITIONTHOMASHCHARLESERONALDLCLIFFORDSTEINRIVESTLEISERSONCORMENIntroductiontoAlgorithmsThirdEditionThomasHCormenCharlesELeisersonRonaldLRivestCliffordSteinIntroductiontoAlgorithmsThirdEditionTheMITPressCambridge,MassachusettsLondon,Englandc�MassachusettsInstituteofTechnologyAllrightsreservedNopartofthisbookmaybereproducedinanyformorbyanyelectronicormechanicalmeans(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,tomakethisabookthatwillbeusefultoyounowasacoursetextbookandalsolaterinyourcareerasamathematicaldeskreferenceoranengineeringhandbookPrefacexvWhataretheprerequisitesforreadingthisbook�YoushouldhavesomeprogrammingexperienceInparticular,youshouldunderstandrecursiveproceduresandsimpledatastructuressuchasarraysandlinkedlists�Youshouldhavesomefacilitywithmathematicalproofs,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,andwehavebrokenoutmaterialonmatrixbasicsintoitsownappendixchapter�Werevisedthechapteronrecurrencestomorebroadlycoverthedivideandconquertechnique,anditsfirsttwosectionsapplydivideandconquertosolvetwoproblemsThesecondsectionofthischapterpresentsStrassen’salgorithmformatrixmultiplication,whichwehavemovedfromthechapteronmatrixoperations�Weremovedtwochaptersthatwererarelytaught:binomialheapsandsortingnetworksOnekeyideainthesortingnetworkschapter,theprinciple,appearsinthiseditionwithinProblemasthesortinglemmaforcompareexchangealgorithmsThetreatmentofFibonacciheapsnolongerreliesonbinomialheapsasaprecursorPrefacexvii�WerevisedourtreatmentofdynamicprogrammingandgreedyalgorithmsDynamicprogrammingnowleadsoffwithamoreinterestingproblem,rodcutting,thantheassemblylineschedulingproblemfromthesecondeditionFurthermore,weemphasizememoizationabitmorethanwedidinthesecondedition,andweintroducethenotionofthesubproblemgraphasawaytounderstandtherunningtimeofadynamicprogrammingalgorithmInouropeningexampleofgreedyalgorithms,theactivityselectionproblem,wegettothegreedyalgorithmmoredirectlythanwedidinthesecondedition�Thewaywedeleteanodefrombinarysearchtrees(whichincludesredblacktrees)nowguaranteesthatthenoderequestedfordeletionisthenodethatisactuallydeletedInthefirsttwoeditions,incertaincases,someothernodewouldbedeleted,withitscontentsmovingintothenodepassedtothedeletionprocedureWithournewwaytodeletenodes,ifothercomponentsofaprogrammaintainpointerstonodesinthetree,theywillnotmistakenlyendupwithstalepointerstonodesthathavebeendeleted�ThematerialonflownetworksnowbasesflowsentirelyonedgesThisapproachismoreintuitivethanthenetflowusedinthefirsttwoeditions�WiththematerialonmatrixbasicsandStrassen’salgorithmmovedtootherchapters,thechapteronmatrixoperationsissmallerthaninthesecondedition�WehavemodifiedourtreatmentoftheKnuthMorrisPrattstringmatchingalgorithm�WecorrectedseveralerrorsMostoftheseerrorswerepostedonourWebsiteofsecondeditionerrata,butafewwerenot�Basedonmanyrequests,wechangedthesyntax(asitwere)ofourpseudocodeWenowuse“D”toindicateassi

用户评价(4)

  • 孟懿 挺不错的,只不过跟标题不怎么符合,是英文版的

    2013-06-03 08:22:46

  • 孟懿 挺不错的

    2013-06-03 08:21:42

  • xu4v 英文高清版,还是不错的,总比中文扫描,有没有书签的好吧

    2013-04-25 20:42:10

  • 10.69.3.32 英文版

    2012-07-30 18:00:25

关闭

新课改视野下建构高中语文教学实验成果报告(32KB)

抱歉,积分不足下载失败,请稍后再试!

提示

试读已结束,如需要继续阅读或者下载,敬请购买!

文档小程序码

使用微信“扫一扫”扫码寻找文档

1

打开微信

2

扫描小程序码

3

发布寻找信息

4

等待寻找结果

我知道了
评分:

/49

算法导论_中文版_第三版

仅供在线阅读

VIP

在线
客服

免费
邮箱

爱问共享资料服务号

扫描关注领取更多福利