计算机基础知识-第2章PPT课件

《计算机基础知识-第2章PPT课件》由会员分享，可在线阅读，更多相关《计算机基础知识-第2章PPT课件（62页珍藏版）》请在金锄头文库上搜索。

1、计算机导论计算机导论第第2 2章章 图灵机模型及数据编码图灵机模型及数据编码2.1 2.1 概述概述图灵机模型理论是计算机学科最核心的理论之一，它是在总结前人制造计算机思想的基础上提出的理论计算模型，它不仅指导了现代电子计算机的设计，为计算机设计指明了方向，并且是算法分析和程序语言设计的基础理论。尽管如此，图灵机模型却并不复杂，也许正因为如此，才注定了其在计算学科中所具有的强大生命力。掌握了图灵机理论，等于获得了学习计算机系统知识的“金钥匙”。计算机导论计算机导论第第2 2章章 图灵机模型及数据编码图灵机模型及数据编码2.2 2.2 图灵机图灵机 在第一台电子计算机ENIAC诞生的10年前即1

2、936年，英国数学家图灵发表了题为“论可计算数及其在判定问题中的应用” OnComputerNumbersWithanApplicationtothentscheidungsproblem 的学术论文，奠定了学术界公认的现代电子计算机的理论和模型基础。1、希尔伯特纲领20世纪初，逐步形成了关于数学基础研究的逻辑主义、直觉主义和形式主义三大流派。其中，形式主义流派的代表人物是数学家希尔伯特。计算机导论计算机导论第第2 2章章 图灵机模型及数据编码图灵机模型及数据编码他在数学基础的研究中提出了一个设想，其大意是：将每一门数学的分支形式化，构成形式系统或形式理论，并在以此为对象的元理论即元数学中，证

3、明每一个形式系统的相容性，从而导出全部数学的相容性，希尔伯特的这一设想，就是所谓的“西尔伯特纲领”。“西尔伯特纲领”的目标，其实质就是要寻找通用的形式逻辑系统，该系统应当是完备的，即在该系统中，可以机械地判定任何给定命题的真伪。计算机导论计算机导论第第2 2章章 图灵机模型及数据编码图灵机模型及数据编码“西尔伯特纲领”的研究基础是逻辑和代数，主要源于19世纪英国数学家乔治布尔所创立的逻辑代数体系 即布尔代数 。1854年，布尔在他的著作中成功地将“真” 、“假”两种逻辑值和“与”、“或”、“非”3种逻辑运算归结为一种代数。这样，形式逻辑系统中的任何命题都可用数学符号表示出来，并能按照一定的规则

4、推导出结论。尽管布尔没有将“布尔代数”与计算机联系起来，但他的工作却为现代计算机的诞生作了重要的理论准备。希尔伯特的工作建计算机导论计算机导论第第2 2章章 图灵机模型及数据编码图灵机模型及数据编码立在布尔工作的基础上，并使其进一步具体化。希尔伯特对实现自己的纲领充满信心。然而，1931年，奥地利25岁的数理逻辑学家哥德尔提出的关于形式系统的“不完备性定理”中指出，这种形式系统是不存在的，从而宣告了著名的“西尔伯特纲领”的失败。希尔伯特纲领的失败同时也暴露了形式系统的局限性，它表明形式系统不能穷尽全部数学命题，任何形式系统中都存在着该系统所不能判定其真伪的命题。计算机导论计算机导论第第2 2章

5、章 图灵机模型及数据编码图灵机模型及数据编码 “西尔伯特纲领”虽然失败了，但它仍然不失为人类抽象思维的一个伟大成果，它的历史意义是多方面的。首先，“西尔伯特纲领”是在保全古典数学的前提下去排除集合论悖论的，它给数学基础问题的研究带来了全新的转机。其次，希尔伯特纲领的提出使元数学得到了确立和发展。最后，对计算学科而言，最具意义的是，希尔伯特纲领的失败启发人们应避免花费大量的精力去证明那些不能判定的问题，而应把精力集中于解决具有能行性的问题。计算机导论计算机导论第第2 2章章 图灵机模型及数据编码图灵机模型及数据编码DHilbert 希尔伯特 GBoole乔治布尔Kurt Gdel库尔特哥德尔计算

