计算理论笔记

未经许可,禁止转载。
本文链接地址: https://www.annhe.net/article-1454.html

转一个学长的总结,原文http://chj-yh.i.sohu.com/blog/view/113784360.htm

 

第一章  导引

1、如果起始状态也是接受状态,则接受空串 。

2、计算的形式定义:

   设M={……},是一台有穷自动机,w=w0w1……wn是字母表上的一个字符串,如果Q中存在状态序列r0,r1,…. rn,满足以下条件:

     r0=q0

     (ri,wi+1)=ri+1  ,i=0,1,….,n-1

       rn 属于F

则M接受w。

3、正则语言的定义:

如果一个语言能够被一台有穷自动机识别,则称他是正则语言。

4、正则语言的运算封闭性:并,连接,星 。

5、DFA    确定型有穷自动机   NFA  非确定型有穷自动机。

6、费确定型有穷自动机:产生的是下一个状态的集合P(Q)。而DFA是一个状态。

7、DFA和NFA识别相同的语言。能够识别相同的语言则认为是等价的。

8、一个语言是正则的当且仅当可以用正则表达式描述它。

第二章  正则语言

1、自动机的形式定义:5元组,状态集,字母表,转移函数,起始状态,终结状态。

第三章          上下文无关语言

1、上下文无关文法的形式定义。四元组—-变元集、终结符集、规则集、起始变元。

2、正则语言与确定性自动机DFA等价。

3、乔姆斯基范式:A—>BC,A—>a,a为任意终结符,A、B、C为变元,其中B、C不能为起始变元,允许S—>空,其中S为起始变元。任意上下文无关语言都可以用乔姆斯基范式产生。

4、CFG转乔姆斯基范式:去空规则,删除变元;处理单一规则,传递增加规则。P65.

5、下推自动机PDA:6元组,状态集、字母表、栈字母表、转移函数、起始状态、终结状态集,与上下文无关文法等价;

6、一个语言是上下文无关的,当且仅当有一台PDA识别他。

7、非上下文无关语言的泵引理:P74。

第四章  丘奇-图灵论题

1、图灵机的形式化定义:7元组。

2、如果有图灵机识别的一个语言,则称这个语言是图灵可识别的。

3、判定器:对所有输入都停机的图灵机。永不循环。总能是拒绝或者接受。

4、图灵可识别的语言不一定都是图灵可判定的。图灵可判定语言都是图灵可识别的。

5、多带图灵机:与单带图灵机等价,虚拟读写头和磁带,相对于单带,用#号将各带子分开。

6、一个语言是图灵可识别的当且仅当有多带图灵机识别他。

7、非确定型图灵机:在任何时刻,机器可以在多种可能性中选择一种继续进行。

8、每个非确定型图灵机都有一个确定型图灵机与之等价。

9、一个语言是可判定的当且仅当有一个非确定性图灵机判定他。

10、枚举器:图解P91。

11、丘奇:那么打演算,图灵:机器判定。

12、图灵机连通图的判定:扫描顶点,做标记,已标记顶点和无标记顶点是否存在边,做标记,扫描所有顶点,决定是接受还是拒绝。

13、0-PDA就是一个NFA,1-PDA就是pda,3PDA不比2PDA强。

第五章  可判定性  停机并相应的进入拒绝或者接受状态

1、与正则语言有关的可判定性问题:

ADFA :DFA  B是否接受w的问题。ADFA是可判定的。ANFA是可判定的。ARES是可判定的。EDFA是可判定的。EQDFA是可判定的。P100。核心思想:图灵机跟踪DFA的状态和当前位置,状态和位置的变化由转移函数决定。

2、与上下文无关语言相关的可判定性问题:

ACFG是一个可判定语言。核心思想:将CFG转换为乔姆斯基文法,w的任意派生都是2n-1步,只需检查2n-1步内的派生,其中n是w的长度。ECFG是可判定的。所有的CFG都是可判定的。

3、停机问题(图灵机进入循环):

ATM是不可判定的,但确实图灵可识别的(识别不一定能判定,能判定则一定可以识别)。

停机问题是不可判定的,存在无限循环。

4、对角化方法:存在语言是不是图灵可识别的。

5、一个语言是可判定的,当且仅当他既是图灵可识别的,也是补图灵可识别的。即:一个语言是可判定的,当且仅当他和他的补都是图灵可识别的。(消除无限循环)

6、ATM的补不是图灵可识别的。

7、D正,上无P。

第六章  可规约性

