大基63：计算理论.pdf

大学计算机 第6章：计算理 论与计算模型 6.3 计算理论 计算理论（theory of computation）用来研究计算的过程与功效 的数学理论，起源于对数学基础问题的研究 计算理论主要包括算法、算法学、计算复杂性理论、可计算性理论、 自动机理论和形式语言理论等 自动机、可计算性、复杂度刚好是计算的三个不同的方面：计算的 模型、计算的界限、计算的代价 计算理论是计算机科学的理论基础计算机科学最自然最根本的问 题：什么是计算，什么可以被计算，什么样的问题是难的、什么样 的问题是容易的这些是计算理论的主题 6.3 计算理论 问题求解是计算科学的根本目的之一，计算科学也是在问题求解的 实践中逐渐发展壮大的 数学模型是连接数学与实际问题的桥梁 在建立数学模型过程中，首先要对问题进行观察，研究其运动 变化的情况，引出数学方法，再回到问题的解决中去 判断问题的数学模型是否可解，如果不可解，则要寻找问题特 征、分类以及不可解的证明 如果可解，则进一步求得计算模型及其复杂度 最后才是算法设计和编程调试 6.3 计算理论 问题求解的计算过程 1935193519361936 19361936 19431943 19511951 邱奇提出邱奇提出 转换演算转换演算 哥德尔等定哥德尔等定 义递归函数义递归函数 图灵和波斯特各图灵和波斯特各 自提出抽象计算自提出抽象计算 机模型机模型 MapkobMapkob定义定义 正规算法正规算法 陆续陆续证明证明，上述这些不同计算模型，上述这些不同计算模型( (算法精确化定义模式算法精确化定义模式) )的计算的计算 能力都是一样的，即能力都是一样的，即它们是等价的它们是等价的。

6.3.1计算模型及计算能力 从20世纪30年代开始，为了讨论所有问题是否都有求解的算法， 数学家和逻辑学家从不同角度提出了几种不同的算法概念精确 化定义 6.3.2 可计算性理论 1. 可计算性的定义和特征 图灵通过精确地描述给出了可计算性的形式定义：通常能够称作算 法的过程，恰好可以在图灵机上执行的过程 图灵之所以能取得成功，很重要的一条是他采用了算法思维来研究 计算的过程，由此揭示可计算性概念 可计算性的特征包括： 确定性：由相同的初始条件，得到相同的结果 有限性：能在有限时间内，在有限设备上执行 机械性：每一个计算过程的执行都是“机械的”或“构造的”， 且可以被精确地描述 可执行性：计算过程的语句甚至是有限的，且自身能被表示为 自然数 终止性：接收初始输入后能否达到停机状态 6.3.2 可计算性理论 2. 可计算性理论的主要内容 可计算性理论的基本论题，也称图灵论题 图灵论题说：图灵机可计算函数类与直观可计算函数类相同 丘奇论题说：可定义函数类与直观可计算函数类相同 图灵证明了图灵机可计算函数类与可定义函数类相同 这表明图灵论题和丘奇论题讲的是一回事，因此把它们统称为丘奇 图灵论题。

6.3.2 可计算性理论 2. 可计算性理论的主要内容 后来人们提出了许多不同的计算模型来精确刻划可计算性，并且证 明了这些模型都与图灵机等价 这表明图灵机和其他等价的模型确实合理地定义了可计算性，因此 丘奇图灵论题得到了计算机科学界和数学界的公认 “凡是可计算的都是图灵机可计算的”，这就是丘奇-图灵论题 6.3.2 可计算性理论 3.判定性问题 判定问题是无穷多个同类个别问题的总称 例如，2是不是素数？6是不是素数？这些都是个别问题 把这类个别问题概括起来，就得到一个判定问题：任意给定的 正整数是不是素数？ 这里的正整数集合称为该判定问题的域，给定域中的一个元素， 判定问题就对应一个个别问题 6.3.2 可计算性理论 4.停机问题 停机问题是：给定任意一个计算机程序和一个特定的输入，判断该 程序是进入死循环，还是可以停机 通俗的说，停机问题就是判断任意一个程序是否会在有限的时间之 内结束运行的问题 6.3.2 可计算性理论 4.停机问题 如果这个问题可以在有限的时间之内解决，那么就可以有一个程序 判断其本身是否会停机但是，在程序停止之前，没有办法判断它 会不会停止这是一个悖论，所以停机问题是一个不可解的问题。

