计算理论与计算模型(精)

计算理论计算模型2/48一、计数与计算手指、石头、结绳计数，算筹计算2.1计算的几种视角计算理论计算模型3/48许多计算领域的求解问题，如计算物理学、计算力学、计算化学和计算经济学等都可以归结为数值计算问题，而数值计算方法是一门与计算机应用紧密结合的、实用性很强的数学课程。2.1计算的几种视角如对气象资料的汇总、加工并生成天气图像，其计算量大且时限性强，要求计算机能够进行高速运算，以便对天气做出短期或中期的预报。科学计算的过程：实际问题数学模型计算方法程序设计计算结果计算理论计算模型4/48二、逻辑与计算2.1计算的几种视角逻辑学有三大源泉：①以亚里士多德的词项逻辑和斯多亚学派的命题逻辑为代表的古希腊逻辑。②以先秦名辩学为代表的古中国逻辑。③以正理论和因明学为代表的古印度逻辑。逻辑是研究推理的学科，人们可以把推理看成是对符号的操作，即符号演算。利用数学方法来研究推理的规律称为数理逻辑。为什么要研究数理逻辑呢？我们知道要使用计算机，就要有程序。程序＝算法＋数据结构，而算法＝逻辑＋控制计算理论计算模型5/48三、算法与计算2.1计算的几种视角从不同角度看，算法的定义有多种：从哲学角度看：算法是解决一个问题的抽象行为序列。从抽象层次看：算法是一个将输入转化为输出的计算步骤序列从技术层面看：算法是接收输入并产生输出的计算过程。简而言之，算法就是计算的办法或法则。算法无处不在，每个人每天都在使用不同的算法来活出自己的人生。比如你去食堂买饭会选择一个较短的队列，而有人则可能选择一个推进速度更快的队列。计算理论计算模型6/48算法：为解决一个特定的问题所采取确定的有限步骤。计算机用于解决数值计算，如科学计算中的数值积分、解线性方程等计算方法，就是数值计算的算法。计算机用于解决非数值计算，如用于管理、文字处理、图像图形等的排序、分类和查找，就是非数值计算的算法。算法的组成：操作、数据。这些操作包括加、减、乘、除和判断等，并按顺序、分支、循环等控制结构所规定的次序执行。数据是指操作对象和操作结果，包括布尔值、字符、整数和实数等；以及向量、记录、集合、树和图以及声音等。2.1计算的几种视角为什么学习算法：①算法是计算机的灵魂；②算法是数学机械化的一部分，能够帮助我们解决复杂的计算问题；③算法作为一种思想，能锻炼我们的思维，使思维变得更清晰、更有逻辑。计算理论计算模型7/48计算理论：关于计算和计算机械的数学理论，它研究计算的过程与功效。计算理论主要包括算法、算法学、计算复杂性理论、可计算性理论、自动机理论和形式语言理论等等。2.2计算理论计算理论计算模型8/48一、计算与计算过程2.2计算理论计算是依据一定的法则对有关符号串的变换过程。抽象地说，计算的本质就是递归。直观描述：计算是从已知符号开始，一步一步地改变符号串，经过有限步骤，最终得到一个满足预定条件的符号串的过程。这样一种有限的符号串变换过程与递归过程是等价的。计算过程：执行算法的过程，而算法的过程正好可以在计算机上执行的过程。即计算机算法是把问题转化为一步一步按规则执行的机械求解过程，再用计算机语言加以表达，最后输入计算机中进行计算。计算理论计算模型9/48二、可计算性理论可计算性理论：研究计算的一般性质的数学理论。计算的过程就是执行算法的过程。2.2计算理论可计算理论的中心课题：将算法这一直观概念精确化，建立计算的数学模型，研究哪些是可计算的，哪些是不可计算的，以此揭示计算的实质。由于计算与算法联系在一起，因此，可计算性理论又称算法理论或能行性理论。计算理论计算模型10/481.可计算理论的发展2.2计算理论可计算理论起源于对数学基础问题的研究。从20世纪30年代开始，为了讨论所有问题是否都有求解的算法，数学家和逻辑学家从不同角度提出了几种不同的算法概念精确化定义。19351936193619431951邱奇提出λ转换演算哥德尔等定义递归函数图灵和波斯特各自提出抽象计算机模型Mapkob定义正规算法陆续证明，上述这些不同计算模型(算法精确化定义模式)的计算能力都是一样的，即它们是等价的。计算理论计算模型11/482.可计算性的定义和特性2.2计算理论定义：凡可用某种程序设计语言描述的问题都是可计算性问题。图灵的定义：能够在图灵机上执行的过程，有时又称算法的过程。图灵之所以能取得成功，很重要的一条是他采用了算法思维来研究计算的过程，由此揭示可计算性概念。由于算法思维与当今在计算机上运行的程序之间有着密切的关系，从而使他的理论受到重视并被广泛使用。特性：确定性、有限性、机械性、可执行性和终止性。计算理论计算模型12/483.可计算理论的主要内容2.2计算理论图灵机：一种在理论计算机科学中广泛采用的抽象计算机用于精确描述算法的特征。通用图灵机正是后来的存储程序的通用数字计算机的理论原型。λ转换演算：一种定义函数的形式演算系统。丘奇为精确定义可计算性而提出的，他引进λ记号以明确区分函数和函数值，并把函数值的计算归结为按照一定规则进行一系列转换，最后得到函数值。丘奇-图灵论题：可计算性理论的基本论题。它规定了直观可计算函数的精确含义。丘奇论题说：λ可定义函数类与直观可计算函数类相同。图灵论题说：图灵机可计算函数类与直观可计算函数类相同。计算理论计算模型13/48原始递归函数：自变量值和函数值都是自然数的函数，称为数论函数。原始递归函数是数论函数的一部分。规定：少量直观可计算的函数为原始递归函数，它们是：函数值恒等于0的零函数C0，函数值等于自变量值加1的后继函数S函数值等于第i个自变量值的n元投影函数Pi(n)。原始递归函数的合成仍是原始递归函数，可以由已知原始递归函数简单递归地计算出函数值的函数仍是原始递归函数。2.2计算理论例如：和函数f(x，y)=x+y可由原始递归函数Pi(1)和S递归地计算出函数值。f(x,0)=P1(1)(x)f(x,S(y))=S(f(x,y))求f(4,2)=？，f(4,0)=P1(1)(4)=4f(4,1)=S(f(4,0))=S(4)=5f(4,2)=S(f(4,1))=S(5)=6计算理论计算模型14/484.可计算理论的意义2.2计算理论可计算性理论的基本思想、概念和方法被广泛应用于计算科学的各个领域。建立数学模型的方法在计算科学中被广泛采用，递归的思想被用于程序设计、数据结构和计算机体系结构，λ演算被用于研究程序设计语言的语义等。计算学科的一个基本结论是不可计算的函数要比可计算的函数多得多。虽然许多问题是可判定的，但更多的问题是不可判定的，如停机问题和波斯特对应问题都是不可判定的。计算理论计算模型15/48三、停机问题停机问题是目前逻辑数学的焦点和第三次数学危机的解决方案，它是重要的不可判定问题。1936年，Turing发表“论可计算数及其在判定问题中的应用”论文中提出一般性停机问题的不可判定性，并用形式化方法证明其为一个不可计算问题。一般性的停机问题：对于任意的图灵机和输入，是否存在一个算法，用于判定图灵机在接收初始输入后可达停机状态。若能找到这种算法，停机问题可解；否则不可解。2.2计算理论计算理论计算模型16/48通俗地说，停机问题就是判断任意一个程序是否在有限的时间内结束运行的问题。例如：main(){inti=1;while(i10){i=i+1;}return;}又如：main(){inti=1;while(i0){i=i+1;}return;}程序可终止程序死循环程序简单时容易做出判断，当例子复杂时会遇到较大的困难，而在某些情况下则无法预测。2.2计算理论计算理论计算模型17/48停机问题的关键：能否找到一个测试程序，这个测试程序能判定任何一个程序在给定的输入下能否终止。数学反证法证明：先假设存在这样的测试程序，然后再构造一个程序，该测试程序不能测试假设存在一个测试程序T，它能接受任何输入。当输入程序P能终止，输出1；P不能终止，输出0。2.2计算理论计算理论计算模型18/48P能终止,X→1P不终止,X→0测试程序T程序PX测试程序TX(1或0)while(x){}S程序P测试程序TX(1或0)while(x){}S程序SP终止,X→1,S→不终止P不终止,X→0,S→终止S终止,X→1,S→不终止S不终止,X→0,S→终止结论：若S终止，则S不终止；若S不终止，则S终止，结论矛盾故可以确定这样的测试程序不存在，从而证明停机问题不可解2.2计算理论计算理论计算模型19/48[例2-1]理发师悖论。一个理发师的招牌：城里所有不自己刮脸的男人都由我给他们刮脸，我也只给这些人刮脸。问题是：谁给这位理发师刮脸呢？如果他自己刮脸，那他就属于自己刮脸的那类人。但是，他的招牌说明他不给这类人刮脸，因此他不能自己来刮。如果另外一个人来给他刮脸，那他就是不自己刮脸的人。但是，他的招牌说他要给所有这类人刮脸。因此，其他任何人也不能给他刮脸。从本质上看，理发师问题和停机问题是一样的。2.2计算理论计算理论计算模型20/48四、计算复杂性理论计算复杂性理论：用数学方法研究各类问题的计算复杂性的学科。计算复杂性理论研究各种可计算问题在计算过程中资源(如时间、空间等)的耗费情况，以及在不同计算模型下，使用不同类型资源和不同数量的资源时，各类问题复杂性的本质特性和相互关系。2.2计算理论计算理论计算模型21/481.计算复杂性理论的发展1993年的图灵奖授予合作奠定了计算复杂性理论基础的两位学者J.Hartmanis和R.E.Stearns。在此以前，已有M.O.Rabin、S.A.Cook、R.M.Karp等学者因在计算复杂性理论研究中做出先驱性工作而分别在1976、1982和1985年获得图灵奖。Hartmanis和Stearns则在前人工作的基础上，比较完整地提出了计算复杂性的理论体系，并首次正式命名了计算复杂性(computationalcomplexity)，因而被公认为计算复杂性理论的主要创始人。2.2计算理论计算理论计算模型22/481995年度的图灵奖授予加州大学伯克利分校的计算机科学家ManuelBlum，他是计算复杂性理论的主要奠基人之一。Blum与前述两人互相独立地进行着相关问题的研究，并完成了他的博士论文：Amachineindependenttheoryofthecomplexityofrecursivefunctions(与机器无关的递归函数复杂性理论)，论文提出了有关计算复杂性的4个公理，被称为布卢姆公理系统。目前，可计算理论的绝大部分结果都可以从这个公理系统推导出来。2.2计算理论计算复杂性理论应用于计算机安全(密码学)、软件工程的程序正确验证，以及算法博弈论。计算理论计算模型23/482.算法复杂性2.2计算理论算法复杂性是对算法效率的度量，它是评价算法优劣的重要依据。一个算法复杂性的高低体现在运行该算法时所需要的资源，所需资源越多，算法复杂性越高；所需资源越低，则算法复杂性越低。计算机的资源，主要是指运行时间和存储空间，因而算法复杂性有时间复杂性和空间复杂性之分。当给定的问题已有多种算法时，选择其中复杂性最低者，是选用算法时应遵循的一个重要准则。计算理论计算模型24/483.计算复杂性2.2计算理论算法复杂性→针对特定算法计算复杂性→针对特定问题，反映问题的固有难度计算复杂性＝最佳的算法复杂性计算复杂性：用计算机求解问题的难易程度。度量标准：①时间复杂度→计算所需的步数或指令条数；②空间复杂度→计算所需的存储空间大小。计算理论计算模型25/48假设一个问题有两种算法：①算法复杂性是n3(0.2s)②算法复杂性是3n(4*1028s,1千万亿年)(用每秒百万次的计算机，n=60)如果一个问题没有多项式时间复杂性的算法，则被称为难解型问题。2.2计算理论复杂性函数问题规模n10305060n0.01ms0.03ms0.05ms0.06msn31ms27ms125ms216msn5100ms24.3s5.2min13min2n1ms17.9min35.7年366世纪计算理论计算模型26/484.P=NP?问题按复杂性