计算理论总结

1计算理论TheoryofComputation2引言什么是计算？ξη12+315x·x2xTimeflieslikeanarrow.时光似箭。计算就是从一个符号行ξ，在能够具体进行的有限步内求出另一符号行η。描述和变换信息3计算理论的主要内容自动机理论计算的数学模型的定义和性质可计算理论把问题分成可解的和不可解的计算复杂性理论把问题分成容易计算和难以计算的4计算模型—正则语言与有穷自动机有穷自动机FA：是一个5元组(Q,,,q0,F):QQ是转移函数。若A是机器M接受的全部字符串集，则称A是机器M的语言，记作L(M)=A，又称M识别A或M接受A。L(M)={w|w至少一个1并且在最后的1后面有偶数个0}q1q2q3100,10122323221110qqqqqqqqqM=({q1,q2,q3},{0,1},,q1,q2)5计算模型—正则语言与有穷自动机正则语言：被一台有穷自动机识别的语言。正则运算：A∪B、AB、A*正则语言类的封闭性：并、连接、星运算下封闭。非确定型有穷自动机(NFA)是一个5元组(Q,,,q0,F):QεP(Q)是转移函数。DFA机器易算，NFA人易制造，通常，人造NFA，让机器把它变成DFA。当用并行技术去实现时实际上是用NFA。直观解释：对应于NFA这样的简单并行程序中可以串行化。6计算模型—正则语言与有穷自动机正则表达式DFA、NFA、RE都是正则语言的模型。泵引理若A是一个正则语言，则存在一个数p(泵长度)使得，如果s是A中任一长度不小于p的字符串，那么s可以被分成3段，s=xyz，满足下述条件：(1)对于每一个i0,xyiz∈A(2)|y|0(3)|xy|≤p7计算模型—上下文无关文法上下文无关文法：是一个4元组(V,,R,S)(1)V是一个有穷集合，称为变元集。(2)是一个与V不相交的有穷集合，称为终结符集。(3)R是一个有穷规则集，每条规则由一个变元和一个由变元及终结符组成的字符串构成。(4)SV是起始变元。文法G=(V,T,R,S)的语言为L(G)={wT*|Sw}设计文法：化繁为简，利用正则，考察子串，利用递归。文法的歧义性上下文无关文法的乔姆斯基范式：ABC，Aa8计算模型—上下文无关文法PDA=NFA+stackwithunlimitedsize下推自动机是6元组(Q,,,,q0,F):Q××P(Q×)xyz$状态控制器栈aabbqpa,Zα9计算模型—上下文无关文法PDA与上下文无关文法等价。上下文无关语言的泵引理如果A是上下文无关语言，则存在p(泵长度)，使得A中任何一个长度不小于p的字符串s都能被划分成5段s=uvxyz，且满足下述条件：(1)对于每一个i0,uvixyizA；(2)|vy|0；(3)|vxy|p。10可计算理论—图灵机图灵机是一个7元组(Q,,,,q0,qaccept,qreject):Q×Q××{L,R}是转移函数。图灵机的格局：当前状态、当前带内容和读写头当前位置组合在一起。图灵机M接受的字符串的集合称为M的语言，或被M识别的语言，记为L(M)。如果一个语言能被某一图灵机识别，则称该语言是图灵可识别的(Turningrecognizable)。也称为递归可枚举语言。如果一个语言能被某一图灵机判定，则称该语言是图灵可判定的(Turningdecidable)。也称为递归语言。图灵机的变形：不确定的TM、多带TM状态控制器baa11可计算理论—可判定性ADFA={B,w|B是DFA，w是串，B接受w}ANFA={B,w|B是NFA，w是串，B接受w}AREX={R,w|R是正则表达式，w是串，R派生w}EDFA={A|A是DFA，且L(A)=}EQDFA={A,B|A和B都是DFA，且L(A)=L(B)}ACFG={G,w|G是CFG，w是串，G派生w}ECFG={G|G是CFG，且L(A)=}……对角线法停机问题ATM={M,w|M是一个TM，且接受w}一个语言是可判定的，当且仅当它既是图灵可识别的，也是补图灵可识别的。ĀTM不是图灵可识别的。12可计算理论—可归约性归约的目的在于：将一个问题转化为另一个问题；且用第二个问题的解来解第一个问题。归约的应用（A可归约到B）如果B是可判定的，则A也是可判定的。如果A是不可判定的，则B也是不可判定的。不可判定问题HALTTM={M,w|M是一个TM,且对输入w停机}ETM={M|M是一个TM，且L(M)=}空问题EQTM={M1,M2|M1和M2都是TM，且L(M1)=L(M2)}检查关于语言的任何一个性质是否可由图灵机识别都是不可判定的。（莱斯定理）13可计算理论—可归约性可计算函数f:**，如果有某个图灵机M，使得在每个输入w上停机，且此时只有f(w)出现在带上。“用映射可归约性将问题A归约为问题B”是指，存在一个可计算函数，它将问题A的实例转换成问题B的实例。语言A是映射可归约到语言B的，如果存在可计算函数f:**使得对每个w，w∈Af(w)∈B记作A≤mB。称函数f为A到B的归约。如果A≤mB且B是可判定的，则A也是可判定的。如果A≤mB且A是不可判定的，则B也是不可判定的。如果A≤mB，且B是可图灵可识别的，则A也是图灵可识别的。如果A≤mB，且A不是图灵可识别的，则B也不是图灵可识别的。EQTM既不是图灵可识别的，也不是补图灵可识别的。14可计算理论—高级专题递归定理及其应用图灵可归约性信息的定义15复杂性理论—时间复杂性分析时间复杂性只把算法的运行时间纯粹作为表示输入字符串的长度来计算，而不考虑其它参数。停机的确定型图灵机M的运行时间或者时间复杂度f(n)是M在所有长度为n的输入上运行时所经过的最大步数。非确定型图灵机N的运行时间f(n)是在任何长度为n的输入上所有的计算分支中最大步数。大O和小o记法TIME(t(n))为由O(t(n))时间的图灵机判定的所有语言的集合。在可计算性理论中，所有合理的计算模型都是等价的。在复杂性理论中，模型的选择影响语言的时间复杂度。根据计算问题的时间复杂度来对问题分类。每一个t(n)时间的多带图灵机都和某一个O(t2(n))时间的单带图灵机等价。每一个t(n)时间的非确定型单带图灵机都与某一2O(t(n))时间的确定型图灵机等价。16复杂性理论—时间复杂性P是确定型单带图灵机在多项式时间内可判定的语言类。P中的问题：PATH={G,s,t|G是具有从s到t的有向路径的有向图}RELPRIME={x,y|x与y互素}一个上下文无关语言都是P的成员。NP是具有多项式时间验证机的语言类。在非确定型多项式时间内判定HAMPATH问题的非确定型图灵机一个语言在NP中，当且仅当它能被某个非确定型多项式时间图灵机判定。NTIME(t(n))={L|L是一个被O(t(n))时间的非确定型图灵机判定的语言}NP=∪kNTIME(nk)17复杂性理论—时间复杂性NP中问题举例。CLIQUE={G,k|G是包含k团的无向图}SUBSET-SUMNP完全性：NP中的某些问题的复杂性与整个类的复杂性相关联。这些问题中任何一个如果存在多项式时间算法，那么所有NP问题都是多项式时间可解的。语言A称为多项式时间映射可归约到语言B，记为A≤pB，若存在多项式时间可计算函数f:**，对于每一个w，有w∈Af(w)∈B。如果语言B满足下面两个条件，就称为NP完全的：1）B属于NP，并且2）NP中的每个A都多项式时间可归约到B。NP完全问题：SAT、3SAT、CLIQUE、VERTEX–COVER、HAMPATH、SUBSET-SUM18复杂性理论—空间复杂性在所有输入上都停机的确定型图灵机M的空间复杂度f(n)是M在任何长为n的输入上扫描带方格的最大数。所有输入在所有分支上都停机的非确定型图灵机M的空间复杂度f(n)为M在任何长为n的输入上，在任何计算分支上所扫描的带方格的最大数。SPACE(f(n))={L|L是被O(f(n))空间的确定型图灵机判定的语言}NSPACE(f(n))={L|L是被O(f(n))空间的非确定型图灵机判定的语言}萨维奇定理：对于任何函数f:NR+，其中f(n)n，NSPACE(f(n))SPACE(f2(n))。PNPPSPACE=NPSPACEEXPTIMEPSPACE完全的、PSPACE难的TQBF={|是真的全量词化的布尔公式}PSPACE完全的L类NL类、NL完全性、NL等于coNL19复杂性理论—难解性层次定理的含义：定理中的每一个都能证明时间和空间复杂性类不全相同，它们形成了一个层次结构，其中时空界限较大的类比时空界限较小的类包含更多的语言。空间层次定理、时间层次定理…在相对化方法中，将修改计算模型，给图灵机一些本质上是“免费”的信息。依据实际提供给它的信息，图灵机就可能比以前更轻松地解决某些问题。电路复杂性布尔电路、电路族、……3SAT是NP完全的20复杂性理论高级专题近似算法k-优，MIN-VERTEX-COVER，MAX-CUT概率算法概率图灵机、素数性、BPP类、费马小定理、判定素数算法交错式交错式图灵机、语言分类交互式证明系统检验者、证明者、模型的定义并行计算密码学单向函数、天窗函数