- 2022-08-30 发布 |
- 37.5 KB |
- 318页
申明敬告: 本站不保证该用户上传的文档完整性,不预览、不比对内容而直接下载产生的反悔问题本站不予受理。
文档介绍
Algorithm计算机算法
AlgorithmsCopyrightc2006S.Dasgupta,C.H.Papadimitriou,andU.V.VaziraniJuly18,2006\n2\nContentsPreface90Prologue110.1Booksandalgorithms...................................110.2EnterFibonacci......................................120.3Big-Onotation.......................................15Exercises.............................................181Algorithmswithnumbers211.1Basicarithmetic......................................211.2Modulararithmetic....................................251.3Primalitytesting.....................................331.4Cryptography.......................................381.5Universalhashing.....................................42Exercises.............................................46Randomizedalgorithms:avirtualchapter382Divide-and-conqueralgorithms512.1Multiplication.......................................512.2Recurrencerelations...................................532.3Mergesort..........................................562.4Medians...........................................602.5Matrixmultiplication...................................622.6ThefastFouriertransform................................64Exercises.............................................793Decompositionsofgraphs873.1Whygraphs?........................................873.2Depth-rstsearchinundirectedgraphs........................893.3Depth-rstsearchindirectedgraphs..........................943.4Stronglyconnectedcomponents.............................97Exercises.............................................1013\n4Pathsingraphs1094.1Distances..........................................1094.2Breadth-rstsearch....................................1104.3Lengthsonedges.....................................1124.4Dijkstra'salgorithm....................................1124.5Priorityqueueimplementations.............................1204.6Shortestpathsinthepresenceofnegativeedges...................1224.7Shortestpathsindags..................................124Exercises.............................................1265Greedyalgorithms1335.1Minimumspanningtrees.................................1335.2Huffmanencoding.....................................1465.3Hornformulas.......................................1515.4Setcover..........................................152Exercises.............................................1556Dynamicprogramming1616.1Shortestpathsindags,revisited............................1616.2Longestincreasingsubsequences............................1626.3Editdistance........................................1656.4Knapsack..........................................1716.5Chainmatrixmultiplication...............................1746.6Shortestpaths.......................................1756.7Independentsetsintrees.................................179Exercises.............................................1817Linearprogrammingandreductions1897.1Anintroductiontolinearprogramming........................1897.2Flowsinnetworks.....................................1997.3Bipartitematching....................................2067.4Duality...........................................2077.5Zero-sumgames......................................2107.6Thesimplexalgorithm..................................2137.7Postscript:circuitevaluation..............................222Exercises.............................................2258NP-completeproblems2338.1Searchproblems......................................2338.2NP-completeproblems..................................2438.3Thereductions.......................................247Exercises.............................................2634\n9CopingwithNP-completeness2699.1Intelligentexhaustivesearch..............................2709.2Approximationalgorithms................................2759.3Localsearchheuristics..................................282Exercises.............................................29110Quantumalgorithms29510.1Qubits,superposition,andmeasurement.......................29510.2Theplan..........................................29910.3ThequantumFouriertransform............................30010.4Periodicity.........................................30210.5Quantumcircuits.....................................30410.6Factoringasperiodicity..................................30710.7Thequantumalgorithmforfactoring..........................308Exercises.............................................311Historicalnotesandfurtherreading313Index3155\n6\nListofboxesBasesandlogs..........................................21Two'scomplement........................................27Isyoursocialsecuritynumberaprime?...........................32Hey,thatwasgrouptheory!..................................35Carmichaelnumbers......................................36Randomizedalgorithms:avirtualchapter..........................37Anapplicationofnumbertheory?...............................39Binarysearch..........................................55Annlognlowerboundforsorting...............................58TheUnixsortcommand...................................62Whymultiplypolynomials?..................................65Theslowspreadofafastalgorithm..............................78Howbigisyourgraph?.....................................89Crawlingfast..........................................100Whichheapisbest?.......................................119Trees...............................................134Arandomizedalgorithmforminimumcut..........................143Entropy..............................................149Recursion?No,thanks......................................164Programming?..........................................164Commonsubproblems.....................................169Ofmiceandmen.........................................170Memoization...........................................173Ontimeandmemory......................................179Amagictrickcalledduality..................................193Reductions............................................197Matrix-vectornotation.....................................198Visualizingduality.......................................210Gaussianelimination......................................220Linearprogramminginpolynomialtime...........................222ThestoryofSissaandMoore.................................2337\nWhyPandNP?.........................................243Thetwowaystousereductions................................245Unsolvableproblems......................................262Entanglement..........................................298TheFouriertransformofaperiodicvector..........................303Settingupaperiodicsuperposition..............................307Quantumphysicsmeetscomputation............................3108\nPrefaceThisbookevolvedoverthepasttenyearsfromasetoflecturenotesdevelopedwhileteachingtheundergraduateAlgorithmscourseatBerkeleyandU.C.SanDiego.Ourwayofteachingthiscourseevolvedtremendouslyovertheseyearsinanumberofdirections,partlytoaddressourstudents'background(undevelopedformalskillsoutsideofprogramming),andpartlytoreectthematuringoftheeldingeneral,aswehavecometoseeit.Thenotesincreasinglycrystallizedintoanarrative,andweprogressivelystructuredthecoursetoemphasizethe“storyline”implicitintheprogressionofthematerial.Asaresult,thetopicswerecarefullyselectedandclustered.Noattemptwasmadetobeencyclopedic,andthisfreedustoincludetopicstraditionallyde-emphasizedoromittedfrommostAlgorithmsbooks.Playingonthestrengthsofourstudents(sharedbymostoftoday'sundergraduatesinComputerScience),insteadofdwellingonformalproofswedistilledineachcasethecrispmathematicalideathatmakesthealgorithmwork.Inotherwords,weemphasizedrigoroverformalism.Wefoundthatourstudentsweremuchmorereceptivetomathematicalrigorofthisform.Itisthisprogressionofcrispideasthathelpsweavethestory.OnceyouthinkaboutAlgorithmsinthisway,itmakessensetostartatthehistoricalbe-ginningofitall,where,inaddition,thecharactersarefamiliarandthecontrastsdramatic:numbers,primality,andfactoring.ThisisthesubjectofPartIofthebook,whichalsoin-cludestheRSAcryptosystem,anddivide-and-conqueralgorithmsforintegermultiplication,sortingandmediannding,aswellasthefastFouriertransform.Therearethreeotherparts:PartII,themosttraditionalsectionofthebook,concentratesondatastructuresandgraphs;thecontrasthereisbetweentheintricatestructureoftheunderlyingproblemsandtheshortandcrisppiecesofpseudocodethatsolvethem.Instructorswishingtoteachamoretradi-tionalcoursecansimplystartwithPartII,whichisself-contained(followingtheprologue),andthencoverPartIasrequired.InPartsIandIIweintroducedcertaintechniques(suchasgreedyanddivide-and-conquer)whichworkforspecialkindsofproblems;PartIIIdealswiththe“sledgehammers”ofthetrade,techniquesthatarepowerfulandgeneral:dynamicprogramming(anovelapproachhelpsclarifythistraditionalstumblingblockforstudents)andlinearprogramming(acleanandintuitivetreatmentofthesimplexalgorithm,duality,andreductionstothebasicproblem).ThenalPartIVisaboutwaysofdealingwithhardproblems:NP-completeness,variousheuristics,aswellasquantumalgorithms,perhapsthemostadvancedandmoderntopic.Asithappens,weendthestoryexactlywherewestartedit,withShor'squantumalgorithmforfactoring.Thebookincludesthreeadditionalundercurrents,intheformofthreeseriesofseparate“boxes,”strengtheningthenarrative(andaddressingvariationsintheneedsandinterestsofthestudents)whilekeepingtheowintact:piecesthatprovidehistoricalcontext;descriptionsofhowtheexplainedalgorithmsareusedinpractice(withemphasisoninternetapplications);9\nandexcursionsforthemathematicallysophisticated.10\nChapter0PrologueLookaroundyou.Computersandnetworksareeverywhere,enablinganintricatewebofcom-plexhumanactivities:education,commerce,entertainment,research,manufacturing,healthmanagement,humancommunication,evenwar.Ofthetwomaintechnologicalunderpinningsofthisamazingproliferation,oneisobvious:thebreathtakingpacewithwhichadvancesinmicroelectronicsandchipdesignhavebeenbringingusfasterandfasterhardware.Thisbooktellsthestoryoftheotherintellectualenterprisethatiscruciallyfuelingthecomputerrevolution:efcientalgorithms.Itisafascinatingstory.Gather'roundandlistenclose.0.1BooksandalgorithmsTwoideaschangedtheworld.In1448intheGermancityofMainzagoldsmithnamedJo-hannGutenbergdiscoveredawaytoprintbooksbyputtingtogethermovablemetallicpieces.Literacyspread,theDarkAgesended,thehumanintellectwasliberated,scienceandtech-nologytriumphed,theIndustrialRevolutionhappened.Manyhistorianssayweoweallthistotypography.Imagineaworldinwhichonlyanelitecouldreadtheselines!Butothersinsistthatthekeydevelopmentwasnottypography,butalgorithms.Todaywearesousedtowritingnumbersindecimal,thatitiseasytoforgetthatGuten-bergwouldwritethenumber1448asMCDXLVIII.HowdoyouaddtwoRomannumerals?WhatisMCDXLVIII+DCCCXII?(Andjusttrytothinkaboutmultiplyingthem.)EvenaclevermanlikeGutenbergprobablyonlyknewhowtoaddandsubtractsmallnumbersusinghisngers;foranythingmorecomplicatedhehadtoconsultanabacusspecialist.Thedecimalsystem,inventedinIndiaaroundAD600,wasarevolutioninquantitativereasoning:usingonly10symbols,evenverylargenumberscouldbewrittendowncompactly,andarithmeticcouldbedoneefcientlyonthembyfollowingelementarysteps.Nonethelesstheseideastookalongtimetospread,hinderedbytraditionalbarriersoflanguage,distance,andignorance.Themostinuentialmediumoftransmissionturnedouttobeatextbook,writteninArabicintheninthcenturybyamanwholivedinBaghdad.AlKhwarizmilaidoutthebasicmethodsforadding,multiplying,anddividingnumbers—evenextractingsquarerootsandcalculatingdigitsof.Theseprocedureswereprecise,unambiguous,mechanical,efcient,correct—inshort,theywerealgorithms,atermcoinedtohonorthewisemanafterthedecimalsystemwasnallyadoptedinEurope,manycenturieslater.11\nSincethen,thisdecimalpositionalsystemanditsnumericalalgorithmshaveplayedanenormousroleinWesterncivilization.Theyenabledscienceandtechnology;theyacceler-atedindustryandcommerce.Andwhen,muchlater,thecomputerwasnallydesigned,itexplicitlyembodiedthepositionalsysteminitsbitsandwordsandarithmeticunit.Scien-tistseverywherethengotbusydevelopingmoreandmorecomplexalgorithmsforallkindsofproblemsandinventingnovelapplications—ultimatelychangingtheworld.0.2EnterFibonacciAlKhwarizmi'sworkcouldnothavegainedafootholdintheWestwereitnotfortheeffortsofoneman:the15thcenturyItalianmathematicianLeonardoFibonacci,whosawthepotentialofthepositionalsystemandworkedhardtodevelopitfurtherandpropagandizeit.ButtodayFibonacciismostwidelyknownforhisfamoussequenceofnumbers0;1;1;2;3;5;8;13;21;34;:::;eachthesumofitstwoimmediatepredecessors.Moreformally,theFibonaccinumbersFnaregeneratedbythesimplerule8