6.3.2 可计算性理论 4. 停机问题 停机问题是目前逻辑数学的焦点和第三次数学危机的解决方案， 它是重要的不可判定问题 19361936年，年，TuringTuring发表“论可计算数及发表“论可计算数及 其在判定问题中的应用”论文中提出一般其在判定问题中的应用”论文中提出一般 性停机问题的不可判定性，并用形式化方性停机问题的不可判定性，并用形式化方 法证明其为一个不可计算问题法证明其为一个不可计算问题 6.3.2 可计算性理论 停机问题的关键：能否找到一个测试程序，这个测试程序能判 定任何一个程序在给定的输入下能否终止 数学反证法证明：先假设存在这样的测试程序，然后再构造一 个程序，该测试程序不能测试 假设存在一个测试程序T，它能接受任何输入 当输入程序P能终止，输出1； P不能终止，输出0 6.3.2 可计算性理论 P P能终止能终止,X,X1 1 P P不终止不终止,X,X0 0 测试程序测试程序T T 程序程序P P X X 测试程序测试程序T T X(1X(1或或0)0) while(x)while(x) S S 程序程序P P 测试程序测试程序T T X(1X(1或或0)0) while(x)while(x) S S 程序程序S S P P终止终止,X,X1,S1,S不终止不终止 P P不终止不终止,X,X0,S0,S终止终止 S S终止终止,X,X1,S1,S不终止不终止 S S不终止不终止,X,X0,S0,S终止终止 结论结论：若：若S S终止，则终止，则S S不终止；若不终止；若S S不终止，则不终止，则S S终止，结论矛盾终止，结论矛盾 故可以确定这样的测试程序不存在，从而证明停机问题不可解故可以确定这样的测试程序不存在，从而证明停机问题不可解 6.3.2 可计算性理论 4.停机问题 将停机问题与悖论放在一起对比，说明它们本质是一样的。

停机问题是一个重要的不可判定问题，由它可以推出计算科学中的 许多不可判定问题 图灵在判定问题上的一大成就是把图灵机的“停机问题”作为研究 许多判定问题的基础，把一个判定问题归结为停机问题：“如果问 题A可判定，则停机问题可判定从而由“停机问题是不可判定 的”推出“问题A是不可判定的” 6.3.3 计算复杂性理论 计算复杂性： 用计算机求解问题的难易程度 度量标准 ： 1、计算所需的步数或指令条数即时间复杂度 2、计算所需的存储单元数量即空间复杂度 一个计算复杂性的高低体现在运行该算法时所需要的资源，所需资 源越多，算法复杂性越高；所需资源越低，则算法复杂性越低 6.3.3 计算复杂性理论 我们当然不可能也不必要就一个个具体问题去研究它的计算复杂性， 而是研究在不同计算模型下，使用不同类型资源和不同数量的资源 时，各类问题复杂性的本质特征和相互关系，按复杂性把问题分成 不同的类，即ComplexityClass 6.3.3 计算复杂性理论 1.计算复杂性的发展 计算复杂性大的进展始于50年代末、60年代初 当时在美国有两个并行的中心 一个是通用电气公司设立于纽约州Schenectady的研究实验室， 核心人物是J。

