计算引论1 绪论.ppt

1、计 算 引 论,第一章 绪 论,本课程的主要内容结构,绪论 计算模型 RAM机器 RASP机器 Lambda演算 文法与语言 集合关系与语言 有限自动机 上下文无关文法 推理与计算,第一章 绪论,计算与计算模型 计算能力与计算效率 计算理论的地位 相关参考书目,1.1 计算与计算模型,计算： 广义地说，计算是信息处理的科学名词。 狭义地说，计算是指算术、代数和微积分等。 科学定义：计算是指建立模型、进行模 拟、实验、验证等。,1.1 计算与计算模型,计算的图灵定义： 1936年由Turing给出，定义计算为： 输入执行过程（有限步内结束）输出 1946年，冯诺依曼与宾夕法尼亚大学的工程师采用电

2、子器件物理实现了图灵的计算模型，建成了世界的第一台计算机。 现在称计算机的体系结构为冯诺依曼体系结构。,1.1 计算与计算模型,上世纪初，德国大数学家希尔伯特(Hilbert)提出： 是否存在着一个通用过程，这个过程能用来判定任意数学命题是否成立，即，输入一个数学命题，在有限时间内，得到一个证明，如果这个命题成立；或是一个反例，如果这个命题不成立。 图灵证明了对于平面几何来说，存在这样的过程。但是，对于一般的数学命题，不存在这样的过程。,1.1 计算与计算模型,实际计算中，有时间需求、空间需求。计算要满足一定的需求，否则为理论上可行，但实际上不可行的计算。 1971年，Cook和Karp提供了

3、实际可行的计算的标准，即多项式时间算法标准。,1.1 计算与计算模型,算法设计，设计一个过程。 算法分析，对设计的过程进行时间和空间需求分析。,1.1 计算与计算模型,图灵给出了过程的科学定义（即算法），区分了可计算的问题和不可计算的问题。 不可计算的问题比可计算的问题要多得多，但很难给出不可计算问题的例子。,1.1 计算与计算模型,Cook-Karp给出了实际可计算的算法标准，区分了实际可计算的问题和实际不可计算的问题。 实际可计算问题称为多项式时间可计算，实际不可计算的问题称为指数时间可计算（因为Cook-Karp研究的对象都是可计算问题）。,1.1 计算与计算模型,Church论题：任意

4、一个算法都可以用一台图灵机来执行。 Cook-Karp论题：一个算法实际可行当且仅当它是多项式时间可计算的。,1.1 计算与计算模型,计算模型的两个需求: 可以形式化地表示算法(用符号串表示算法)； 可以机械地执行算法。,1.1 计算与计算模型,图灵关于计算装置设计思想要点 一套符号体系来表示信息，包括基本符号表（Alphabet） 证明最小的基本符号集有二个基本符号，即，用0和1可表示任意符号串（信息串） 读写介质，可以抽象成为一维的线性数据带,1.1 计算与计算模型,图灵关于计算装置设计思想要点(续) 读写头，阅读介质上的信息 输入和输出 信息处理状态，用状态转移来表示过程的不同步骤 状态转移有一定的规则 实施的算法是一个状态的转移序列,1.2 计算能力与计算效率,一个计算模型的计算能力是用它可计算的问题类的大小来刻画的。 目前人类尚无找到其它的计算模型，其可计算的问题类超过图灵机的计算能力。 算法的计算效率用算法的时间需求（或空间需求）来刻画。空间需求可以转化成时间需求。,1.3 计算理论的地位,参 考 书 目,The Design and Analysis of Computer Algorithms, Aho, Hopcroft and Ullman 计算机和难