1、可规约性:计算上是不可解的问题。规约就是将一个问题转化为另一个问题的方法。

2、HALTTM是不可判定的。核心思想,将其规约到一个图灵机可以判定的问题。构造一个图灵机来判定ATM,得出矛盾。ETM是不可判定的。

3、REGULARTM是不可判定的(M是一个TM,而且其识别的语言是正则语言)。核心思想:

4、赖斯定理:检查关于语言的任何一个性质是否有图灵机识别都是不可判定的。EQTM是不可判定的(核心思想:根据Etm的不可判定性)。

5、LBA:线性界限自动机。不会离开带子的左右端点,TM不会离开带子的左端点。

6、每个CFL都可以用一个LBA判定,ADFA,ACFG,EDFA,ECFG的判定器都是LBA。

7、ALBA是可判定的。ELBA是不可判定的。ALLCFG是不可判定的。PCP(波斯特对应问题)是不可判定的。核心思想:将其规约到ATM是不可判定的。

8、ALBA的格局是有限的,qngn个。Q为状态数,n为带子长度,g为符号数。

9、映射可规约性(上面讲的都是计算历史可规约性):

10、可计算函数:

11、映射可规约的定义(略)。P124。

12、EQTM既不是图灵可识别的,也不是补图灵可识别的(是不可判定的)。核心思想:

构造ATM到EQTM的映射归约。P125。

第七章  可计算理论的高级专题

第八章   时间复杂性

1、时间复杂度的定义:w的长度的函数f(n)所经过的最大步数。

2、时间复杂性类:略。P149。

3、单带图灵机在o(nlogn)时间内判定的语言都是正则语言。如果是双带图灵机,则可以在O(n)时间内判定。核心思想:复制比较。

4、模型间的复杂性关系:

每一个t(n)时间的多带图灵机都和某个o(t2(n))的单带图灵机等价。

每一个t(n)的非确定性单带图灵机都与某个2Otn))的确定性图灵机等价。

5、P类:是确定型单带图灵机在多项式时间内可以判定的语言类。

PATH是P类问题——核心思想:进行单点标记。

REALPRIME是P类问题——核心思想:欧几里德算法,gcd(x,y)=1。

每一个上下文无关语言是多项式时间可判定的——核心思想:2n-1步推到,动态规划。

6、NP类:是具有多项式时间验证机的语言类。不具备多项式时间解决方法。

验证机:是一个算法,多项式时间算法。

一个语言在NP中,当且仅当它能够被某个非确定型多项式时间图灵机判定。或者是存在验证机在多项式时间内判定。

图中团的判定。子集和问题。

NP《= EXPTIME《= TIME( )

7、NP    完全问题:NP中的某些问题的复杂性与整个类的复杂性相关,这些问题中的任何一个问题如果存在多项式时间算法,那么所有NP问题都是多项式时间可解的,这些问题称为NP完全的。

8、SAT是P,当且仅当P=NP。SAT是NP完全的。

9、多项式时间可规约性:定义见P162。

10、NP完全性的定义:满足两个条件

B属于NP,并且,NP中的每个A都可以多项式时间可规约到B。

11、几个NP完全问题:coNP

团,顶点覆盖,哈密顿回路问题,SAT问题,子集和问题。

补充:

文字:变量或者变量的非。

子句:由或者连接起来的文字。

合取范式(cnf):由并连接起来的子句。

3cnf:所有的子句都有3个文字。

第九章  空间复杂性问题

1、核心思想:空间可以重用,而时间不能。比如说SAT可以在线性空间内解决。

2、SPACE(f(n))和NSPACE(f(n))。定义略,确定型图灵机和非确定型图灵机判定的语言类。

3、萨维奇定理:任何非确定型TM都可以转化为f2(n)空间的确定型TM。

核心思想:t步的格局变化问题——可产生性问题。

4、PSPACE类:在确定型图灵机在多项式时间内可以判定的语言类。P183。

5、P<=NP<=PSPACE<=NPSPACE<=EXPTIME。

6、PSPACE完全性:

     B属于PSPACE,PSPACE中的每一个语言A可多项式时间可规约到B。

     如果只有第二条满足,则称B为PSPACE难的。

7、PSPACE完全性问题:

补充:

前述范式:量词出现在语句的开头。带量词的布尔公式称为量词化布尔公式。全量词化布尔公式称为句子。全量词化:变量出现在某个量词的辖域内。



未经许可,禁止转载。
本文链接地址: https://www.annhe.net/article-1454.html

发表评论

电子邮件地址不会被公开。 必填项已用*标注