16-计算模型.

解放军理工大学指挥自动化学院第17讲计算模型杨明指挥信息系统学院软件工程教研中心[e-mail]算法设计与分析2020/1/14第17讲计算模型解放军理工大学指挥自动化学院2内容确定性图灵机模型随机存取机模型第17讲计算模型解放军理工大学指挥自动化学院3易解问题和难解问题欧拉回路和哈密顿回路2-CNF-SAT与3-CNF-SAT最短路径和最长路径123123123()()()xxxxxxxxx122313()()()xxxxxx第17讲计算模型解放军理工大学指挥自动化学院4易解问题和难解问题第17讲计算模型解放军理工大学指挥自动化学院5多项式时间问题难度划分的重要依据易解性快捷性：求解问题的规模可以很大易于改进：即便对某个问题来说，当前最佳算法的运行时间为O(n100)，很有可能在很短的时间内，就能找到一个运行时间要好得多的算法。计算模型的相关性对很多合理的计算模型来说，在一个模型上用多项式时间可解的问题，在另一个模型上也可以在多项式时间内获得解决。多项式时间可解问题类具有很好的封闭性．加法、乘法和组合运算下，多项式是封闭的。第17讲计算模型解放军理工大学指挥自动化学院6可计算函数可计算函数是一个直观的概念，它的内涵无法在数学的范畴内严格定义，人们只能说某函数直觉上是可计算的。如果严谨些，也许可以说用人的某些约定俗成的计算规则可计算；用某种计算模型可计算；用某个计算程序可计算；丘奇-图灵论题研究成果表明，从这三个角度看可计算函数的集合，它们都是同一个集合，即递归函数集。可计算函数集等同于递归函数集。第17讲计算模型解放军理工大学指挥自动化学院7计算模型计算模型为确定计算问题的分类，需要一个通用的计算装置定义计算结构和所用的基本指令或操作目的是使问题计算复杂性分析有一个共同的客观尺度三种计算模型图灵机（TM）随机存取机（RAM）随机存取可存储程序（RASP）特点计算能力相当计算速度不同第17讲计算模型解放军理工大学指挥自动化学院8图灵机模型的建立思路问题的抽象问题(问题实例，问题解)编码：(问题实例，问题解)输入/输出符号符号的有限化：有限字母表上的字符串符号的线性化：所有信息变换为一维有限符号串纸带表示：纸带可能很长，但总是有限的。控制的简化使用状态来描述这些计算阶段状态的改变不仅与当前状态有关，通常还与某个数据项有关。为使检查最少和最简洁，一次检查一个方格。操作的简化机械除了有改变状态、沿纸带左右移动、记忆方格符号和重写方格符号的能力就这些能力而已第17讲计算模型解放军理工大学指挥自动化学院9多带确定性图灵机将数据简化为有限字母表上的序列把控制简化为沿纸带一格格移动的有限状态并采用符号重写作为唯一的原始操作产生了与任何算法学同样有力的机械........................优先状态控制器带1带2带k...第17讲计算模型解放军理工大学指挥自动化学院10图灵机形式化描述k带图灵机可形式化地描述为一个7元组(Q，T，I，δ，b，q0，qf)，其中:(1)Q是有限个状态的集合。(2)T是有限个带符号的集合。(3)I是输入符号的集合，IT。(4)b是唯一的空白符，b∈T-I。(5)q0是初始状态。(6)qf是终止(或接受)状态。(7)δ是移动函数。它是从QTk的某一子集映射到Q(T{L，R，S})k的函数。第17讲计算模型解放军理工大学指挥自动化学院11图灵机运算图灵机的一个计算步可实现下面3个操作的组合改变有限状态控制器中的状态清除当前读写头下的方格中原有带符号并写上新的带符号独立地将任何一个或所有读写头，向左移动一个方格(L)或向右移动一个方格(R)或停在当前单元不动(S))),(,),,(),,(,(),,,,(221121kkkdadadaqaaaq第17讲计算模型解放军理工大学指挥自动化学院12图灵机的解释一个图灵机定义了从输入带到输出带的一个映射这种映射关系的两个重要解释将这种映射关系看成是计算一个函数如果一个DTM程序P总是从输入带的方格中读入n个整数，并且在输出带的第一个方格输出一个数后停机f(x1,x2,…,xn)=y将这种映射关系看成是接受一种语言若L是∑*的一个子集，给定x∈∑*，判定x∈L？P可接受的语言L是P可接受的所有字符串的集合。对于不在P可接受的语言L中的输入串，程序P在输出带输出一个不同于1的符号并停机或程序P永远不停机。第17讲计算模型解放军理工大学指挥自动化学院13例：图灵机识别回文串01110b...bb...q001110b...x01110bq101110b...x01110bq201110b...x01110bq5第17讲计算模型解放军理工大学指挥自动化学院14图灵机识别回文串的状态机q0q1q2q3q4q5(0,b)|(1,b)b|bb|b(0,b)|(1,b)b/x(0,0)|(1,1)(0,b)|(1,b)(0,0)|(0,1)|(1,0)|(1,1)(0,b)|1,b)第17讲计算模型解放军理工大学指挥自动化学院15图灵机的计算步骤瞬像(InstantaneousDescription)图灵机的计算步骤可用瞬像来描述一台k带的图灵机的瞬像是一个k元组(a1,a2,…ak)，其中ai为形如xqy的字符串,q为图灵机的当前状态，所在位置为第i带的读写头的位置。如果经过图灵机M一个运算步骤后由瞬像D1变为瞬像D2，记为D1├D2；(q0010,q0)├(q1010,Xq1)第17讲计算模型解放军理工大学指挥自动化学院16瞬像示例(q0010,q0)├(q1010,Xq1)├(0q110,X0q1)├(01q10,X01q1)├(010q1X010q1)├(010q2X01q20)├(010q2X0q210)├(010q2Xq2010)├(010q2,q2X010)├(01q30,Xq3010)├(01q40,X0q410)├(0q310,X0q310)├(0q410,X01q40)├(q3010,X01q30)├(q4010,X010q4)├(q5010,X010q5)第17讲计算模型解放军理工大学指挥自动化学院17图灵机复杂性时间复杂性T(n)处理所有长度为n的输入实例所需的最大计算步数。如果对某个长度为n的输入，图灵机不停机，T(n)对这个n值无定义空间复杂性S(n)处理所有长度为n的输入实例时，在k条带上所使用过的方格数的总和。如果某个读写头无限地向右移动而不停机，S(n)也无定义。第17讲计算模型解放军理工大学指挥自动化学院18随机存取机的结构和原理程序存储部件r0r1r2r3指令计数器x1x2...xn...y1y2...yn...只读输入带只写输出带...内存储器第17讲计算模型解放军理工大学指挥自动化学院19RAM基本指令集操作码操作数指令含义（1）LOAD=i/i/*i取操作数入累加器（2）STOREi/*i将累加器中的数存入内存（3）ADD=i/i/*i加法运算（4）SUB=i/i/*i减法运算（5）MULT=i/i/*i乘法运算（6）DIV=i/i/*i除法运算（7）READi/*i读入（8）WRITE=i/i/*i输出（9）JUMP标号无条件跳转（10）JGTZ标号正转移到标号语句（11）JZERO标号零转移到标号语句（12）HALT停机取数指令算术指令读写指令控制指令第17讲计算模型解放军理工大学指挥自动化学院20RAM程序解释一个RAM程序定义了从输入带到输出带的一个映射这种映射关系的两个重要解释将这种映射关系看成是计算一个函数如果一个RAM程序P总是从输入带前个方格中读入n个整数，并且在输出带的第一个方格输出一个整数后停机f(x1,x2,…,xn)=y将这种映射关系看成是接受一种语言RAM程序P接受字符串SP可接受的语言L是P可接受的所有字符串的集合。对于不在P可接受的语言L中的输入串，程序P在输出带输出一个不同于1的符号并停机或程序P永远不停机。第17讲计算模型解放军理工大学指挥自动化学院21RAM程序的例子(1)000)(nnnnfnf(n)r1←nif(r1=0)thenreturn0;r2←1;r3←n;while(r3!=0)dor2←r2*r1;r3←r3-1;endwhilereturnr2;end计算第17讲计算模型解放军理工大学指挥自动化学院22RAM程序(1)READ1//r1←nLOAD1//r0←r1JGTZpos//n0WRITE=0JUMPendpos:LOAD=1STORE2//r2←1LOAD1STORE3//r3←nwhile:LOAD2MULT1//r2←r2*r1LOAD3SUB=1STORE3//r3←r3-1JGTZwhileWRITE2end:HALT第17讲计算模型解放军理工大学指挥自动化学院23RAM程序的例子(2)考虑一个RAM程序，它接受字母表{1,2}上的一个语言，该语言包含所有由同样多个1与2组成的字符串。Accept()r1←read()r2←0while(r1!=0)doif(r1=1)thenr2←r2-1elser2←r2+1r1←read()endwhileif(r2=0)thenreturn1elsereturn0end第17讲计算模型解放军理工大学指挥自动化学院24RAM耗费标准两种RAM耗费标准均匀耗费标准对数耗费标准。均匀耗费标准每条RAM指令需要一个单位时间每个寄存器占用一个单位空间。第17讲计算模型解放军理工大学指挥自动化学院25对数耗费标准执行一条指令的耗费与二进制表示指令的操作数长度成比例0101||log)(iiiil操作数对数耗费=il(i)il(i)+l(c(i))*il(i)+l(c(i))+l(c(c(i)))第17讲计算模型解放军理工大学指挥自动化学院26RAM程序分析对一个给定的RAM程序，用不同的耗费标准，时间复杂性完全不同。基本准则如果一个问题需要存放的每个数不超过一个计算机字长，那么用均匀耗费标准是合理的；否则用对数耗费标准更符合实际情况。第17讲计算模型解放军理工大学指挥自动化学院27RAM程序(1)均匀耗费每个MULT指令耗费一个单位时间，总的时间复杂性为O(n)；空间复杂性为O(1)。对数耗费MULT指令耗费为l(ni)+l(n)=(i+1)logn,总的时间复杂性为O(n2logn)空间复杂性为l(nn)=O(nlogn)f(n)r1←nif(r1=0)thenreturn0;r2←1;r3←n;while(r3!=0)dor2←r2*r1;r3←r3-1;endwhilereturnr2;end第17讲计算模型解放军理工大学指挥自动化学院28多项式相关定义函数f1(n)和f2(n)是多项式相关的，如果存在多项式p1(x)和p2(x)，使得对于任意的n值均有f1(n)≤p1(f2(n))和f2(n)≤p2(f1(n))。例f1(n)=2n2，f2(n)=n5，p1(x)=2x，p2(x)=x3f1(n)=2n，f2(n)=n5第17讲计算模型解放军理工大学指挥自动化学院29TM模型与RAM模型的关系在对数耗费标准下，TM模型与RAM模型是多项式相关的定理1对于问题P的任何长度为n的输入，设求解问题P的算法A在k带图灵机模型TM下的时间复杂性为T(n)，那么算法A在RAM模型下的时间复杂性为O(T2(n))。第17讲计算模型解放军理工大学指挥自动化学院30TM模型与RAM模型的关系定理2对于问题P的任何长度为n的输入，设求解问题P的算法A在RAM模型下，不含有乘法和除法指令，且按对数耗费标准的时间复杂性为T(n)，那么算法A在k带图灵机模型TM下的时间复杂性为O(T2(n))。两种模型的应用图灵机对于研究算