《计算机导论》PPT课件.ppt
《《计算机导论》PPT课件.ppt》由会员分享,可在线阅读,更多相关《《计算机导论》PPT课件.ppt(58页珍藏版)》请在三一办公上搜索。
1、内容提要,2.1 概,2.3 数据在计算机中的表示,2.2 图灵机,在第一台电子计算机ENIAC诞生的10年前即1936年,英国数学家图灵发表了题为“论可计算数及其在判定问题中的应用”On Computer Numbers With an Application to the Entscheidungs Problem的学术论文,奠定了学术界公认的现代电子计算机的理论和模型基础。1、希尔伯特纲领 20世纪初,逐步形成了关于数学基础研究的逻辑主义、直觉主义和形式主义三大流派。其中,形式主义流派的代表人物是数学家希尔伯特DHilbert。他在数学基础的研究中提出了一个设想,其大意是:将每一门数学的
2、分支形式化,构成形式系统或形式理论,并在以此为对象的元理论即,元数学中,证明每一个形式系统的相容性,从而导出全部数学的相容性,希尔伯特的这一设想,就是所谓的“西尔伯特纲领”。“西尔伯特纲领”的目标,其实质就是要寻找通用的形式逻辑系统,该系统应当是完备的,即在该系统中,可以机械地判定任何给定命题的真伪。,DHilbert 希尔伯特,“西尔伯特纲领”的研究基础是逻辑和代数,主要源于19世纪英国数学家乔治布尔GBoole所创立的逻辑代数体系即布尔代数。1854年,布尔在他的著作中成功地将“真”、“假”两种逻辑值和“与”、“或”、“非”3种逻辑运算归结为一种代数。这样,形式逻辑系统中的任何命题都可用数
3、学符号表示出来,并能按照一定的规则推导出结论。尽管布尔没有将“布尔代数”与计算机联系起来,但他的工作却为现代计算机的诞生作了重要的理论准备。,GBoole乔治布尔,希尔伯特的工作建立在布尔工作的基础上,并使其进一步具体化。希尔伯特对实现自己的纲领充满信心。然而,1931年,奥地利25岁的数理逻辑学家哥德尔KGdel提出的关于形式系统的“不完备性定理”中指出,这种形式系统是不存在的,从而宣告了著名的“西尔伯特纲领”的失败。希尔伯特纲领的失败同时也暴露了形式系统的局限性,它表明形式系统不能穷尽全部数学命题,任何形式系统中都存在着该系统所不能判定其真伪的命题。,“西尔伯特纲领”虽然失败了,但它仍然不
4、失为人类抽象思维的一个伟大成果,它的历史意义是多方面的。首先,“西尔伯特纲领”是在保全古典数学的前提下去排除集合论悖论的,它给数学基础问题的研究带来了全新的转机。其次,希尔伯特纲领的提出使元数学得到了确立和发展。最后,对计算学科而言,最具意义的是,希尔伯特纲领的失败启发人们应避免花费大量的精力去证明那些不能判定的问题,而应把精力集中于解决具有能行性的问题。,2、图灵对计算本质的揭示 在哥德尔研究成果的影响下20世纪30年代后期,图灵AMTuring从计算一个数的一般过程入手对计算的本质进行了研究,从而实现了对计算本质的真正认识。根据图灵的研究,直观地说,所谓计算就是计算者人或机器对一条两端可无
5、限延长的纸带上的一串0和1执行指令,一步一步地改变纸带上的0或1,经过有限步骤,最后得到一个满足预先规定的符号串的变换过程。图灵用形式化方法成功表述可计算这一过程的本质。图灵的研究成果是哥德尔研究成果的进一步深化,该成果不仅再次表明了某些数学问题是不能用任何机械过程来解决的思想,而且还深刻揭示可计算所具有的“能行过程”的本质特征。,图灵的描述是关于数值计算的,不过,我们知道英文字母表的字母以及汉字均可以用数来表示,因此,图灵机同样可以处理非数值计算。不仅如此,更为重要的是,由数值和非数值英文字母、汉字等组成的字符串,既可以解释成数据,又可以解释成程序,从而计算的每一过程都可以用字符串的形式进行
6、编码,并存放在存储器中,以后使用时译码,并由处理器执行,机器码结果可以从高级符号形式即程序设计语言机械地推导出来。图灵的研究成果是:可计算性图灵可计算性。在进行可计算性问题的讨论时,不可避免地要提到一个与计算具有同等地位和意义的基本概念,那就是算法。算法也称为能行,方法或能行过程,是对解题计算过程的精确描述,它由一组定义明确且能机械执行的规则语句、指令等组成。根据图灵的论点,可以得到这样的结论:任一过程是能行的能够具体表现在一个算法中,当且仅当它能够被一台图灵机实现。图灵机等计算模型均是用来解决问题的,理论上的能行性隐含着计算模型的正确性,而实际实现中的能行性还包含时间与空间的有效性。,3、图
7、灵机,为纪念图灵对计算机的贡献,美国计算机博物馆于1966年设立了“图灵奖”,计算机是使用相应的程序来完成任何设定好的任务。,图灵机是一种思想模型,它由三部分组成:一个控制器,一条可以无限延伸的带子和一个在带子上左右移动的读写头。,根据图灵的观点可以得到这样的结论:凡是能用算法方法解决的问题,也一定能用图灵机解决;凡是图灵机解决不了的问题,任何算法也解决不了。今天我们知道,图灵机与当时提出的用于解决计算问题的递归函数、演算和POST规范系统等计算模型在计算能力上是等价的。它们于20世纪30年代共同奠定了计算科学的理论基础。相比于其他几种计算模型,图灵机是从过程这一角度来刻画计算的本质,其结构简
8、单,操作运行规则也较少,从而为更多的人所理解。图灵机的特征 图灵机由一条两端可无限延长的带子、一个读写头以及一组控制读写头工作的命令组成,如图所示。图灵机,的带子被划分为一系列均匀的方格。读写头可以沿带子方向左右移动,并可以在每个方格上进行读写。写在带子上的符号为一个有穷字母表:S0,S1,S2,SP。通常,可以认为这个有穷字母表仅有两个S0、S1字符,其中S0可以看作是“0”,S1可以看作是“1”,它们只是两个符号,要说有意义的话,也只有形式的意义。,由字符“0”和“1”组成的字母表可以表示任何一个数。机器的控制状态表为q1,q2,qm,。通常,将一个图灵机的初始状态设为q1,在每一个具体的
9、图灵机中还要确定一个结束状态qw。一个给定机器的“程序”认为是机器内的五元组qiSjSkR或L或Nql形式的指令集,五元组定义了机器在一个特定状态下读入一个特定字符时所采取的动作。5个元素的含义如下:qi 表示机器目前所处的状态;Sj 表示机器从方格中读入的符号;Sk 表示机器用来代替写入方格中的符号;R、L、N 分别表示向右移一格、向左移一格、不移动;ql 表示下一步机器的状态。,图灵机的工作原理机器从给定带子上的某起始点出发,其动作完全由其初始状态及机内五元组来决定。就某种意义而言,一个机器其实就是它作用于纸带上的五元组集。一个机器计算的结果是从机器停止时带子上的信息得到的。4、冯诺依曼型
10、计算机 1946年2月14日,世界上第一台数字电子计算机ENIAC在美国宾夕法尼亚大学研制成功。该机是使用电子线路来执行算术和逻辑运算以及信息存储的真正工作的计算机器,它的成功研制显示了电子线路的巨大优越性。但是,ENIAC的结构在很大程度上是依照机电系统设计的,还存在重大的线路结构等问题。在图灵等人工作的影响下,1946年6月,美国杰出的数学家冯诺依曼及其同事完成了关于电子计算装置逻辑结构设计的研究报告,具体,介绍了制造电子计算机和程序设计的新思想,给出了由控制器、运算器、存储器、输入和输出设备5类部件组成的,被称为冯诺依曼型计算机或存储程序式计算机的组织结构,以及实现它们的方法,为现代计算
11、机的研制奠定了基础,至尽为止,大多数计算机采用的仍然是冯诺依曼型计算机的组织结构,只是作了一些改进而已。因此,冯诺依曼被人们誉为“计算机器之父”。,冯诺依曼型计算机的组织结构,John von Neumann冯诺依曼,1949 EDSAC,存储程序工作原理计算机的两个基本能力:一是能够存储程序,二是能够自动地执行程序。计算机是利用“存储器”(内存)来存放所要执行的程序的,而称之为CPU的部件可以依次从存储器中取出程序中的每一条指令,并加以分析和执行,直至完成全部指令任务为止。,香侬是现代信息论的著名创始人。1938年,香侬在发表的论文中,首次用布尔代数进行开关电路分析,并证明布尔代数的逻辑运算
12、可以通过继电器电路来实现。阿塔纳索夫提出了计算机的三条原则:1)以二进制的逻辑基础来实现数字运算,以保证 精度;2)利用电子技术来实现控制、逻辑运算和算术运 算,以保证计算速度;3)采用把计算功能和二进制数更新存储功能相分 离的结构。,Claude Shannon,奠定现代计算机发展的重要人物和思想,2.3 数据在计算机中的表示,计算机中的数据和指令都是用二进制代码表示的,这是因为计算机的各组成部分是仅具有两个稳定状态的物理元件电子开关线路所组成。为此,要想深入学习计算机的各个部分,必须掌握二进制代码的有关知识。计算机中用二进制代码表示数据信息有两种方法:按“值”表示:在选定的进位制中正确地表
13、示出数值,包括数字、符号、小数点位置及正负号等。如“9.5”可表示为二进制的“1001.1”。按“形”表示:按照一定的编码方法来表示数据。如用ASCII码表示“9.5”,其形式为0101101、0111001、0101110、0110101。,1、进位制数及其相互转化(一)进位制数(进位计数制)数制的定义:用一组固定的数字(数码符号)和一套统一的规则来表示数值的方法就叫做数制(number system也称计数制)。这一定义主要的内涵是:(1)数制的种类很多,除了十进制数,还有二十四进制(24小时为一天),六十进制(60分为1小时,60秒为1分),二进制(鞋、袜、筷子等两只为一双),等等。(2
14、)在一种数制中,只能使用一组固定的数字来表示数的大小。数字在一个数中所处的位置称为数位。具体使用多少个数字来表示一个数值的大小,就称为该数制的基数(base)。例如,十进制数(Decimal),的基数是10,使用09十个数字,二进制数(Binary)的基数为2,使用0,1两个数字。在计算机文献中,十进制数是在数的末尾加字母D来标识。例如,1989D,表示十进制数1989。一般情况下,1989就是一个十进制数,不在后面加D。二进制数是在数的末尾加字母B来标识。例如,101B,表示二进制数的101,即十进制数的5。(3)在一种数制中,有一套统一的规则。N进制的规则是逢N进1,或者借1为N。权 或称
15、位权,是指数位上的数字乘上一个固定的数值。十制数是逢十进一,所以对每一位数可以分别赋以位权100,101,102,。用这样的位权就能够表示十进制的数。,基数 某一基数中的最大数是“基数减1”,而不是基数本身,如十进制数中的最大数为(101)9,二进制数中的最大数为(21)1;最小数均为0。数位、基数和位权是进位计数制中的三个要素。采用二进制记数法 原因目前,在计算机内部,数据的计算和处理都采用二进制记数法,主要是由二进制数在技术操作上的可行性、可靠性、简易性以及其逻辑性所决定的。(1)可行性若用十进制数,需要0,1,9等不同的10个基数,用电子技术实现这10种状态就很困难。而用二进制数,则只需
16、0,1两个基数,要表示两个状态,这在电学技术上的,实现最为容易。例如,电灯的亮和灭,晶体管的导通和截止,等等。(2)可靠性因二进制数只要两个状态,数字转移和处理就不易出错,这样计算机工作的可靠性就高。(3)简易性二进制数运算法则简单。例如,二进制的加法、积法法则都只有三个。运算法则少,使计算机运算器结构大大简化,控制也可随之简化。(4)逻辑性由于二进制数只要0,1两个数码,可以代表逻辑代数中的“假”和“真”,这就是在计算机中使用二进制的逻辑性。,具体分析二进制、十进制、八进制、十六进制的性质:十进制D 具有十个数字符号0,1,2,3,9;逢十进一;基数为10,第i位的权为10i。举例:123.
17、4510110221013100410-1 510-2表示方法:123.4510123.45D二进制B 具有两个数字符号0,1;逢二进一;基数为2,第i位的权为2i。,举例:101.101212202112012-102-2 12-3表示方法:101.1012101.101B八进制Q 具有八个数字符号0,1,2,7;逢八进一;基数为8,第i位的权为8i。举例:137.438 18238178048-1 38-2表示方法:137.438137.43Q,十六进制H 具有十六个数字符号0,1,2,9,A,B,C,D,E,F;逢十六进一;基数为16,第i位的权为16i。举例:147B.CD161163
18、41627161 B160C16-1D16-2表示方法:147B.CD16147B.CDH进位制数的相互转换 1、十进制数与二进制数间的相互转换,D B,2710?2,例1:510?2,0 1,0 1,即5101012,2710110112,例2:0.62510?2,0.625,2,1.250 1,2,0.50 0,2,1.0 1,即 0.625100.1012,例3:27.6251011011.1012,口 诀:整数部分,除2取余数,直到商为0。余数排列,由下到上;小数部分,乘2取整数,直到小数部分为0或达到所求的精确度。整数排列,由上到下。,将二进制数的各位按权展开相加。例4:1012?1
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 计算机导论 计算机 导论 PPT 课件
链接地址:https://www.31ppt.com/p-5604222.html