文档介绍：第八章 NP完全性理论
2017/11/10
1
计算机算法设计与分析
随机存取机RAM的构造
累加器
指令
计数器
程序存储部件
内存储器
r0
r1
r2
…
只读输入带
…
…
只写输出带
2017/11/10
2
计算机算法设计与分析
随机存取机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
停机
2017/11/10
3
计算机算法设计与分析
RAM机的复杂性标准
均匀耗费标准
对数耗费标准
每条RAM指令需要一个单位时间,每个寄存器占用一个单位空间。
RAM指令的执行时间与操作数的长度的对数成比例,一个寄存器可放一个任意大小的整数。
若每个操作数不超过一个机器字,则用均匀耗费标准是合理的,否则适用对数耗费标准。
2017/11/10
4
计算机算法设计与分析
随机存取存储程序机RASP
RASP与RAM的区别在于(1)RASP的程序存储在内存并且可以修改自身;(2)RASP不允许间接寻址,它通过修改指令模拟间接寻址。
RASP的指令集见P-238的表8-6。
RASP更加接近冯·诺伊曼体系结构。
无论是采用均匀耗费标准还是对数耗费标准,在相差一个常数因子的意义下,RAM与RASP是等价的。
2017/11/10
5
计算机算法设计与分析
RAM的变形与简化
(1)实随机存取机RRAM;
(2)直线式程序;
(3)位式计算;
(4)位向量计算;
(5)判定数;
(6)代数计算树ACT;
(7)代数判定树。
2017/11/10
6
计算机算法设计与分析
图林机的构造
图林机(Turing Machine)是英国数学家Turing在1936年提出的计算模型,被认为是当今计算机的理论模型。下面是图林机(TM)原型的构造:
……
输入带
有限
控制器
磁头
输入带被视为右无穷,并被划分为一个个单元用于存放符号(带符号)。
有限控制器由有限个状态构成。
磁头可左右移动,读写带符号。
2017/11/10
7
计算机算法设计与分析
TM的数学描述
Q是有限状态的集合;
T是有限个带符号的集合;
I T,是输入符号的集合;
δ:Q×T→Q×T×{L, R}为转移函数;
b是唯一的空白符,b∈T – I;
q0和qf分别为初始状态和终止状态。
M = (Q, T, I, δ, b, q0, qf )
其中:
2017/11/10
8
计算机算法设计与分析
图林机的变形
多道图林机(输入带上有多个道)。
双向图林机(输入带被视为左右均是无穷的)。
多带图林机(具有多条输入带)。
多头图林机(具有多个磁头)。
多维图林机(输入带是多维的)。
不确定的图林机(有限控制器是不确定的)。
不确定的图林机类似于不确定的自动机,即
δ:Q×T→ρ(Q×T×{L, R})
将图林机是原型称为确定的,记为DTM;而将不确定的图林机记为NDTM,
已经证明各类变形图林机在可计算的能力上等价于原型图林机。但是在复杂性是有区别的。
2017/11/10
9
计算机算法设计与分析
通用图林机
不失一般性,任何图林机的T = {0, 1};
δ:Q×T→Q×T×{L, R}的每个动作由五个部分构成(五字诀),δ含有有限个五字诀。
于是,任一图林机都可写成一个二进制编码。
所以任一图林机可用一个三带图林机来模拟。
这个三带图林机就被称为通用图林机。
输入带
编码带
工作带
有限
控制器
code1#code2#…#coden
qi
通用图林机将某个图林机Mi的编码存储在编码带上;工作带上初始时为初始状态q0;然后依据状态及现行扫描的符号选择并执行编码。
2017/11/10
10
计算机算法设计与分析