《计算理论导引》PPT课件.ppt

《《计算理论导引》PPT课件.ppt》由会员分享，可在线阅读，更多相关《《计算理论导引》PPT课件.ppt（19页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、 计算理论导引与算法复杂性计算理论导引与算法复杂性Introduction to the Theory of Computation and Algorithm Complexities 主讲：刘国华主讲：刘国华（学院楼学院楼225225室室，），）助教：辛婷婷助教：辛婷婷（学院楼学院楼153153室室，），）6 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)Equality 00=1,1 0=06)Implication 10=0,1

2、1=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!CHAPTER 2COMPUTATIONAL MODELS(1)Computation?Computation is a general term for any type of process,algorithm or measurement;this often includes but is not limited to digital data.Computation is a process fol

3、lowing 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.CHAPTER 2COMPUTATIONAL MODELS(1)AUTOMATATURING MACHINESCHAPTER 2 COMPUTATIONAL MODELS(1)AUTOMATA1 FINITE AUTOMATA1)DETERMINISTIC FINITE AUTO

4、MATA(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 door is opening,if some one is standing on the rear pad(REAR),then the door keeps opening;

5、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;CHAPTER 2 COMPUTATIONAL MODELS(1)front padrear padRules for closing:1 The door is opening,if no one is standing on either pad(NEITHER),then the door closes;2 The

6、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 rear pad(BOTH),then the door keeps closing.How to implement this system?Hardwares:two sensors;one computer(only 1 b

7、it memory),etc.How about the software?CHAPTER 2 COMPUTATIONAL MODELS(1)satrttTRUE;d 0t=TRUE?Ys1sensor1s2sensor2d=0and(s2=1ors1=1ands2=1ors1=0ands2=0)Yd=1and(s1=1ors2=1ors1=1ands2=1)NYd=0ands1=1NYd1d=1ands1=0ands2=0Yd0NendNNCHAPTER 2 COMPUTATIONAL MODELS(1)front padrear padCLOSED(d=0)OPEN(d=1)NEITHER

8、(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)CHAPTER 2 COMPUTATIONAL MODELS(1)front padrear padCLOSEDOPENNEITHERFORNTREARBOTHNEITHER FORNTREARBOTHCHAPTER 2 COMPUTATIONAL MODELS(1)front padrear padCLOSEDOPENNEITHERFORNTBOTH REARNEITHER F

9、ORNT BOTHREARCHAPTER 2 COMPUTATIONAL MODELS(1)CLOSEDOPENNEITHERFORNTREARBOTHNEITHER FORNTREARBOTHfront padrear padCHAPTER 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

10、),where1.Q is a finite set called the states,2.is a finite set called the alphabet,3.:Q Q is the transition function,4.q0 Q is the start state,and5.F Q is the set of accept states.CHAPTER 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

11、 q2 q2 q3 q2 q3 q2 q24.q1 is the start state,and5.F=q2.CHAPTER 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

12、w if a sequence of states r0,r1,rn in Q exists 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 recognizesCHAPTER 2 COMPUTATIONAL MODELS(1)DESIGNING FINITE AUTOMATAqevenqodd0011How to design a DFA t

13、o recognize the language of all strings that contain the string 001 as a substring.q11q2q3010,10q410CHAPTER 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,

14、girlA B=goodboy,goodgirl,badboy,badgirlA =,good,bad,goodgood,goodbad,badbad,badgood,goodgoodgood,goodgoodbad,goodbadgood,goodbadbad,*CHAPTER 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

15、,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 F2CHAPTER 2 COMPUTATIONAL MODELS(1)THEOREM 2.2 The class of regular languages is closed under the concatenation operation.CHAPTER 2 COMPUTATIONAL MODELS(1)练习题：练习题：1 1 写出该状态图所表示写出该状态图所表示DFADFA的形式化定义的形式化定义.q10,q2q310212,021,2 2 给定一个语言给定一个语言A=w|wA=w|w以以1 1结束结束，设计一个识别它的，设计一个识别它的DFA.DFA.