电子教案6-3计算理论

大学计算机,第6章：计算理论与计算模型,计算理论,6.3,6.3计算理论,计算理论（theoryofcomputation）用来研究计算的过程与功效的数学理论，起源于对数学基础问题的研究。计算理论主要包括算法、算法学、计算复杂性理论、可计算性理论、自动机理论和形式语言理论等。自动机、可计算性、复杂度刚好是计算的三个不同的方面：计算的模型、计算的界限、计算的代价。计算理论是计算机科学的理论基础。计算机科学最自然最根本的问题：什么是计算，什么可以被计算，什么样的问题是难的、什么样的问题是容易的。这些是计算理论的主题。,6.3计算理论,问题求解是计算科学的根本目的之一，计算科学也是在问题求解的实践中逐渐发展壮大的。数学模型是连接数学与实际问题的桥梁。在建立数学模型过程中，首先要对问题进行观察，研究其运动变化的情况，引出数学方法，再回到问题的解决中去。判断问题的数学模型是否可解，如果不可解，则要寻找问题特征、分类以及不可解的证明。如果可解，则进一步求得计算模型及其复杂度最后才是算法设计和编程调试,6.3计算理论,问题求解的计算过程,陆续证明，上述这些不同计算模型(算法精确化定义模式)的计算能力都是一样的，即它们是等价的。,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.停机问题停机问题是目前逻辑数学的焦点和第三次数学危机的解决方案，它是重要的不可判定问题。,1936年，Turing发表“论可计算数及其在判定问题中的应用”论文中提出一般性停机问题的不可判定性，并用形式化方法证明其为一个不可计算问题。,6.3.2可计算性理论,停机问题的关键：能否找到一个测试程序，这个测试程序能判定任何一个程序在给定的输入下能否终止。数学反证法证明：先假设存在这样的测试程序，然后再构造一个程序，该测试程序不能测试,假设存在一个测试程序T，它能接受任何输入。当输入程序P能终止，输出1；P不能终止，输出0。,6.3.2可计算性理论,P能终止,X1P不终止,X0,P终止,X1,S不终止P不终止,X0,S终止,S终止,X1,S不终止S不终止,X0,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和R。Stearns。他们两人是1993年度图灵奖获得者。另一个中心是麻省理工学院MIT，在那里，加州大学伯克利分校著名的计算机科学家ManuelBlum与前述两人互相独立地进行着相关问题的研究。三人被学术界公认为计算复杂性理论的主要奠基人,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足够大时，指数型时间比多项式要大得多的多。如果一个问题没有多项式时间复杂性的算法，则被称为难解型问题。,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城，并且不超出预算，请你帮他找出应走的路线。如果给出的预算宽裕，则任务很简单；如果预算比较紧张，你就得认真设计路线了。你得考虑每一种可能的次序，以使旅费最少。,6.3.3计算复杂性理论,3.P类问题与NP类问题如果有6个城市互相之间都有往返的飞机，则有6！=720种次序。这种急剧增长的可能性的数目也远远超过计算资源的处理能力，对此，算法复杂性专家史蒂芬。库克（StephenCook）评论：“如果有100个城市，需要求出100！条路线的费用，没有哪一台计算机能够胜任这一任务。NP概念的奥妙在于，它躲开了求解到底需要多少时间这样的问题，而仅仅只是强调验证需要多少时间，从而为P与NP这一千年难题的产生埋下了伏笔。,6.3.3计算复杂性理论,3.P类问题