计算理论与计算模型精选PPT.ppt

《计算理论与计算模型精选PPT.ppt》由会员分享，可在线阅读，更多相关《计算理论与计算模型精选PPT.ppt（48页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、计算理论与计算模型1第1页，此课件共48页哦一、计数与计算一、计数与计算 手指、石头、结绳计数，算筹计算手指、石头、结绳计数，算筹计算2.1 计算的几种视角圆周率:10万亿位2第2页，此课件共48页哦 许多计算领域的许多计算领域的求解问题求解问题，如计算物理学、计算力学、，如计算物理学、计算力学、计算化学和计算经济学等都可以归结为数值计算问题，而计算化学和计算经济学等都可以归结为数值计算问题，而数值数值计算方法计算方法计算方法计算方法是一门与计算机应用紧密结合的、实用性很强是一门与计算机应用紧密结合的、实用性很强的数学课程。的数学课程。2.1 计算的几种视角 如对气象资料的汇总、加工并生成天气

2、图像，如对气象资料的汇总、加工并生成天气图像，其计算量大且时限性强，要求计算机能够进行高速其计算量大且时限性强，要求计算机能够进行高速运算，以便对天气做出短期或中期的预报。运算，以便对天气做出短期或中期的预报。科学计算的过程科学计算的过程：实际问题实际问题数学模型数学模型计算方法计算方法程序设计程序设计计算结果计算结果3第3页，此课件共48页哦二、逻辑与计算二、逻辑与计算2.1 计算的几种视角 逻辑学有三大源泉逻辑学有三大源泉：以亚里士多德的词项逻辑和斯多亚以亚里士多德的词项逻辑和斯多亚学派的命题逻辑为代表的古希腊逻辑。学派的命题逻辑为代表的古希腊逻辑。以先秦名辩学为代表的古中国逻辑。以先秦名

3、辩学为代表的古中国逻辑。以正理论和因明学为代表的古印度逻辑。以正理论和因明学为代表的古印度逻辑。逻辑是研究推理的学科，人们可以把推理看成是对符号的操作，即逻辑是研究推理的学科，人们可以把推理看成是对符号的操作，即符号演算。符号演算。利用数学方法来研究推理的规律称为利用数学方法来研究推理的规律称为数理逻辑数理逻辑。为什么要研究。为什么要研究数理逻辑呢？我们知道要使用计算机，就要有程序。数理逻辑呢？我们知道要使用计算机，就要有程序。程序算法数据结构，而算法逻辑控制程序算法数据结构，而算法逻辑控制4第4页，此课件共48页哦三、算法与计算三、算法与计算2.1 计算的几种视角从不同角度看，算法的定义有多

4、种从不同角度看，算法的定义有多种：从哲学角度看：算法是解决一个问题的抽象行为序列。从哲学角度看：算法是解决一个问题的抽象行为序列。从抽象层次看：算法是一个将输入转化为输出的计算步骤序列从抽象层次看：算法是一个将输入转化为输出的计算步骤序列从技术层面看：算法是接收输入并产生输出的计算过程。从技术层面看：算法是接收输入并产生输出的计算过程。简而言之，简而言之，算法就是计算的办法或法则算法就是计算的办法或法则。算法无处不在，每个人每天都在算法无处不在，每个人每天都在使用不同的算法来活出自己的人生。使用不同的算法来活出自己的人生。比如你去食堂买饭会选择一个较短的比如你去食堂买饭会选择一个较短的队列，而

5、有人则可能选择一个推进速队列，而有人则可能选择一个推进速度更快的队列。度更快的队列。5第5页，此课件共48页哦 算法算法：为解决一个特定的问题所采取确定的有限步骤。：为解决一个特定的问题所采取确定的有限步骤。计算机用于解决数值计算，如科学计算中的数值积分、解线性方程等计计算机用于解决数值计算，如科学计算中的数值积分、解线性方程等计算方法，就是数值计算的算法。算方法，就是数值计算的算法。计算机用于解决非数值计算，如用于管理、文字处理、图像图形计算机用于解决非数值计算，如用于管理、文字处理、图像图形等的排序、分类和查找，就是非数值计算的算法。等的排序、分类和查找，就是非数值计算的算法。算法的组成算

6、法的组成：操作、数据。：操作、数据。这些操作包括加、减、乘、除和判断等，并按顺序、分支、循这些操作包括加、减、乘、除和判断等，并按顺序、分支、循环等控制结构所规定的次序执行。环等控制结构所规定的次序执行。数据是指操作对象和操作结果，包括布尔值、字符、整数和实数据是指操作对象和操作结果，包括布尔值、字符、整数和实数等；以及向量、记录、集合、树和图以及声音等。数等；以及向量、记录、集合、树和图以及声音等。2.1 计算的几种视角 为什么学习算法为什么学习算法：算法是计算机的灵魂；算法是计算机的灵魂；算法是数学机算法是数学机械化的一部分，能够帮助我们解决复杂的计算问题；械化的一部分，能够帮助我们解决复