6、机导论计算机导论第第2 2章章 图灵机模型及数据编码图灵机模型及数据编码2、图灵对计算本质的揭示 在哥德尔研究成果的影响下20世纪30年代后期，图灵AMTuring从计算一个数的一般过程入手对计算的本质进行了研究，从而实现了对计算本质的真正认识。 根据图灵的研究，直观地说，所谓计算就是计算者人或机器对一条两端可无限延长的纸带上的一串0和1执行指令，一步一步地改变纸带上的0或1，经过有限步骤，最后得到一个满足预先规定的符号串的变换过程。图灵用形式化方法成功表述可计计算机导论计算机导论第第2 2章章 图灵机模型及数据编码图灵机模型及数据编码算这一过程的本质。图灵的研究成果是哥德尔研究成果的进一步深

7、化，该成果不仅再次表明了某些数学问题是不能用任何机械过程来解决的思想，而且还深刻揭示可计算所具有的“能行过程”的本质特征。 图灵的描述是关于数值计算的，不过，我们知道英文字母表的字母以及汉字均可以用数来表示，因此，图灵机同样可以处理非数值计算。不仅如此，更为重要的是，由数值和非数值英文字母、汉字等组成的字符串，既可以解释成计算机导论计算机导论第第2 2章章 图灵机模型及数据编码图灵机模型及数据编码数据，又可以解释成程序，从而计算的每一过程都可以用字符串的形式进行编码，并存放在存储器中，以后使用时译码，并由处理器执行，机器码结果可以从高级符号形式即程序设计语言机械地推导出来。 图灵的研究成果是：

8、可计算性图灵可计算性。在进行可计算性问题的讨论时，不可避免地要提到一个与计算具有同等地位和意义的基本概念，那就是算法。算法也称为能行方法或能行过程，是对解题计算过程的精确描述，它由一组定义明确且计算机导论计算机导论第第2 2章章 图灵机模型及数据编码图灵机模型及数据编码能机械执行的规则语句、指令等组成。 根据图灵的论点，可以得到这样的结论：任一过程是能行的能够具体表现在一个算法中，当且仅当它能够被一台图灵机实现。 图灵机等计算模型均是用来解决问题的，理论上的能行性隐含着计算模型的正确性，而实际实现中的能行性还包含时间与空间的有效性。计算机导论计算机导论第第2 2章章 图灵机模型及数据编码图灵机

9、模型及数据编码3、图灵机 为纪念图灵对计算机的贡献，美国计算机博物馆于1966年设立了“图灵奖”计算机是使用相应的程序来完成任何设定好的任务。图灵机是一种思想模型，它由三部分组成：一个控制器，一条可以无限延伸的带子和一个在带子上左右移动的读写头。计算机导论计算机导论第第2 2章章 图灵机模型及数据编码图灵机模型及数据编码 根据图灵的观点可以得到这样的结论：凡是能用算法方法解决的问题，也一定能用图灵机解决；凡是图灵机解决不了的问题，任何算法也解决不了。今天我们知道，图灵机与当时提出的用于解决计算问题的递归函数、演算和POST规范系统等计算模型在计算能力上是等价的。它们于20世纪30年代共同奠定了

10、计算科学的理论基础。相比于其他几种计算模型，图灵机是从过程这一角度来刻画计算的本质，其结构简单，操作运行规则也较少，从而为更多的人所理解。图灵机的特征 图灵机由一条两端可无限延长的带子、一个读写头以及一组控制读写头工作的命令组成，如图所示。图灵机计算机导论计算机导论第第2 2章章 图灵机模型及数据编码图灵机模型及数据编码的带子被划分为一系列均匀的方格。读写头可以沿带子方向左右移动，并可以在每个方格上进行读写。写在带子上的符号为一个有穷字母表：S0,S1,S2,SP。通常，可以认为这个有穷字母表仅有两个S0、S1字符，其中S0可以看作是“0”，S1可以看作是“1”，它们只是两个符号，要说有意义的

11、话，也只有形式的意义。 bb10100010bbb 状态q1读写头控制器计算机导论计算机导论第第2 2章章 图灵机模型及数据编码图灵机模型及数据编码由字符“0”和“1”组成的字母表可以表示任何一个数。机器的控制状态表为q1,q2,qn,。通常，将一个图灵机的初始状态设为q1，在每一个具体的图灵机中还要确定一个结束状态qw。一个给定机器的“程序”认为是机器内的五元组 qiSjSkR 或L或Nql形式的指令集，五元组定义了机器在一个特定状态下读入一个特定字符时所采取的动作。5个元素的含义如下：qi表示机器目前所处的状态；Sj表示机器从方格中读入的符号；Sk表示机器用来代替写入方格中的符号；R、L、

