第4章计算学科中的基本概念.ppt

《第4章计算学科中的基本概念.ppt》由会员分享，可在线阅读，更多相关《第4章计算学科中的基本概念.ppt（234页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、第4章计算学科中的基本概念 Still waters run deep.流静水深流静水深,人静心深人静心深 Where there is life,there is hope。有生命必有希望。有生命必有希望4.1计算模型与二进制计算模型与二进制4.1.1计算模型与图灵机计算模型与图灵机计算模型与图灵机计算模型与图灵机计算模型与图灵机oo计算模型：计算模型：计算模型：计算模型：n n刻刻刻刻画画画画计计计计算算算算这这这这一一一一概概概概念念念念的的的的一一一一种种种种抽抽抽抽象象象象的的的的形形形形式式式式系系系系统统统统或或或或数数数数学学学学系统。系统。系统。系统。n n在在在在计计计计算

2、算算算科科科科学学学学中中中中，是是是是指指指指具具具具有有有有状状状状态态态态转转转转换换换换特特特特征征征征，能能能能够够够够对对对对所所所所处处处处理理理理的的的的对对对对象象象象的的的的数数数数据据据据或或或或信信信信息息息息进进进进行行行行表表表表示示示示、加加加加工工工工、变变变变化、接收、输出的数学机器。化、接收、输出的数学机器。化、接收、输出的数学机器。化、接收、输出的数学机器。oo计算模型的层次：计算模型的层次：计算模型的层次：计算模型的层次：n n计算某个（类）具体问题的计算方法；计算某个（类）具体问题的计算方法；计算某个（类）具体问题的计算方法；计算某个（类）具体问题的计

3、算方法；n n按按按按照照照照计计计计算算算算方方方方法法法法对对对对应应应应的的的的程程程程序序序序完完完完成成成成某某某某类类类类问问问问题题题题特特特特定定定定计计计计算算算算所需要的平台。所需要的平台。所需要的平台。所需要的平台。n n 在计算能力上具有某种等价性的形式系统。在计算能力上具有某种等价性的形式系统。在计算能力上具有某种等价性的形式系统。在计算能力上具有某种等价性的形式系统。n n 计算模型的模型（一切计算模型所内含的机理）计算模型的模型（一切计算模型所内含的机理）计算模型的模型（一切计算模型所内含的机理）计算模型的模型（一切计算模型所内含的机理）计算模型与图灵机计算模型与

4、图灵机计算模型与图灵机计算模型与图灵机oo图灵的观点及结论：图灵的观点及结论：n n凡凡是是能能用用算算法法方方法法解解决决的的问问题题，也也一一定定能能用用图图灵灵机机解解决决；凡凡是是图图灵灵机机解解决决不不了了的的问问题，任何算法也解决不了。题，任何算法也解决不了。oo与图灵机等价的计算模型：与图灵机等价的计算模型：n n递归函数递归函数n n-演算演算n nPOST规范系统规范系统oo图图灵灵机机是是从从过过程程这这一一角角度度来来刻刻画画计计算算的的本本质质，其其结结构构简简单单、操操作作运运算算规规则则也也较较少少，从从而而为为更多的人所理解。更多的人所理解。图灵机图灵机图灵机图灵

5、机oo图图灵灵机机由由一一条条两两端端可可无无限限延延长长的的带带子子、一一个个读写头以及一组控制读写头工作的命令组成，读写头以及一组控制读写头工作的命令组成，图灵机图灵机图灵机图灵机oo写在带子上的符号为一个有穷字母表：写在带子上的符号为一个有穷字母表：S0，S1，S2，Sp。n n可以认为这个有穷字母表仅有可以认为这个有穷字母表仅有S0、S1两个两个字符，字符，n n其中其中S0可以看作是可以看作是“0”，S1可以看作是可以看作是“1”，n n由由“0”和和“1”组成的字母表可以表示任组成的字母表可以表示任何一个数。何一个数。oo由于由于“0”和和“1”只有形式的意义，因此，只有形式的意义

6、，因此，也可以将也可以将S0改称为改称为“白白”，S1改称为改称为“黑黑”，甚至，还可以改称为甚至，还可以改称为“桌子桌子”和和“老虎老虎”，这样改称的目的在于割断与直觉的联系，并这样改称的目的在于割断与直觉的联系，并加深对布尔域中的值加深对布尔域中的值真，假真，假，以及二进制，以及二进制机器本质的理解。机器的控制状态表为：机器本质的理解。机器的控制状态表为：q1，q2，qm。n n将一个图灵机的初始状态设为将一个图灵机的初始状态设为q1，在每一在每一个具体的图灵机中还要确定一个结束状态个具体的图灵机中还要确定一个结束状态qw。一个给定机器的一个给定机器的“程序程序”oo机器内的五元组（qiS