7、杂的计算问题；算法作为算法作为一种思想，能锻炼我们的思维，使思维变得更清晰、更有逻辑。一种思想，能锻炼我们的思维，使思维变得更清晰、更有逻辑。6第6页，此课件共48页哦 计算理论计算理论：关于计算和计算机械的数学理论，：关于计算和计算机械的数学理论，它研究计算的过程与功效。它研究计算的过程与功效。计算理论主要包括算法、算法学、计算复杂计算理论主要包括算法、算法学、计算复杂性理论、可计算性理论、自动机理论和形式语言性理论、可计算性理论、自动机理论和形式语言理论等等。理论等等。2.2 计算理论7第7页，此课件共48页哦一、计算与计算过程一、计算与计算过程2.2 计算理论 计算计算是依据一定的法则对

8、有关符号串的变换过程。抽象是依据一定的法则对有关符号串的变换过程。抽象地说，计算的本质就是递归。地说，计算的本质就是递归。直观描述直观描述：计算是从已知符号开始，一步一步地改变符号：计算是从已知符号开始，一步一步地改变符号串，经过有限步骤，最终得到一个满足预定条件的符号串的过串，经过有限步骤，最终得到一个满足预定条件的符号串的过程。这样一种有限的符号串变换过程与递归过程是等价的。程。这样一种有限的符号串变换过程与递归过程是等价的。计算过程计算过程：执行算法的过程，而算法的过程正好可：执行算法的过程，而算法的过程正好可以在计算机上执行的过程。即计算机算法是把问题转化以在计算机上执行的过程。即计算

9、机算法是把问题转化为一步一步按规则执行的机械求解过程，再用计算机语为一步一步按规则执行的机械求解过程，再用计算机语言加以表达，最后输入计算机中进行计算。言加以表达，最后输入计算机中进行计算。8第8页，此课件共48页哦二、可计算性理论二、可计算性理论 可计算性理论可计算性理论：研究计算的一般性质的数学：研究计算的一般性质的数学理论。计算的过程就是执行算法的过程。理论。计算的过程就是执行算法的过程。2.2 计算理论 可计算理论的中心课题可计算理论的中心课题：将算法这一直观概念：将算法这一直观概念精确化精确化，建立计算的建立计算的数学模型数学模型，研究哪些是，研究哪些是可计算可计算的，哪些是的，哪些

10、是不可不可计算计算的，以此揭示计算的实质。的，以此揭示计算的实质。由于计算与算法联系在一起，因此，可计算性理论由于计算与算法联系在一起，因此，可计算性理论又称又称算法理论算法理论或或能行性理论能行性理论。9第9页，此课件共48页哦 1.1.可计算理论的发展可计算理论的发展2.2 计算理论 可计算理论起源于对数学基础问题的研究。从可计算理论起源于对数学基础问题的研究。从2020世纪世纪3030年代开始，为年代开始，为了讨论所有问题是否都有求解的算法，数学家和逻辑学家从不同角度提了讨论所有问题是否都有求解的算法，数学家和逻辑学家从不同角度提出了几种不同的算法概念精确化定义。出了几种不同的算法概念精

11、确化定义。1935193519361936193619361943194319511951邱奇提出邱奇提出转换演算转换演算哥德尔等定哥德尔等定义递归函数义递归函数图灵和波斯特图灵和波斯特各自提出抽象各自提出抽象计算机模型计算机模型MapkobMapkob定义定义正规算法正规算法陆续陆续证明证明，上述这些不同计算模型，上述这些不同计算模型(算法精确化定义模算法精确化定义模式式)的计算能力都是一样的，即的计算能力都是一样的，即它们是等价的它们是等价的。10第10页，此课件共48页哦 2.2.可计算性的定义和特性可计算性的定义和特性2.2 计算理论 定义定义：凡可用某种程序设计语言描述的问题都是可计

12、算性问题。：凡可用某种程序设计语言描述的问题都是可计算性问题。图灵的定义图灵的定义：能够在图灵机上执行的过程，有时又称：能够在图灵机上执行的过程，有时又称算法的过算法的过程程。图灵之所以能取得成功，很重要的一条是他采用了算法思图灵之所以能取得成功，很重要的一条是他采用了算法思维来研究计算的过程，由此揭示可计算性概念。由于算法思维维来研究计算的过程，由此揭示可计算性概念。由于算法思维与当今在计算机上运行的程序之间有着密切的关系，从而使他与当今在计算机上运行的程序之间有着密切的关系，从而使他的理论受到重视并被广泛使用。的理论受到重视并被广泛使用。特性特性：确定性、有限性、机械性、可执行性和终止性。

