计算引论论文.doc

计算引论 36060203柴巧珍浅谈计算模型计算复杂性理论是用数学方法研究使用数位计算机解决各种算法问题困难度的理论，通俗说来，就是研究用计算机求解问题的难易程度。它有两个度量标准：一是计算所需的步数或指令条数(这叫时间复杂度)，二是计算所需的存储单元数量(这叫空间复杂度)。我们当然不可能也不必要就一个个具体问题去研究它的计算复杂性，而是依据难度去研究各种计算问题之间的联系，按复杂性把问题分成不同的类:常见的时间复杂度按数量级递增排列依次为：常数0(1)、对数阶0(logn)、线形阶0(n)、线形对数阶0(nlogn)、平方阶0(n2)立方阶0(n3)、k次方阶0(nk)、指数阶0(2n)。显然，时间复杂度为指数阶0(2n)的算法效率极低，当n值稍大时就无法应用。不言而喻，对于任意给定的问题。设计出复杂性尽可能低的算法是我们在设计算法时追求的一个重要目标。而可计算性（calculability）是指一个实际问题是否可以使用计算机来解决从广义上讲如“帮我洗衣服”这样的问题是无法用计算机来解决的（至少在目前）而计算机本身的优势在于数值计算，因此可计算性通常指这一类问题是否可以用计算机解决事实上，很多非数值问题（比如文字识别，图象处理等）都可以通过转化成为数值问题来交给计算机处理，但是一个可以使用计算机解决的问题应该被定义为“可以在有限步骤内被解决的问题”，故哥德巴赫猜想这样的问题是不属于“可计算问题”之列的，因为计算机没有办法给出数学意义上的证明，因此也没有任何理由期待计算机能解决世界上所有的问题分析某个问题的可计算性意义重大，它使得人们不必浪费时间在不可能解决的问题上（因而可以尽早转而使用除计算机以外更加有效的手段），集中资源在可以解决的问题集中语言可以看作是一个非空的字母集合，自动机则是一种控制结构，是抽象的计算机模型。形式语言和自动机密切相关。图灵机0型语言（递归可枚举）无限制文法；下面我再说说看书时所得的关于其他自动机的内容。一、正则文法正则语言有穷自动机（DFA、NFA）1、正则语言与正则表达式本质上相同：定理1.1：r是正则表达式，则一定存在某个带_转移的NFA接受r表示的语言L（r），因此，L（r）是正则语言。定理1.2：设L是正则语言，那么总存在正则表达式r，使得LL（r）。L是正则语言L可被某个NFA接受通过删除NFA节点的方法写出r2、右线性文法和左线性文法都是正则文法也就是说，在正则文法中，任何产生式的右侧至多有一个非终结符（变量），且此非终结符一定在产生式右侧的最右端或最左端。如：A xBA x（右线性文法）或A BxA x（左线性文法）3、L是正则语言，当且仅当存在正则文法G，满足LL（G）。4、DFA、NFA的定义定义一个DFA M 是一个5元组M=(Q, , , q0, F)其中，Q：有限的状态集合（非空）：用穷的字母表：转移函数q0Q：初始状态 FQ：终态集合(q , a) = p, 扩充转移函数，就得到了NFA M。5、定理1.3 设L为某个NFA M接受，则存在一个DFA M接受L。DFA和NFA的等价性6、识别非正则语言泵引理泵引理 设L是正则语言，那么一定存在一个只与L相关的正整常数m，使得对任意wL且|w|m，都可以分解成：w = xyz其中，|xy|m|y|1并且，对所有的i0, 1, 2, 都有wi xyiz L。7、正则语言对并、交、补、连接、星闭包、代换（含同态、逆同态）运算都是封闭的。8、构造正则文法、DFA以及正则语言的判断例题见作业本。二、上下文无关文法CFG上下文无关语言CFL非确定型下推自动机（NPDA或PDA）1、定义：文法G（V, T, S, P）称为上下文无关文法CFG(context-free grammar)，如果P中的产生式具有形式A x其中，AV , x(VT)*。L是上下文无关语言CFL，当且仅当存在一个CFG，满足L = L(G)。对任何上下文无关语言CFL，都存在一个NPDA M使得LL(M)。 NPDA（或PDA）的定义：DPDA的定义：2、识别非上下文无关语言CFL泵引理泵引理 设L是上下文无关语言CFL，那么一定存在一个只与L相关的正整常数m，使得对任意wL且|w|m，都可以分解成：w = uvxyz其中，|vxy|m|vy|1并且，对所有的i0, 1, 2, 都有wi uvixyiz L。3、上下文无关语言对并、连接、闭包运算封闭，对交、补运算不封闭。4、设L1是一个CFL，L2是一个正则语言，则L1L2是一个CFL。CFL与正则语言的交是CFL。三、上下文相关文法CSG上下文无关语言CSL线性有界自动机（LBA）1、定义：文法G（V, T, S, P）称为上下文相关文法CSG(context-sensitive)，如果P中的所有产生式都有如下形式x y其中，x,y(VT)*，且|x| |y|L是上下文相关语言CSL，当且仅当存在一个CSG，满足L = L(G)或L(G)。对任何不包含的上下文相关语言CSL，都存在一个LBA M使得LL(M)。 图灵机的运行：让存储带运作起来，外界的信息开始进入图灵机；读写头读出存储带的内容，控制器控制图灵机，使之按照某种特定的规则对纸带传入的信息作出反应，完成程序所规定的动作；完成动作之后，纸带继续移动，开始下一个循环的工作。关于N与NP问题，首先还是说一下我是怎么理解的吧！为了研究问题的复杂性，我们必须将问题抽象，为了简化问题，我们只考虑一类简单的问题，判定性问题，即提出一个问题，只需要回答yes或者no的问题。任何一般的最优化问题都可以转化为一系列判定性问题，比如求图中从A到B的最短路径，可以转化成：从A到B是否有长度为1的路径？从A到B是否有长度为2的路径？。从A到B是否有长度为k的路径？如果问到了k的时候回答了yes，则停止发问，我们可以说从A到B的最短路径就是k。如果一个判定性问题的复杂度是该问题的一个实例的规模n的多项式函数，则我们说这种可以在多项