第二章计算理论与计算模型.pptx

第二章计算理论与计算模型圆周率:10万亿位2.1 计算的几种视角2.1.1 计数与计算 手指、石头、结绳计数，算筹计算科学计算的过程：实际问题数学模型计算方法计算结果程序设计2.1 计算的几种视角 许多计算领域的求解问题，如计算物理学、计算力学、计算化学和计算经济学等都可以归结为数值计算问题，而数值计算方法是一门与计算机应用紧密结合的、实用性很强的数学课程。 如对气象资料的汇总、加工并生成天气图像，其计算量大且时限性强，要求计算机能够进行高速运算，以便对天气做出短期或中期的预报。 2.1 计算的几种视角2.1.2 逻辑与计算 逻辑学有三大源泉：①以亚里士多德的词项逻辑和斯多亚学派的命题逻辑为代表的古希腊逻辑。 ②以先秦名辩学为代表的古中国逻辑。 ③以正理论和因明学为代表的古印度逻辑。 逻辑是研究推理的学科，人们可以把推理看成是对符号的操作，即符号演算。 利用数学方法来研究推理的规律称为数理逻辑。为什么要研究数理逻辑呢？我们知道要使用计算机，就要有程序。 程序＝算法＋数据结构，而算法＝逻辑＋控制 算法无处不在，每个人每天都在使用不同的算法来活出自己的人生。比如你去食堂买饭会选择一个较短的队列，而有人则可能选择一个推进速度更快的队列。2.1 计算的几种视角2.1.3 算法与计算从不同角度看，算法的定义有多种：从哲学角度看：算法是解决一个问题的抽象行为序列。从抽象层次看：算法是一个将输入转化为输出的计算步骤序列从技术层面看：算法是接收输入并产生输出的计算过程。 简而言之，算法就是计算的办法或法则。2.1 计算的几种视角 算法：为解决一个特定的问题所采取确定的有限步骤。 计算机用于解决数值计算，如科学计算中的数值积分、解线性方程等计算方法，就是数值计算的算法。 计算机用于解决非数值计算，如用于管理、文字处理、图像图形等的排序、分类和查找，就是非数值计算的算法。 算法的组成：操作、数据。 这些操作包括加、减、乘、除和判断等，并按顺序、分支、循环等控制结构所规定的次序执行。 数据是指操作对象和操作结果，包括布尔值、字符、整数和实数等；以及向量、记录、集合、树和图以及声音等。 为什么学习算法：①算法是计算机的灵魂；②算法是数学机械化的一部分，能够帮助我们解决复杂的计算问题；③算法作为一种思想，能锻炼我们的思维，使思维变得更清晰、更有逻辑。2.2 计算理论 计算理论：关于计算和计算机械的数学理论，它研究计算的过程与功效。 计算理论主要包括算法、算法学、计算复杂性理论、可计算性理论、自动机理论和形式语言理论等等。2.2 计算理论2.2.1 计算与问题求解 计算是依据一定的法则对有关符号串的变换过程。抽象地说，计算的本质就是递归。 直观描述：计算是从已知符号开始，一步一步地改变符号串，经过有限步骤，最终得到一个满足预定条件的符号串的过程。这样一种有限的符号串变换过程与递归过程是等价的。 问题求解：虽然某一问题可能找到不同的算法或方法，但是否可以计算取决于算法的存在性和计算的复杂性，也就是说，取决于是否存在可求解的算法。2.2 计算理论 计算思维的三大任务：问题求解、系统设计、人类行为的理解。2.2 计算理论2.2.2 可计算性理论可计算性理论：研究计算的一般性质的数学理论。可计算理论的中心课题：将算法这一直观概念精确化，建立计算的数学模型，研究哪些是可计算的，哪些是不可计算的，以此揭示计算的实质。由于计算与算法联系在一起，因此，可计算性理论又称算法理论。19361943193519361951图灵和波斯特各自提出抽象计算机模型邱奇提出λ转换演算哥德尔等定义递归函数Mapkob定义正规算法2.2 计算理论 1.可计算理论的发展 可计算理论起源于对数学基础问题的研究。从20世纪30年代开始，为了讨论所有问题是否都有求解的算法，数学家和逻辑学家从不同角度提出了几种不同的算法概念精确化定义。 陆续证明，上述这些不同计算模型(算法精确化定义模式)的计算能力都是一样的，即它们是等价的。 2.2 计算理论 2.可计算性的定义和特性 可计算性的定义应算是一个哲学定义。如果存在一个机械的过程，对给定的一个输入，能在有限步内给出答案，那么这个问题是可计算性的。定义：凡可用某种程序设计语言描述的问题都是可计算性问题。特性：确定性、有限性、机械性、可执行性、终止性。2.2 计算理论 2.可计算性的定义和特性 图灵给出的可计算性定义：能够在图灵机上执行的过程（通常又称算法的过程）。图灵之所以能取得成功，是他采用了算法思维来研究计算的过程，从而揭示可计算性的概念。算法思维与目前在计算机上运行的程序之间有着密切的关系，从而使他的理论受到重视并被广泛使用。 2.2 计算理论3、可计算性理论的主要内容图灵机：用于精确描述算法的特征。可以用图灵机来计算其值的函数是可计算函数，