7、jSkR（或L或N）ql）形式的指令集，五元组定义了机器在一个特定状态下读入一个特定字符时所采取的动作。5个元素的含义如下：n nqi表示机器目前所处的状态；n nSj表示机器从方格中读入的符号；n nSk表示机器用来代替Sj写入方格中的符号；n nR、L、N分别表示向右移一格、向左移一格、不移动；n nql表示下一步机器的状态。oo一个机器计算的结果是从机器停止时带子上的信一个机器计算的结果是从机器停止时带子上的信息得到的。容易看出，息得到的。容易看出，q q1 1S S2 2S S2 2RqRq3 3指令和指令和q q3 3S S3 3S S3 3LqLq1 1指令如果同时出现在机器中，当

8、机器处于状态指令如果同时出现在机器中，当机器处于状态q q1 1，第一条指令读入的是，第一条指令读入的是S S2 2，第二条指令读入的是，第二条指令读入的是S S3 3，那么机器会在两个方块之间无休止地工作。，那么机器会在两个方块之间无休止地工作。oo另外，如果另外，如果q q3 3S S2 2S S2 2RqRq4 4和和q q3 3S S2 2S S4 4LqLq6 6指令同时出现在指令同时出现在机器中，当机器处于状态机器中，当机器处于状态q q3 3并在带子上扫描到符并在带子上扫描到符号号S S2 2时，就产生了二义性的问题，机器就无法判时，就产生了二义性的问题，机器就无法判定。定。例子

9、：例子：例子：例子：oob b表示空格，表示空格，表示空格，表示空格，q q1 1表示机器的初始状态，表示机器的初始状态，表示机器的初始状态，表示机器的初始状态，q q4 4表示机器的表示机器的表示机器的表示机器的结束状态，设带子上的输入信息是结束状态，设带子上的输入信息是结束状态，设带子上的输入信息是结束状态，设带子上的输入信息是1010001010100010，读入头，读入头，读入头，读入头位对准位对准位对准位对准最右边最右边最右边最右边第一个为第一个为第一个为第一个为0 0的方格，状态为初始状态的方格，状态为初始状态的方格，状态为初始状态的方格，状态为初始状态q q1 1。规则如下：规则

10、如下：规则如下：规则如下：n nq q1 10101L L q q22q q1 11010L L q q33q q1 1 b b b b N N q q4 4n nq q2 20000L L q q22q q2 21111L L q q22q q2 2 b b b b N N q q4 4n nq q3 30101L L q q22q q3 31010L L q q33q q3 3 b b b b N N q q4 4计算结果是10100011，即对给定的数加1。以上命令计算的是这样一个函数：S(x)x1。当没有输入时，即初始状态所指的方格为空格（b）时，不改变空格符，读写头不动并停机。图灵机

11、的计算能力图灵机的计算能力图灵机的计算能力图灵机的计算能力o第一第一，把图灵机看作识别器，即判断带子上最，把图灵机看作识别器，即判断带子上最初的内容能否被图灵机所接受。假定图灵机从初的内容能否被图灵机所接受。假定图灵机从左向右扫描完带子上的内容后停机则为接受，左向右扫描完带子上的内容后停机则为接受，否则为不接受。否则为不接受。o例例2一台图灵机可以设计成识别下面的序列：一台图灵机可以设计成识别下面的序列：1000110,10011101,010101011。图灵机的计算能力图灵机的计算能力图灵机的计算能力图灵机的计算能力oo第二，第二，把图灵机看作生成器，对给定的输入集把图灵机看作生成器，对给

12、定的输入集合，考察输出集合，并研究输入输出集合性质合，考察输出集合，并研究输入输出集合性质之间的关系，这就研究了图灵机的生成能力。之间的关系，这就研究了图灵机的生成能力。oo例例3设一台图灵机的输入集合为设一台图灵机的输入集合为In1n0nnN，可设计一台图灵机，对给定的，可设计一台图灵机，对给定的输入集合输入集合In，得到输出集合，得到输出集合Out0n1nnN。其中，。其中，N是全体自然数的集合。是全体自然数的集合。图灵机的计算能力图灵机的计算能力图灵机的计算能力图灵机的计算能力o第三第三，把图灵机看作计算器，相当于一个函数。，把图灵机看作计算器，相当于一个函数。图灵机的输入是函数的自变量

