《计算理论》复习题总结
1、 自动机、可计算性、复杂性内涵及关系;
计算理论的三个传统的核心领域:自动机、可计算性和复杂性。通过“计算机的基本能力和局限性是什么?“这一问题将这三个领域联系在一起。可计算理论与复杂性理论是密切相关的,在复杂性理论中,目标是把问题分成容易计算的和难计算的;而在可计算理论中,是把问题分成可解的和不可解。自动机阐述了计算的数学模型的定义和性质,主要包含两种模型:有穷自动机模型;上下文无关文法模型。可计算性理论和复杂性理论需要对计算机给了一个准确的定义。自动机理论允许在介绍与计算机科学的其他非理论领域有关的概念时使用计算的形式化定义。
2、 有穷自动机、正则语言、正则表达式、非确定有穷自 动机、非正则语言;
有穷自动机:描述能力和资源极其有限的计算机模型。是一个5元组(Q,∑,δ,q0,F),其中1)Q是一个有穷集合,称为状态集。2)∑是一个有穷集合,称为字母表。3)δ:Q×∑→Q是转移函数。4)q0 Q是起始状态。5)F Q是接受状态集。 正则语言:如果一个语言能被有穷自动机识别。
正则表达式:用正则运算符构造描述语言的表达式。称R是正则表达式,如果R是:1)a,a是字母表中的一个元素;2) ;3) ;4)(R1 R2);5)(R1 R2);6)(R1*)
非确定有穷自动机:是一个5元组(Q,∑,δ,q0,F),其中1)Q是有穷状态集。2)∑是有穷字母表。3)δ:Q×∑ →P(Q)是转移函数。4)q0 Q是起始状态。5)F Q是接受状态集。
3、 上下文无关语言及上下文无关文法、歧义性、乔姆 斯基范式、下推自动机、等价性、非上下文无关语言;
上下文无关语言:用上下文无关文法生成的语言。
上下文无关文法:是一个4元组(V,∑,R,S)且1)V是一个有穷集合,称为变元集2)∑是一个与V不相交的有穷集合,称为终结符集3)R是一个有穷规则集,每条规则由一个变元和一个由变元及终结符组成的字符串构成,4)S V是起始变元
歧义性:如果字符串W在上下文无关文法G中有两个或者两上以上不同的最左派生,则称G歧义地产生的字符串W。如果文法G歧义的产生某个字符串则称G是歧义的。
乔姆斯基范式:一个上下文无关文法如果它的每一个规则具有如下形式A→BC A→a其中a为任意终结符,ABC为任意变元且BC不是起始变元,此外允许规则S→ 其中S是起始变元。 下推自动机:是6元组Q,∑, ,δ,q0,F),这里Q,∑, ,F都是有穷集合,并且1)Q是状态集 2)∑是字母表 3) 是栈字母表 4)δ: Q×∑ × →P(Q× )是转移函数学 5)q0 Q是起始状态。6)F Q是接受状态集。
4、 各种等价性;
每一台非确定型有穷自动机等价于一台确定的有穷自动机;一个语言是正则的当且仅当可以用正则表达式描述;一个语言是上下文无关的则存在一台下推自动机识别它。
5、 计算科学;能性问题;Church-Turing论题;计算; 可计算;
计算科学:系统的研究信息描述和变换的算法,包括其理论、分析、设计、效率、实现和应用。用计算科学涵盖并称谓计算机科学和计算机工程。计算机科学所研究问题的核心是能行问题。能行问题:什么能被(有效的)自动化?什么不能被(有效)的自动化? Church-Turing论题:可计算性等价于Turing机可计算性。 计算:Truing机所进行的工作就是计算。 可计算:Turing机能够进行的工作就叫可计算。
6、 几个计算模型;各种计算模型的特点;图灵机的特点;
计算模型:1、递归函数。Gödel,Church,等人提出并完善了递归函数理论。从数学演算的思想出发,考虑从简单的、直观上可计算的函数出发构复杂的可计算函数。2、Turing机(理论模型):Turing研究的Turing机计算模型与现代计算机更接近,在Turing机的基础上引进了大量的自动机。 3、Church-λ演算:用来描述计算过程,基本思想主要用于函数式程序语言的研制。4、Post系统(符号变换系统):Post系统的基础上引进了大量的形式语言。
Turing机的特点:存储无穷,时间无限制。Turing机可计算只是理论上可计算,并不是现实可计算。现实可计算:研究计算复杂性。但如果Turing机不可计算 则现实更不可计算。
7、 原语言,指令系统,输入输出规定;
原语言:变元、标号(语句标号)、指令:X=X+1;X=X-1;To A IF X≠0;To A;Y=X输入变元用x表示 x,x1,x2,x3, 输出变元
用y表示,函数只输出一个值。
对程序做如下两点规定:1、当程序开始执行时自动认为一切变元的值为0 (输入变元除外)2、当程序出现下列两种情形之一时,自动认为停机。a、转向无定义的标号b、执行程序的最后一条指令。
8、 n元程序对应的n元函数的定义;
若程序P恰有n个输入变元X1,X2, ,Xn,而没有其它X变元,则称P为n元程序。
数据结构复习题总结 22页 1财富值 广播电视概论复习题总结 8页 免费 细胞复习题总结 2页 免费 教育学总结后复习题 5页 免费 《计算理论》复习题总结 11页 ...
4页 免费 计算理论试卷 5页 1财富值 计算理论试卷(2006)参考答... 4页 免费 《计算理论》复习题总结 11页 免费 计算机研究生《计算理论》... 4页 免费...
《计算理论》复习题总结 11页 免费 第二章、正则语言 139页 免费 photoshop ...课后练习: 一、选择题 1、用二维表来表示实体及实体之间联系的数据模型是:关系...
《计算理论》复习题总结 11页 免费 计算机理论基础试题及答案 14页 10财富值 计算理论试题及答案 3页 免费 计算机基础知识试题详解 10页 免费 计算理论课件打印...
计算理论复习 7页 1财富值 计算机基础知识测试题(带答... 24页 免费 计算机研究生《计算理论》... 4页 免费 《计算理论》复习题总结 11页 免费 计算机一...
护理学基础期末总结复习... 1页 1下载券 2012导游基础试题总结 9页 1下载...根据刑法理论,甲的行为触犯何种罪名,请从犯罪的客观方面说明理由。 答案要点:甲...
计算理论习题答案 CHAP2 n... 9页 1财富值 计算理论习题答案CHAP4new 6页 1财富值 计算理论习题答案CHAP7new 7页 1财富值 《计算理论》复习题总结 11页 ...
研究生 计算机理论题库研究生 计算机理论题库隐藏>> 《计算理论》复习题 1、设语言 A={w w 含有子串 0101,即对某个 x 和 y,w=x0101y} ,字母表为{...
计算理论答案ch4 4页 2财富值 计算理论答案ch2 6页 2财富值 计算理论答案ch1 2页 2财富值 《计算理论》复习题总结 11页 免费 计算理论试题及答案 3页 免费...
热门文档