资源描述：
《the algorithm the key concept》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。
1、Chapter4Thealgorithm:thekeyconceptHowshamelessMartinappliesmathematicallogicwhencourtinggirls,andhowapoliceocermaybeunabletoidentifyacriminalgangintheWeb.Thealgorithm1isthekeyconceptofthisbook.Wheninthe1930sAlanTuringandotherlogicianscameupwithasoundd
2、e nitionofthealgorithm,computersciencetookits rststeps,althoughnocomputershadyetbeeninvented.AlgorithmsaccompaniedthegrowthofthisnewscienceuptotheInternetandthroughtotheWeberawheretheylieatthefoundationofeverything.Basedontheprimitiveconceptsdiscussedi
3、nthepreviouschapterswewillnowillustrateseveralalgorithmstobeusedlaterasbuildingblocks,startingfromtheindispensabletheoreticalfoundationsofourdiscussion.Letusreturntotheworldofsequences.Ouranalysiswillnotlosegeneralityifwerestrictthisworldtothebinarycas
4、ethatinterestsusmost.Callthesesequences0;1;2;:::andarrangethemincanonicalorder,i.e.,byincreasinglengthand,forthesamelength,byincreasingvalueofthecorrespondingbinarynumbers,startingfromtheemptysequence.Wehave:012345678:::1415:::010001101
5、1000001:::1110000:::(4:1)i.e.,thebinarysequencescanbeputinaone-to-onecorrespondencewiththenaturalnumbers0,1,2,....,or,intheterminologyofsettheory,suchsequencesarenumerable.Adoptingthenumberinginducedbythecanonicalorder,foranygivensequenceiwecanreconst
6、ructin nitetimeitsnumberi,andviceversa,nomatterhowlongthesequenceis.Keepinmindthatwearetalkingofsequencesof nitebutunboundedlength,thatis,foranylengthlarbitrarily xedthereare(in nite)sequenceslongerthanl.Thisin niteworldofnumerableobjectshasattractedth
7、inkerssincean-cienttimes.Themereexistenceofin nitywasamatterofdiscussionuntil1Abookonthealgorithmicfoundationsofnetworkingmustincludeachapterlikethisone.Readerswithsomeknowledgeofcomputabilityandcomplexitytheory,asacquired,forexample,inastandardunivers
8、itycourseincomputerscience,mayskipthechapterorjustskimittorefreshthememory.43©2012byTaylor&FrancisGroup,LLC44MathematicalandAlgorithmicFoundationsoftheInternetAristotleassertedbeyondany(personal)doubtthatin nityhadtoexist:forexample,hes