13、：确定性、有限性、机械性、可执行性和终止性。11第11页，此课件共48页哦 3.3.可计算理论的主要内容可计算理论的主要内容 2.2 计算理论 图灵机图灵机：一种在理论计算机科学中广泛采用的：一种在理论计算机科学中广泛采用的抽象计算机用于精抽象计算机用于精确描述算法的特征确描述算法的特征。通用图灵机正是后来的存储程序的通用数字计算机。通用图灵机正是后来的存储程序的通用数字计算机的理论原型。的理论原型。转换演算转换演算：一种定义函数的形式演算系统一种定义函数的形式演算系统。丘奇丘奇为精确定义可为精确定义可计算性而提出的，他引进计算性而提出的，他引进记号以明确区分函数和函数值，并把函数记号以明确区

14、分函数和函数值，并把函数值的计算归结为按照一定规则进行一系列转换，最后得到函数值。值的计算归结为按照一定规则进行一系列转换，最后得到函数值。丘奇丘奇-图灵论题图灵论题：可计算性理论的基本论题。它规定了直观可计算：可计算性理论的基本论题。它规定了直观可计算函数的精确含义。丘奇论题说：函数的精确含义。丘奇论题说：可定义函数类与直观可计算函数可定义函数类与直观可计算函数类相同。图灵论题说：图灵机可计算函数类与直观可计算函数类类相同。图灵论题说：图灵机可计算函数类与直观可计算函数类相同。相同。12第12页，此课件共48页哦 原始递归函数原始递归函数：自变量值和函数值都是自然数的函数，称为数论函数。：自

15、变量值和函数值都是自然数的函数，称为数论函数。原始递归函数是数论函数的一部分。原始递归函数是数论函数的一部分。规定规定：少量直观可计算的函数为原始递归函数，它们是：函数值恒等：少量直观可计算的函数为原始递归函数，它们是：函数值恒等于于0 0的零函数的零函数C0 0，函数值等于自变量值加，函数值等于自变量值加1 1的后继函数的后继函数S函数值等于第函数值等于第i个个自变量值的自变量值的n元投影函数元投影函数Pi(n)。原始递归函数的合成仍是原始递归函数，可以由已知原始递归函数简原始递归函数的合成仍是原始递归函数，可以由已知原始递归函数简单递归地计算出函数值的函数仍是原始递归函数。单递归地计算出函

