计算理论导引3ppt课件

,计算理论导引与算法复杂性IntroductiontotheTheoryofComputationandAlgorithmComplexities,主讲：刘国华（学院楼225室，ghliu）助教：辛婷婷（学院楼153室，xtt.moon）FTP:,1,6BOOLEANLOGIC1)Negation0=1,1=02)Conjunction01=0,11=13)Disjunction01=14)Exclusiveor00=0,01=15)Equality00=1,10=06)Implication10=0,11=1,01=1,00=17)DistributivelawP(QR)=(PQ)(PR)P(QR)=(PQ)(PR),CHAPTER1FUNDATION,Imsorry!,2,CHAPTER2COMPUTATIONALMODELS(1),Computation?,Computationisageneraltermforanytypeofprocess,algorithmormeasurement;thisoftenincludesbutisnotlimitedtodigitaldata.Computationisaprocessfollowingawell-definedmodel.Computationisalsoamajorsubjectmatterofcomputerscience:itinvestigateswhatcanorcannotbedoneinacomputationalmanner.,3,CHAPTER2COMPUTATIONALMODELS(1),AUTOMATATURINGMACHINES,4,CHAPTER2COMPUTATIONALMODELS(1),AUTOMATA1FINITEAUTOMATA1)DETERMINISTICFINITEAUTOMATA(DFA)Example.Anautomaticdoor.,Rulesforopening:1Thedoorisclosing,ifsomeoneisstandingonthefrontpad(FRONT)andnooneisstandingontherearpad(REAR),thenthedooropens;2Thedoorisopening,ifsomeoneisstandingontherearpad(REAR),thenthedoorkeepsopening;3Thedoorisopening,ifsomeoneisstandingonthefrontpadandsomeoneisstandingontherearpad(BOTH),thenthedoorkeepsopening;,5,CHAPTER2COMPUTATIONALMODELS(1),Rulesforclosing:1Thedoorisopening,ifnooneisstandingoneitherpad(NEITHER),thenthedoorcloses;2Thedoorisclosing,ifsomeoneisstandingontherearpad(REAR),thenthedoorkeepsclosing;3Thedoorisclosing,ifsomeoneisstandingonthefrontpadandsomeoneisstandingontherearpad(BOTH),thenthedoorkeepsclosing.,Howtoimplementthissystem?,Hardwares:twosensors;onecomputer(only1bitmemory),etc.,Howaboutthesoftware?,6,CHAPTER2COMPUTATIONALMODELS(1),satrt,tTRUE;d0,t=TRUE?,Y,s1sensor1,s2sensor2,d=0and(s2=1ors1=1ands2=1ors1=0ands2=0),Y,d=1and(s1=1ors2=1ors1=1ands2=1),N,Y,d=0ands1=1,N,Y,d1,d=1ands1=0ands2=0,Y,d0,N,end,N,N,7,CHAPTER2COMPUTATIONALMODELS(1),CLOSED(d=0),OPEN(d=1),NEITHER(s1=0ands2=0),FORNT(s1=1),REAR(s2=1)BOTH(s1=1ands2=1)NEITHER(s1=0ands2=0),FORNT(s1=1)REAR(s2=1)BOTH(s1=1ands2=1),8,CHAPTER2COMPUTATIONALMODELS(1),CLOSED,OPEN,NEITHER,FORNT,REARBOTHNEITHER,FORNTREARBOTH,9,CHAPTER2COMPUTATIONALMODELS(1),frontpad,rearpad,CLOSED,OPEN,BOTH,NEITHER,FORNT,BOTH,REAR,10,CHAPTER2COMPUTATIONALMODELS(1),CLOSED,OPEN,NEITHER,FORNTREARBOTH,NEITHER,FORNTREARBOTH,11,CHAPTER2COMPUTATIONALMODELS(1),ThestatediagramforDFAM1,1,11,01,001,00001,01,011,0011,00110,FORMALDEFINITIONOFAFINITEATUOMATONAfiniteautomatonisa5-tuple(Q,q0,F),where1.Qisafinitesetcalledthestates,2.isafinitesetcalledthealphabet,3.:QQisthetransitionfunction,4.q0Qisthestartstate,and5.FQisthesetofacceptstates.,12,CHAPTER2COMPUTATIONALMODELS(1),ThestatediagramforDFAM1,1.Q=q1,q2,q3,2.=0,1,3.isdesribedas01q1q1q2q2q3q2q3q2q24.q1isthestartstate,and5.F=q2.,13,CHAPTER2COMPUTATIONALMODELS(1),L(M)=A:LanguageofmachineM,wesaythatMrecoginizesA.FORMALDEFINITIONOFCOMPUTATIONLetM=(Q,q0,F)beafiniteautomatonandletw=w1w2wnbeastringwhereeachwiisamemberofthealphabet.ThenMacceptswifasequenceofstatesr0,r1,rninQexistswiththreeconditions:1.r0=q0,2.(r0,wi+1)=ri+1,fori=0,n-1,and3.rnF.Regularlanguage:alanguageiscalledaregularlanguageifsomefiniteautomatonrecognizes,14,CHAPTER2COMPUTATIONALMODELS(1),DESIGNINGFINITEAUTOMATA,qeven,qodd,0,0,1,1,HowtodesignaDFAtorecognizethelanguageofallstringsthatcontainthestring001asasubstring.,q1,1,q2,q3,0,1,0,1,0,q4,1,0,15,CHAPTER2COMPUTATIONALMODELS(1),THEREGULAROPERATIONUnion:AB=x|xAorxBConcatenation:AB=xy|xAandyBStar:A=x1x2xk|k0andeachxiAEXAMPLE.A=good,bad,B=boy,girlAB=？AB=？A=?,*,*,AB=good,bad,boy,girlAB=goodboy,goodgirl,badboy,badgirlA=,good,bad,goodgood,goodbad,badbad,badgood,goodgoodgood,goodgoodbad,goodbadgood,goodbadbad,*,16,CHAPTER2COMPUTATIONALMODELS(1),THEOREM2.1Theclassofregularlanguagesisclosedundertheunionoperation.PROOFIDEA.A1=L(M1);A2=L(M2)A1A2=L(M3)?LetM1=(Q1,1,q1,F1),M2=(Q2,2,q2,F2),thenM3=(Q3,3,q3,F3),whereQ3=(r1,r2)|r1Q1andr2Q2,3(r1,r2),a)=(1(r1,a),2(r2,a),q3=(q1,q2),F=(r1,r2)|r1F1orr2F2