关闭

关闭

关闭

封号提示

内容

首页 算法概论[Algorithms].pdf

算法概论[Algorithms].pdf

算法概论[Algorithms].pdf

上传者: florajun1314 2011-10-28 评分 0 0 0 0 0 0 暂无简介 简介 举报

简介:本文档为《算法概论[Algorithms]pdf》,可适用于IT/计算机领域,主题内容包含AlgorithmsCopyrightcSDasgupta,CHPapadimitriou,andUVVaziraniJuly,ContentsPr符等。

AlgorithmsCopyrightcSDasgupta,CHPapadimitriou,andUVVaziraniJuly,ContentsPrefacePrologueBooksandalgorithmsEnterFibonacciBigOnotationExercisesAlgorithmswithnumbersBasicarithmeticModulararithmeticPrimalitytestingCryptographyUniversalhashingExercisesRandomizedalgorithms:avirtualchapterDivideandconqueralgorithmsMultiplicationRecurrencerelationsMergesortMediansMatrixmultiplicationThefastFouriertransformExercisesDecompositionsofgraphsWhygraphsDepthfirstsearchinundirectedgraphsDepthfirstsearchindirectedgraphsStronglyconnectedcomponentsExercisesPathsingraphsDistancesBreadthfirstsearchLengthsonedgesDijkstra’salgorithmPriorityqueueimplementationsShortestpathsinthepresenceofnegativeedgesShortestpathsindagsExercisesGreedyalgorithmsMinimumspanningtreesHuffmanencodingHornformulasSetcoverExercisesDynamicprogrammingShortestpathsindags,revisitedLongestincreasingsubsequencesEditdistanceKnapsackChainmatrixmultiplicationShortestpathsIndependentsetsintreesExercisesLinearprogrammingandreductionsAnintroductiontolinearprogrammingFlowsinnetworksBipartitematchingDualityZerosumgamesThesimplexalgorithmPostscript:circuitevaluationExercisesNPcompleteproblemsSearchproblemsNPcompleteproblemsThereductionsExercisesCopingwithNPcompletenessIntelligentexhaustivesearchApproximationalgorithmsLocalsearchheuristicsExercisesQuantumalgorithmsQubits,superposition,andmeasurementTheplanThequantumFouriertransformPeriodicityQuantumcircuitsFactoringasperiodicityThequantumalgorithmforfactoringExercisesHistoricalnotesandfurtherreadingIndexListofboxesBasesandlogsTwo’scomplementIsyoursocialsecuritynumberaprimeHey,thatwasgrouptheory!CarmichaelnumbersRandomizedalgorithms:avirtualchapterAnapplicationofnumbertheoryBinarysearchAnnlognlowerboundforsortingTheUnixsortcommandWhymultiplypolynomialsTheslowspreadofafastalgorithmHowbigisyourgraphCrawlingfastWhichheapisbestTreesArandomizedalgorithmforminimumcutEntropyRecursionNo,thanksProgrammingCommonsubproblemsOfmiceandmenMemoizationOntimeandmemoryAmagictrickcalleddualityReductionsMatrixvectornotationVisualizingdualityGaussianeliminationLinearprogramminginpolynomialtimeThestoryofSissaandMooreWhyPandNPThetwowaystousereductionsUnsolvableproblemsEntanglementTheFouriertransformofaperiodicvectorSettingupaperiodicsuperpositionQuantumphysicsmeetscomputationPrefaceThisbookevolvedoverthepasttenyearsfromasetoflecturenotesdevelopedwhileteachingtheundergraduateAlgorithmscourseatBerkeleyandUCSanDiegoOurwayofteachingthiscourseevolvedtremendouslyovertheseyearsinanumberofdirections,partlytoaddressourstudents’background(undevelopedformalskillsoutsideofprogramming),andpartlytoreflectthematuringofthefieldingeneral,aswehavecometoseeitThenotesincreasinglycrystallizedintoanarrative,andweprogressivelystructuredthecoursetoemphasizethe“storyline”implicitintheprogressionofthematerialAsaresult,thetopicswerecarefullyselectedandclusteredNoattemptwasmadetobeencyclopedic,andthisfreedustoincludetopicstraditionallydeemphasizedoromittedfrommostAlgorithmsbooksPlayingonthestrengthsofourstudents(sharedbymostoftoday’sundergraduatesinComputerScience),insteadofdwellingonformalproofswedistilledineachcasethecrispmathematicalideathatmakesthealgorithmworkInotherwords,weemphasizedrigoroverformalismWefoundthatourstudentsweremuchmorereceptivetomathematicalrigorofthisformItisthisprogressionofcrispideasthathelpsweavethestoryOnceyouthinkaboutAlgorithmsinthisway,itmakessensetostartatthehistoricalbeginningofitall,where,inaddition,thecharactersarefamiliarandthecontrastsdramatic:numbers,primality,andfactoringThisisthesubjectofPartIofthebook,whichalsoincludestheRSAcryptosystem,anddivideandconqueralgorithmsforintegermultiplication,sortingandmedianfinding,aswellasthefastFouriertransformTherearethreeotherparts:PartII,themosttraditionalsectionofthebook,concentratesondatastructuresandgraphsthecontrasthereisbetweentheintricatestructureoftheunderlyingproblemsandtheshortandcrisppiecesofpseudocodethatsolvethemInstructorswishingtoteachamoretraditionalcoursecansimplystartwithPartII,whichisselfcontained(followingtheprologue),andthencoverPartIasrequiredInPartsIandIIweintroducedcertaintechniques(suchasgreedyanddivideandconquer)whichworkforspecialkindsofproblemsPartIIIdealswiththe“sledgehammers”ofthetrade,techniquesthatarepowerfulandgeneral:dynamicprogramming(anovelapproachhelpsclarifythistraditionalstumblingblockforstudents)andlinearprogramming(acleanandintuitivetreatmentofthesimplexalgorithm,duality,andreductionstothebasicproblem)ThefinalPartIVisaboutwaysofdealingwithhardproblems:NPcompleteness,variousheuristics,aswellasquantumalgorithms,perhapsthemostadvancedandmoderntopicAsithappens,weendthestoryexactlywherewestartedit,withShor’squantumalgorithmforfactoringThebookincludesthreeadditionalundercurrents,intheformofthreeseriesofseparate“boxes,”strengtheningthenarrative(andaddressingvariationsintheneedsandinterestsofthestudents)whilekeepingtheflowintact:piecesthatprovidehistoricalcontextdescriptionsofhowtheexplainedalgorithmsareusedinpractice(withemphasisoninternetapplications)andexcursionsforthemathematicallysophisticatedChapterPrologueLookaroundyouComputersandnetworksareeverywhere,enablinganintricatewebofcomplexhumanactivities:education,commerce,entertainment,research,manufacturing,healthmanagement,humancommunication,evenwarOfthetwomaintechnologicalunderpinningsofthisamazingproliferation,oneisobvious:thebreathtakingpacewithwhichadvancesinmicroelectronicsandchipdesignhavebeenbringingusfasterandfasterhardwareThisbooktellsthestoryoftheotherintellectualenterprisethatiscruciallyfuelingthecomputerrevolution:efficientalgorithmsItisafascinatingstoryGather’roundandlistencloseBooksandalgorithmsTwoideaschangedtheworldInintheGermancityofMainzagoldsmithnamedJohannGutenbergdiscoveredawaytoprintbooksbyputtingtogethermovablemetallicpiecesLiteracyspread,theDarkAgesended,thehumanintellectwasliberated,scienceandtechnologytriumphed,theIndustrialRevolutionhappenedManyhistorianssayweoweallthistotypographyImagineaworldinwhichonlyanelitecouldreadtheselines!Butothersinsistthatthekeydevelopmentwasnottypography,butalgorithmsTodaywearesousedtowritingnumbersindecimal,thatitiseasytoforgetthatGutenbergwouldwritethenumberasMCDXLVIIIHowdoyouaddtwoRomannumeralsWhatisMCDXLVIIIDCCCXII(Andjusttrytothinkaboutmultiplyingthem)EvenaclevermanlikeGutenbergprobablyonlyknewhowtoaddandsubtractsmallnumbersusinghisfingersforanythingmorecomplicatedhehadtoconsultanabacusspecialistThedecimalsystem,inventedinIndiaaroundAD,wasarevolutioninquantitativereasoning:usingonlysymbols,evenverylargenumberscouldbewrittendowncompactly,andarithmeticcouldbedoneefficientlyonthembyfollowingelementarystepsNonethelesstheseideastookalongtimetospread,hinderedbytraditionalbarriersoflanguage,distance,andignoranceThemostinfluentialmediumoftransmissionturnedouttobeatextbook,writteninArabicintheninthcenturybyamanwholivedinBaghdadAlKhwarizmilaidoutthebasicmethodsforadding,multiplying,anddividingnumbersevenextractingsquarerootsandcalculatingdigitsofpiTheseprocedureswereprecise,unambiguous,mechanical,efficient,correctinshort,theywerealgorithms,atermcoinedtohonorthewisemanafterthedecimalsystemwasfinallyadoptedinEurope,manycenturieslaterSincethen,thisdecimalpositionalsystemanditsnumericalalgorithmshaveplayedanenormousroleinWesterncivilizationTheyenabledscienceandtechnologytheyacceleratedindustryandcommerceAndwhen,muchlater,thecomputerwasfinallydesigned,itexplicitlyembodiedthepositionalsysteminitsbitsandwordsandarithmeticunitScientistseverywherethengotbusydevelopingmoreandmorecomplexalgorithmsforallkindsofproblemsandinventingnovelapplicationsultimatelychangingtheworldEnterFibonacciAlKhwarizmi’sworkcouldnothavegainedafootholdintheWestwereitnotfortheeffortsofoneman:thethcenturyItalianmathematicianLeonardoFibonacci,whosawthepotentialofthepositionalsystemandworkedhardtodevelopitfurtherandpropagandizeitButtodayFibonacciismostwidelyknownforhisfamoussequenceofnumbers,,,,,,,,,,,eachthesumofitstwoimmediatepredecessorsMoreformally,theFibonaccinumbersFnaregeneratedbythesimpleruleFn=FnFnifn>ifn=ifn=Noothersequenceofnumbershasbeenstudiedasextensively,orappliedtomorefields:biology,demography,art,architecture,music,tonamejustafewAnd,togetherwiththepowersof,itiscomputerscience’sfavoritesequenceInfact,theFibonaccinumbersgrowalmostasfastasthepowersof:forexample,Fisoveramillion,andFisalreadydigitslong!Ingeneral,Fnn(seeExercise)ButwhatistheprecisevalueofF,orofFFibonaccihimselfwouldsurelyhavewantedtoknowsuchthingsToanswer,weneedanalgorithmforcomputingthenthFibonaccinumberAnexponentialalgorithmOneideaistoslavishlyimplementtherecursivedefinitionofFnHereistheresultingalgorithm,inthe“pseudocode”notationusedthroughoutthisbook:functionfib(n)ifn=:returnifn=:returnreturnfib(n)fib(n)Wheneverwehaveanalgorithm,therearethreequestionswealwaysaskaboutit:IsitcorrectHowmuchtimedoesittake,asafunctionofnAndcanwedobetterThefirstquestionismoothere,asthisalgorithmispreciselyFibonacci’sdefinitionofFnButtheseconddemandsananswerLetT(n)bethenumberofcomputerstepsneededtocomputefib(n)whatcanwesayaboutthisfunctionForstarters,ifnislessthan,theprocedurehaltsalmostimmediately,afterjustacoupleofstepsTherefore,T(n)fornForlargervaluesofn,therearetworecursiveinvocationsoffib,takingtimeT(n)andT(n),respectively,plusthreecomputersteps(checksonthevalueofnandafinaladdition)Therefore,T(n)=T(n)T(n)forn>ComparethistotherecurrencerelationforFn:weimmediatelyseethatT(n)FnThisisverybadnews:therunningtimeofthealgorithmgrowsasfastastheFibonaccinumbers!T(n)isexponentialinn,whichimpliesthatthealgorithmisimpracticallyslowexceptforverys

职业精品

热点搜索换一换

用户评论

0/200
    暂无评论

精彩专题

上传我的资料

热门资料

资料评价:

/49
仅支持在线阅读

意见
反馈

返回
顶部