- 1、本文档共30页,可阅读全部内容。
- 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
- 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载。
- 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
查看更多
算法设计与分析Ch
第8章 NP完全性理论 8.1 计算模型 8.1.1 随机存取机RAM 8.1.2 随机存取存储程序机RASP 8.1.3 图灵机 8.1.4 图灵机模型与RAM模型的关系 8.1.5 问题变换与计算复杂性归约 8.1.1 随机存取机RAM 1. RAM的结构 8.1.1 随机存取机RAM 2. RAM程序 8.1.1 随机存取机RAM 3. RAM程序的耗费标准 8.1.2 随机存取存储程序机RASP 1. RASP的结构 RASP的整体结构类似于RAM,所不同的是RASP的程序是存储在寄存器中的。每条RASP指令占据2个连续的寄存器。第一个寄存器存放操作码的编码,第二个寄存器存放地址。RASP指令用整数进行编码。 2. RASP程序的复杂性 不管是在均匀耗费标准下,还是在对数耗费标准下,RAM程序和RASP程序的复杂性只差一个常数因子。在一个计算模型下T(n)时间内完成的输入-输出映射可在另一个计算模型下模拟,并在kT(n)时间内完成。其中k是一个常数因子。空间复杂性的情况也是类似的。 8.3 图灵机 1. 多带图灵机 8.1.3 图灵机 8.1.3 图灵机 8.1.4 图灵机模型与RAM模型的关系 8.1.5 问题变换与计算复杂性归约 8.1.5 问题变换与计算复杂性归约 8.2 P类与NP类问题 8.2.1 非确定性图灵机 8.2.2 P类与NP类语言 8.2.3 多项式时间验证 8.2.1 非确定性图灵机 8.2.2 P类与NP类语言 8.2.2 P类与NP类语言 8.2.2 P类与NP类语言 8.2.3 多项式时间验证 8.3 NP完全问题 8.3.1 多项式时间变换 8.3.2 Cook定理 8.3.1 多项式时间变换 8.3.1 多项式时间变换 8.3.2 Cook定理 8.4 一些典型的NP完全问题 8.4.1 合取范式的可满足性问题(CNF-SAT) 8.4.2 3元合取范式的可满足性问题(3-SAT) 8.4.3 团问题CLIQUE 8.4.4 顶点覆盖问题 (VERTEX-COVER) 8.4.5 子集和问题 (SUBSET-SUM) 8.4.6 哈密顿回路问题 (HAM-CYCLE) 8.4.7 旅行售货员问题TSP * 一个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计算模型下, 假定一个寄存器可存放一个任意大小的整数。 1. 多带图灵机 根据有限状态控制器的当前状态及每个读写头读到的带符号,图灵机的一个计算步可实现下面3个操作之一或全部。 (1)改变有限状态控制器中的状态。 (2)清除当前读写头下的方格中原有带符号并写上新的带符号。 (3)独立地将任何一个或所有读写头,向左移动一个方格(L)或向右移动一个方格(R)或停在当前单元不动(S)。 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的函数。 1. 多带图灵机 图灵机M的时间复杂性T(n)是它处理所有长度为n的输入所需的最大计算步数。如果对某个长度为n的输入,图灵机不停机,T(n)对这个n值无定义。 图灵机的空间复杂性S(n)是它处理所有长度为n的输入时,在k条带上所使用过的方格数的总
文档评论(0)