欢迎来到天天文库
浏览记录
ID:35319467
大小:729.50 KB
页数:11页
时间:2019-03-23
《《计算理论》复习题总结》由会员上传分享,免费在线阅读,更多相关内容在应用文档-天天文库。
1、《计算理论》复习题总结1、自动机、可计算性、复杂性内涵及关系;计算理论的三个传统的核心领域:自动机、可计算性和复杂性。通过“计算机的基本能力和局限性是什么?“这一问题将这三个领域联系在一起。可计算理论与复杂性理论是密切相关的,在复杂性理论中,目标是把问题分成容易计算的和难计算的;而在可计算理论中,是把问题分成可解的和不可解。自动机阐述了计算的数学模型的定义和性质,主要包含两种模型:有穷自动机模型;上下文无关文法模型。可计算性理论和复杂性理论需要对计算机给了一个准确的定义。自动机理论允许在介绍与计算机科学的其他非理论领域有关的概
2、念时使用计算的形式化定义。2、有穷自动机、正则语言、正则表达式、非确定有穷自动机、非正则语言;有穷自动机:描述能力和资源极其有限的计算机模型。是一个5元组(Q,∑,δ,q0,F),其中1)Q是一个有穷集合,称为状态集。2)∑是一个有穷集合,称为字母表。3)δ:Q×∑→Q是转移函数。4)q0Q是起始状态。5)FQ是接受状态集。正则语言:如果一个语言能被有穷自动机识别。正则表达式:用正则运算符构造描述语言的表达式。称R是正则表达式,如果R是:1)a,a是字母表中的一个元素;2);3);4)(R1R2);5)(R1R2);6)(R1
3、*)非确定有穷自动机:是一个5元组(Q,∑,δ,q0,F),其中1)Q是有穷状态集。2)∑是有穷字母表。3)δ:Q×∑→P(Q)是转移函数。4)q0Q是起始状态。5)FQ是接受状态集。3、上下文无关语言及上下文无关文法、歧义性、乔姆斯基范式、下推自动机、等价性、非上下文无关语言;上下文无关语言:用上下文无关文法生成的语言。上下文无关文法:是一个4元组(V,∑,R,S)且1)V是一个有穷集合,称为变元集2)∑是一个与V不相交的有穷集合,称为终结符集3)R是一个有穷规则集,每条规则由一个变元和一个由变元及终结符组成的字符串构成,4
4、)SV是起始变元歧义性:如果字符串W在上下文无关文法G中有两个或者两上以上不同的最左派生,则称G歧义地产生的字符串W。如果文法G歧义的产生某个字符串则称G是歧义的。乔姆斯基范式:一个上下文无关文法如果它的每一个规则具有如下形式A→BCA→a其中a为任意终结符,ABC为任意变元且BC不是起始变元,此外允许规则S→其中S是起始变元。下推自动机:是6元组Q,∑,,δ,q0,F),这里Q,∑,,F都是有穷集合,并且1)Q是状态集2)∑是字母表3)是栈字母表4)δ:Q×∑×→P(Q×)是转移函数学5)q0Q是起始状态。6)FQ是接受状态
5、集。4、各种等价性;每一台非确定型有穷自动机等价于一台确定的有穷自动机;一个语言是正则的当且仅当可以用正则表达式描述;一个语言是上下文无关的则存在一台下推自动机识别它。5、计算科学;能性问题;Church-Turing论题;计算;可计算;计算科学:系统的研究信息描述和变换的算法,包括其理论、分析、设计、效率、实现和应用。用计算科学涵盖并称谓计算机科学和计算机工程。计算机科学所研究问题的核心是能行问题。能行问题:什么能被(有效的)自动化?什么不能被(有效)的自动化?Church-Turing论题:可计算性等价于Turing机可计
6、算性。计算:Truing机所进行的工作就是计算。可计算:Turing机能够进行的工作就叫可计算。6、几个计算模型;各种计算模型的特点;图灵机的特点;计算模型:1、递归函数。Gödel,Church,等人提出并完善了递归函数理论。从数学演算的思想出发,考虑从简单的、直观上可计算的函数出发构复杂的可计算函数。2、Turing机(理论模型):Turing研究的Turing机计算模型与现代计算机更接近,在Turing机的基础上引进了大量的自动机。3、Church-λ演算:用来描述计算过程,基本思想主要用于函数式程序语言的研制。4、Po
7、st系统(符号变换系统):Post系统的基础上引进了大量的形式语言。Turing机的特点:存储无穷,时间无限制。Turing机可计算只是理论上可计算,并不是现实可计算。现实可计算:研究计算复杂性。但如果Turing机不可计算则现实更不可计算。7、原语言,指令系统,输入输出规定;原语言:变元、标号(语句标号)、指令:X=X+1;X=X-1;ToAIFX≠0;ToA;Y=X输入变元用x表示x,x1,x2,x3,……输出变元用y表示,函数只输出一个值。对程序做如下两点规定:1、当程序开始执行时自动认为一切变元的值为0(输入变元除外)
8、2、当程序出现下列两种情形之一时,自动认为停机。a、转向无定义的标号b、执行程序的最后一条指令。8、n元程序对应的n元函数的定义;若程序P恰有n个输入变元X1,X2,……,Xn,而没有其它X变元,则称P为n元程序。n元程序P对应的函数Ψp(X1,X2,……,Xn)定义如下:Ψ
此文档下载收益归作者所有