离散数学北京邮电大学ppt课件

.,Algorithms,Rosen6thed.,3.1,Abual-Khowarizmi(ca.780-850),.,Chapter3:MoreFundamentals,3.1:AlgorithmsFormalprocedures3.2:GrowthofFunctions3.3:ComplexityofalgorithmsAnalysisusingorder-of-growthnotation.3.4:TheIntegersotherwise,justskiponaheadtothenextstatementaftertheifstatement.Variant:ifcondthenstmt1elsestmt2Likebefore,butifftruthvalueisFalse,executesstmt2.,.,whileconditionstatement,Evaluatethepropositional(Boolean)expressioncondition.IftheresultingvalueisTrue,thenexecutestatement.ContinuerepeatingtheabovetwoactionsoverandoveruntilfinallytheconditionevaluatestoFalse;thenproceedtothenextstatement.,.,whileconditionstatement,Alsoequivalenttoinfinitenestedifs,likeso:ifconditionbeginstatementifconditionbeginstatement(continueinfinitenestedifs)endend,.,forvar:=initialtofinalstmt,Initialisanintegerexpression.Finalisanotherintegerexpression.Semantics:Repeatedlyexecutestmt,firstwithvariablevar:=initial,thenwithvar:=initial+1,thenwithvar:=initial+2,etc.,thenfinallywithvar:=final.Question:Whathappensifstmtchangesthevalueofvar,orthevaluethatinitialorfinalevaluatesto?,.,forvar:=initialtofinalstmt,Forcanbeexactlydefinedintermsofwhile,likeso:,beginvar:=initialwhilevarfinalbeginstmtvar:=var+1endend,.,procedure(argument),Aprocedurecallstatementinvokesthenamedprocedure,givingitasitsinputthevalueoftheargumentexpression.Variousrealprogramminglanguagesrefertoproceduresasfunctions(sincetheprocedurecallnotationworkssimilarlytofunctionapplicationf(x),orassubroutines,subprograms,ormethods.,.,Maxprocedureinpseudocode,proceduremax(a1,a2,an:integers)v:=a1largestelementsofarfori:=2tongothrurestofelemsifaivthenv:=aifoundbigger?atthispointvsvalueisthesameasthelargestintegerinthelistreturnv,.,InventinganAlgorithm,RequiresalotofcreativityandintuitionLikewritingproofs.Unfortunately,wecantgiveyouanalgorithmforinventingalgorithms.JustlookatlotsofexamplesAndpractice(preferably,onacomputer)AndlookatmoreexamplesAndpracticesomemoreetc.,etc.,.,Algorithm-InventingExample,Supposeweaskyoutowriteanalgorithmtocomputethepredicate:IsPrime:NT,FComputeswhetheragivennaturalnumberisaprimenumber.First,startwithacorrectpredicate-logicdefinitionofthedesiredfunction:n:IsPrime(n)1n1/2thenbn1/2(sinceaisnssmallestdivisor)andson=ab(n1/2)2=n,anabsurdity.,Furtheroptimizationsarepossible:-E.g.,onlytrydivisorsthatareprimeslessthann1/2.,Notesmallerrangeofsearch.,.,Anotherexampletask,Problemofsearchinganorderedlist.GivenalistLofnelementsthataresortedintoadefiniteorder(e.g.,numeric,alphabetical),Andgivenaparticularelementx,Determinewhetherxappearsinthelist,andifso,returnitsindex(position)inthelist.Problemoccursofteninmanycontexts.Letsfindanefficientalgorithm!,.,Searchalg.#1:LinearSearch,procedurelinearsearch(x:integer,a1,a2,an:distinctintegers)i:=1startatbeginningoflistwhile(inxai)notdone,notfoundi:=i+1gotothenextpositionifinthenlocation:=iitwasfoundelselocation:=0itwasntfoundreturnlocationindexor0ifnotfound,.,Searchalg.#2:BinarySearch,Basicidea:Oneachstep,lookatthemiddleelementoftheremaininglisttoeliminatehalfofit,andquicklyzeroinonthedesiredelement.,x,c2cr;n:apositiveinteger)Fori:=1torwhilencibeginaddacoinwithvaluecitothechangen:=n-ciend,.,TheHaltingProblem(Turing36),Thehaltingproblemwasthefirstmathematicalfunctionproventohavenoalgorithmthatcomputesit!Wesay,itisuncomputable.ThedesiredfunctionisHalts(P,I):thetruthvalueofthisstatement:“ProgramP,giveninputI,eventuallyterminates.”Theorem:Haltsisuncomputable!I.e.,theredoesnotexistanyalgorithmAthatcomputesHaltscorrectlyforallpossibleinputs.Itsproofisthusanon-existenceproof.Corollary:Generalimpossibilityofpredictiveanalysisofarbitrarycomputerprograms.,AlanTuring1912-1954,.,停机问题HaltingProblem,一个实际问题：给定一个算法和相应的输入，判定这个算法是否能够完成？（还是进入死循环不能完成？）由于算法都可以用图灵机描述，所以问题转变为，给定一个图灵机和相应的输入，判定是否停机？对于特定的算法，我们大概是可以判定的，但是否存在对一般的算法进行判定的方法？程序正确性证明：包括了给一段程序，判断这段程序是否会进入死循环注意：这个方法本身也是一个算法，否则没有意义,.,停机问题,是否有算法能够判定某个图灵机M在输入I下是否停机？即Halt(M,I)=TrueiifM在I处停机，FalseiifM在I处不停机答案是否定的，不存在这样的算法停机问题是不可计算问题,.,停机问题证明,假设存在这样的算法，对应的图灵机是Halt(a,k)，a是要判定的图灵机编码，k是输入的编码我们构造这么一个图灵机Trouble(a)functionTrouble(a)ifHalt(a,a)=FalsethenreturnTrueelseloopforeverTrouble图灵机自然也可以编码，记为t，我们来看把t作为Trouble输入会怎么样？Trouble(t)=?,.,停机问题证明,矛盾？矛盾！如果Trouble(t)停机返回了，也就是Halt(t,t)=False，但这样是说Trouble(t)不停机，矛盾如果Trouble(t)不停机，也就是Halt(t,t)返回了True，但这样却是说Trouble(t)能停机，矛盾消除矛盾的唯一途径就是否定假设，即不存在能一般性地判定图灵机停机的算法人的智能就能解决停机问题么？至少目前还是否对于太长的算法，或者输入太复杂的算法，不能对于一些短而简单的算法，也不能（一些数论难题）寻找大于给定N的孪生素数,.,Review3.1:Algorithms,Characteristicsofalgorithms.Pseudocode.Examples:Maxalgorithm,primality-testing,linearsearch&binarysearchalgorithms.Sorting.Intuitivelyweseethatbinarysearchismuchfasterthanlinearsearch,buthowdoweanalyzetheefficiencyofalgorithmsformally?Usemethodsofalgorithmiccomplexity,whichutilizetheorder-of-growthconceptsfrom3.3.,.,OrdersofGrowth,Rosen6thed.,3.2,.,OrdersofGrowth(3.2),Forfunctionsovernumbers,weoftenneedtoknowaroughmeasureofhowfastafunctiongrows.Iff(x)isfastergrowingthang(x),thenf(x)alwayseventuallybecomeslargerthang(x)inthelimit(forlargeenoughvaluesofx).Usefulinengineeringforshowingthatonedesignscalesbetterorworsethananother.,.,OrdersofGrowth-Motivation,Supposeyouaredesigningawebsitetoprocessuserdata(e.g.,financialrecords).SupposedatabaseprogramAtakesfA(n)=30n+8microsecondstoprocessanynrecords,whileprogramBtakesfB(n)=n2+1microsecondstoprocessthenrecords.Whichprogramdoyouchoose,knowingyoullwanttosupportmillionsofusers?,A,.,VisualizingOrdersofGrowth,Onagraph,asyougototheright,thefaster-growingfunc-tionalwayseventuallybecomesthelargerone.,fA(n)=30n+8,Increasingn,fB(n)=n2+1,Valueoffunction,.,Example:,f(n)=100n2,g(n)=n4,thefollowingtableandfigureshowthatg(n)growsfasterthanf(n)whenn10.Wesayfisbig-Ohofg.,.,Conceptoforderofgrowth,WesayfA(n)=30n+8is(atmost)ordern,orO(n).Itis,atmost,roughlyproportionalton.fB(n)=n2+1isordern2,orO(n2).Itis(atmost)roughlyproportionalton2.Anyfunctionwhoseexact(tightest)orderisO(n2)isfaster-growingthananyO(n)function.Laterwewillintroduceforexpressingexactorder.Forlargenumbersofuserrecords,theexactlyordern2functionwillalwaystakemoretime.,.,Definition:O(g),atmostorderg,LetgbeanyfunctionRR.Define“atmostorderg”,writtenO(g),tobe:f:RR|c,k:xk:f(x)cg(x).“Beyondsomepointk,functionfisatmostaconstantctimesg(i.e.,proportionaltog).”“fisatmostorderg”,or“fisO(g)”,or“f=O(g)”alljustmeanthatfO(g).Oftenthephrase“atmost”isomitted.,.,Pointsaboutthedefinition,NotethatfisO(g)solongasanyvaluesofcandkexistthatsatisfythedefinition.But:Theparticularc,k,valuesthatmakethestatementtruearenotunique:Anylargervalueofcand/orkwillalsowork.Youarenotrequiredtofindthesmallestcandkvaluesthatwork.(Indeed,insomecases,theremaybenosmallestvalues!),However,youshouldprovethatthevaluesyouchoosedowork.,.,“Big-O”ProofExamples,Showthat30n+8isO(n).Showc,k:nk:30n+8cn.Letc=31,k=8.Assumenk=8.Thencn=31n=30n+n30n+8,so30n+8k:n2+1cn2.Letc=2,k=1.Assumen1.Thencn2=2n2=n2+n2n2+1,orn2+10).Itisntevenlessthan31neverywhere.Butitislessthan31neverywheretotherightofn=8.,Big-Oexample,graphically,Increasingn,Valueoffunction,n,30n+8,30n+8O(n),.,UsefulFactsaboutBigO,BigO,asarelation,istransitive:fO(g)gO(h)fO(h)Owithconstantmultiples,roots,andlogs.f(in(1)&constantsa,bR,withb0,af,f1-b,and(logbf)aareallO(f).Sumsoffunctions:IfgO(f)andhO(f),theng+hO(f).,.,MoreBig-Ofacts,c0,O(cf)=O(f+c)=O(fc)=O(f)f1O(g1)f2O(g2)f1f2O(g1g2)f1+f2O(g1+g2)=O(max(g1,g2)=O(g1)ifg2O(g1)(Veryuseful!),.,Example,Iff1isO(g1)andf2isO(g2)thenf1f2isO(g1g2)f1+f2isO(maxg1,g2),.,Proofoff1f2isO(g1g2),Thereisak1andc1suchthat1.f1(n)k1.Thereisak2andc2suchthat2.f2(n)k2.Wemustfindak3andc3suchthat3.f1(n)f2(n)k3.,.,Proofoff1f2isO(g1g2),Weusetheinequalityif0maxk1,k2sothatbothinequalities1and2.holdatthesametime.Therefore,choosec3=c1c2andk3=maxk1,k2.Q.E.D.,.,OrdersofGrowth,Foranyg:RR,“atmostorderg”,O(g)f:RR|c,kxk|f(x)|cg(x)|.Often,onedealsonlywithpositivefunctionsandcanignoreabsolutevaluesymbols.“fO(g)”oftenwritten“fisO(g)”or“f=O(g)”.Thelatterformisaninstanceofamoregeneralconvention.,.,Order-of-GrowthExpressions,“O(f)”whenusedasaterminanarithmeticexpressionmeans:“somefunctionfsuchthatfO(f)”.E.g.:“x2+O(x)”means“x2plussomefunctionthatisO(x)”.Formally,youcanthinkofanysuchexpressionasdenotingasetoffunctions:x2+O(x):g|fO(x):g(x)=x2+f(x),.,OrderofGrowthEquations,SupposeE1andE2areorder-of-growthexpressionscorrespondingtothesetsoffunctionsSandT,respectively.Thenthe“equation”E1=E2reallymeansfS,gT:f=gorsimplyST.Example:x2+O(x)=O(x2)meansfO(x):gO(x2):x2+f(x)=g(x),.,UsefulFactsaboutBigO,f,g(e.g.x1=O(x)(logb|f|)a=O(f).(e.g.logx=O(x)g=O(fg)(e.g.x=O(xlogx)fgO(g)(e.g.xlogxO(x)a=O(f)(e.g.3=O(x),.,Big-OmegaandBig-Theta,Big-ohconcernswiththelessthanorequaltorelationbetweenfunctionsforlargevaluesofthevariable.Itisalsopossibletoconsiderthegreaterthanorequaltorelationandequaltorelationinasimilarway.Big-Omegaisfortheformerandbig-thetaisforthelatter.,.,Definition(big-omega):,Letfandgbefunctionsfromthesetofintegers(orthesetofrealnumbers)tothesetofrealnumbers.Thenf(x)issaidtobe(g(x),whichisreadasf(x)isbig-omegaofg(x),ifthereareconstantsCandn0suchthat|f(x)|C|g(x)|wheneverxn0.,.,Definition:(g),exactlyorderg,IffO(g)andgO(f),thenwesay“gandfareofthesameorder”or“fis(exactly)orderg”andwritef(g).Another,equivalentdefinition:(g)f:RR|c1c2k0xk:|c1g(x)|f(x)|c2g(x)|“Everywherebeyondsomepointk,f(x)liesinbetweentwomultiplesofg(x).”,.,Rulesfor,MostlylikerulesforO(),except:f,g0&constantsa,bR,withb0,af(f),butSameaswithO.f(fg)unlessg=(1)UnlikeO.|f|1-b(f),andUnlikewithO.(logb|f|)c(f).UnlikewithO.Thefunctionsinthelattertwocaseswesayarestrictlyoflowerorderthan(f).,.,example,Determinewhether:Quicksolution:,.,OtherOrder-of-GrowthRelations,(g)=f|gO(f)“Thefunctionsthatareatleastorderg.”o(g)=f|c0kxk:|f(x)|0kxk:|cg(x)|0.(na)islowerthan(nb)ifandonlyif01.(an)islowerthan(n!)foranya1.(n!)islowerthan(nn),.,Ifrisnotzero,then(rf)=(f)foranyfunctionf.Ifhisanonzerofunctionand(f)islowerthan(orsameorderas)(g),then(fh)islowerthan(orsameorderas)(gh).If(f)islowerthan(g),then(f+g)=(g).,.,Determinethe-classofeachofthefollowing.,(a)f(n)=4n2-6n7+25n3(b)g(n)=lg(n)-3n(c)h(n)=1.1n+n15,.,Arrangethefollowinginorderfromlowesttohighest,(1000000)(n0.2)(n+107)(nlg(n)(1000n2-n)(1.3n),(nlg(n)(1000n2-n)(n0.2)(1000000)(1.3n)(n+107),.,Example,Findthecomplexityclassofthefunction(nn!+3n+2+3n100)(nn+n2n)Solution:Thismeanstosimplifytheexpression.Throwoutstuffwhichyouknowdoesntgrowasfast.Andatlast:nn!nn,.,Whyo(f)O(x)(x),AfunctionthatisO(x),butneithero(x)nor(x):,.,StrictOrderingofFunctions,Temporarilyletswritefgtomeanfo(g),fgtomeanf(g)Notethat:Letk1.Thenthefollowingaretrue:1loglognlognlogknlogknn1/knnlognnkknn!nn,.,Review:OrdersofGrowth,Definitionsoforder-of-growthsets,g:RRO(g):f|c0kxk|f(x)|0kxk|f(x)|vthenv:=ait3returnvt4First,whatsanexpressionfortheexacttotalworst-casetime?(Notitsorderofgrowth.),Timesforeachexecutionofeachline.,.,Complexityanalysis,cont.,proceduremax(a1,a2,an:integers)v:=a1t1fori:=2tont2ifaivthenv:=ait3returnvt4w.c.t.c.:,Timesforeachexecutionofeachline.,.,Complexityanalysis,cont.,Now,whatisthesimplestformoftheexact()orderofgrowthoft(n)?,.,Example2:LinearSearch,procedurelinearsearch(x:integer,a1,a2,an:distinctintegers)i:=1t1while(inxai)t2i:=i+1t3ifinthenlocation:=it4elselocation:=0t5returnlocationt6,.,Linearsearchanalysis,Worstcasetimecomplexityorder:Bestcase:Averagecase,ifitemispresent:,.,Review3.3:Complexity,Algorithmiccomplexity=costofcomputation.Focusontimecomplexityforourcourse.Althoughspace&energyarealsoimportant.Characterizecomplexityasafunctionofinputsize:Worst-case,best-case,oraverage-case.Useorders-of-growthnotationtoconciselysummarizethegrowthpropertiesofcomplexityfunctions.,.,Example3:BinarySearch,procedurebinarysearch(x:integer,a1,a2,an:distinctintegers,sortedsmallesttolargest)i:=1j:=nwhileiamtheni:=m+1elsej:=mendifx=aithenlocation:=ielselocation:=0returnlocation,(1),(1),(1),Keyquestion:Howmanyloopiterations?,.,Binarysearchanalysis,Supposethatnisapowerof2,i.e.,k:n=2k.Originalrangefromi=1toj=ncontainsnitems.Eachiteration:Sizeji+1ofrangeiscutinhalf.Loopterminateswhensizeofrangeis1=20(i=j).Therefore,thenumberofiterationsis:k=log2n=(log2n)=(logn)Evenforn2k(notanintegralpowerof2),timecomplexityisstill(log2n)=(logn).,.,Namesforsomeordersofgrowth,(1)Constant(logcn)Logarithmic(sameorderc)(logcn)Polylogarithmic(n)Linear(nc)Polynomial(foranyc)(cn)Exponential(forc1)(n!)Factorial,(Withcaconstant.),.,ProblemComplexity,Thecomplexityofacomputationalproblemortaskis(theorderofgrowthof)thecomplexityofthealgorithmwiththelowestorderofgrowthofcomplexityforsolvingthatproblemorperformingthattask.E.g.theproblemofsearchinganorderedlisthasatmostlogarithmictimecomplexity.(ComplexityisO(logn).),.,Tractable,Aproblemoralgorithmwithatmostpolynomialtimecomplexityisconsideredtractable(orfeasible).Pisthesetofalltractableproblems.Aproblemoralgorithmthathascomplexitygreaterthanpolynomialisconsideredintractable(orinfeasible).Notethatn1,000,000istechnicallytractable,butreallyveryhard.nlogloglognistechnicallyintractable,buteasy.Suchcasesarerarethough.,.,ComputerTimeExamples,Assumetime=1ns(109second)perop,problemsize=nbits,and#opsisafunctionofn,asshown.,(125kB),(1.25bytes),.,Unsolvableproblems,Turingdiscoveredinthe1930sthatthereareproblemsunsolvablebyanyalgorithm.Orequivalently,thereareundecidableyes/noquestions,anduncomputablefunctions.Classicexample:thehaltingproblem.Givenanarbitraryalgorithmanditsinput,willthata