16、数值的函数仍是原始递归函数。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)=4 f(4,1)=S(f(4,0)=S(4)=5 f(4,2)=S(f(4,1)=S(5)=613第13页，此课件共48页哦 4.4.可计算理论的意义可计算理论的意义2.2 计算理论 可计算性理论的基本思想、概念和方法被广泛应用于计算可计算性理论的基本思想、概念和方法被广泛应用于计算科学的各个

17、领域。建立数学模型的方法在计算科学中被广泛采科学的各个领域。建立数学模型的方法在计算科学中被广泛采用，递归的思想被用于程序设计、数据结构和计算机体系结构，用，递归的思想被用于程序设计、数据结构和计算机体系结构，演算被用于研究程序设计语言的语义等。演算被用于研究程序设计语言的语义等。计算学科的一个基本结论是不可计算的函数要比可计计算学科的一个基本结论是不可计算的函数要比可计算的函数多得多。虽然许多问题是可判定的，但更多的问算的函数多得多。虽然许多问题是可判定的，但更多的问题是不可判定的，如题是不可判定的，如停机问题停机问题和波斯特对应问题都是不可和波斯特对应问题都是不可判定的。判定的。14第14

18、页，此课件共48页哦三、停机问题三、停机问题 停机问题停机问题是目前逻辑数学的焦点和第三次数是目前逻辑数学的焦点和第三次数学危机的解决方案，它是重要的不可判定问题。学危机的解决方案，它是重要的不可判定问题。1936 1936年，年，TuringTuring发表发表“论可计算数及论可计算数及其在判定问题中的应用其在判定问题中的应用”论文中提出一般论文中提出一般性停机问题的不可判定性，并用形式化方性停机问题的不可判定性，并用形式化方法证明其为一个不可计算问题。法证明其为一个不可计算问题。一般性的停机问题一般性的停机问题：对于任意的图灵机和输入，是否存在：对于任意的图灵机和输入，是否存在一个算法，用

19、于判定图灵机在接收初始输入后可达停机状一个算法，用于判定图灵机在接收初始输入后可达停机状态。若能找到这种算法，停机问题可解；否则不可解。态。若能找到这种算法，停机问题可解；否则不可解。2.2 计算理论15第15页，此课件共48页哦 通俗地说，通俗地说，停机问题停机问题就是判断任意一个程序就是判断任意一个程序是否在有限的时间内结束运行的问题。是否在有限的时间内结束运行的问题。例如：例如：main()int i=1;while(i0)i=i+1;return;程序可终止程序可终止程序死循环程序死循环程序简单时容易做出判断，当例子复杂时会遇程序简单时容易做出判断，当例子复杂时会遇到较大的困难，而在某

20、些情况下则无法预测。到较大的困难，而在某些情况下则无法预测。2.2 计算理论16第16页，此课件共48页哦 停机问题的关键停机问题的关键：能否找到一个测试程序，：能否找到一个测试程序，这个测试程序能判定任何一个程序在给定的输入这个测试程序能判定任何一个程序在给定的输入下能否终止。下能否终止。数学反证法证明数学反证法证明：先假设存在这样的测试程序，：先假设存在这样的测试程序，然后再构造一个程序，该测试程序不能测试然后再构造一个程序，该测试程序不能测试假设存在一个测试程序假设存在一个测试程序T T，它能接受任何输入。，它能接受任何输入。当输入程序当输入程序P P能终止，输出能终止，输出1 1；P

21、P不能终止，输出不能终止，输出0 0。2.2 计算理论17第17页，此课件共48页哦P P能终止能终止,X,X1 1P P不终止不终止,X,X0 0测试程序测试程序T T程序程序P PX X测试程序测试程序T TX(1X(1或或0)0)while(x)while(x)S S程序程序P P测试程序测试程序T TX(1X(1或或0)0)while(x)while(x)S S程序程序S SP 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终止，则

22、终止，则S S不终止；若不终止；若S S不终止，则不终止，则S S终止，结论矛盾终止，结论矛盾故可以确定这样的测试程序不存在，从而证明停机问题不可解故可以确定这样的测试程序不存在，从而证明停机问题不可解2.2 计算理论18第18页，此课件共48页哦 例例2-12-1理理发发师师悖悖论论。一一个个理理发发师师的的招招牌牌：城城里里所所有有不不自自己己刮刮脸脸的男人都由我给他们刮脸，我也只给这些人刮脸。的男人都由我给他们刮脸，我也只给这些人刮脸。问题是问题是：谁给这位理发师刮脸呢？如果他自己刮脸，那他就属：谁给这位理发师刮脸呢？如果他自己刮脸，那他就属于自己刮脸的那类人。但是，他的招牌说明他不给这

23、类人刮脸，于自己刮脸的那类人。但是，他的招牌说明他不给这类人刮脸，因此他不能自己来刮。因此他不能自己来刮。如果另外一个人来给他刮脸，那他就是不自己刮脸的人。如果另外一个人来给他刮脸，那他就是不自己刮脸的人。但是，他的招牌说他要给所有这类人刮脸。因此，其他任但是，他的招牌说他要给所有这类人刮脸。因此，其他任何人也不能给他刮脸。何人也不能给他刮脸。从本质上看，理发师问题和停机问题是一样的。从本质上看，理发师问题和停机问题是一样的。2.2 计算理论19第19页，此课件共48页哦四、计算复杂性理论四、计算复杂性理论 计算复杂性理论计算复杂性理论：用数学方法研究各类问题：用数学方法研究各类问题的计算复杂

24、性的学科。的计算复杂性的学科。计算复杂性理论研究各种可计算问题在计算计算复杂性理论研究各种可计算问题在计算过程中资源过程中资源(如时间、空间等如时间、空间等)的耗费情况，以及的耗费情况，以及在不同计算模型下，使用不同类型资源和不同数在不同计算模型下，使用不同类型资源和不同数量的资源时，各类问题复杂性的本质特性和相互量的资源时，各类问题复杂性的本质特性和相互关系。关系。2.2 计算理论20第20页，此课件共48页哦 1.1.计算复杂性理论的发展计算复杂性理论的发展 1993 1993年的图灵奖授予合作奠定了计算复杂性理论基础的两位学年的图灵奖授予合作奠定了计算复杂性理论基础的两位学者者J.Har

25、tmanisJ.Hartmanis和和R.E.StearnsR.E.Stearns。在此以前，已有在此以前，已有M.O.RabinM.O.Rabin、S.A.CookS.A.Cook、R.M.KarpR.M.Karp等学者因在计算等学者因在计算复杂性理论研究中做出先驱性工作而分别在复杂性理论研究中做出先驱性工作而分别在19761976、19821982和和19851985年获年获得图灵奖。得图灵奖。HartmanisHartmanis和和StearnsStearns则在前人工作的基础上，比较完整地则在前人工作的基础上，比较完整地提出了计算复杂性的理论体系，并首次正式命名了提出了计算复杂性的理论

26、体系，并首次正式命名了计算复杂性计算复杂性(computational complexity)，因而被公认为计算复杂性理论的主要创，因而被公认为计算复杂性理论的主要创始人。始人。2.2 计算理论21第21页，此课件共48页哦 1995 1995年度的图灵奖授予加州大学伯克利分校的计算机科学家年度的图灵奖授予加州大学伯克利分校的计算机科学家Manuel BlumManuel Blum，他是计算复杂性理论的主要奠基人之一。，他是计算复杂性理论的主要奠基人之一。BlumBlum与前述两人互相独立地进行着相关问题的研究，并完成了他与前述两人互相独立地进行着相关问题的研究，并完成了他的博士论文：的博士论

27、文：A machine independent theory of the complexity of recursive functions(与机器无关的递归函数复杂性理论与机器无关的递归函数复杂性理论)，论文提出了有，论文提出了有关计算复杂性的关计算复杂性的4 4个公理，被称为布卢姆公理系统。目前，可计算理论的绝个公理，被称为布卢姆公理系统。目前，可计算理论的绝大部分结果都可以从这个公理系统推导出来。大部分结果都可以从这个公理系统推导出来。2.2 计算理论计算复杂性理论应用于计计算复杂性理论应用于计算机安全算机安全(密码学密码学)、软件、软件工程的程序正确验证，以工程的程序正确验证，以及算

28、法博弈论。及算法博弈论。22第22页，此课件共48页哦 2.2.算法复杂性算法复杂性2.2 计算理论 算法复杂性是对算法效率的度量，它是评价算法优算法复杂性是对算法效率的度量，它是评价算法优劣的重要依据。劣的重要依据。一个算法复杂性的高低体现在运行该算法时所需要的资源，一个算法复杂性的高低体现在运行该算法时所需要的资源，所需资源越多，算法复杂性越高；所需资源越低，则算法复杂所需资源越多，算法复杂性越高；所需资源越低，则算法复杂性越低。性越低。计算机的资源，主要是指运行时间和存储空间，因而计算机的资源，主要是指运行时间和存储空间，因而算算法复杂性法复杂性有有时间复杂性时间复杂性和和空间复杂性空间

29、复杂性之分。之分。当给定的问题已有多种算法时，选择其中复杂性最当给定的问题已有多种算法时，选择其中复杂性最低者，是选用算法时应遵循的一个重要准则。低者，是选用算法时应遵循的一个重要准则。23第23页，此课件共48页哦 3.3.计算复杂性计算复杂性2.2 计算理论 算法复杂性算法复杂性针对特定算法针对特定算法 计算复杂性计算复杂性针对特定问题，反映问题的固有难度针对特定问题，反映问题的固有难度 计算复杂性最佳的算法复杂性计算复杂性最佳的算法复杂性 计算复杂性计算复杂性：用计算机求解问题的难易程度。：用计算机求解问题的难易程度。度量标准度量标准：时间复杂度时间复杂度计算所需的步数或指令条数；计算所

30、需的步数或指令条数；空间复杂度空间复杂度计算所需的存储空间大小。计算所需的存储空间大小。24第24页，此课件共48页哦 假设一个问题有两种算法：假设一个问题有两种算法：算法复杂性是算法复杂性是n n3 3(0.2s)(0.2s)算法复杂性是算法复杂性是3 3n n(4*10(4*102828s,1s,1千万亿年千万亿年)(用每秒百万次的计算机，用每秒百万次的计算机，n=60)n=60)如果一个问题没有多项式时间复杂性的算法，则被称如果一个问题没有多项式时间复杂性的算法，则被称为难解型问题为难解型问题。2.2 计算理论复杂性复杂性复杂性复杂性函数函数函数函数问题规模问题规模问题规模问题规模n n

31、 n n 10 30 50 60 10 30 50 60 10 30 50 60 10 30 50 60n n 0.01ms 0.03ms 0.05ms 0.06ms 0.01ms 0.03ms 0.05ms 0.06msn n3 3 1ms 27ms 125ms 216ms 1ms 27ms 125ms 216msn n5 5 100ms 24.3s 5.2min 13min 100ms 24.3s 5.2min 13min2 2n n 1ms 17.9min 35.7 1ms 17.9min 35.7年年 366366世纪世纪25第25页，此课件共48页哦 4.P=NP?4.P=NP?问题

32、问题 按复杂性把问题分成不同的类。按复杂性把问题分成不同的类。2.2 计算理论 P P类问题类问题：由确定型图灵机在多项式时间内可解的一切判定问题所：由确定型图灵机在多项式时间内可解的一切判定问题所组成的集合。组成的集合。P P类问题包含了大量的已知自然问题，如计算最大公约数、计算类问题包含了大量的已知自然问题，如计算最大公约数、计算值、排序问题、二维匹配问题等。值、排序问题、二维匹配问题等。NP NP类问题类问题：由非确定型图灵机在多项式时间内可计算的判定问题所：由非确定型图灵机在多项式时间内可计算的判定问题所组成的集合。组成的集合。也就是说，如果一个问题的潜在解答可以在多项式时间内被也就是

33、说，如果一个问题的潜在解答可以在多项式时间内被证实或证伪，则该问题属于证实或证伪，则该问题属于NPNP。NPNP类问题数量巨大，如完全子图类问题数量巨大，如完全子图问题、图的着色问题、汉密尔顿回路问题、以及旅行销售员问问题、图的着色问题、汉密尔顿回路问题、以及旅行销售员问题等。题等。26第26页，此课件共48页哦 对于对于NPNP来说，一个常见的来说，一个常见的误解误解是人们认为是人们认为NPNP问题不存在多项式时问题不存在多项式时间解。这是否意味着间解。这是否意味着P PNPNP呢？或者说，呢？或者说，P P类集合是否与类集合是否与NPNP类问题集合类问题集合完全重合呢？这个问题是完全重合呢

34、？这个问题是2121世纪数学界和计算机科学理论界面临的一世纪数学界和计算机科学理论界面临的一个重大问题。个重大问题。所有所有P P类问题都是类问题都是NPNP类问题类问题：因为确定性图灵机能够解决的问题当然：因为确定性图灵机能够解决的问题当然能够被非确定性图灵机解决。能够被非确定性图灵机解决。是否所有是否所有NPNP问题都是问题都是P P问题问题：凭直觉：凭直觉NPNP应该不属于应该不属于P P，因为非确定性，因为非确定性图灵机比确定性图灵机强大得多，很难相信一个强大得多的机器所能图灵机比确定性图灵机强大得多，很难相信一个强大得多的机器所能够解决的问题都可以被一个功能更弱的机器解决！够解决的问

35、题都可以被一个功能更弱的机器解决！必须拿出证据来说明必须拿出证据来说明NPNP不属于不属于P P。要证明这一点，只需证明某个。要证明这一点，只需证明某个NPNP问问题不属于题不属于P P即可。但遗憾的是，目前尚没有人证明即可。但遗憾的是，目前尚没有人证明NPNP不属于不属于P P。当然也。当然也没有人证明了没有人证明了NPNP属于属于P P。也就是说，。也就是说，P P与与NPNP是否等价是一个既没有证实是否等价是一个既没有证实也没有证伪的问题！也没有证伪的问题！2.2 计算理论27第27页，此课件共48页哦 计算模型是刻画计算的抽象的形式系统或数计算模型是刻画计算的抽象的形式系统或数学系统。

36、在计算科学中，计算模型是指具有状态学系统。在计算科学中，计算模型是指具有状态转换特征，能够对所处理对象的数据或信息进行转换特征，能够对所处理对象的数据或信息进行表示、加工、变换和输出的数学机器。表示、加工、变换和输出的数学机器。2.3 计算模型 19361936年，图灵发表年，图灵发表“论可计算数及其在论可计算数及其在判定问题中的应用判定问题中的应用”论文，给论文，给“可计算性可计算性”下了严格的数学定义，并提出著名的下了严格的数学定义，并提出著名的图灵机图灵机(Turing Machine)(Turing Machine)的设想。的设想。图灵机是一种十分简单但运算能力很强图灵机是一种十分简单

37、但运算能力很强的理想计算装置，它描述了一种假想的可实的理想计算装置，它描述了一种假想的可实现通用计算的机器。现通用计算的机器。28第28页，此课件共48页哦一、图灵机一、图灵机 1.1.直观描述直观描述 图灵机的计算装置：一条两端可无限延长图灵机的计算装置：一条两端可无限延长的带子，一个读写头，一组控制指令。的带子，一个读写头，一组控制指令。b b 1 0 1 0 0 0 1 0 b b 状态状态q1读写头读写头控制指令控制指令读写头可以沿带子读写头可以沿带子方向左右移动，并方向左右移动，并可以在每个方格上可以在每个方格上进行读写。进行读写。2.3 计算模型29第29页，此课件共48页哦 带子

38、上的符号为一个有穷字母表：带子上的符号为一个有穷字母表：SS0 0,S,S1 1,S,S2 2,S,Sp p 通常仅有通常仅有S S0 0、S S1 1两个字符，其中：两个字符，其中：S S0 000，S S1 111 这可加深对布尔值、二进制机器的理解。这可加深对布尔值、二进制机器的理解。机器的控制状态：机器的控制状态：q q1 1,q,q2 2,q,qn n 图灵机的初始状态设为图灵机的初始状态设为q q1 1,结束状态设为结束状态设为q qn n2.3 计算模型30第30页，此课件共48页哦 五元组指令集合：五元组指令集合：(q(qi iS Sj jS Sk kR(LN)qR(LN)qn

39、 n)q qi i-机器目前所处的状态机器目前所处的状态 S Sj j-机器从方格中读入的符号机器从方格中读入的符号 S Sk k-机器用来代替机器用来代替S Sj j写入方格的符号写入方格的符号 R,L,N-R,L,N-右移一格右移一格,左移一格左移一格,不移动不移动 q qn n-下一步机器的状态下一步机器的状态 一个给定机器的程序是机器内的五元组一个给定机器的程序是机器内的五元组形式的指令集，它定义了机器在特定状态下形式的指令集，它定义了机器在特定状态下读入一个特定字符时所采取的动作。读入一个特定字符时所采取的动作。2.3 计算模型31第31页，此课件共48页哦 2.2.工作原理工作原理

40、 机器从给定带子上的某起点出发，其动作完机器从给定带子上的某起点出发，其动作完全由其初始状态值及机内五元组指令集来决定。全由其初始状态值及机内五元组指令集来决定。计算结果是从机器停止时带子上的信息得到。计算结果是从机器停止时带子上的信息得到。指令死循环：指令死循环：q q1 1S S2 2S S2 2RqRq3 3 q q3 3S S3 3S S3 3LqLq1 1 指令二义性：指令二义性：q q3 3S S2 2S S2 2RqRq4 4 q q3 3S S2 2S S4 4LqLq6 6 2.3 计算模型32第32页，此课件共48页哦 3.3.应用实例应用实例 例例 假设：假设：b b表示

41、空格表示空格 q q1 1表示机器的初始状态表示机器的初始状态 q q4 4表示机器的结束状态表示机器的结束状态 如果带子上的输入信息为如果带子上的输入信息为1010001010100010，读写头，读写头位对准最右边第一个为位对准最右边第一个为0 0的方格，且状态为的方格，且状态为q q1 1。按照以下五元组指令集执行后，输出正确的按照以下五元组指令集执行后，输出正确的计算结果是什么？计算结果是什么？2.3 计算模型33第33页，此课件共48页哦指令集指令集q q1 101Lq01Lq2 2q q1 110Lq10Lq3 3q q1 1bbNqbbNq4 4q q2 200Lq00Lq2 2

42、q q2 211Lq11Lq2 2q q2 2bbNqbbNq4 4q q3 301Lq01Lq2 2q q3 310Lq10Lq3 3q q3 3bbNqbbNq4 4计算函数是：计算函数是：S(S(x)=)=x+1+1b b 1 0 1 0 0 0 1 0 b bq q1b b 1 1 0 0 0 1 0 1 b bq q11q q21q q20q q20q q20q q21q q20q q21q q2bq q42.3 计算模型34第34页，此课件共48页哦 例例 图灵机图灵机MzMz：其中：其中Q=qQ=q1 1,q,q2 2,q,qf f 五元组指令集为：五元组指令集为：q q1 11

43、0Rq10Rq1 1 q q1 100Lq00Lq2 2 q q2 201Nq01Nqf f 求求MzMz对任何一串对任何一串“1 1”的作用是什么？的作用是什么？b b 1 1 1 1 1 1 0 0 b bq q1仅留下最后一个仅留下最后一个“1 1”2.3 计算模型35第35页，此课件共48页哦 图灵机图灵机：S(x)=)=x+1+1 后继函数后继函数 N(x)=0 )=0 零函数零函数 Ui(n)=xi 投影函数投影函数 任何原始递归函数都是从这任何原始递归函数都是从这3 3个初始递归函个初始递归函数经有限次的复合、递归和极小化操作得到。数经有限次的复合、递归和极小化操作得到。2.3

44、计算模型 非确定性图灵机与确定性图灵机的区别是：在给非确定性图灵机与确定性图灵机的区别是：在给定状态和输入时，其行为将不是唯一确定的。也就是定状态和输入时，其行为将不是唯一确定的。也就是说，对应同一个状态和输入，非确定性图灵机可以有说，对应同一个状态和输入，非确定性图灵机可以有多种行为来选择。多种行为来选择。36第36页，此课件共48页哦二、冯二、冯诺依曼机诺依曼机 重要思想重要思想：存储程序、二进制：存储程序、二进制存储器存储器输入设备输入设备输出设备输出设备运算器运算器控制器控制器结果结果程序或数据程序或数据数据传送线数据传送线控制信号线控制信号线1.1.冯冯诺依曼机模型诺依曼机模型2.3

45、 计算模型37第37页，此课件共48页哦 运算器运算器：对数据进行加工处理的部件。：对数据进行加工处理的部件。在控制器的操纵下，它与内存交换数据，负在控制器的操纵下，它与内存交换数据，负责算术运算、逻辑运算和移位运算等。责算术运算、逻辑运算和移位运算等。运算器控制器中央处理单元运算器控制器中央处理单元(CPU)(CPU)控制器控制器：负责对指令进行分析和判断，发出控：负责对指令进行分析和判断，发出控制信号，使计算机各部件协调工作，确保系统的自制信号，使计算机各部件协调工作，确保系统的自动运行。动运行。2.3 计算模型38第38页，此课件共48页哦 存储器存储器：存放大量程序和数据的部件，其：存

46、放大量程序和数据的部件，其 分类是内存储器和外存储器。分类是内存储器和外存储器。输入设备输入设备：用来接受用户输入的原始数据：用来接受用户输入的原始数据和程序，并将它们转变为计算机能够识别的形和程序，并将它们转变为计算机能够识别的形式存放在内存中，如键盘、鼠标、扫描仪等。式存放在内存中，如键盘、鼠标、扫描仪等。输出设备输出设备：将计算机处理的信息以人们所：将计算机处理的信息以人们所能接受的形式表示出来，如显示器、打印机等能接受的形式表示出来，如显示器、打印机等运算器控制器内存储器运算器控制器内存储器主机主机输入设备、输出设备、外存储器输入设备、输出设备、外存储器外部设备外部设备 2.3 计算模

47、型39第39页，此课件共48页哦 2.2.冯冯诺依曼机工作原理诺依曼机工作原理 先将程序先将程序(一组指令一组指令)和数据存入计算机，启和数据存入计算机，启动程序就能按照程序指定的逻辑顺序把指令读取动程序就能按照程序指定的逻辑顺序把指令读取并逐条执行，自动完成指令规定的操作。并逐条执行，自动完成指令规定的操作。2.3 计算模型40第40页，此课件共48页哦 3.3.冯冯诺依曼机的特点诺依曼机的特点 机器以运算器为中心，输入、输出设备与机器以运算器为中心，输入、输出设备与存储器之间的数据传送都要经过运算器。存储器之间的数据传送都要经过运算器。采用存储程序原理。采用存储程序原理。指令是由操作码和地

48、址码组成。指令是由操作码和地址码组成。数据以二进制表示，并采用二进制运算。数据以二进制表示，并采用二进制运算。硬件与软件完全分开，硬件在结构和功能硬件与软件完全分开，硬件在结构和功能上是不变的，完全靠编制软件来适应用户需要。上是不变的，完全靠编制软件来适应用户需要。2.3 计算模型41第41页，此课件共48页哦 4.4.冯冯诺依曼机结构的局限性诺依曼机结构的局限性 冯冯诺依曼瓶颈诺依曼瓶颈：存储器与中央处理单元之：存储器与中央处理单元之间的通路太狭窄，每次执行一条指令，所需的指间的通路太狭窄，每次执行一条指令，所需的指令和数据都必须经过这条通路。令和数据都必须经过这条通路。2.3 计算模型 从

49、本质上讲，冯从本质上讲，冯诺依曼机是采取串行顺序处诺依曼机是采取串行顺序处理的工作机制，即使有关数据已经准备好，也必须理的工作机制，即使有关数据已经准备好，也必须逐条执行指令序列，而提高计算机性能的根本方向逐条执行指令序列，而提高计算机性能的根本方向之一是并行处理。之一是并行处理。42第42页，此课件共48页哦三、量子计算机三、量子计算机2.3 计算模型 量子计算机量子计算机：一类遵循量子力学规律进行高速数学和逻辑运：一类遵循量子力学规律进行高速数学和逻辑运算、存储及处理量子信息的物理装置。量子计算机处理和计算的算、存储及处理量子信息的物理装置。量子计算机处理和计算的是量子信息，运行的是量子算

50、法。是量子信息，运行的是量子算法。由于量子态具有相干叠加性质，特别是量子纠缠特性，使得由于量子态具有相干叠加性质，特别是量子纠缠特性，使得量子计算机具有天然的量子计算机具有天然的大规模并行计算大规模并行计算的能力，其并行规模随芯的能力，其并行规模随芯片上集成量子位数目指数增加。片上集成量子位数目指数增加。承载承载1616个个量子位的量子位的硅芯片硅芯片43第43页，此课件共48页哦 基本原理基本原理：量子计算机以量子态为记忆单元、：量子计算机以量子态为记忆单元、开关电路和信息存储形式，以量子动力学演化为开关电路和信息存储形式，以量子动力学演化为信息传递与量子通信，其硬件的各种元件的尺寸信息传递