《计算机导论》PPT课件.ppt

内容提要,2.1 概述,2.2 图灵机,2.3 数据在计算机中的表示,2.1 概述,图灵机模型理论是计算机学科最核心的理论之 一，它是在总结前人制造计算机思想的基础上提出 的理论计算模型，它不仅指导了现代电子计算机的 设计，为计算机设计指明了方向，并且是算法分析 和程序语言设计的基础理论。尽管如此，图灵机模 型却并不复杂，也许正因为如此，才注定了其在计 算学科中所具有的强大生命力。掌握了图灵机理论， 等于获得了学习计算机系统知识的“金钥匙”。,2.2 图灵机,在第一台电子计算机ENIAC诞生的10年前即1936年，英 国数学家图灵发表了题为“论可计算数及其在判定问题中的 应用”On Computer Numbers With an Application to the Entscheidungs Problem的学术论文，奠定了学术界公认的 现代电子计算机的理论和模型基础。 1、希尔伯特纲领 20世纪初，逐步形成了关于数学基础研究的逻辑主义、 直觉主义和形式主义三大流派。其中，形式主义流派的代表 人物是数学家希尔伯特DHilbert。他在数学基础的研 究中提出了一个设想，其大意是：将每一门数学的分支形式 化，构成形式系统或形式理论，并在以此为对象的元理论即,元数学中，证明每一个形式系统的相容性，从而导出全部 数学的相容性，希尔伯特的这一设想， 就是所谓的“西尔伯特纲领”。 “西尔伯特纲领”的目标，其实质就 是要寻找通用的形式逻辑系统，该系 统应当是完备的，即在该系统中，可 以机械地判定任何给定命题的真伪。,DHilbert 希尔伯特,“西尔伯特纲领”的研究基础是逻辑和代数，主要源于19世纪 英国数学家乔治布尔GBoole所 创立的逻辑代数体系即布尔代数。 1854年，布尔在他的著作中成功地将 “真” 、“假”两种逻辑值和“与”、“或”、 “非”3种逻辑运算归结为一种代数。这 样，形式逻辑系统中的任何命题都可 用数学符号表示出来，并能按照一定 的规则推导出结论。尽管布尔没有将 “布尔代数”与计算机联系起来，但 他的工作却为现代计算机的诞生作 了重要的理论准备。,GBoole 乔治布尔,希尔伯特的工作建立在布尔工作的基础上，并使其进一步具 体化。 希尔伯特对实现自己的纲领充满信心。然而，1931年， 奥地利25岁的数理逻辑学家哥德尔KGdel提出的关 于形式系统的“不完备性定理”中指出，这种形式系统是不存 在的，从而宣告了著名的“西尔伯特纲领”的失败。希尔伯特 纲领的失败同时也暴露了形式系统的局限性，它表明形式系 统不能穷尽全部数学命题，任何形式系统中都存在着该系统 所不能判定其真伪的命题。,“西尔伯特纲领”虽然失败了，但它仍然不失为人类抽象 思维的一个伟大成果，它的历史意义是多方面的。 首先，“西尔伯特纲领”是在保全古典数学的前提下去排 除集合论悖论的，它给数学基础问题的研究带来了全新的转 机。其次，希尔伯特纲领的提出使元数学得到了确立和发展。 最后，对计算学科而言，最具意义的是，希尔伯特纲领的失 败启发人们应避免花费大量的精力去证明那些不能判定的问 题，而应把精力集中于解决具有能行性的问题。,2、图灵对计算本质的揭示 在哥德尔研究成果的影响下20世纪30年代后期，图灵 AMTuring从计算一个数的一般过程入手对计算的本 质进行了研究，从而实现了对计算本质的真正认识。 根据图灵的研究，直观地说，所谓计算就是计算者人 或机器对一条两端可无限延长的纸带上的一串0和1执行指 令，一步一步地改变纸带上的0或1，经过有限步骤，最后得 到一个满足预先规定的符号串的变换过程。图灵用形式化方 法成功表述可计算这一过程的本质。图灵的研究成果是哥德 尔研究成果的进一步深化，该成果不仅再次表明了某些数学 问题是不能用任何机械过程来解决的思想，而且还深刻揭示 可计算所具有的“能行过程”的本质特征。,图灵的描述是关于数值计算的，不过，我们知道英文字 母表的字母以及汉字均可以用数来表示，因此，图灵机同样 可以处理非数值计算。不仅如此，更为重要的是，由数值和 非数值英文字母、汉字等组成的字符串，既可以解释成 数据，又可以解释成程序，从而计算的每一过程都可以用字 符串的形式进行编码，并存放在存储器中，以后使用时译码， 并由处理器执行，机器码结果可以从高级符号形式即 程序设计语言机械地推导出来。 图灵的研究成果是：可计算性图灵可计算性。在进行 可计算性问题的讨论时，不可避免地要提到一个与计算具有 同等地位和意义的基本概念，那就是算法。算法也称为能行,方法或能行过程，是对解题计算过程的精确描述，它由 一组定义明确且能机械执行的规则语句、指令等组成。 根据图灵的论点，可以得到这样的结论：任一过程是能行的 能够具体表现在一个算法中，当且仅当它能够被一台图 灵机实现。 图灵机等计算模型均是用来解决问题的，理论上的能行 性隐含着计算模型的正确性，而实际实现中的能行性还包 含时间与空间的有效性。,3、图灵机,为纪念图灵对计算机的贡献， 美国计算机博物馆于1966年 设立了“图灵奖”,计算机是使用相应的程序来完成任何设定好的任务。,图灵机是一种思想模型， 它由三部分组成： 一个控制器，一条可以无限延伸的 带子和一个在带子上左右移动的读 写头。,根据图灵的观点可以得到这样的结论：凡是能用算 法方法解决的问题，也一定能用图灵机解决；凡是图灵机 解决不了的问题，任何算法也解决不了。今天我们知道， 图灵机与当时提出的用于解决计算问题的递归函数、演 算和POST规范系统等计算模型在计算能力上是等价的。它 们于20世纪30年代共同奠定了计算科学的理论基础。相比 于其他几种计算模型，图灵机是从过程这一角度来刻画计 算的本质，其结构简单，操作运行规则也较少，从而为更 多的人所理解。 图灵机的特征 图灵机由一条两端可无限延长的带子、一个读写头以及一组控制读写头工作的命令组成，如图所示。图灵机,的带子被划分为一系列均匀的方格。读写头可以沿带子方向左 右移动，并可以在每个方格上进行读写。 写在带子上的符号为一个有穷字母表： S0,S1,S2,SP。 通常，可以认为这个有穷字母表仅有两个S0、S1字符，其中S0 可以看作是“0”，S1可以看作是“1”，它们只是两个符号，要说 有意义的话，也只有形式的意义。,由字符“0”和“1”组成的字母表可以表示任何一个数。 机器的控制状态表为q1, q2,qm,。通常，将一个图灵 机的初始状态设为q1，在每一个具体的图灵机中还要确定一 个结束状态qw。 一个给定机器的“程序”认为是机器内的五 元组qiSjSkR或L或Nql形式的指令集，五元组定义了 机器在一个特定状态下读入一个特定字符时所采取的动作。 5个元素的含义如下： qi 表示机器目前所处的状态； Sj 表示机器从方格中读入的符号； Sk 表示机器用来代替写入方格中的符号； R、L、N 分别表示向右移一格、向左移一格、不移动； ql 表示下一步机器的状态。,图灵机的工作原理 机器从给定带子上的某起始点出发，其动作完全由其初始状态及机内五元组来决定。就某种意义而言，一个机器其实就是它作用于纸带上的五元组集。一个机器计算的结果是从机器停止时带子上的信息得到的。 4、冯诺依曼型计算机 1946年2月14日，世界上第一台数字电子计算机ENIAC在美国宾夕法尼亚大学研制成功。该机是使用电子线路来执行算术和逻辑运算以及信息存储的真正工作的计算机器，它的成功研制显示了电子线路的巨大优越性。但是，ENIAC的结构在很大程度上是依照机电系统设计的，还存在重大的线路结构等问题。在图灵等人工作的影响下，1946年6月，美国杰出的数学家冯诺依曼及其同事完成了关于电子计算装置逻辑结构设计的研究报告，具体,介绍了制造电子计算机和程序设计的新思想，给出了由控 制器、运算器、存储器、输入和输出设备5类部件组成的， 被称为冯诺依曼型计算机或存储程序式计算机的组织 结构，以及实现它们的方法，为现代计算机的研制奠定了 基础，至尽为止，大多数计算机采用的仍然是冯诺依曼型 计算机的组织结构，只是作了一些改进而已。因此，冯诺 依曼被人们誉为“计算机器之父”。,冯诺依曼型计算机的组织结构,John von Neumann 冯诺依曼,1949 EDSAC,存储程序工作原理 计算机的两个基本能力：一是能够存储程序，二是能够自动地执行程序。 计算机是利用“存储器”（内存）来存放所要执行的程序的，而称之为CPU的部件可以依次从存储器中取出程序中的每一条指令，并加以分析和执行，直至完成全部指令任务为止。,香侬是现代信息论的著名创始人。1938年，香侬在发表的论文中， 首次用布尔代数进行开关电路分析，并证明布尔代数的逻辑运算可 以通过继电器电路来实现。 阿塔纳索夫提出了计算机的三条原则： 1）以二进制的逻辑基础来实现数字运算，以保证 精度； 2）利用电子技术来实现控制、逻辑运算和算术运 算，以保证计算速度； 3）采用把计算功能和二进制数更新存储功能相分 离的结构。,Claude Shannon,奠定现代计算机发展的重要人物和思想,2.3 数据在计算机中的表示,计算机中的数据和指令都是用二进制代码表示的，这是因为计算机的各组成部分是仅具有两个稳定状态的物理元件电子开关线路所组成。为此，要想深入学习计算机的各个部分，必须掌握二进制代码的有关知识。 计算机中用二进制代码表示数据信息有两种方法： 按“值”表示：在选定的进位制中正确地表示出数值，包括数字、符号、小数点位置及正负号等。如“9.5”可表示为二进制的 “1001. 1”。 按“形”表示：按照一定的编码方法来表示数据。如用ASCII码表示“9.5”，其形式为0101101、0111001、0101110、0110101。,1、进位制数及其相互转化 (一)进位制数（进位计数制） 数制的定义：用一组固定的数字(数码符号)和一套统一的 规则来表示数值的方法就叫做数制(number system也称计数 制)。这一定义主要的内涵是： (1) 数制的种类很多，除了十进制数，还有二十四进制(24小 时为一天)，六十进制(60分为1小时，60秒为1分)，二进制(鞋、 袜、筷子等两只为一双)，等等。 (2) 在一种数制中，只能使用一组固定的数字来表示数的大 小。数字在一个数中所处的位置称为数位。具体使用多少个 数字来表示一个数值的大小，就称为该数制的基数(base)。 例如，十进制数(Decimal),的基数是10，使用09十个数字，二进制数(Binary)的基数为 2，使用0，1两个数字。在计算机文献中，十进制数是在数 的末尾加字母D来标识。例如，1989D，表示十进制数1989。 一般情况下，1989就是一个十进制数，不在后面加D。二进 制数是在数的末尾加字母B来标识。例如，101B，表示二进 制数的101，即十进制数的5。 (3) 在一种数制中，有一套统一的规则。N进制的规则是逢N 进1，或者借1为N。 权 或称位权，是指数位上的数字乘上一个固定的数值。十 制数是逢十进一，所以对每一位数可以分别赋以位权100， 101，102，。 用这样的位权就能够表示十进制的数。,基数 某一基数中的最大数是“基数减1”，而不是基数本身，如 十进制数中的最大数为(101)9，二进制数中的最大数为 (21)1；最小数均为0。 数位、基数和位权是进位计数制中的三个要素。 采用二进制记数法 原因目前，在计算机内部，数据的计算和处理都采用二 进制记数法，主要是由二进制数在技术操作上的可行性、可 靠性、简易性以及其逻辑性所决定的。 (1) 可行性若用十进制数，需要0，1，9等不同的10个基 数，用电子技术实现这10种状态就很困难。而用二进制数， 则只需0，1两个基数，要表示两个状态，这在电学技术上的,实现最为容易。例如，电灯的亮和灭，晶体管的导通和截止， 等等。 (2) 可靠性因二进制数只要两个状态，数字转移和处理就不 易出错，这样计算机工作的可靠性就高。 (3) 简易性二进制数运算法则简单。例如，二进制的加法、 积法法则都只有三个。运算法则少，使计算机运算器结构大 大简化，控制也可随之简化。 (4) 逻辑性由于二进制数只要0，1两个数码，可以代表逻辑 代数中的“假”和“真”，这就是在计算机中使用二进制的逻辑 性。,具体分析二进制、十进制、八进制、十六进制的性质： 十进制D 具有十个数字符号0，1，2，3，9； 逢十进一； 基数为10，第i位的权为10i。 举例：123.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.4381 38-2 表示方法：137.438137.43Q,十六进制H 具有十六个数字符号0，1，2，9，A，B，C，D，E，F； 逢十六进一； 基数为16，第i位的权为16i。 举例： 147B. CD16116341627161 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？10 1012122021120510 例5：11011.1012？10 11011.1012124123022121120 12-102-212 -3 270.50.125 27.62510, B D,2、十进制与八进制间的相互转化 D Q 同与二进制间的转化类似，整数部分除以8，取余数； 小数部分则乘以8，取整数。 此外，我们知道，八进制的基数8正好是二进制基数 的3次幂，即8123，故八进制的一位相当于二进制的三位。因此在转化时，也可以先将十进制数转化为二进制数，而后在进一步转化为八进制数。 例略 Q D 将八进制数的各位按权展开相加。 例略,八进制与二进制的关系,3、十进制数与十六进制数间的相互转化 D H 同与二进制间的转化类似，整数部分除以16，取余数； 小数部分则乘以16，取整数。 十六进制的基数16正好是二进制基数的4次幂，即16124，故十六进制的一位相当于二进制的四位。因此在转化时，也可以先将十进制数转化为二进制数，而后在进一步转化为十六进制数。 例略 H D 将十六进制数的各位按权展开相加。 例略,十六进制与二进制的关系,2、数据的长度单位 数据的长度单位有位、字节和字等。 (1) 位 也称比特，记为bit(binary digit的缩写)或小写b，这是最小的 信息单位，是用0或1来表示的1个二进制数位。 (2) 字节 记为Byte或大写B，这是计算机的最小存储单元。PC机中由 8个二进制位构成一个字节，从最小的00000000到最大的 11111111，即一个字节可有256个值。一个字节也可以表示 由8个二进制位构成的其它信息。一个字节可存放一个半角 英文字符的编码( ASCII码)。两个字节可存放一个汉字编码，,1个汉字至少需要两个字节或两个字符来表示。这里所说的 字符是指ASCII码字符，即半角下的英文字母、数字或其它 符号。,字节（Byte）：最常用的基本单位,K (KiloBytes，千) 字节 1K = 1024 byte =210 M（MegaBytes，兆）字节 1M = 1024 K =220 G（GigaBytes，吉）字节 1G = 1024 M =230 T（TeraBytes，太）字节 1T = 1024 G =240 P（PetaBytes，拍）字节 1T = 1024 G =250,(3)字 记为word或小写w，是计算机信息交换、加工、存储的基本 单元。用二进制代码表示，一个字由一个字节或若干字节 构成。它可以代表数据代码、字符代码、 操作码和地址码 或它们的组合。计算机的“字”用来表示数据或信息长度。 3、数值的表示 机器数 在计算机中，因为只有“0” 和“1”两种形式，为了表示数 的正、负号，也必须以“0” 和“1”表示。通常把一个数的最 高位定义为符号位，用0表示正，1表示负，称为数符；其 余位仍表示数值。通常，把在机器内存放的正负号数码化 的数成为机器数，把机器外部由正负表示的数称为真值数。,例如，若一个数占8位，真值数0101100B的机器数 为10101100，存放在机器中如图示。 机器数表示的范围受到字长和数据类型的限制。字长和数据类型确定了，机器数表示的范围也定了。 整数和实数 在机器中，难以表示小数点，故在机器中通过对小数点的位置加以规定来表示。因此，就有整数和实数区分。,数符,1、整数 整数是没有小数部分的数，也可以认为小数点在数的 最右边。整数分为带符号和不带符号两类。对带符号的整 数，符号位被放在最高位。整数表示的数是精确的，但数的范围是有限的。根据存放数的字长，它们可以用8、16、32位等表示，各自表示数的范围见下表。,不同位数和数的表示范围,2、实数 计算机处理的数值大部分是实数，即带有小数部分 的数，尤其是在科学计算中。通常，为了能表示特大或 特小的数，实数采用“浮点数”或称“科学表示法”表示， “浮点数”由两部分组成，即尾数和阶码。 任意二进制规格化浮点数的表示形式为： Nd2 p,式中：d是尾数，前面的“”表示数符；p是阶码，前面的“”表示阶符。它在计算机内的存储形式如图示：,浮点数存储格式,阶码通常用整数形式来表示，它指出的是小数点在 数据中的位置，决定了浮点数的表示范围；尾数通常用 小数形式表示，给出了有效数字的位数，决定了浮点数 的表示精度。所谓规格化的浮点数就是指尾数需满足条 件：S1。 二进制的原码、反码及补码表示 按值表示数需解决的一个问题是如何表示数的正负 号。在计算机中，数的正负号是用“0”、“1”表示的。机器 数在计算机时，若将符号同时和数值参加运算，则会产生 错误的结果；否则要考虑计算机结果的符号问题，将增加 计算机实现的难度。例如，54的结果应为1，但在,计算机中若按照上面讲的符号和数值同时参加运算，结果 为9，显然是错误的。 若要考虑符号位的处理，则运算变得复杂。为了解决 此类问题，在机器数中，数有三种表示法：原码 primary code、反码ones complement和补码tows complement。 设计算机的字长为n位，它可表示的真值 xxn-2xn-3x0,其中xi0或1二进制数，则有：1、真值x xn-2xn-3x0时，原码、反码和补码完全 相同，即x原x反x补0 xn-2xn-3x0,2、真值x xn-2xn-3x0 时，原码、反码和补码与 x的关系如下： x原1 xn-2 xn-3x0 x反1 x补1 ( +1) 从而可知，在n位的机器数中，最高位为符号位，若 该位为0真值为正，该位为1则真值为负；其余的 n1位为数值位，其取值为0或1。当真值为正时， 原码、反码和补码的数值位完全相同；当真值为负时， 原码的数值位保持真值的原样，反码的数值位为原码的 各位取反，补码则是反码的最低位加1。根据以上关系， 很容易实现真值与机器数之间及三种机器数之间的相互。,转换。 例1：已知计算机字长为8位，试写出二进制数101010和 101010在机器中表示的原码、反码及补码。 首先写出它们的真值。设该机器采用定点整数表示， 则真值形式如下： x0101010 y0101010 真值x为正，故有 x原 x反 x x补00101010 真值y为负，有 x原10101010 x反11010101 x补11010110,例2：已知101101，求真值x。 分析：最高位为符号位，先由x补求出x反 x反1011011101100 x补110011 从而有 y10011 运算基础 计算机中的运算有两类，一是算术运算，另一类是 逻辑运算。算术运算包括加、减、乘、除等四则运算。 逻辑运算 常用的逻辑运算有逻辑乘“与”运算、逻辑加 “或”运算、逻辑非“非”运算等运算，它们都是按位进行运算的，也称逻辑操作。,“与”运算， “与”AND运算的规则如下： 000 010 100 111 式中，“”是“与”的运算符号，也可以用“”代替。 “与”运算的一般式为 CAB 或 CABAB “或”运算， “或”OR运算的规则如下： 000 011 101 111 式中，“”是“或”的运算符号，也可以用“”代替。 “或”运算的一般式为 CAB 或 CAB,“非”运算 “非”NOT运算的规则如下： 1 0 式中，“”是“非”的运算符号。 “非”运算的一般式为C “异或”运算 “异或”EOR：Exclusive OR运算的规则如下： 式中，“ ”是“异或”的运算符号。,0,0,1,=1,1,0,=1,1,1,=0,B,2、算术运算 二进制的四则运算按位进行运算,例2：1110-0011？,例4：1000001 101？,例1：10011000？,例3：11011001？,补码加减运算 补码加法 设x,y为正或负整数的真值，则由补码的定 x补 y补 x+y补 应用这一公式很容易实现补码的加法运算。 例1：设x0110110,y1111001。 求xy？ 解：在计算机中，真值x,y表示下列补码形式 x补0,0110110 y补1,0000111 根据式，有 x+y补x补y补1，0111101 求得 xy1000011 结果正确,例2：设x1010011,y0100101。求xy？ 解： x补0,1010011 y补0,0100101 根据式，有 x+y补x补y补0，1111000 求得 xy1111000 结果正确 例3：设x1000011,y0100001。 求xy？,即x补y补x+y补1,0011100 求得 xy1100100 结果正确,该例中，因机器字长假定为8位，故x补y补 的结果中最高位“1”无法保存，自动丢失，计算机中的实结果为1,0011100。,例4：设x1000101,y1100111。 求xy？ 解： x补0,1000101 y补0,1100111 x补 y补1，0101100 即 x+y补x补y补1,0101100 求得 xy1010100 显然，该结果是错误的，因为两个正数想加，其和 不可能为负数。分析如下： 真值x和y所表示的十进制数分别为6910和 10310，其和为17210。该十进制数所对应的 二进制数为10101100，需用9位字长的机器数表示， 现机器只有8位字长，无法表示，称这种现象为“溢出 overflow”。,在计算机中，一旦发生溢出，其运算结果肯定是错误的，机器将进行溢出处理。 补码减法 设x，y为正或负整数的真值，则可利用下列补码关系求得xy之值。 x-y补x+(-y)补x补-y补 例如，设x1010101,y1100001。 求xy？ x补0,1010101 y-1100001 -y补1，0011111 故得 x-y补 x+(-y)补1，1110100 xy0001100,字符的表示 字符包括西文字符和中文字符。字符编码的方法和简 单，首先确定需要编码的字符总数，然后将每一个字符 按顺序编号，编号值的大小无意义，仅作为识别与使用 这些字符的依据。 1、西文字符 对西文字符编码最常用的是ASCII字符编码，即 American Standard Code for Information Interchange美国信息交换标准代码。ASCII是用7为 二进制编码，它可以表示2即128个字符。每个字符用7位 二进制码表示，其排列次序为d6d5dd3d2d1d0，d6为高位， d0为低位。,在ASCII码表中，十进制码值032和127NULSP 和DEL共34个字符称为非图形字符又称为控制字符 其余94个字符称为图形字符又称为普通字符。在这些 字符中，从“0” “9”、从“A” “Z”、从“a” “z”都是顺 序排列的，且小写比大写字母码值大32，即位值d5为0或1， 这有利于大、小写字母之间的编码转换。 计算机的内部存储与操作常以字节为单位，即8个二 进制位为单位。因此，一个字符在计算机内实际是