Hartmanis和RStearns他们两人是1993年 度 图灵奖获得者 另一个中心是麻省理工学院MIT，在那里，加州大学伯克利分 校著名的计算机科学家Manuel Blum与前述两人互相独立地进 行着相关问题的研究 三人被学术界公认为计算复杂性理论的主要奠基人 6.3.3 计算复杂性理论 2.时间复杂度 要计算或解决一个问题，该问题通常有一个大小规模，用n表示 例如，从n个数里面找出最大的那个数，这个n就是该问题的规模大小 怎么找？我们要比较n-1次才能得到结果，这个n-1就是所花的时间， 也就是时间复杂度 再比如，将n个数按从大至小排序，n是其规模大小，若是我们按这样 的方法：第一次从n个数里找最大，第二次从n-1个数里找最大，以此 类推，需要的比较次数就是n(n-1)/2,称我们所用的方法为算法，称 n(n-1)/2为该算法的时间复杂度 对于时间复杂度，当n足够大时，我们只注重最高次方的那一项，其他各 项可以忽略，另外，其常数系数也不重要，所以，n(n-1)/2我们只重视n 的平方这一项了，记为O(n的平方），这就是该算法对该问题的时间复杂 度的专业表示 6.3.3 计算复杂性理论 2.时间复杂度 时间复杂度并不是表示一个程序解决问题需要花多少时间，而是当问题 规模扩大后，程序需要的时间长度增长得有多快。

也就是说，对于高速处理数据的计算机来说，处理某一个特定数据的效 率不能衡量一个程序的好坏，而应该看当这个数据的规模变大到数百倍 后，程序运行时间是否还是一样，或者也跟着慢了数百倍，或者变慢了 数万倍 6.3.3 计算复杂性理论 2.时间复杂度 假设问题的大小规模用n表示，所有算法时间复杂度形a*nk+b*n(k- 1)+c*n(k-2)都可记为O(nk)， nk表示n的k次方，*为乘号，这 样的复杂度称为多项式时间复杂度 若是时间复杂度形如kn，k为大于1的常数，或n!，或更大的，就称为 指数型时间复杂度 6.3.3 计算复杂性理论 假设一个问题有两种算法： 算法复杂性是n3 (0.2s) 算法复杂性是3n (4*1028s,1千万亿年) (用每秒百万次的计算机，n=60) 显然，当显然，当n n足够大时，指数型时间比多项式要大得多的多足够大时，指数型时间比多项式要大得多的多 如果一个问题没有多项式时间复杂性的算法，则被称如果一个问题没有多项式时间复杂性的算法，则被称为难解型问题为难解型问题 复杂性函复杂性函 数数 问题规模问题规模n n 10 30 50 6010 30 50 60 n n0.01ms 0.03ms 0.05ms 0.06ms0.01ms 0.03ms 0.05ms 0.06ms n n3 31ms 27ms 125ms 216ms1ms 27ms 125ms 216ms n n5 5100ms 24.3s 5.2min 13min100ms 24.3s 5.2min 13min 2 2n n1ms 17.9min 35.71ms 17.9min 35.7年年366366世纪世纪 6.3.3 计算复杂性理论 3. P类问题与NP类问题 按复杂性把问题分成不同的类 P类问题：所有能用多项式时间算法计算得到结果的问题，称为多项 式问题，也就是P类问题，所有绝对不可能用多项式时间求解的问题， 称为指数型问题。

P类问题包含了大量的已知问题，如计算最大公约数、计算值、排序 问题、二维匹配问题等 6.3.3 计算复杂性理论 3. P类问题与NP类问题 按复杂性把问题分成不同的类 NP问题：有这样一类问题，假使你得到了问题的解，我要验证你的 解是否正确，我验证所花的时间是多项式，至于求解本身所花的时间 是否是多项式我不管，可能有多项式算法，可能没有，也可能是不知 道，这类问题称为NP问题 如完全子图问题、图的着色问题、汉密尔顿回路问题、以及旅行销售 员问题等 拼图游戏：找到正确的排列方式很难，但你只要看一眼就知道它是不 是拼对了 6.3.3 计算复杂性理论 3. P类问题与NP类问题 NP问题举例：拿推销员旅行问题为例，假设推销员亨利有向6个城市推 销公司产品的任务，并规定了一个旅行预算他手中有一张航班票价表， 他要从A城开始走遍图中的6个城市后返回A城，并且不超出预算，请你 帮他找出应走的路线如果给出的预。