第9章 NP完全性理论与近似算法.ppt

第9章NP完全性理论与近似算法1学****要点理解RAM,RASP和图灵机计算模型理解非确定性图灵机的概念理解P类与NP类语言的概念理解NP完全问题的概念2引言问题的计算复杂性可以通过解决问题所需计算量的多少来度量。易:可在多项式时间(O(nk))内解决的问题难:需要指数函数(O(kn)) 计算模型在进行问题的计算复杂性分析之前,首先必须建立求解问题所用的计算模型,包括定义该计算模型中所用的基本运算。建立计算模型的目的是为了使问题的计算复杂性分析有一个共同的客观尺度。3个基本计算模型:随机存取机RAM(essMachine);随机存取存储程序机RASP(essStoredProgramMachine)图灵机(TuringMachine)。、、RAM程序一个RAM程序定义了从输入带到输出带的一个映射。可以对这种映射关系作2种不同的解释。解释一:把RAM程序看成是计算一个函数 若一个RAM程序P总是从输入带前n个方格中读入n个整数x1,x2,…,xn,并且在输出带的第一个方格上输出一个整数y后停机,那么就说程序P计算了函数f(x1,x2,…,xn)=y解释二:把RAM程序当作一个语言接受器。 将字符串S=a1a2…an放在输入带上。在输入带的第一个方格中放入符号a1,第二个方格中放入符号a2,…,第n个方格中放入符号an。然后在第n+1个方格中放入0,作为输入串的结束标志符。如果一个RAM程序P读了字符串S及结束标志符0后,在输出带的第一格输出一个1并停机,就说程序P接受字符串S。、RAM程序的耗费标准标准一:均匀耗费标准 在均匀耗费标准下,每条RAM指令需要一个单位时间;每个寄存器占用一个单位空间。以后除特别注明,RAM程序的复杂性将按照均匀耗费标准衡量。标准二:对数耗费标准 对数耗费标准是基于这样的假定,即执行一条指令的耗费与以二进制表示的指令的操作数长度成比例。在RAM计算模型下,假定一个寄存器可存放一个任意大小的整数。因此若设l(i)是整数i所占的二进制位数,、RASP的结构RASP的整体结构类似于RAM,所不同的是RASP的程序是存储在寄存器中的。每条RASP指令占据2个连续的寄存器。第一个寄存器存放操作码的编码,第二个寄存器存放地址。RASP指令用整数进行编码。2、RASP程序的复杂性不管是在均匀耗费标准下,还是在对数耗费标准下,RAM程序和RASP程序的复杂性只差一个常数因子。在一个计算模型下T(n)时间内完成的输入-输出映射可在另一个计算模型下模拟,并在kT(n)时间内完成。其中k是一个常数因子。空间复杂性的情况也是类似的。、深刻的概念用他的图灵机模型讲清楚了。正是因为图灵奠定的理论基础,人们才有可能发明20世纪以来甚至是人类有史以来最伟大的发明:计算机。因此人们称图灵为:计算机理论之父。图灵在二战期间他曾经为英国政府效力成功破译了德国的密码,因而为英国做出了突出贡献。为了纪念这个伟大的学者,计算机界设立了最高荣誉奖:ACM图灵奖。