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

上传资料

关闭

关闭

关闭

封号提示

内容

首页 算法之美

算法之美.pdf

算法之美

dodo
2009-06-16 0人阅读 举报 0 0 暂无简介

简介:本文档为《算法之美pdf》,可适用于人文社科领域

AlgorithmsCopyrightc©SDasgupta,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=Fn−Fn−ifn>ifn=ifn=Noothersequenceofnumbershasbeenstudiedasextensively,orappliedtomorefields:biology,demography,art,architecture,music,tonamejustafewAnd,togetherwiththepowersof,itiscomputerscience’sfavoritesequenceInfact,theFibonaccinumbersgrowalmostasfastasthepowersof:forexample,Fisoveramillion,andFisalreadydigitslong!Ingeneral,Fn≈n(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)≤forn≤Forlargervaluesofn,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)

关闭

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

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

提示

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

文档小程序码

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

1

打开微信

2

扫描小程序码

3

发布寻找信息

4

等待寻找结果

我知道了
评分:

/49

算法之美

仅供在线阅读

VIP

在线
客服

免费
邮箱

爱问共享资料服务号

扫描关注领取更多福利