湘潭大学：《计算机算法设计与分析》课程教学资源（PPT课件讲稿）第八章 NP完全性理论

第八章 NP宠全性理论 2021/2/21 计算机算法设计与分析

2021/2/21 计算机算法设计与分析 1 第八章 NP完全性理论

随机存取机RAM的构造 ●●● 只读输入带 指令 累加器 计数器「程序存储部件r1 内存储器 ●● 只写输出带 2021/221 计算机算法设计与分析 2

2021/2/21 计算机算法设计与分析 2 随机存取机RAM的构造 累加器 指令 计数器 程序存储部件 内存储器 r0 r1 r2 … … 只读输入带 … 只写输出带

随机存取机RAM的指令集 操作码 操作数 指令含义 (LOAD =1/i/*i 取操作数入累加器 (OSTORE /*i 将累加器中数存入内存 (3ADD i/i/* 加法运算 ()SUB =1/i/*i 减法运算 (MULT 1/i/*i 乘法运算 (6DIV =1/i/*i 除法运算 OREAD 读入 (8WRITE =1/i/*i 输出 (9)JUMP 标号 无条件转移到标号语句 (OJGTZ 标号 正转移到标号语句 (DJZERO 标号 零转移到标号语句 (DHALT 停机 2021/2/21 计算机算法设计与分析 3

2021/2/21 计算机算法设计与分析 3 随机存取机RAM的指令集 操作码 操作数 指令含义 ⑴LOAD =i / i / *i 取操作数入累加器 ⑵STORE i / *i 将累加器中数存入内存 ⑶ADD =i / i / *i 加法运算 ⑷SUB =i / i / *i 减法运算 ⑸MULT =i / i / *i 乘法运算 ⑹DIV =i / i / *i 除法运算 ⑺READ i / *i 读入 ⑻WRITE =i / i / *i 输出 ⑼JUMP 标号 无条件转移到标号语句 ⑽JGTZ 标号 正转移到标号语句 ⑾JZERO 标号 零转移到标号语句 ⑿HALT 停机

RAM机的复杂性标准 ■均匀耗费标准 每条RAM指令需要一个单位时间,每个寄存器 占用一个单位空间。 ■对数耗费标准 RAM指令的执行时间与操作数的长度的对数成 比例,一个寄存器可放一个任意大小的整数。 ■若每个操作数不超过一个机器字,则用均匀耗 费标准是合理的,否则适用对数耗费标准 2021/221 计算机算法设计与分析

2021/2/21 计算机算法设计与分析 4 RAM机的复杂性标准 ◼ 均匀耗费标准 ◼ 对数耗费标准 每条RAM指令需要一个单位时间，每个寄存器 占用一个单位空间。 RAM指令的执行时间与操作数的长度的对数成 比例，一个寄存器可放一个任意大小的整数。 ◼ 若每个操作数不超过一个机器字，则用均匀耗 费标准是合理的，否则适用对数耗费标准

随机存取存储程序机RASP RASP与RAM的区别在于(1)RASP的程序存储 在内存并且可以修改自身;(2RASP不允许间 接寻址,它通过修改指令模拟间接寻址 RASP的指令集见P238的表8-6。 ■RASP更加接近冯诺伊曼体系结构 无论是采用均匀耗费标准还是对数耗费标准, 在相差一个常数因子的意义下,RAM与RASP 是等价的。 2021/221 计算机算法设计与分析 5

2021/2/21 计算机算法设计与分析 5 随机存取存储程序机RASP ◼ RASP与RAM的区别在于(1)RASP的程序存储 在内存并且可以修改自身；(2)RASP不允许间 接寻址，它通过修改指令模拟间接寻址。 ◼ RASP的指令集见P-238的表8-6。 ◼ RASP更加接近冯·诺伊曼体系结构。 ◼ 无论是采用均匀耗费标准还是对数耗费标准， 在相差一个常数因子的意义下，RAM与RASP 是等价的

RAM的变形与简化 (1)实随机存取机RRAM; (2)直线式程序; (3)位式计算; (4)位向量计算; (5)判定数; (6代数计算树ACT; (7)代数判定树 2021/221 计算机算法设计与分析 6

2021/2/21 计算机算法设计与分析 6 RAM的变形与简化 ◼ (1)实随机存取机RRAM； ◼ (2)直线式程序； ◼ (3)位式计算； ◼ (4)位向量计算； ◼ (5)判定数； ◼ (6)代数计算树ACT； ◼ (7)代数判定树

图林机的构造 图林机( Turing Machine是英国数学家 Turing在 1936年提出的计算模型,被认为是当今计算机 的理论模型。下面是图林机(TM)原型的构造: 输入带 磁头 输入带被视为右无穷,并被划分为一个个 有限单元用于存放符号(带符号 控制器有限控制器由有限个状态构成。 磁头可左右移动,读写带符号 2021/22 计算机算法设计与分析

2021/2/21 计算机算法设计与分析 7 图林机的构造 ◼ 图林机(Turing Machine)是英国数学家Turing在 1936年提出的计算模型，被认为是当今计算机 的理论模型。下面是图林机(TM)原型的构造： …… 输入带 有限 控制器 磁头 输入带被视为右无穷，并被划分为一个个 单元用于存放符号(带符号)。 有限控制器由有限个状态构成。 磁头可左右移动，读写带符号

TM的数学描述 M=(Q,T,L,δ,b,q,qr) 其中: Q是有限状态的集合; ■T是有限个带符号的集合; ■IcT,是输入符号的集合; 6:Q×T→Q×T×{L,R}为转移函数; ■b是唯一的空白符,b∈T-1; q0和q分别为初始状态和终止状态。 2021/221 计算机算法设计与分析

2021/2/21 计算机算法设计与分析 8 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/221 计算机算法设计与分析 9

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

通用图林机 输入带 有限 控制器 code1#code2#,# code编码带 gi 工作带 通用图林机将某个图林机M的编码存储在编码 带上;工作带上初始时为初始状态q0;然后依 据状态及现行扫描的符号选择并执行编码。 2021/221 计算机算法设计与分析 10

2021/2/21 计算机算法设计与分析 10 通用图林机 ◼ 不失一般性，任何图林机的T = {0, 1}； ◼ δ：Q×T→Q×T×{L, R}的每个动作由五个部 分构成(五字诀)，δ含有有限个五字诀。 ◼ 于是，任一图林机都可写成一个二进制编码。 ◼ 所以任一图林机可用一个三带图林机来模拟。 ◼ 这个三带图林机就被称为通用图林机。 输入带 编码带 工作带 有限 控制器 code1#code2#…#coden qi 通用图林机将某个图林机Mi的编码存储在编码 带上；工作带上初始时为初始状态q0；然后依 据状态及现行扫描的符号选择并执行编码