13、的值，图灵机的图灵机的输入是函数的自变量的值，图灵机的输出是函数的值。输出是函数的值。例例4图灵机可以计算下列函数：图灵机可以计算下列函数：(1)s(x)x1；(2)o(x)0；(3)A(0，y)y1，A(x1，0)A(x，1)，A(x1，y1)A(x，A(x1，y)。图灵机的计算能力图灵机的计算能力图灵机的计算能力图灵机的计算能力o第一和第二个函数读者不难从图灵机的定义出第一和第二个函数读者不难从图灵机的定义出发感悟到它们是图灵机可以计算的函数，而第发感悟到它们是图灵机可以计算的函数，而第三个函数就比较复杂，一时难于判断。顺便提三个函数就比较复杂，一时难于判断。顺便提一下，第三个函数叫做一下

14、，第三个函数叫做阿克曼函数阿克曼函数，它是阿克，它是阿克曼（曼（W.Ackermann）在研究原始递归函数和）在研究原始递归函数和递归函数的关系时给出的。这个函数在计算理递归函数的关系时给出的。这个函数在计算理论中具有重要价值。论中具有重要价值。o事实上，图灵机还可以计算形式上比第三个函事实上，图灵机还可以计算形式上比第三个函数更复杂的函数。数更复杂的函数。图灵机的计算能力图灵机的计算能力图灵机的计算能力图灵机的计算能力oo图灵机可以计算图灵机可以计算n nS(x)x1（后继函数），后继函数），n nN(x)0（零函数），零函数），n nUi(n)(x1，x2，xn)xi，1in（投影函数）投

15、影函数）n n上述上述3个函数的任意组合。个函数的任意组合。oo从递归论中，我们知道这从递归论中，我们知道这从递归论中，我们知道这从递归论中，我们知道这3 3个函数属于个函数属于个函数属于个函数属于初始递归函数初始递归函数初始递归函数初始递归函数，n n任何原始递归函数都是从这任何原始递归函数都是从这任何原始递归函数都是从这任何原始递归函数都是从这3 3个初始递归函数经有个初始递归函数经有个初始递归函数经有个初始递归函数经有限次的复合、递归和极小化操作得到的。限次的复合、递归和极小化操作得到的。限次的复合、递归和极小化操作得到的。限次的复合、递归和极小化操作得到的。n n从可计算理论可知每一个

16、原始递归函数都是图灵从可计算理论可知每一个原始递归函数都是图灵从可计算理论可知每一个原始递归函数都是图灵从可计算理论可知每一个原始递归函数都是图灵机可计算的。机可计算的。机可计算的。机可计算的。4.1计算模型与二进制计算模型与二进制4.1.2二进制计算机的数字系统计算机的数字系统计算机的数字系统计算机的数字系统oo计算机采用的是二进制数字系统。计算机采用的是二进制数字系统。oo基本符号：基本符号：0 0、1 1oo进位原则：逢二进一进位原则：逢二进一oo优点：优点：n n易于物理实现易于物理实现n n二进制数运算简单二进制数运算简单n n机器可靠性高机器可靠性高n n通用性强通用性强oo缺点：

17、对人来说可读性差缺点：对人来说可读性差十进制数的表示十进制数的表示十进制数的表示十进制数的表示各位数字与它的权相乘，其积相加。各位数字与它的权相乘，其积相加。各位数字与它的权相乘，其积相加。各位数字与它的权相乘，其积相加。例如例如例如例如:27997.63=21*1027997.63=21*104 4+7*10+7*103 3+9*10+9*102 2+9*10+9*101 1+7*10+7*100 0+6*10+6*10-1-1+3*10+3*10-2-2 对于任意的十进制数：对于任意的十进制数：对于任意的十进制数：对于任意的十进制数：S=S=k kn n*10*10n n+k kn-1n-

18、1*10*10n-1n-1+k k1 1*10*101 1+k k0 0*10*100 0+k k-1-1*10*10-1-1+k k-m+1-m+1*10*10-m+1-m+1+k k-m-m*10*10-m-m(n1,m1)(n1,m1)其中，其中，其中，其中，1010称为十进制的基数称为十进制的基数称为十进制的基数称为十进制的基数,ki,ki0,1,2,3,4,5,6,7,80,1,2,3,4,5,6,7,899，mm，n n为正整数。小数点的位置不言自明。为正整数。小数点的位置不言自明。为正整数。小数点的位置不言自明。为正整数。小数点的位置不言自明。计算机的数字系统计算机的数字系统计算

19、机的数字系统计算机的数字系统oo计算机采用的是二进制数字系统。二进制和十进计算机采用的是二进制数字系统。二进制和十进计算机采用的是二进制数字系统。二进制和十进计算机采用的是二进制数字系统。二进制和十进制一样，是一种数制，它用于表示数的符号（数制一样，是一种数制，它用于表示数的符号（数制一样，是一种数制，它用于表示数的符号（数制一样，是一种数制，它用于表示数的符号（数字）由于在书写中的位置不同而具有不同的值。字）由于在书写中的位置不同而具有不同的值。字）由于在书写中的位置不同而具有不同的值。字）由于在书写中的位置不同而具有不同的值。oo基本符号：基本符号：基本符号：基本符号：0 0 0 0、1

20、1 1 1oo进位原则：逢二进一进位原则：逢二进一进位原则：逢二进一进位原则：逢二进一oo优点：优点：优点：优点：n n易于物理实现易于物理实现易于物理实现易于物理实现n n二进制数运算简单二进制数运算简单二进制数运算简单二进制数运算简单n n机器可靠性高机器可靠性高机器可靠性高机器可靠性高n n通用性强通用性强通用性强通用性强oo缺点：对人来说可读性差缺点：对人来说可读性差缺点：对人来说可读性差缺点：对人来说可读性差二进制数二进制数 Sknkn-1k0.k-mkn2nkn-12n-1k020k-m2-m-mki2iin其中，其中，2称为二进制的基数，称为二进制的基数，ki0,1,m,n为正整

21、数。为正整数。进一步，读者可从十进制数和二进制数的一般表示进一步，读者可从十进制数和二进制数的一般表示公式得到启发，将这种表示推广到更一般的任意进制，公式得到启发，将这种表示推广到更一般的任意进制，不同之处只是基数不一样。不同之处只是基数不一样。二进制数二进制数 二二进进制制的的运运算算规规则则比比十十进进制制的的运运算算规规则则简简单单得得多多。只只要要建建立立两两种种进进制制的的数数据据之之间间的的转转换换方方法法，那那么么，二二进进制制将将具具有有更更多多的的优优势势。计计算算机机的的理理论论基基础础是是逻逻辑辑和和代代数数。当当二二进进制制与与同同样样只只使使用用“真真”和和“假假”两

22、两个个值值的的逻逻辑辑代代数数建建立立了了联联系系后后，这这就就为为计计算算机机的的逻逻辑辑设设计计提提供供了了便便利的工具。利的工具。不同进位计数制间的转换不同进位计数制间的转换不同进位计数制间的转换不同进位计数制间的转换 R R 进制进制进制进制十进制十进制十进制十进制各位数字与它的权相乘，其积相加。各位数字与它的权相乘，其积相加。例如例如:(11111111.11)2=1*27+1*26+1*25+1*24+1*23+1*22+1*21+1*20+1*2-1+1*2-2=(255.75)10(3506.2)8=3*83+5*82+0*81+6*80+2*8-1=(1862.25)10(0

23、.2A)16=2*16-1+10*16-2=(0.1640625)10二进制与十进制间的转换二进制与十进制间的转换二进制与十进制间的转换二进制与十进制间的转换 十进制十进制十进制十进制 二进制二进制二进制二进制十进制整数转换成二进制的整数十进制整数转换成二进制的整数“除除R取余取余”法，例如：法，例如：268268余余余余 数数数数 23423400低位低位低位低位 2172170 028281 124240 022220 02121000011高位高位高位高位所以所以所以所以 68681010100010010001002 2二进制与十进制间的转换二进制与十进制间的转换二进制与十进制间的转换

24、二进制与十进制间的转换十进制十进制十进制十进制 二进制二进制二进制二进制十进制小数转换成二进制小数十进制小数转换成二进制小数“乘乘R取整取整”法，例如：法，例如：高位高位0.31252=0.6250.6252=1.250.252=0.50.52=1.0所以所以0.312510=0.01012不同进位计数制间的转换不同进位计数制间的转换不同进位计数制间的转换不同进位计数制间的转换二、八、十六进制的相互转换二、八、十六进制的相互转换二、八、十六进制的相互转换二、八、十六进制的相互转换oo每位八进制数相当于三位二进制数每位八进制数相当于三位二进制数oo每位十六进制数相当于四位二进制数每位十六进制数相

25、当于四位二进制数(1011010.10)2=(001011010.100)2=(132.4)8(1011010.10)2=(01011010.1000)2=(5A.8)16(F7)16(11110111)2(11110111)2信息的存储单位信息的存储单位信息的存储单位信息的存储单位oo位位(bit)：度量数据的最小单位，表示一位二：度量数据的最小单位，表示一位二进制信息。进制信息。oo字节字节(byte)：由八位二进制数字组成：由八位二进制数字组成(1byte=8bit)。K字节字节1K=1024byteM字节字节1M=1024KG字节字节1G=1024MT字节字节1T=1024G非数值信息

26、的表示非数值信息的表示非数值信息的表示非数值信息的表示oo西文字符：西文字符：n nASCII码：用码：用7位二进制数表示一个字符，位二进制数表示一个字符，最多可以表示最多可以表示27=128个字符个字符n nEBCDIC码：用码：用8位二进制数表示一个字位二进制数表示一个字符，最多可以表示符，最多可以表示28=256个字符个字符oo汉字：n n应用较为广泛的是应用较为广泛的是国家标准信息交换用国家标准信息交换用汉字编码汉字编码(GB2312-80标准标准)，简称国标码。，简称国标码。是二字节码，用二个七位二进制数编码表是二字节码，用二个七位二进制数编码表示一个汉字。示一个汉字。4.2存储程序

27、式计算机的基本存储程序式计算机的基本结构与工作原理结构与工作原理4.2.1冯诺依曼型计算机冯冯冯冯 诺依曼型计算机诺依曼型计算机诺依曼型计算机诺依曼型计算机 图灵机的出现为现代计算机的发明提供了图灵机的出现为现代计算机的发明提供了重要的思想。图灵机的带子可以看成是计算机重要的思想。图灵机的带子可以看成是计算机的存储设备，数据可以存储在上面，也可以根的存储设备，数据可以存储在上面，也可以根据需要擦去。图灵机的命令相当于一组事先设据需要擦去。图灵机的命令相当于一组事先设计、存储好了的程序，它们在控制器安排下，计、存储好了的程序，它们在控制器安排下，决定读写头的每一步操作。这样一种数学机器，决定读写

28、头的每一步操作。这样一种数学机器，如果不考虑它的实用性，就思想和原理而言，如果不考虑它的实用性，就思想和原理而言，确实包含了确实包含了存储程序存储程序的重要思想。的重要思想。冯冯冯冯 诺依曼型计算机诺依曼型计算机诺依曼型计算机诺依曼型计算机oo计计算算机机程程序序是是指指能能够够在在计计算算机机系系统统中中运运行行的的程序。程序。oo现现在在的的计计算算机机全全称称为为存存储储程程序序式式通通用用电电子子数数字计算机。其含义是：字计算机。其含义是：n n在在计计算算机机中中各各种种信信息息用用数数字字代代码码表表示示，如如指令、数值型数据、字符、图像等。指令、数值型数据、字符、图像等。n n在

29、在物物理理机机制制上上，数数字字代代码码以以数数字字型型信信号号出出现。现。oo信息表示数字化信息表示数字化-理解计算机工作原理的基理解计算机工作原理的基本出发点。本出发点。冯冯冯冯 诺依曼型计算机诺依曼型计算机诺依曼型计算机诺依曼型计算机oo目前有两种电信号：目前有两种电信号：n n模模拟拟信信号号：一一种种在在时时间间上上连连续续的的信信号号，用用信号的某些参数（如幅值）去模拟信息。信号的某些参数（如幅值）去模拟信息。n n数数字字信信号号：一一种种在在时时间间上上或或空空间间上上不不连连续续（离散）的信号。（离散）的信号。冯冯冯冯 诺依曼型计算机诺依曼型计算机诺依曼型计算机诺依曼型计算机

30、oo采用数字化方法表示信息的优点：采用数字化方法表示信息的优点：n n抗干扰能力强，可靠性高。抗干扰能力强，可靠性高。n n位位数数增增多多则则数数的的表表示示范范围围扩扩大大，可可以以表表示示更精确的数字。更精确的数字。n n物理上容易实现，并可存储。物理上容易实现，并可存储。n n表示信息的类型和范围极其广泛。表示信息的类型和范围极其广泛。n n能用逻辑代数等数字逻辑技术进行处理。能用逻辑代数等数字逻辑技术进行处理。冯冯冯冯 诺依曼型计算机诺依曼型计算机诺依曼型计算机诺依曼型计算机 ooENIAC的的结结构构在在很很大大程程度度上上是是依依照照机机电电系系统统设计的，还存在设计的，还存在重

31、大的线路结构重大的线路结构等问题。等问题。oo在在图图灵灵等等人人工工作作的的影影响响下下，1946年年6月月，美美国国杰杰出出的的数数学学家家冯冯诺诺依依曼曼（VonNeumann）及及其其同同事事完完成成了了关关于于“电电子子计计算算装装置置逻逻辑辑结结构设计构设计”的研究报告，的研究报告，n n具具体体介介绍绍了了制制造造电电子子计计算算机机和和程程序序设设计计的的新思想：新思想：存储程序、顺序控制存储程序、顺序控制n n至至今今为为止止，大大多多数数计计算算机机采采用用的的仍仍然然是是冯冯诺诺依依曼曼型型计计算算机机的的组组织织结结构构，只只是是作作了了一一些些改改进进而而已已。因因此

32、此，冯冯诺诺依依曼曼被被人人们们誉誉为为“计算机器之父计算机器之父”。冯冯冯冯 诺依曼型计算机的组织结构诺依曼型计算机的组织结构诺依曼型计算机的组织结构诺依曼型计算机的组织结构 输入设备和输出设备输入设备和输出设备输入设备和输出设备输入设备和输出设备输入设备和输出设备oo作用：是将信息输入计算机和输出计算机。作用：是将信息输入计算机和输出计算机。oo常常用用的的文文字字输输入入设设备备是是键键盘盘（还还有有扫扫描描仪仪、穿孔卡片读入机和鼠标等专用输入设备）穿孔卡片读入机和鼠标等专用输入设备）n n当当在在键键盘盘上上按按下下一一个个键键时时，按按下下的的键键通通过过编码变换成机器可读的数据形式

33、，编码变换成机器可读的数据形式，n n如如字字符符“A”变变换换成成ASCII码码“1000001”，该编码数据随即存入存储器等待处理，该编码数据随即存入存储器等待处理，n n通通过过与与“1000001”对对应应的的字字符符点点阵阵数数据据在在屏幕上显示一个字符屏幕上显示一个字符“A”。oo输输出出设设备备有有打打印印机机、显显示示器器、绘绘图图仪仪、磁磁记记录设备等。录设备等。存储器存储器存储器存储器存储器oo存储器是一种数据或信息的存储部件，它分成很多存储单元，并按照一定的方式进行排列。每个单元都编了号，称为存储地址。指令和数据存放在存储器中,而且对指令和数据同等对待，都不加区别地送到运

34、算器中运算。指令在存储器中基本上是按执行顺序存储的，由指令计数器指明要执行的指令在存储器中的地址。存储器存储器存储器存储器oo存储器一般分为内存储器与外存储器两大类。内存一般安装在主机板上，根据材料和工作原理的不同，内存可分为随机存储器（RAM）和只读存储器（ROM）两种。控制器和运算器只能接受在内存中存放的指令和数据。oo外存一般安装在主机板之外，例如磁盘就是一种常用的外存。外存上面的信息可长久保存，但这些信息必须读入内存之后才能被控制器和运算器所利用。磁盘按其材料的不同，又可分为软盘和硬盘两种。CPU(CPU(运算器和控制器)central processing unitRegisterR

35、egister、控制单元、控制单元、控制单元、控制单元oo计算机中控制数据操作的电路并不与主存直计算机中控制数据操作的电路并不与主存直接相连接相连n n这些电路被封装在一起，即这些电路被封装在一起，即CPUooCPU含有自己的存储单元（含有自己的存储单元（register）n nRegister作为临时空间来存储作为临时空间来存储CPU所操作的所操作的数，保存算术逻辑单元的输入与输出数据数，保存算术逻辑单元的输入与输出数据n n控制单元负责将主存中的数据移到控制单元负责将主存中的数据移到register，然后通知算术逻辑单元所需要的数据在然后通知算术逻辑单元所需要的数据在哪个哪个registe

36、r总线总线总线总线oo总线：总线：CPU与主存之间用总线连接，利用总与主存之间用总线连接，利用总线线n nCPU通过提供存储单元目标地址以及读信通过提供存储单元目标地址以及读信号来选择、读取数据号来选择、读取数据n nCPU通过提供存储单元目标地址以及写信通过提供存储单元目标地址以及写信号来放置、写入信号号来放置、写入信号oo谁发明了什么谁发明了什么n n程序存储的概念：由宾西法尼亚大学程序存储的概念：由宾西法尼亚大学Moore电子工程学院的电子工程学院的J.P.Echert提出，提出，JohnvonNeumann只是先发表了程序存储只是先发表了程序存储的概念的概念CPUCPU和主存储器通过总

37、线相连和主存储器通过总线相连和主存储器通过总线相连和主存储器通过总线相连4.3数字逻辑与集成电路数字逻辑与集成电路4.3.1数字逻辑数字逻辑数字逻辑oo数字逻辑是数字电路逻辑设计的简称，其内数字逻辑是数字电路逻辑设计的简称，其内容是应用数字电路进行数字系统逻辑设计。容是应用数字电路进行数字系统逻辑设计。oo组成计算机的逻辑部件可分为组合逻辑电路组成计算机的逻辑部件可分为组合逻辑电路和时序逻辑电路两种。和时序逻辑电路两种。n n组合逻辑电路组合逻辑电路：由与门、或门和非门等门：由与门、或门和非门等门电路组合而成的逻辑电路。电路组合而成的逻辑电路。n n时序逻辑电路：由触发器和门电路组成的时序逻辑

38、电路：由触发器和门电路组成的具有记忆能力的逻辑电路。具有记忆能力的逻辑电路。门电门电门电门电路路路路oo“与与”门电路：两个以上的输入，一个输出。门电路：两个以上的输入，一个输出。仅当所有的输入为仅当所有的输入为1时，输出才为时，输出才为1。P=A B Coo“或或”门电路：两个以上的输入，一个输出。门电路：两个以上的输入，一个输出。仅当有一个输入为仅当有一个输入为1时，输出就为时，输出就为1。P=A+B+Coo“非非”门电路：一个输入，一个输出。当输入门电路：一个输入，一个输出。当输入为为1时，输出为时，输出为0；输入为；输入为0时，输出为时，输出为1。门电门电门电门电路路路路“与与”、“或

39、或”、“非非”三种门电路示意图三种门电路示意图PPPABCABCA（a）（b）（c）4.4机器指令与汇编语言机器指令与汇编语言4.4.1机器指令 机器指令oo为了实现程序存储的概念，为了实现程序存储的概念，CPUCPU要能识要能识别二进制编码的指令别二进制编码的指令oo机器语言机器语言指令集合以及编码系统指令集合以及编码系统机器指令机器指令机器指令机器指令oo用计算机求解一个问题，必须事先编制好程序。程用计算机求解一个问题，必须事先编制好程序。程用计算机求解一个问题，必须事先编制好程序。程用计算机求解一个问题，必须事先编制好程序。程序是由指令组成的。每一台计算机都设计规定了一序是由指令组成的。

40、每一台计算机都设计规定了一序是由指令组成的。每一台计算机都设计规定了一序是由指令组成的。每一台计算机都设计规定了一组指令集合，称为机器指令系统。组指令集合，称为机器指令系统。组指令集合，称为机器指令系统。组指令集合，称为机器指令系统。oo机器指令的格式一般分为两部分，如下所示：机器指令的格式一般分为两部分，如下所示：机器指令的格式一般分为两部分，如下所示：机器指令的格式一般分为两部分，如下所示：指令格式：指令格式：指令格式：指令格式：操作码操作码操作码操作码地址部分地址部分地址部分地址部分其中，操作码指出运算的种类，如，其中，操作码指出运算的种类，如，其中，操作码指出运算的种类，如，其中，操作

41、码指出运算的种类，如，跳转等，地址部分用来指示参与运算的数据保存，跳转等，地址部分用来指示参与运算的数据保存，跳转等，地址部分用来指示参与运算的数据保存，跳转等，地址部分用来指示参与运算的数据保存在什么地方，如存储器的某个地址或某个寄存器等。在什么地方，如存储器的某个地址或某个寄存器等。在什么地方，如存储器的某个地址或某个寄存器等。在什么地方，如存储器的某个地址或某个寄存器等。操作码和地址部分都用二进制代码表示。操作码和地址部分都用二进制代码表示。操作码和地址部分都用二进制代码表示。操作码和地址部分都用二进制代码表示。机器指令机器指令机器指令机器指令o机器指令一般可根据其功能划分为以下几类：机

42、器指令一般可根据其功能划分为以下几类：(1)(1)控制指令；控制指令；(2)(2)算术运算指令；算术运算指令；(3)(3)逻辑逻辑运算指令；运算指令；(4)(4)移位操作指令；移位操作指令；(5)(5)传送操作传送操作指令；指令；(6)(6)输入输入/输出指令。输出指令。o应当注意的是，不同的机器，其指令系统是应当注意的是，不同的机器，其指令系统是不同的。不同的。o指令系统的日渐增大虽然给用户的程序设计指令系统的日渐增大虽然给用户的程序设计带来了方便，但也带来了硬件设计复杂性的带来了方便，但也带来了硬件设计复杂性的增加和因译码、存储、寻址等开销的增大而增加和因译码、存储、寻址等开销的增大而使运

43、算速度下降。研究发现，使运算速度下降。研究发现，指令系统存在指令系统存在着改进的必要和可能。着改进的必要和可能。指令系统指令系统指令系统指令系统ooCPU必须能够解码并执行的机器指令很少必须能够解码并执行的机器指令很少n n一旦计算机可以执行一些基本的而且是精一旦计算机可以执行一些基本的而且是精选的操作，加入额外的操作理论上是不会选的操作，加入额外的操作理论上是不会改变计算机的能力的改变计算机的能力的oo是否充分利用这种特性导致了两种不同的计是否充分利用这种特性导致了两种不同的计算机设计：算机设计：n nCISC(complexinstructionsetcomputer)n nRISC(re

44、ducedinstructionsetcomputer)CISCCISCoo最初人们采用的是进一步增强原有指令的功最初人们采用的是进一步增强原有指令的功能，并设置更为复杂的指令的方法能，并设置更为复杂的指令的方法oo采用这种设计思路的计算机被称为复杂指令采用这种设计思路的计算机被称为复杂指令系统计算机（系统计算机（CISC）。）。n nCISC的思路是由的思路是由IBM公司提出的，并以公司提出的，并以1964年年IBM研制的研制的IBM360系统为代表。系统为代表。CISCCISC缺点缺点缺点缺点oo80%的指令只在的指令只在20%的运行时间里用到；的运行时间里用到；oo一些指令非常繁杂，而执

45、行效率甚至比用几一些指令非常繁杂，而执行效率甚至比用几条简单的基本指令组合的实现还要慢。条简单的基本指令组合的实现还要慢。oo庞杂的指令系统也给超大规模集成电路庞杂的指令系统也给超大规模集成电路（VLSI）的设计带来了困难，的设计带来了困难，n n它不但不利于设计自动化技术的应用，延它不但不利于设计自动化技术的应用，延长了设计周期，增加了成本，长了设计周期，增加了成本，n n容易增加设计中出现错误的机会，从而降容易增加设计中出现错误的机会，从而降低了系统的可靠性。低了系统的可靠性。RISCo思路主要是通过减少指令总数和简化指令的思路主要是通过减少指令总数和简化指令的功能来降低硬件设计的复杂度，

46、从而提高指功能来降低硬件设计的复杂度，从而提高指令的执行速度。令的执行速度。o优点优点:与与CISC技术相比技术相比n简化了指令系统，适合超大规模集成电路简化了指令系统，适合超大规模集成电路的实现；的实现；n提高了机器执行的速度和效率；提高了机器执行的速度和效率；n降低了设计成本，提高了系统的可靠性；降低了设计成本，提高了系统的可靠性；n提供了直接支持高级语言的能力，简化了提供了直接支持高级语言的能力，简化了编译程序的设计。编译程序的设计。机器指令oo机器指令系统每台数字电子计算机在设计中，都规定了一组指令。oo机器语言用机器指令形式编写的程序。oo在裸机级，计算机语言关于算法的描述采用的是实

47、际机器的机器指令，它的符号集是0，1，n n支撑实际机器的理论是图灵机等计算模型；n n在图灵机等计算模型理论的指导下，有关设计形态的主要成果有冯诺依曼型计算机等具体实现思想和技术，以及各类数字电子计算机产品。计算机语言在裸机级所取得的主要成果计算机语言在裸机级所取得的主要成果计算机语言在裸机级所取得的主要成果计算机语言在裸机级所取得的主要成果计算机语言抽象理论设计裸 机级 的主 要内 容和 成果语言的符号集为：0，1；用机器指令对算法进行描述图灵机（过程语言的基础）、波斯特系统（字符串处理语言的基础）、-演算（函数式语言的基础）等计算模型冯诺依曼型计算机等实现技术；数字电子计算机产品4.4机

48、器指令与汇编语言机器指令与汇编语言4.4.2汇编语言汇编语言o汇编语言实际上是由一组汇编指令构成的语汇编语言实际上是由一组汇编指令构成的语言。每一条汇编指令用某个西文字符串的缩言。每一条汇编指令用某个西文字符串的缩写来表示其所代表的操作，用符号来代表数写来表示其所代表的操作，用符号来代表数据的二进制、八进制和十进制数字序列。大据的二进制、八进制和十进制数字序列。大多数情况下，一条汇编指令对应一条机器指多数情况下，一条汇编指令对应一条机器指令，少数对应几条机器指令。例如，下面是令，少数对应几条机器指令。例如，下面是几条汇编指令的操作符，右边中文是名称。几条汇编指令的操作符，右边中文是名称。add

49、add 加法加法 idividiv 有符号除法有符号除法 mulmul 无符无符号乘法号乘法 neg neg 求补求补 xchgxchg 交换交换 testtest 逻辑比较逻辑比较 jmpjmp 无条件转移无条件转移汇编语言汇编语言汇编语言汇编语言oo采采用用字字符符和和十十进进制制数数来来代代替替二二进进制制代代码码的的思思想。想。oo例例3.10对对2+6进行计算的算法描述进行计算的算法描述n n用机器指令对用机器指令对“2+6”进行计算的算法描述：进行计算的算法描述：oo1011000000000110oo0000010000000010oo1010001001010000000000

50、00n n汇编语言对汇编语言对“2+6”进行计算的算法描述：进行计算的算法描述：ooMOVALMOVAL，6 6ooADDALADDAL，2 2ooMOVVCMOVVC，ALALoo汇编语言语句与特定的机器指令有一一对应汇编语言语句与特定的机器指令有一一对应的关系，但是它毕竟不同于由二进制组成的的关系，但是它毕竟不同于由二进制组成的机器指令，它还需要经汇编程序翻译为机器机器指令，它还需要经汇编程序翻译为机器指令后才能运行。指令后才能运行。oo汇编语言源程序经汇编程序翻译成机器指令，汇编语言源程序经汇编程序翻译成机器指令，再在实际的机器中执行。再在实际的机器中执行。n n就汇编语言的用户而言，该