12、N分别表示向右移一格、向左移一格、不移动；ql表示下一步机器的状态。计算机导论计算机导论第第2 2章章 图灵机模型及数据编码图灵机模型及数据编码计算机导论计算机导论第第2 2章章 图灵机模型及数据编码图灵机模型及数据编码图灵机的工作原理 图灵机执行一步工作的过程可以归纳为3个步骤：第一，读写磁头在扫描的磁带存储单元上写上符号，原有符号被覆盖而消失；第二，磁头向右或向左移动一个存储单元位置，由当前状态转向另一状态，进入下一步工作。如此反复重复第二个过程，直至遇到命令图灵机停止工作的状态。 在上图中，图灵机正处于q4 状态，假设它将A改写为E，左移一个单元位置，进入q3 状态。 计算机导论计算机导

13、论第第2 2章章 图灵机模型及数据编码图灵机模型及数据编码 图灵机下一步的工作将由q3和符号T决定。图灵机这种由状态和符号确定的工作过程叫做图灵机的程序，可以用5元组来确定，即qiSjSkR或L或N ql 。其中qi为有限状态控制器中的当前状态，ql为下一状态，Sj为当前存储单元符号，Sk为修改后的存储单元符号，R或L或N为磁头移动方向。按照这种描述方法，上述图灵机的一步动作描述可以表示为（q4、A、E、L、q3）。 图灵机的功能是完成对输入信息进行变换得到输出信息的计算。 计算机导论计算机导论第第2 2章章 图灵机模型及数据编码图灵机模型及数据编码 机器从给定带子上的某起始点出发，其动作完全

14、由其初始状态及机内五元组来决定。就某种意义而言，一个机器其实就是它作用于纸带上的五元组集。一个机器计算的结果是从机器停止时带子上的信息得到的。4、冯诺依曼型计算机 1946年2月14日，世界上第一台数字电子计算机ENIAC在美国宾夕法尼亚大学研制成功。该机是使用电子线路来执行算术和逻辑运算以及信息存储计算机导论计算机导论第第2 2章章 图灵机模型及数据编码图灵机模型及数据编码的真正工作的计算机器，它的成功研制显示了电子线路的巨大优越性。但是，ENIAC的结构在很大程度上是依照机电系统设计的，还存在重大的线路结构等问题。在图灵等人工作的影响下，1946年6月，美国杰出的数学家冯诺依曼及其同事完成

15、了关于电子计算装置逻辑结构设计的研究报告，具体介绍了制造电子计算机和程序设计的新思想，给出了由控制器、运算器、存储器、输入和输出设备5类部件组成的，被称为冯诺依曼型计算机 或存储程序式计算机 的组织结构，以计算机导论计算机导论第第2 2章章 图灵机模型及数据编码图灵机模型及数据编码及实现它们的方法，为现代计算机的研制奠定了基础，至尽为止，大多数计算机采用的仍然是冯诺依曼型计算机的组织结构，只是作了一些改进而已。因此，冯诺依曼被人们誉为“计算机器之父”。John von Neumann冯诺依曼计算机导论计算机导论第第2 2章章 图灵机模型及数据编码图灵机模型及数据编码数据信号控制信号注：冯冯 诺

16、依曼型计算机的组织结构诺依曼型计算机的组织结构运算器控制器内存储器输入设备输出设备外存储器CPU计算机导论计算机导论第第2 2章章 图灵机模型及数据编码图灵机模型及数据编码2.3 2.3 数据在计算机中的表示数据在计算机中的表示 计算机中的数据和指令都是用二进制代码表示的，这是因为计算机的各组成部分是仅具有两个稳定状态的物理元件电子开关线路所组成。为此，要想深入学习计算机的各个部分，必须掌握二进制代码的有关知识。计算机中用二进制代码表示数据信息有两种方法：按“值”表示：在选定的进位制中正确地表示出数值，包括数字、符号、小数点位置及正负号等。如“9.5”可表示为二进制的“1001.1”。按“形”表示：按照一定的编码方法来表示数据。如用ASCII码表示“9.5”，其形式为0101101、0111001、0101100、0110101。计算机导论计算机导论第第2 2章章 图灵机模型及数据编码图灵机模型及数据编码1、进位制数及其相互转化 (一)进位制数（进位计数制）数制的定义：用一组固定的数字(数码符号)和一套统一的规则来表示数值的方法就叫做数制(numbersystem也称计数制)。这一定义