计算理论导引总结.ppt

1,计算理论,Theory of Computation,2,引言,什么是计算？, 12+3 15 xx 2x Time flies like an arrow. 时光似箭。,计算就是从一个符号行，在能够具体进行的有限步内求出另一符号行。 描述和变换信息,3,计算理论的主要内容,自动机理论 计算的数学模型的定义和性质 可计算理论 把问题分成可解的和不可解的 计算复杂性理论 把问题分成容易计算和难以计算的,4,计算模型正则语言与有穷自动机,有穷自动机 FA：是一个 5 元组 ( Q, , , q0, F ) : QQ 是转移函数。 若 A 是机器 M 接受的全部字符串集，则称 A 是机器 M 的语言，记作 L(M)=A，又称 M 识别 A 或 M 接受 A。,L(M) = w | w 至少一个 1 并且在最后的 1 后面有偶数个 0 ,M = ( q1, q2 , q3 , 0,1 , , q1, q2 ),5,计算模型正则语言与有穷自动机,正则语言：被一台有穷自动机识别的语言。 正则运算： AB 、AB 、A* 正则语言类的封闭性：并、连接、星运算下封闭。 非确定型有穷自动机 (NFA) 是一个 5 元组 ( Q, , , q0, F ) : QP(Q)是转移函数。 DFA机器易算，NFA 人易制造， 通常，人造NFA，让机器把它变成DFA。 当用并行技术去实现时实际上是用NFA。 直观解释：对应于NFA这样的简单并行程序中可以串行化。,6,计算模型正则语言与有穷自动机,正则表达式 DFA、NFA、RE都是正则语言的模型。 泵引理 若 A 是一个正则语言，则存在一个数 p (泵长度) 使得，如果 s 是 A 中任一长度不小于 p 的字符串，那么 s 可以被分成 3 段，s = xyz，满足下述条件： (1) 对于每一个 i 0, xyizA (2) | y | 0 (3) | xy | p,7,计算模型上下文无关文法,上下文无关文法：是一个 4 元组 ( V, , R, S ) (1) V 是一个有穷集合，称为变元集。 (2) 是一个与 V 不相交的有穷集合，称为终结符集。 (3) R 是一个有穷规则集，每条规则由一个变元和一个由变元及终结符组成的字符串构成。 (4) SV 是起始变元。 文法 G = (V,T,R,S)的语言为 L(G) = wT*| S w 设计文法：化繁为简，利用正则，考察子串，利用递归。 文法的歧义性 上下文无关文法的乔姆斯基范式： A BC，A a,8,计算模型上下文无关文法,PDA = NFA + stack with unlimited size 下推自动机是 6 元组(Q, , , , q0, F) : Q P(Q),状态 控制器,栈,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)。 如果一个语言能被某一图灵机识别，则称该语言是图灵可识别的 (Turning recognizable)。也称为递归可枚举语言。 如果一个语言能被某一图灵机判定，则称该语言是图灵可判定的 (Turning decidable)。也称为递归语言。 图灵机的变形：不确定的 TM 、多带 TM,状态 控制器,11,可计算理论可判定性,ADFA = | B 是 DFA，w 是串，B 接受 w ANFA = | B 是 NFA，w 是串，B 接受 w AREX = | R是正则表达式，w是串，R 派生w EDFA = | A 是 DFA，且 L(A) = EQDFA = | A 和 B 都是 DFA，且 L(A)=L(B) ACFG= | G 是 CFG，w 是串，G 派生 w ECFG = | G 是 CFG，且 L(A) = 对角线法 停机问题 ATM= | M 是一个 TM，且接受 w 一个语言是可判定的，当且仅当它既是图灵可识别的，也是补图灵可识别的。 TM 不是图灵可识别的。,12,可计算理论可归约性,归约的目的在于：将一个问题转化为另一个问题；且用第二个问题的解来解第一个问题。 归约的应用（A 可归约到 B ） 如果 B 是可判定的，则 A 也是可判定的。 如果 A 是不可判定的，则 B 也是不可判定的。 不可判定问题 HALTTM = | 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， wA f (w) B 记作AmB。称函数 f 为 A 到 B 的归约。 如果 AmB 且 B 是可判定的，则 A 也是可判定的。 如果 AmB 且 A 是不可判定的，则 B 也是不可判定的。 如果AmB，且B是可图灵可识别的，则A也是图灵可识别的。 如果AmB，且A不是图灵可识别的，则B也不是图灵可识别的。 EQTM 既不是图灵可识别的，也不是补图灵可识别的。 递归定理及其应用,14,复杂性理论时间复杂性,分析时间复杂性只把算法的运行时间纯粹作为表示输入字符串的长度来计算，而不考虑其它参数。 停机的确定型图灵机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) 时间的确定型图灵机等价。,15,复杂性理论时间复杂性,P 是确定型单带图灵机在多项式时间内可判定的语言类。 P 中的问题： PATH = | G 是具有从 s 到 t 的有向路径的有向图 RELPRIME = | x 与 y 互素 一个上下文无关语言都是 P 的成员。 NP 是具有多项式时间验证机的语言类。 在非确定型多项式时间内判定 HAMPATH 问题的非确定型图灵机 一个语言在 NP 中，当且仅当它能被某个非确定型多项式时间图灵机判定。 NTIME(t(n) = L | L是一个被O (t(n)时间的非确定型图灵机判定的语言 NP = kNTIME(nk),16,复杂性理论时间复杂性,NP中问题举例。 CLIQUE = | G 是包含 k 团的无向图 SUBSET-SUM NP完全性： NP 中的某些问题的复杂性与整个类的复杂性相关联。这些问题中任何一个如果存在多项式时间算法，那么所有 NP 问题都是多项式时间可解的。 语言 A 称为多项式时间映射可归约到语言 B，记为ApB，若存在多项式时间可计算函数 f : *，对于每一个 w，有 wA f(w)B。 如果语言 B 满足下面两个条件，就称为NP完全的： 1）B 属于 NP，并且 2）NP 中的每个 A 都多项式时间可归约到 B。 NP完全问题： SAT 、3 SAT 、 CLIQUE 、 VERTEX COVER 、 HAMPATH、 SUBSET-SUM,17,复杂性理论空间复杂性,在所有输入上都停机的确定型图灵机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 : NR+ ，其中 f(n) n，NSPACE( f(n) ) SPACE( f 2(n) )。 P NP PSPACE=NPSPACE EXPTIME PSPACE完全的、 PSPACE难的 TQBF=| 是真的全量词化的布尔公式 PSPACE 完全的 L 类 NL 类、 NL 完全性、 NL 等于 coNL,18,复杂性理论难解性,层次定理的含义：定理中的每一个都能证明时间和空间复杂性类不全相同，它们形成了一个层次结构，其中时空界限较大的类比时空界限较小的类包含更多的语言。 相应的概念和结论 在相对化方法中，将修改计算模型，给图灵机一些本质上是“免费”的信息。依据实际提供给它的信息，图灵机就可能比以前更轻松地解决某些