第八章 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 是等价的