16-计算模型解读.ppt

解放军理工大学指挥自动化学院 第17讲 计算模型 杨 明 指挥信息系统学院软件工程教研中心 yangming@lgdx.mtn 内容 确定性图灵机模型 随机存取机模型 易解问题和难解问题 欧拉回路和哈密顿回路 2-CNF-SAT与3-CNF-SAT 最短路径和最长路径 易解问题和难解问题 多项式时间 问题难度划分的重要依据 易解性 快捷性：求解问题的规模可以很大 易于改进：即便对某个问题来说，当前最佳算法的运行时间为O(n100)，很有可能在很短的时间内，就能找到一个运行时间要好得多的算法。 计算模型的相关性 对很多合理的计算模型来说，在一个模型上用多项式时间可解的问题，在另一个模型上也可以在多项式时间内获得解决。 多项式时间可解问题类具有很好的封闭性． 加法、乘法和组合运算下，多项式是封闭的。 可计算函数 可计算函数 是一个直观的概念，它的内涵无法在数学的范畴内严格定义，人们只能说某函数直觉上是可计算的。 如果严谨些，也许可以说 用人的某些约定俗成的计算规则可计算； 用某种计算模型可计算； 用某个计算程序可计算； 丘奇-图灵论题 研究成果表明，从这三个角度看可计算函数的集合，它们都是同一个集合，即递归函数集。 可计算函数集等同于递归函数集。 计算模型 计算模型 为确定计算问题的分类，需要一个通用的计算装置 定义计算结构和所用的基本指令或操作 目的是使问题计算复杂性分析有一个共同的客观尺度 三种计算模型 图灵机（TM） 随机存取机（RAM） 随机存取可存储程序（RASP） 特点 计算能力相当 计算速度不同 图灵机模型的建立思路 问题的抽象 问题?(问题实例，问题解) 编码：(问题实例，问题解)?输入/输出符号 符号的有限化：有限字母表上的字符串 符号的线性化：所有信息变换为一维有限符号串 纸带表示：纸带可能很长，但总是有限的。 控制的简化 使用状态来描述这些计算阶段 状态的改变不仅与当前状态有关，通常还与某个数据项有关。 为使检查最少和最简洁，一次检查一个方格。 操作的简化 机械除了有改变状态、沿纸带左右移动、记忆方格符号和重写方格符号的能力 就这些能力而已 多带确定性图灵机 将数据简化为有限字母表上的序列 把控制简化为沿纸带一格格移动的有限状态 并采用符号重写作为唯一的原始操作 产生了与任何算法学同样有力的机械 图灵机形式化描述 图灵机运算 图灵机的一个计算步可实现下面3个操作的组合 改变有限状态控制器中的状态 清除当前读写头下的方格中原有带符号并写上新的带符号 独立地将任何一个或所有读写头，向左移动一个方格(L)或向右移动一个方格(R)或停在当前单元不动(S) 图灵机的解释 一个图灵机定义了从输入带到输出带的一个映射 这种映射关系的两个重要解释 将这种映射关系看成是计算一个函数 如果一个DTM程序P总是从输入带的方格中读入n个整数，并且在输出带的第一个方格输出一个数后停机 f(x1,x2,…,xn)=y 将这种映射关系看成是接受一种语言 若L 是∑*的一个子集，给定x∈∑* ，判定x∈ L？ P可接受的语言L是P可接受的所有字符串的集合。 对于不在P可接受的语言L中的输入串，程序P在输出带输出一个不同于1的符号并停机或程序P永远不停机。 例：图灵机识别回文串 图灵机识别回文串的状态机 图灵机的计算步骤 瞬像(Instantaneous Description) 图灵机的计算步骤可用瞬像来描述 一台k带的图灵机的瞬像是一个k元组 (a1,a2,…ak) ，其中ai为形如xqy的字符串,q为图灵机的当前状态，所在位置为第i带的读写头的位置。 如果经过图灵机M一个运算步骤后由瞬像D1变为瞬像D2，记为D1├ D2 ； (q0010, q0)├ (q1010, Xq1) 瞬像示例 图灵机复杂性 时间复杂性T(n) 处理所有长度为n的输入实例所需的最大计算步数。 如果对某个长度为n的输入，图灵机不停机，T(n)对这个n值无定义 空间复杂性S(n) 处理所有长度为n的输入实例时，在k条带上所使用过的方格数的总和。 如果某个读写头无限地向右移动而不停机，S(n)也无定义。 随机存取机的结构和原理 RAM基本指令集 RAM程序解释 一个RAM程序定义了从输入带到输出带的一个映射 这种映射关系的两个重要解释 将这种映射关系看成是计算一个函数 如果一个RAM程序P总是从输入带前个方格中读入n个整数，并且在输出带的第一个方格输出一个整数后停机 f(x1,x2,…,xn)=y 将这种映射关系看成是接受一种语言 RAM程序P接受字符串S P可接受的语言L是P可接受的所有字符串的集合。 对于不在P可接受的语言L中的输入串，程序P在输出带输出一个不同于1的符号并停机或程序P永远不停机。