算法设计和分析08np完全性理论.ppt

第十章 NP完全性理论 10.1 计算模型 10.1.1 随机存取机RAM 10.1.2 随机存取存储程序机RASP 10.1.3 RAM模型的变形与简化 10.1.4 图灵机 10.1.5 图灵机模型与RAM模型的关系 10.1.6 问题变换与计算复杂性归约 10.1.1 随机存取机RAM 1. RAM的结构 10.1.1 随机存取机RAM 2. RAM程序 一个RAM程序定义了从输入带到输出