计算理论导引3PPT课件

1、2021/7/241 计算理论导引与算法复杂性计算理论导引与算法复杂性Introduction to the Theory of Computation and Algorithm Complexities 主讲：刘国华主讲：刘国华（学院楼学院楼225225室室，） 助教：辛婷婷助教：辛婷婷（学院楼学院楼153153室室，） FTP:2021/7/2426 BOOLEAN LOGIC1)Negation 0=1, 1=02)Conjunction 0 1=0,1 1 =13)Disjunction 0 1=14)Exclusive or 0 0=0,0 1=15)Eq

2、uality 00=1,1 0=06)Implication 10=0, 11=1,01=1,00=17)Distributive law P (Q R)= (P Q) (P R)P (Q R)= (P Q) (P R)CHAPTER 1 FUNDATIONIm sorry!2021/7/243CHAPTER 2COMPUTATIONAL MODELS(1)Computation?Computation is a general term for any type of process, algorithm or measurement; this often includes but is

3、not limited to digital data. Computation is a process following a well-defined model. Computation is also a major subject matter of computer science: it investigates what can or cannot be done in a computational manner. 2021/7/244CHAPTER 2COMPUTATIONAL MODELS(1) AUTOMATATURING MACHINES2021/7/245CHAP

4、TER 2 COMPUTATIONAL MODELS(1) AUTOMATA1 FINITE AUTOMATA1)DETERMINISTIC FINITE AUTOMATA(DFA)Example. An automatic door.front padrear padRules for opening:1 The door is closing, if some one is standing on the front pad (FRONT) and no one is standing on the rear pad (REAR) , then the door opens;2 The d

5、oor is opening, if some one is standing on the rear pad (REAR) , then the door keeps opening;3 The door is opening, if some one is standing on the front pad and some one is standing on the rear pad (BOTH) , then the door keeps opening;2021/7/246CHAPTER 2 COMPUTATIONAL MODELS(1)front padrear padRules

6、 for closing:1 The door is opening, if no one is standing on either pad (NEITHER), then the door closes;2 The door is closing, if some one is standing on the rear pad (REAR) , then the door keeps closing;3 The door is closing, if some one is standing on the front pad and some one is standing on the

7、rear pad (BOTH) , then the door keeps closing.How to implement this system?Hardwares: two sensors; one computer(only 1 bit memory), etc.How about the software?2021/7/247CHAPTER 2 COMPUTATIONAL MODELS(1)satrttTRUE;d 0t=TRUE?Ys1sensor1s2sensor2d=0and(s2=1ors1=1ands2=1ors1=0ands2=0)Yd=1and(s1=1ors2=1or

8、s1=1ands2=1)NYd=0ands1=1NYd1d=1ands1=0ands2=0Yd0NendNN2021/7/248CHAPTER 2 COMPUTATIONAL MODELS(1)front padrear padCLOSED(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)2021/7/249CHAPTER 2 COMPUTATIONAL MODELS(1)front p

9、adrear padCLOSEDOPENNEITHERFORNTREARBOTHNEITHER FORNTREARBOTH2021/7/2410CHAPTER 2 COMPUTATIONAL MODELS(1)front padrear padCLOSEDOPENNEITHERFORNTBOTH REARNEITHER FORNT BOTHREAR2021/7/2411CHAPTER 2 COMPUTATIONAL MODELS(1)CLOSEDOPENNEITHERFORNTREARBOTHNEITHER FORNTREARBOTHfront padrear pad2021/7/2412CH

10、APTER 2 COMPUTATIONAL MODELS(1)q10q2q3110,11The state diagram for DFA M11, , 11, 01, 001, 00001, , 01, 011, , 0011, , 00110FORMAL DEFINITION OF A FINITE ATUOMATONA finite automaton is a 5-tuple (Q, , , q0,F), where1.Q is a finite set called the states,2. is a finite set called the alphabet,3. : Q Q

11、is the transition function,4. q0 Q is the start state, and5. F Q is the set of accept states.2021/7/2413CHAPTER 2 COMPUTATIONAL MODELS(1)q10q2q3110,11The state diagram for DFA M11.Q =q1, q2, q3,2. =0,1,3. is desribed as 0 1 q1 q1 q2 q2 q3 q2 q3 q2 q24. q1 is the start state, and5. F=q2.2021/7/2414CH

12、APTER 2 COMPUTATIONAL MODELS(1)L(M)=A: Language of machine M, we say that M recoginizes A.FORMAL DEFINITION OF COMPUTATIONLet M= (Q, , , q0,F) be a finite automaton and let w=w1w2wn be a string where each wi is a member of the alphabet . Then M accepts w if a sequence of states r0, r1,rn in Q exists

13、 with three conditions:1.r0=q0,2. (r0, wi+1 )=ri+1, for i=0,n-1, and3.rn F.Regular language: a language is called a regular language if some finite automaton recognizes2021/7/2415CHAPTER 2 COMPUTATIONAL MODELS(1)DESIGNING FINITE AUTOMATAqevenqodd0011How to design a DFA to recognize the language of a

14、ll strings that contain the string 001 as a substring.q11q2q3010,10q4102021/7/2416CHAPTER 2 COMPUTATIONAL MODELS(1)THE REGULAR OPERATIONUnion: A B=x|x A or x BConcatenation:A B=xy|x A and y BStar:A=x1x2xk|k 0 and each xi AEXAMPLE .A=good, bad, B=boy, girlA B=？A B=？A =?*A B=good, bad, boy, girlA B=go

15、odboy, goodgirl, badboy, badgirlA = , good, bad, goodgood, goodbad, badbad, badgood, goodgoodgood, goodgoodbad, goodbadgood, goodbadbad, *2021/7/2417CHAPTER 2 COMPUTATIONAL MODELS(1)THEOREM 2.1 The class of regular languages is closed under the union operation.PROOF IDEA.A1=L(M1);A2=L(M2)A1 A2=L(M3)?Let M1=(Q1, , 1, q1,F1) , M2=(Q2, , 2, q2,F2) , thenM3=(Q3, , 3, q3,F3) , where Q3=(r1,r2)|r1 Q1 and r2 Q2, 3(r1,r2), a)=( 1(r1,a), 2(r2,a), q3=(q1, q2), F=(r1,r2)|r1 F1 or r2 F22021/7/2418CHAPTER 2 COMPUTATIONAL MODELS(1) THEOREM 2.2 T