第八章NP完全性理论.ppt

《第八章NP完全性理论.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第八章NP完全性理论2021/9/151计算机算法设计与分析随机存取机RAM的构造累加器指令计数器程序存储部件内存储器r0r1r2…只读输入带……只写输出带2021/9/152计算机算法设计与分析随机存取机RAM的指令集操作码操作数指令含义⑴LOAD=i/i/*i取操作数入累加器⑵STOREi/*i将累加器中数存入内存⑶ADD=i/i/*i加法运算⑷SUB=i/i/*i减法运算⑸MULT=i/i/*i乘法运算⑹DIV=i/i/*i除法运算⑺READi/*i读入⑻WRITE=i/i/*i输出⑼JUMP标号无条件转移到标号语句⑽J

2、GTZ标号正转移到标号语句⑾JZERO标号零转移到标号语句⑿HALT停机2021/9/153计算机算法设计与分析RAM机的复杂性标准均匀耗费标准对数耗费标准每条RAM指令需要一个单位时间，每个寄存器占用一个单位空间。RAM指令的执行时间与操作数的长度的对数成比例，一个寄存器可放一个任意大小的整数。若每个操作数不超过一个机器字，则用均匀耗费标准是合理的，否则适用对数耗费标准。2021/9/154计算机算法设计与分析随机存取存储程序机RASPRASP与RAM的区别在于(1)RASP的程序存储在内存并且可以修改自身；(2)RASP不

3、允许间接寻址，它通过修改指令模拟间接寻址。RASP的指令集见P-238的表8-6。RASP更加接近冯·诺伊曼体系结构。无论是采用均匀耗费标准还是对数耗费标准，在相差一个常数因子的意义下，RAM与RASP是等价的。2021/9/155计算机算法设计与分析RAM的变形与简化(1)实随机存取机RRAM；(2)直线式程序；(3)位式计算；(4)位向量计算；(5)判定数；(6)代数计算树ACT；(7)代数判定树。2021/9/156计算机算法设计与分析图林机的构造图林机(TuringMachine)是英国数学家Turing在1936年提

4、出的计算模型，被认为是当今计算机的理论模型。下面是图林机(TM)原型的构造：……输入带有限控制器磁头输入带被视为右无穷，并被划分为一个个单元用于存放符号(带符号)。有限控制器由有限个状态构成。磁头可左右移动，读写带符号。2021/9/157计算机算法设计与分析TM的数学描述Q是有限状态的集合；T是有限个带符号的集合；IT，是输入符号的集合；δ：Q×T→Q×T×{L,R}为转移函数；b是唯一的空白符，b∈T–I；q0和qf分别为初始状态和终止状态。M=(Q,T,I,δ,b,q0,qf)其中：2021/9/158计算机算法设计与

5、分析图林机的变形多道图林机(输入带上有多个道)。双向图林机(输入带被视为左右均是无穷的)。多带图林机(具有多条输入带)。多头图林机(具有多个磁头)。多维图林机(输入带是多维的)。不确定的图林机(有限控制器是不确定的)。不确定的图林机类似于不确定的自动机，即δ：Q×T→ρ(Q×T×{L,R})将图林机是原型称为确定的，记为DTM；而将不确定的图林机记为NDTM，已经证明各类变形图林机在可计算的能力上等价于原型图林机。但是在复杂性是有区别的。2021/9/159计算机算法设计与分析通用图林机不失一般性，任何图林机的T={0,1}；

6、δ：Q×T→Q×T×{L,R}的每个动作由五个部分构成(五字诀)，δ含有有限个五字诀。于是，任一图林机都可写成一个二进制编码。所以任一图林机可用一个三带图林机来模拟。这个三带图林机就被称为通用图林机。输入带编码带工作带有限控制器code1#code2#…#codenqi通用图林机将某个图林机Mi的编码存储在编码带上；工作带上初始时为初始状态q0；然后依据状态及现行扫描的符号选择并执行编码。2021/9/1510计算机算法设计与分析用RAM模拟TM定理8-3：设算法A，对于任何长度为n的输入，在图林机TM下的时间复杂性为T(n)

7、，则A在RAM下的时间复杂性为O(T2(n))。证明：每个寄存器放输入带一个单元的内容，这样RAM就可以模拟TM的工作。均匀耗费标准下，模拟TM一个动作，RAM需常数时间。A在RAM下时间复杂性为O(T(n))。对数耗费标准下，RAM模拟TM的时间复杂性为O(T(n)logT(n))=O(T2(n))。。2021/9/1511计算机算法设计与分析用TM模拟RAM定理8-4：设算法A，对于任何长度为n的输入，按对数耗费标准在RAM下的时间复杂性为T(n)，则A在TM下的时间复杂性为O(T2(n))。证明：用一个五带TM模拟RAM

8、的工作，其中：带1用<地址,内容>的形式存放寄存器；带2存放累加器内容；带3作为暂存工作带；带4和带5作为输入带和输出带；用TM的状态对应RAM的一步程序。TM模拟RAM除乘/除法外的指令的时间为常数，查找寄存器的时间为n，整个时间为O(T2(n))。对RAM的乘除法，TM用