计算理论与计算模型ppt课件.ppt

《计算理论与计算模型ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、计算思维与计算机文化第二章计算理论与计算模型计算理论与计算模型主要内容2.1计算的几种视角2.2计算理论2.3计算模型计算机能够解决所有的问题吗？计算机能够解决什么样的问题？什么问题是可计算的？如何判定一个问题是可计算的？2.1计算的几种视角计数与计算中国古代计算工具：最初的计算工具——手指digit——手指，整数易得的计数工具——石头、木棍、绳结calculus——计算，微积分，结石公园前四世纪战国时期，《周易·系辞下》上古结绳而治，后世圣人易之以书契5算筹：中国古代普遍采用的一种计算工具。不仅可以计数，还可以进行加、减、乘、除等算数运算。出土的西汉时

2、期的算筹6算筹的摆放有两种方式，横式和纵式。竖横1500年前的《孙子算经》“凡算之法，先识其位，一纵十横，百立千僵，千十相望，万百相当。”即横式和纵式要间隔排放。7比如计算3748+289从左向右算=40378比如计算4231-789从左向右算=3442南北朝时期的数学家祖冲之借助算筹，将圆周率的值计算到小数点后第7位。之后国际上又进行了许多有效的计算，人工计算达到了808位。1949年美国科学家，利用ENIAC将计算到2037位。10算筹存在着纵横记数、占用地方面积大、运筹的数字较大容易出现失误等缺点。唐朝后，另一种计算工具走上了历史舞台，这就是算盘。

3、算盘用带孔的珠子代替了竹棍，有档位限制，不易乱，又有计算口诀，学的快，准确性高，所以很快就普及了。2.逻辑与计算逻辑是研究推理的学科，研究形式体系，作为其组成部分的命题演算和谓词演算等在计算机学科中作用巨大，影响很深。推理与计算是相通的，数理逻辑的许多研究成果都可以用于计算科学，数理逻辑给出的思维过程可以通过计算机来实现。3.算法与计算问题求解是计算，求解算法的每一步也是计算，计算的过程是算法，算法又由计算步骤组成。算法是计算机科学中最重要的内容，计算机科学就是算法科学。2.2计算理论1.可计算性理论（ComputabilityTheory）可计算理论是

4、研究计算的可行性和算法的理论，又称算法理论。（1）可计算理论的发展“计算”是解决问题的最基本手段，计算的过程就是执行算法的过程。随着计算机科学与技术的发展，“计算”的内涵与外延均发生了巨大的变化，涉及到了社会发展的各个领域。“计算”离不开计算的规则与方法（算法），正确的计算规则建立与可行的计算方法设计是正确地解决问题的关键所在。可计算性理论的研究分为两个方面：通过建立计算的数学模型，研究哪些算法问题是可计算的（可行的），哪些算法问题是不可计算的（不可行的）。另一主要内容就是计算复杂性理论，研究一个问题怎样才能被有效的解决（算法的复杂度）。在20世纪以前，

5、人们普遍认为，所有的问题都是有算法的，人们关于计算问题的研究就是找出解决各类问题的算法来。随着时间的迁移，人们发现有许多问题虽然经过长期的研究仍然找不到算法，于是人们开始怀疑，是否对有些问题来说根本就不存在算法，即它们是不可计算的。那么什么是可计算，什么又是不可计算的呢？（2）可计算性定义如果存在一个机械过程，对给定的一个输入，能在有限步骤内给出答案，那么这个问题就是可计算性的。计算机科学的定义：凡可用某种程序设计语言描述的问题都是可计算性的。图灵通过精确地描述给出了“可计算性”的形式定义，他提出一类直观而合理的抽象机，就是图灵机。（3）计算性理论的主要

6、内容到了20世纪30年代，一些著名的数学家和逻辑学家从不同的角度分别给出了“可计算性”概念的确切定义，为计算科学的研究与发展奠定了重要基础。其中包括丘奇的λ-转换演算，哥德尔的一般递归性概念，图灵（Turing）的可计算性概念等。经证明，这些形式上完全不同的概念都是等价的，而其中图灵提出来的“图灵机”模型直观形象，于是很快得到了大家的普遍接受。图灵机图灵机是一种在理论计算机科学中广泛采用的抽象计算机，由阿兰.图灵1936年提出的。核心：可用一个图灵机来计算其值的函数是可计算函数，找不到图灵机来计算其值的函数是不可计算函数。可以证明，存在一个图灵机U，它可

7、以模拟任何其他的图灵机.这就是通用图灵机，这正是后来存储程序的通用数字计算机的理论模型。正是因为图灵奠定的理论基础，人们才有可能发明20世纪以来甚至是人类有史以来最伟大的发明：计算机。1912年出生，演算能力突出1931年，进剑桥大学学数学1936年，提出图灵机模型1938年，获普灵斯顿大学博士学位1939年，英国外交部通信处1950年，发表论文“计算机和智能”，提出图灵测试1951年，成为英皇家学会院士1954年，不幸去世图灵机有以下四个部分组成：无限长的纸带可移动的读写头状态存储器(开始结束)规则表（程序）图灵用机器来模拟人用纸笔进行数学运算的过程，

8、两种简单的动作：在纸上写上或擦除某个符号；把注意力从纸的一个位置移动到另一个位置