第4部分计算学科中的基本概念

上传人:re****.1 文档编号:570953602 上传时间:2024-08-07 格式:PPT 页数:234 大小:1.13MB
返回 下载 相关 举报
第4部分计算学科中的基本概念_第1页
第1页 / 共234页
第4部分计算学科中的基本概念_第2页
第2页 / 共234页
第4部分计算学科中的基本概念_第3页
第3页 / 共234页
第4部分计算学科中的基本概念_第4页
第4页 / 共234页
第4部分计算学科中的基本概念_第5页
第5页 / 共234页
点击查看更多>>
资源描述

《第4部分计算学科中的基本概念》由会员分享,可在线阅读,更多相关《第4部分计算学科中的基本概念(234页珍藏版)》请在金锄头文库上搜索。

1、第4部分计算学科中的基本概念Stillwatersrundeep.流静水深流静水深,人静心深人静心深Wherethereislife,thereishope。有生命必有希望。有生命必有希望4.1计算模型与二进制计算模型与二进制4.1.1计算模型与图灵机计算模型与图灵机计算模型与图灵机计算模型与图灵机计算模型与图灵机oo计算模型:计算模型:计算模型:计算模型:n n刻刻刻刻画画画画计计计计算算算算这这这这一一一一概概概概念念念念的的的的一一一一种种种种抽抽抽抽象象象象的的的的形形形形式式式式系系系系统统统统或或或或数数数数学学学学系统。系统。系统。系统。n n在在在在计计计计算算算算科科科科学学

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

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

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

5、由由一一条条两两端端可可无无限限延延长长的的带带子子、一一个个读写头以及一组控制读写头工作的命令组成,读写头以及一组控制读写头工作的命令组成,图灵机图灵机图灵机图灵机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机器内的五元组(qiSjSkR(

7、或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

20、 0、1 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

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

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

23、)10(0.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.

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

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

29、等。n n在在物物理理机机制制上上,数数字字代代码码以以数数字字型型信信号号出出现。现。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 unit

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

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

37、U和主存储器通过总线相连和主存储器通过总线相连和主存储器通过总线相连和主存储器通过总线相连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(complexinstructionsetcomp

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

45、到;oo一些指令非常繁杂,而执行效率甚至比用几一些指令非常繁杂,而执行效率甚至比用几条简单的基本指令组合的实现还要慢。条简单的基本指令组合的实现还要慢。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;用机器指令对算法进行描述图灵机(过程语言的基础)、波斯特系统(字符串处理语言的基础)、-演算(函数式语言的基础)等计算模型冯诺依曼型计算机等实现技

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

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

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

51、。n n就汇编语言的用户而言,该机器是可以直就汇编语言的用户而言,该机器是可以直接识别汇编语言的,从而产生了一个属于接识别汇编语言的,从而产生了一个属于抽象形态的重要概念,即抽象形态的重要概念,即虚拟机虚拟机的概念。的概念。n n一般说来,汇编程序被看成是系统软件的一般说来,汇编程序被看成是系统软件的一部分。一部分。 汇编语言o当然,汇编语言在可读性和编写程序时仍然当然,汇编语言在可读性和编写程序时仍然是不能令人满意的,这导致进一步发展了高是不能令人满意的,这导致进一步发展了高级程序设计语言。不过,由于高级语言在使级程序设计语言。不过,由于高级语言在使用时通常还是要通过编译程序逐步将高级语用时

52、通常还是要通过编译程序逐步将高级语言写的程序翻译成机器指令的程序,而这种言写的程序翻译成机器指令的程序,而这种翻译的结果往往不如机器指令或汇编语言写翻译的结果往往不如机器指令或汇编语言写的程序效率高,所以,直到今天,不少工程的程序效率高,所以,直到今天,不少工程师在系统软件的开发中还在使用机器指令和师在系统软件的开发中还在使用机器指令和汇编语言。汇编语言。4.5算法、数据结构与程序算法、数据结构与程序 求解一个给定的问题,不同的人常编写出不同的然而都是正确的程序,这是为什么呢? 这里存在两个层面的问题,一个是与计算方法密切相关的算法问题,另一个是程序设计的技术问题。 4.5算法、数据结构与程序

53、算法、数据结构与程序4.5.1算法算法的历史简介算法的历史简介算法的历史简介算法的历史简介 oo公元公元825年,阿拉伯数学家阿科瓦里茨米年,阿拉伯数学家阿科瓦里茨米(AlKhowarizmi)写了著名的波斯教科书写了著名的波斯教科书(Persian Textbook),),书中概括了进行四书中概括了进行四则算术运算的法则。则算术运算的法则。n n“算法算法”(Algorithm)一词就来源于这一词就来源于这位数学家的名字。位数学家的名字。oo后来,韦氏新世界词典将其定义为后来,韦氏新世界词典将其定义为“解解某种问题的任何专门的方法某种问题的任何专门的方法”。oo而据考古学家发现,古巴比伦人在

54、而据考古学家发现,古巴比伦人在求解代数求解代数方程方程时,就已经采用了时,就已经采用了“算法算法”的思想。的思想。丢番图方程的可解性问题丢番图方程的可解性问题丢番图方程的可解性问题丢番图方程的可解性问题 oo古希腊数学家丢番图(古希腊数学家丢番图(Diophantus):代数:代数学之父学之父n n在算术(在算术(Arithmetica)一书中提出了一书中提出了有关有关两个或多个变量整数系数方程两个或多个变量整数系数方程的有理的有理数解问题。数解问题。n n对于具有对于具有整数系数的不定方程整数系数的不定方程,如果只考,如果只考虑其虑其整数解整数解,这类方程就叫做丢番图方程。,这类方程就叫做丢

55、番图方程。oo“丢番图方程可解性问题丢番图方程可解性问题”的实质为:能否的实质为:能否写出一个可以判定写出一个可以判定任意丢番图方程是否可解任意丢番图方程是否可解的算法?的算法?一个未知数的线性丢番图方程的解一个未知数的线性丢番图方程的解一个未知数的线性丢番图方程的解一个未知数的线性丢番图方程的解ooax=b,只只要要a能能整整除除b,就就可可判判定定其其有有整整数解,该整数解即数解,该整数解即b/a。两个未知数的线性丢番图方程两个未知数的线性丢番图方程两个未知数的线性丢番图方程两个未知数的线性丢番图方程 的解的解的解的解ooaxax+ +byby= =c c,先求出先求出a a和和b b的最

56、大公因子的最大公因子d d,若若d d能能整除整除c c,则该方程有解(整数解)。则该方程有解(整数解)。 oo问:方程问:方程1313x x+26+26y y=52=52有无整数解?有无整数解?n n答:答:1313和和2626的最大公因子是的最大公因子是1313,1313又可整又可整除除5252,故该方程有整数解(如,故该方程有整数解(如x x=2=2,y y=1=1即即方程的解)。方程的解)。oo例例4.2 4.2 问:方程问:方程2 2x x+4+4y y=15=15有无整数解?有无整数解?n n答:答:2 2和和4 4的最大公因子是的最大公因子是2 2,2 2不能整除不能整除1515

57、,故该方程无整数解。,故该方程无整数解。 两个未知数的线性丢番图方程两个未知数的线性丢番图方程两个未知数的线性丢番图方程两个未知数的线性丢番图方程 的解:的解:的解:的解:欧几里德算法欧几里德算法欧几里德算法欧几里德算法 oo给给定定两两个个正正整整数数m和和n,求求它它们们的的最最大大公公因因子子,即能同时整除即能同时整除m和和n的最大正整数。的最大正整数。oo步骤如下:步骤如下:n n(1)以以n除除m,并并令令所所得得余余数数为为r(r必必小小于于n););n n(2)若若r=0,算算法法结结束束,输输出出结结果果n;否否则则,继续步骤(继续步骤(3););n n(3)将将n置置换换为为

58、m,r置置换换为为n,并并返返回回步步骤(骤(1)继续进行。)继续进行。例例例例4.34.3设设设设mm=56=56,n n=32=32,求求求求mm、n n的最大公因子的最大公因子的最大公因子的最大公因子算法如下算法如下:(1)32除除56余数为余数为24;(2)24除除32余数为余数为8;(3)8除除24余数为余数为0,算法结束,输出结果,算法结束,输出结果8。答:答:m、n的最大公因子为的最大公因子为8。oo欧几里德算法既表述了一个数的求解过程,欧几里德算法既表述了一个数的求解过程,n n又又表表述述了了一一个个判判定定过过程程,该该过过程程可可以以判判定定“m和和n是是互互质质的的”(

59、即即除除1以以外外,m和和n没没有公因子)这个命题的真假。有公因子)这个命题的真假。oo不难想象,不同的求解方法将产生出不同的不难想象,不同的求解方法将产生出不同的算法,不同的算法将使我们设计出不同的程算法,不同的算法将使我们设计出不同的程序,而决定这个程序功能的本质是计算方法序,而决定这个程序功能的本质是计算方法及其算法。一般地说,对不同计算方法过程及其算法。一般地说,对不同计算方法过程的抽象描述就产生了相应的不同算法,但同的抽象描述就产生了相应的不同算法,但同一算法由不同的人来写程序则完全可能设计一算法由不同的人来写程序则完全可能设计出差别很大的程序。出差别很大的程序。oo凭直觉想象给出的

60、算法往往不是最好的算法。凭直觉想象给出的算法往往不是最好的算法。算法算法算法的定义和特征算法的定义和特征 算法的定义和特征算法的定义和特征 算法算法被认为是计算科学的核心问题之一。被认为是计算科学的核心问题之一。 有关算法的定义不少,其内涵基本上是一致的,有关算法的定义不少,其内涵基本上是一致的,其中最为著名的是计算机科学家克努特在其经典巨其中最为著名的是计算机科学家克努特在其经典巨著著计算机程序设计的艺术计算机程序设计的艺术(The Art of The Art of Computer ProgrammingComputer Programming)第一卷中对算法的定义和)第一卷中对算法的定

61、义和特性所作的有关描述。特性所作的有关描述。1算法的一些定义算法的一些定义 oo定风定风定风定风1 1 1 1:给定问题和设备,一个算法是用该设备可理:给定问题和设备,一个算法是用该设备可理:给定问题和设备,一个算法是用该设备可理:给定问题和设备,一个算法是用该设备可理解的语言表示的,解决这个问题的一种方法的精确解的语言表示的,解决这个问题的一种方法的精确解的语言表示的,解决这个问题的一种方法的精确解的语言表示的,解决这个问题的一种方法的精确刻划。特别,算法具有下列特征属性:刻划。特别,算法具有下列特征属性:刻划。特别,算法具有下列特征属性:刻划。特别,算法具有下列特征属性: (1) (1)

62、(1) (1) 算法应用于一个具体的输入集合或问题描述算法应用于一个具体的输入集合或问题描述算法应用于一个具体的输入集合或问题描述算法应用于一个具体的输入集合或问题描述将在有穷步动作序列之后得到结果;将在有穷步动作序列之后得到结果;将在有穷步动作序列之后得到结果;将在有穷步动作序列之后得到结果; (2) (2) (2) (2) 该序列有一个唯一的初始动作;该序列有一个唯一的初始动作;该序列有一个唯一的初始动作;该序列有一个唯一的初始动作; (3) (3) (3) (3) 该序列中的每一个动作有一个唯一的后继动该序列中的每一个动作有一个唯一的后继动该序列中的每一个动作有一个唯一的后继动该序列中的

63、每一个动作有一个唯一的后继动作;作;作;作; (4) (4) (4) (4) 该序列终止时或者得到这个问题的解,或者该序列终止时或者得到这个问题的解,或者该序列终止时或者得到这个问题的解,或者该序列终止时或者得到这个问题的解,或者因该问题不可解而获得不可解说明。因该问题不可解而获得不可解说明。因该问题不可解而获得不可解说明。因该问题不可解而获得不可解说明。算法的定义和特征算法的定义和特征1算法的一些定义算法的一些定义 oo定风定风定风定风1 1 1 1:给定问题和设备,一个算法是用该设备可理:给定问题和设备,一个算法是用该设备可理:给定问题和设备,一个算法是用该设备可理:给定问题和设备,一个算

64、法是用该设备可理解的语言表示的,解决这个问题的一种方法的精确解的语言表示的,解决这个问题的一种方法的精确解的语言表示的,解决这个问题的一种方法的精确解的语言表示的,解决这个问题的一种方法的精确刻划。特别,算法具有下列特征属性:刻划。特别,算法具有下列特征属性:刻划。特别,算法具有下列特征属性:刻划。特别,算法具有下列特征属性: (1) (1) (1) (1) 算法应用于一个具体的输入集合或问题描述算法应用于一个具体的输入集合或问题描述算法应用于一个具体的输入集合或问题描述算法应用于一个具体的输入集合或问题描述将在有穷步动作序列之后得到结果;将在有穷步动作序列之后得到结果;将在有穷步动作序列之后

65、得到结果;将在有穷步动作序列之后得到结果; (2) (2) (2) (2) 该序列有一个唯一的初始动作;该序列有一个唯一的初始动作;该序列有一个唯一的初始动作;该序列有一个唯一的初始动作; (3) (3) (3) (3) 该序列中的每一个动作有一个唯一的后继动该序列中的每一个动作有一个唯一的后继动该序列中的每一个动作有一个唯一的后继动该序列中的每一个动作有一个唯一的后继动作;作;作;作; (4) (4) (4) (4) 该序列终止时或者得到这个问题的解,或者该序列终止时或者得到这个问题的解,或者该序列终止时或者得到这个问题的解,或者该序列终止时或者得到这个问题的解,或者因该问题不可解而获得不可

66、解说明。因该问题不可解而获得不可解说明。因该问题不可解而获得不可解说明。因该问题不可解而获得不可解说明。算法的定义和特征算法的定义和特征定义定义2(Knuth算法定义)算法定义) 一个算法,就是一个有穷规则的集合,其中之规则一个算法,就是一个有穷规则的集合,其中之规则确定了一个解决某一特定类型问题的运算序列。此外,确定了一个解决某一特定类型问题的运算序列。此外,算法的规则序列须满足如下五个重要条件(特性):算法的规则序列须满足如下五个重要条件(特性): (1) (1) 有穷性。算法必须总是在执行有穷步之后结束;有穷性。算法必须总是在执行有穷步之后结束; (2) (2) 确定性。算法的每一个步骤

67、必须是确切地定义确定性。算法的每一个步骤必须是确切地定义的;的; (3) (3) 输入。算法有零个或多个输入;输入。算法有零个或多个输入; (4) (4) 输出。算法有一个或多个输出,即与输入有某输出。算法有一个或多个输出,即与输入有某个特定关系的量;个特定关系的量; (5) (5) 能行性。算法中有待执行的运算和操作必须是能行性。算法中有待执行的运算和操作必须是相当基本的,即是说,它们原则上都是能够精确地进行相当基本的,即是说,它们原则上都是能够精确地进行的,而且用笔和纸做有穷次就可以完成。的,而且用笔和纸做有穷次就可以完成。2 2算法的重要特性算法的重要特性算法的重要特性算法的重要特性oo

68、有有穷穷性性:一一个个算算法法在在执执行行有有穷穷步步之之后后必必须须结束。结束。如如在在欧欧几几里里德德算算法法中中,由由于于m和和n均均为为正正整整数数,在在步步骤骤(1)之之后后,r必必小小于于n,若若r0,下下一一次次进进行行步步骤骤(1)时时,n的的值值已已经经减减小小,而而正正整整数数的的递递降降序序列列最最后后必必然然要要终终止止。因因此此,无无论论给给定定m和和n的的原原始始值值有有多多大大,步骤(步骤(1)的执行都是有穷次。)的执行都是有穷次。2 2算法的重要特性算法的重要特性算法的重要特性算法的重要特性oo确确定定性性:算算法法的的每每一一个个步步骤骤必必须须要要确确切切地

69、地定定义义。即即算算法法中中所所有有有有待待执执行行的的动动作作必必须须严严格格而而不不含含混地进行规定,不能有歧义性。混地进行规定,不能有歧义性。如如欧欧几几里里德德算算法法中中,步步骤骤(1)中中明明确确规规定定“以以n除除m”,而而不不能能有有类类似似“以以n除除m或或以以m除除n”这类有两种可能做法的规定。这类有两种可能做法的规定。oo输输入入:算算法法有有零零个个或或多多个个的的输输入入,即即在在算算法法开开始之前,对算法最初给出的量。始之前,对算法最初给出的量。如欧几里德算法中,有两个输入,即如欧几里德算法中,有两个输入,即m和和n。2 2算法的重要特性算法的重要特性算法的重要特性

70、算法的重要特性oo输输出出:算算法法有有一一个个或或多多个个的的输输出出,即即与与输输入入有有某某个个特特定定关关系系的的量量,简简单单地地说说就就是是算算法法的的最最终终结果。结果。如如在在欧欧几几里里德德算算法法中中只只有有一一个个输输出出,即即步步骤(骤(2)中的)中的n。oo能能行行性性:算算法法中中有有待待执执行行的的运运算算和和操操作作必必须须是是相当基本的。相当基本的。如:欧几里德算法最终得出正确的结果。如:欧几里德算法最终得出正确的结果。2 2算法的重要特性算法的重要特性算法的重要特性算法的重要特性oo输输出出:算算法法有有一一个个或或多多个个的的输输出出,即即与与输输入入有有

71、某某个个特特定定关关系系的的量量,简简单单地地说说就就是是算算法法的的最最终终结果。结果。如如在在欧欧几几里里德德算算法法中中只只有有一一个个输输出出,即即步步骤(骤(2)中的)中的n。oo能能行行性性:算算法法中中有有待待执执行行的的运运算算和和操操作作必必须须是是相当基本的。相当基本的。如:欧几里德算法最终得出正确的结果。如:欧几里德算法最终得出正确的结果。2 2算法的重要特性算法的重要特性算法的重要特性算法的重要特性oo有有穷穷性性和和能能行行性性是是算算法法最最重重要要的的两两个个特特征征。对对有有些些问问题题来来说说,如如果果我我们们给给出出了了一一个个类类似似于于算算法法的的有有穷

72、穷运运算算序序列列,而而它它对对某某些些输输入入可可能能不不停停机机,那那么么,我我们们就就称称这这样样的的运运算算序序列列为为一一个个过过程程。算算法法和和过过程程都都满满足足能能行行性性和和确确定定性性,唯唯一一的的本本质质区区别别是是算算法法的的执执行行必必须须终终止止,而而过过程程则则不不然然,它它可可以以永永不不停停止止。需需要要指指出出的的是是,高高级级程程序序设设计计语语言言中中也也有有过过程程的的概概念念,但但与与这这里里所所讲的过程不同,那里实际上指的是一种子程序。讲的过程不同,那里实际上指的是一种子程序。3算法的形式化定义算法的形式化定义 算法是一个四元组,即(算法是一个四

73、元组,即(Q,I,F)。)。其中:其中:(1)Q是是一一个个包包含含子子集集I和和的的集集合合,它它表表示示计计算的状态;算的状态;(2)I表示计算的输入集合;表示计算的输入集合;(3)表示计算的输出集合;表示计算的输出集合;(4)F表表示示计计算算的的规规则则,它它是是一一个个由由Q到到它它自自身身的的函函数数,且且具具有有自自反反性性,即即对对于于任任何何一一个个元元素素qQ,有有F(q)=q。算法算法算法实例算法实例 例例4.4求求1+2+3+100 设设变变量量X表表示示加加数数,Y表表示示被被加加数数,用用自自然然语语言言将算法描述如下:将算法描述如下:(1)将)将1赋值给赋值给X;

74、(2)将将2赋值给赋值给Y;(3)将将X与与Y相加,结果存放在相加,结果存放在X中;中;(4)将)将Y加加1,结果存放在,结果存放在Y中;中;(5)若若Y小小于于或或等等于于100,转转到到步步骤骤(3)继继续续执行;否则,算法结束,结果为执行;否则,算法结束,结果为X。例例4.5求解调和级数求解调和级数设变量设变量X表示累加和,变量表示累加和,变量I表示循环的次数,自表示循环的次数,自然语言描述算法如下:然语言描述算法如下:(1)将)将0赋值给赋值给X;(2)将将1赋值给赋值给I;(3)将将X与与1/I相加,然后把结果存入相加,然后把结果存入X;(4)将将I加加1;(5)若)若I大于等于大于

75、等于N,算法结束,结果为算法结束,结果为X;否否则转到步骤(则转到步骤(3)继续执行。)继续执行。例例例例4.64.6求解斐波那契数求解斐波那契数求解斐波那契数求解斐波那契数 0 0,1 1,1 1,2 2,3 3,5 5,8 8,1313,2121,3434, (1 1)oo来来 源源 于于 12021202年年 意意 大大 利利 数数 学学 家家 斐斐 波波 那那 契契( L.P.FibonacciL.P.Fibonacci) 在在 其其 珠珠 算算 之之 书书 (Liber Liber AbaciAbaci)中中提提出出的的一一个个“兔兔子子问问题题”:n n假假设设一一对对刚刚出出生生

76、的的兔兔子子一一个个月月后后就就能能长长大大,再再过过一一个个月月就就能能生生下下一一对对兔兔子子,并并且且此此后后每每个个月月都都能能生生一一对对兔兔子子,且且新新生生的的兔兔子子在在第二个月后也是每个月生一对兔子。第二个月后也是每个月生一对兔子。n n问问:一一对对兔兔子子一一年年内内可可繁繁殖殖成成多多少少对对兔兔子子?oo在在序序列列(1)中中,每每个个数数都都是是它它的的前前两两个个数数之之和和,Fn表表示示这这个个序序列列的的第第n个个数数,该该序序列列可以形式化的定义为:可以形式化的定义为:n nF0=0,F1=1,Fn+2=Fn+1+Fn,n0oo斐斐波波那那契契数数列列还还是

77、是一一个个关关于于加加法法算算法法的的典典型型实例。实例。oo设变量设变量X表示前一个数的值,即定义中的表示前一个数的值,即定义中的Fn,变量变量Y表示当前数的值,即定义中的表示当前数的值,即定义中的Fn+1,变变量量Z表示后一个数的值,即定义中的表示后一个数的值,即定义中的Fn+2。那那么求解问题的自然语言描述如下:么求解问题的自然语言描述如下:算法设计算法设计算法设计算法设计(1 1)如如如如果果果果=0=0,那那那那么么么么将将将将0 0赋赋赋赋值值值值给给给给Y Y,并并并并输输输输出出出出Y Y,转转转转步步步步骤骤骤骤(1111)继续执行;)继续执行;)继续执行;)继续执行;(2

78、2)将)将)将)将0 0赋给赋给赋给赋给X X,将将将将1 1赋值给赋值给赋值给赋值给Y Y;(3 3)输出输出输出输出X X、Y Y;(4 4)将将将将1 1赋值给赋值给赋值给赋值给I I;(5 5)如如如如果果果果I I大大大大于于于于-1-1,则则则则转转转转到到到到步步步步骤骤骤骤(1111),否否否否则则则则继继继继续续续续执执执执行;行;行;行;(6 6)将)将)将)将X X和和和和Y Y的和赋值给的和赋值给的和赋值给的和赋值给Z Z;(7 7)将将将将Y Y赋值给赋值给赋值给赋值给X X;(8 8)将将将将Z Z赋值给赋值给赋值给赋值给Y Y;(9 9)将将将将Y Y输出;输出;

79、输出;输出;(1010)将)将)将)将I I加加加加1 1,转步骤(,转步骤(,转步骤(,转步骤(5 5)继续执行;)继续执行;)继续执行;)继续执行;(1111)算法结束。)算法结束。)算法结束。)算法结束。算法算法算法的表示方法算法的表示方法原语原语原语原语oo一个算法的表达需要使用一些语言形式一个算法的表达需要使用一些语言形式n n自然语言自然语言“Visitinggrandchildrencanbenerve-racking”,可能即意味着孙子孙女导致了可能即意味着孙子孙女导致了很多问题,也表示去看他们可能会有问题很多问题,也表示去看他们可能会有问题n n图形语言:很少人能够根据折纸图

80、给出的步图形语言:很少人能够根据折纸图给出的步骤成功地叠出一只鸟来,但一个专门学习过骤成功地叠出一只鸟来,但一个专门学习过折纸的学生可以轻松完成折纸的学生可以轻松完成oo当用来描述算法的语言并没有被准确定义或者没当用来描述算法的语言并没有被准确定义或者没有给予足够信息的时候,交流就会产生问题有给予足够信息的时候,交流就会产生问题原语原语原语原语oo通过建立一个可以描述算法的意义明确的基通过建立一个可以描述算法的意义明确的基本块(本块(原语原语)集合,计算机科学即就可以解)集合,计算机科学即就可以解决上述的勾通问题决上述的勾通问题oo原语描述算法需要建立一个统一的细节描述原语描述算法需要建立一个

81、统一的细节描述级别,原语连同一组表达了原语如何表达复级别,原语连同一组表达了原语如何表达复杂的想法的规定组成了一种程序设计语言杂的想法的规定组成了一种程序设计语言oo组成组成n n语法:原语的符号表示语法:原语的符号表示n n语义:表达了原语的意义语义:表达了原语的意义1 1自然语言自然语言自然语言自然语言oo缺点缺点n n由由于于自自然然语语言言的的歧歧义义性性,容容易易导导致致算算法法执行的不确定性;执行的不确定性;n n自自然然语语言言的的语语句句一一般般太太长长,从从而而导导致致了了用自然语言描述的算法太长;用自然语言描述的算法太长;n n由由于于自自然然语语言言表表示示的的串串行行性

82、性,因因此此,当当一一个个算算法法中中循循环环和和分分支支较较多多时时就就很很难难清清晰地表示出来;晰地表示出来;n n自自然然语语言言表表示示的的算算法法不不便便翻翻译译成成计计算算机机程序设计语言理解的语言。程序设计语言理解的语言。2 2流程图流程图流程图流程图 oo它它 采采 用用 美美 国国 国国 家家 标标 准准 化化 协协 会会ANSI( AmericanNationalStandardInstitute)规定的一组图形符号来表示算法。规定的一组图形符号来表示算法。n n流流程程图图可可以以很很方方便便地地表表示示顺顺序序、选选择择和和循循环环结结构构,而而任任何何程程序序的的逻逻

83、辑辑结结构构都都可可以用顺序、选择和循环结构来表示,以用顺序、选择和循环结构来表示,n n流程图可以表示任何程序的逻辑结构。流程图可以表示任何程序的逻辑结构。n n用用流流程程图图表表示示的的算算法法不不依依赖赖于于任任何何具具体体的计算机和计算机程序设计语言,的计算机和计算机程序设计语言,(1 1)求解例)求解例)求解例)求解例4.44.4的算法流程图的算法流程图的算法流程图的算法流程图(2 2)求解例)求解例)求解例)求解例4.54.5的算法流程图的算法流程图的算法流程图的算法流程图 (3 3)求解例)求解例)求解例)求解例4.64.6的算法流程图的算法流程图的算法流程图的算法流程图 3

84、3伪代码伪代码伪代码伪代码(1 1)求解例)求解例)求解例)求解例4.44.4的伪代码算法描述:的伪代码算法描述:的伪代码算法描述:的伪代码算法描述:BEGIN(BEGIN(算法开始算法开始算法开始算法开始) )1 1 X X 2 2YYwhilewhile(Y=100Y=n)while(I=n)ENDEND(算法结束)算法结束)算法结束)算法结束)(3 3)例)例)例)例4.64.6的伪代码算法描述:的伪代码算法描述:的伪代码算法描述:的伪代码算法描述: BEGINBEGINifn=0ifn=0 0 0YYPrintYPrintY elseelse 0 0XX1 1YYPrintXPrint

85、X,Y Yfor(i=1;i=n-1;i+)for(i=1;i=n-1;i+) X+YZX+YZYXYXZYZYPrintYPrintY ENDEND4 4计算机程序设计语言计算机程序设计语言计算机程序设计语言计算机程序设计语言 oo计计算算机机程程序序设设计计语语言言描描述述的的算算法法(程程序序)是是清晰的、简明的,最终也能由计算机处理的。清晰的、简明的,最终也能由计算机处理的。oo缺点:缺点:n n算算法法的的基基本本逻逻辑辑流流程程难难于于遵遵循循。与与自自然然语语言一样,程序设计语言也是基于串行的言一样,程序设计语言也是基于串行的n n用用特特定定程程序序设设计计语语言言编编写写的的

86、算算法法限限制制了了与与他人的交流,不利于问题的解决;他人的交流,不利于问题的解决;n n要要花花费费大大量量的的时时间间去去熟熟悉悉和和掌掌握握某某种种特特定定的程序设计语言;的程序设计语言;n n要要求求描描述述计计算算步步骤骤的的细细节节,而而忽忽视视算算法法的的本质。本质。例例例例4.44.4的计算机程序设计语言(的计算机程序设计语言(的计算机程序设计语言(的计算机程序设计语言(C C语言)的算法描述:语言)的算法描述:语言)的算法描述:语言)的算法描述: main()main() intX,Y;intX,Y;X=1;X=1;Y=2;Y=2;while(Y=100)while(Y=10

87、0)X=X+Y;X=X+Y;Y=Y+1;Y=Y+1;printf(%d,X);printf(%d,X); 例例例例4.54.5的计算机程序设计语言(的计算机程序设计语言(的计算机程序设计语言(的计算机程序设计语言(C C语言)的算法描述语言)的算法描述语言)的算法描述语言)的算法描述 main()main() intn;intn;floatX,I;floatX,I;printf(Pleaseinputn:);printf(Pleaseinputn:);scanf(%d,&n);scanf(%d,&n);X=0;X=0;I=1;I=1;dodoX=X+1/I;X=X+1/I;I=I+1;I=I+

88、1;while(I=n);while(I=n);printf(n%f,X);printf(n%f,X);算法算法算法分析算法分析oo在在计计算算机机科科学学研研究究中中,事事实实上上存存在在一一条条规规律律:一一个个问问题题,当当它它的的描描述述及及其其求求解解方方法法或或求求解解过过程程可可以以用用构构造造性性数数学学描描述述,而而且且该该问问题题所所涉涉及及的的论论域域为为有有穷穷,或或虽虽为为无无穷穷但但存存在在有有穷穷表表示示时时,那那么么,这这个个问问题题一一定定能能用用计计算算机机来来求解;求解;oo反反过过来来,凡凡是是能能用用计计算算机机求求解解的的问问题题,也也一一定定能能对

89、对该该问问题题的的求求解解过过程程数数学学化化,而而且且这这种种数学化是构造性的。数学化是构造性的。算法分析考虑的问题;算法分析考虑的问题;算法分析考虑的问题;算法分析考虑的问题; oo当当一一个个问问题题的的求求解解获获得得了了计计算算方方法法和和算算法法时时,并并不不等等于于万万事事大大吉吉了了。在在许许多多情情况况下下,找找到到求求解解一一个个问问题题的的算算法法只只是是走走完完了了第第一一步步。至至于于现现实实是是否否可可以以计计算算,则则取取决决于于算算法法的的存存在在性性和和计计算算的的复复杂杂性性,即即取取决决于于该该问问题题是是否否存存在在求求解解算算法法,算算法法所所需需要要

90、的的时时间间和和空空间间在在数数量级上能否被接受。量级上能否被接受。oo要要注注意意的的是是,有有的的问问题题虽虽然然存存在在求求解解问问题题的的计计算算方方法法,但但是是,不不存存在在算算法法。原原因因有有两两种种可可能能:一一是是计计算算方方法法可可能能不不是是构构造造性性的的;二二是是虽虽为为构构造造性性的的,但但计计算算方方法法不不能能保保证证计计算算过程在任何初值的情况下都能结束。过程在任何初值的情况下都能结束。算法分析考虑的问题;算法分析考虑的问题;算法分析考虑的问题;算法分析考虑的问题; oo解解一一个个问问题题,往往往往有有若若干干不不同同的的算算法法,这这些些算算法法决决定定

91、着着根根据据该该算算法法编编写写的的程程序序性性能能的的好好坏坏。那那么么,在在保保证证算算法法正正确确性性的的前前提提下下,如如何确定算法的优劣就是一个值得研究的课题。何确定算法的优劣就是一个值得研究的课题。oo在算法的分析中,一般应考虑以下在算法的分析中,一般应考虑以下3个问题:个问题:(1)算法的时间复杂度;算法的时间复杂度;(2)算法的空间复杂度;)算法的空间复杂度;(3)算法是否便于阅读、修改和测试。)算法是否便于阅读、修改和测试。算法分析考虑的问题;算法分析考虑的问题;算法分析考虑的问题;算法分析考虑的问题; oo使使用用计计算算机机计计算算各各种种问问题题,需需要要存存储储空空间

92、间、计计算算时时间间。不不同同的的算算法法计计算算所所需需要要的的时时间间和和空空间间是是不不同同的的。所所谓谓算算法法的的复复杂杂性性就就是是对对算算法法计计算算所所需需要要的的时时间间和和空空间间的的一一种种度度量量。由由于于不不同同的的计计算算机机千千差差万万别别,运运算算速速度度和和字字长长可可以以相相差差很很大大,因因此此,不不可可能能用用算算法法在在某某一一台台计计算算机机上上计计算算所所需需要要的的实实际际的的时时间间和和存存储储单单元元(空空间间)去去衡衡量量这这个个算算法法的的复复杂杂性性。那那么么,怎怎样样才才能能准准确确刻刻划划算算法法的的计计算算复复杂杂性性呢呢?什么是

93、算法的复杂性呢?什么是算法的复杂性呢?什么是算法的复杂性呢?什么是算法的复杂性呢?oo科科学学家家们们采采用用了了与与问问题题规规模模大大小小相相联联系系的的一一个个近近似似函函数数(称称为为渐渐近近增增长长率率)来来刻刻画画算算法法的的计计算算复复杂杂度度。该该函函数数表表示示了了算算法法随随问问题题规规模模大大小小变变化化引引起起的的算算法法中中抽抽象象的的基基本本运运算算执执行的次数或存储空间量的变化规律。行的次数或存储空间量的变化规律。oo例例如如,某某个个计计算算问问题题当当输输入入规规模模分分别别为为1,2,3,n时时,经经分分析析算算法法中中抽抽象象的的基基本本运运算算次次数数分

94、分别别为为1,4,9,n2,那那么么,就就可可以以用用函函数数n2来来刻刻划划这这个个算算法法的的时时间间复复杂杂性性,并称这个算法的时间复杂性度量为并称这个算法的时间复杂性度量为 (n2)级。级。(1 1)算法的时间复杂度;)算法的时间复杂度;)算法的时间复杂度;)算法的时间复杂度; oo有有了了复复杂杂性性度度量量函函数数,一一旦旦选选定定具具体体计计算算机机,可可以以根根据据这这台台计计算算机机对对某某个个n值值的的实实际际运运算算速速度度比比较较准准确确地地估估算算出出对对其其他他的的n值值完完成成计计算算所所需要的时间。需要的时间。oo于于是是,对对各各种种算算法法的的复复杂杂性性进

95、进行行分分析析的的关关键键是是要要设设法法去去找找出出这这样样的的函函数数,它它涉涉及及到到与与数数学学密密切切相相关关的的算算法法的的设设计计原原理理、思思想想和和方方法法,算法分析是具有智力挑战性的研究课题。算法分析是具有智力挑战性的研究课题。(1 1)算法的时间复杂度;)算法的时间复杂度;)算法的时间复杂度;)算法的时间复杂度; oo用用T(n)表示,表示,n表示问题规模的大小。表示问题规模的大小。oo使用一个记号使用一个记号 n nOrder(数量级)的第一个字母,数量级)的第一个字母,n n允允 许许 使使 用用 “=”代代 替替 “”。 如如 n2+n+1= (n2)(1 1)算法

96、的时间复杂度;)算法的时间复杂度;)算法的时间复杂度;)算法的时间复杂度; (1 1)算法的时间复杂度;)算法的时间复杂度;)算法的时间复杂度;)算法的时间复杂度; oo设设f(n)是是一一个个关关于于正正整整数数n的的函函数数,若若存存在在一一个个 正正 整整 数数 n0和和 一一 个个 常常 数数 C, 当当 nn0时时 , T(n) Cf(n) 均均成成立立,则则称称f(n)为为T(n)的的同同数量级的函数。数量级的函数。n n算法时间复杂度算法时间复杂度T(n)可表示为:可表示为:T(n)= (f(n)常见的大常见的大常见的大常见的大 表示形式有:表示形式有:表示形式有:表示形式有:

97、(1):称为常数级;:称为常数级; (logn):称为对数级;称为对数级; (n):称为线性级;:称为线性级; (nc):称为多项式级;:称为多项式级; (cn):称为指数级;:称为指数级; (n!):称为阶乘级。:称为阶乘级。在在梵梵天天塔塔问问题题中中,需需要要移移动动的的盘盘子子次次数数为为h(n)=2n-1,则则该该问问题题的的算算法法时时间间复复杂杂度度表表示示为为 (2n);例例4.4的的算算法法时时间间复复杂杂度度表表示示为为 (1);例例4.5的的算算法法时时间间复复杂杂度度表表示示为为 (n);例例4.6的算法时间复杂度表示为的算法时间复杂度表示为 (n)等等。等等。 一一般

98、般而而言言,对对于于较较复复杂杂的的算算法法,应应将将它它分分成成容容易易估估算算的的几几个个部部分分,然然后后用用 的的求求解解原原则则计计算算整整个个算算法法的的时时间间复复杂杂度度,最最好好不不要要采采用用指指数数级级和和阶阶乘乘级级的的算算法法,而而应应尽尽可可能能选选用用多多项项式式级级或或线线性性级级等等时时间间复复杂杂度度较较小小的的算算法法。另另外外,还还要要在在算算法法最最好好、平平均均和和最最坏坏的的情情况况下区别执行效率的不同。下区别执行效率的不同。在在阶阶乘乘级级的的算算法法中中,如如果果问问题题规规模模n为为10,则则算算法法时时间间复复杂杂度度为为10!(3,628

99、,800)。若若要要检检验验10!种种情情况况,设设每每种种情情况况需需要要1毫毫秒秒的的计计算算时时间间,则则整整个个计计算算将将需需1小小时时左左右右。一一般般来来说说,如如果果选选用用了了阶阶乘乘级级的的算算法法,则则当当问问题题规规模模等等于于或或者者大大于于10时时,就就要要认认真真考考虑虑算算法的适用性问题。法的适用性问题。算法的空间复杂度算法的空间复杂度算法的空间复杂度算法的空间复杂度oo指算法在执行过程中所占存储空间的大小,指算法在执行过程中所占存储空间的大小,oo用用S(n)表示,表示,S为英文单词为英文单词Space的第一个字的第一个字母。与算法的时间复杂度相同母。与算法的

100、时间复杂度相同oo算法的空间复杂度算法的空间复杂度S(n)也可表示为:也可表示为: S(n)= (g(n)。算法算法算法的研究算法的研究算法算法oo算法:定义一项工作如何完成的步骤的集合算法:定义一项工作如何完成的步骤的集合n n在一台机器可以完成一个任务之前,必须在一台机器可以完成一个任务之前,必须找到完成这个任务的算法并且用与机器兼找到完成这个任务的算法并且用与机器兼容的方式来描述容的方式来描述n n一个与机器兼容的算法的描述一个与机器兼容的算法的描述程序程序oo算法的研究开始是作为数学的一个学科算法的研究开始是作为数学的一个学科n n目标:找到描述特定类型问题是如何被解目标:找到描述特定

101、类型问题是如何被解决的指令的集合,如决的指令的集合,如Euclidean算法算法n n一旦一个完成任务的算法被找到,任务的一旦一个完成任务的算法被找到,任务的实现就不再需要对算法原理的理解,任务实现就不再需要对算法原理的理解,任务的实现仅仅是遵循算法的只是过程的实现仅仅是遵循算法的只是过程n n现有的解决问题需要的智慧被编码进了算现有的解决问题需要的智慧被编码进了算法法算法转化为智慧算法转化为智慧算法转化为智慧算法转化为智慧oo通过使用算法来得到并转化智慧,我们才可通过使用算法来得到并转化智慧,我们才可以构建起可以表现以构建起可以表现智慧行为的机器智慧行为的机器。n n机器表现的智能等级受到通

102、过算法转化的机器表现的智能等级受到通过算法转化的智慧所限制智慧所限制n n如果没有解决问题的算法,意味着问题的如果没有解决问题的算法,意味着问题的解决方案超出了机器的能力范围解决方案超出了机器的能力范围oo算法的开发就成了计算机领域的一个主要目算法的开发就成了计算机领域的一个主要目标标n n如何找到算法如何找到算法一个十分接近于寻找通一个十分接近于寻找通用问题解决方案用问题解决方案n n描述这个算法描述这个算法转变为一个清晰的指令转变为一个清晰的指令的集合(程序设计语言描述)的集合(程序设计语言描述)计算机技术别用于复杂问题(大型软件系统)计算机技术别用于复杂问题(大型软件系统)计算机技术别用

103、于复杂问题(大型软件系统)计算机技术别用于复杂问题(大型软件系统)oo不仅仅包括实现任务的单个算法的开发不仅仅包括实现任务的单个算法的开发n n还要求对组件之间的交互进行设计还要求对组件之间的交互进行设计n n软件工程:借鉴了工程领域、项目管理领软件工程:借鉴了工程领域、项目管理领域、人力资源管理以及程序语言设计领域域、人力资源管理以及程序语言设计领域的经验的经验执行算法的机器的设计和实现执行算法的机器的设计和实现执行算法的机器的设计和实现执行算法的机器的设计和实现oo数据的存储数据的存储oo数据的操作数据的操作oo体系结构中涵盖了对现今技术的讨论体系结构中涵盖了对现今技术的讨论n n我们的目

104、标不是去熟知类似当今体系结构我们的目标不是去熟知类似当今体系结构是如何用电路来实现这样的细节问题,那是如何用电路来实现这样的细节问题,那将会导致过分陷入电子工程学科将会导致过分陷入电子工程学科n n正如昨天的齿轮驱动的计算机让位于电子正如昨天的齿轮驱动的计算机让位于电子设备一样,今天的电子技术也许很快也被设备一样,今天的电子技术也许很快也被其它的技术所取代其它的技术所取代理想情况下理想情况下oo希望计算机的体系结构是我们的有关算法过希望计算机的体系结构是我们的有关算法过程知识的延续,并且不应该被技术能力酸限程知识的延续,并且不应该被技术能力酸限制制n n使我们的算法知识在当代机器体系结构的使我

105、们的算法知识在当代机器体系结构的发展背后起推动作用,而不仅仅是从技术发展背后起推动作用,而不仅仅是从技术的要求触发来解顶机器的设计的要求触发来解顶机器的设计oo构建允许使用多个指令序列来代替算法的机构建允许使用多个指令序列来代替算法的机器是可能的器是可能的n n这些指令被同时执行或者作为这些指令被同时执行或者作为机器于外部世界的接口的设计于计算机的设计紧密相连机器于外部世界的接口的设计于计算机的设计紧密相连机器于外部世界的接口的设计于计算机的设计紧密相连机器于外部世界的接口的设计于计算机的设计紧密相连oo算法是如何机器中的?算法是如何机器中的?oo机器是如何被告知执行的是哪一个算法?机器是如何

106、被告知执行的是哪一个算法?计算理论计算理论oo对解决越来越复杂问题的算法的研究对解决越来越复杂问题的算法的研究n n导致了算法过程的最终限制问题导致了算法过程的最终限制问题n n如果没有算法可以解决这个问题,那么算法如果没有算法可以解决这个问题,那么算法是不能被机器所解决的,机器仅仅可以解决是不能被机器所解决的,机器仅仅可以解决在算法上可解的问题在算法上可解的问题ooGodel的不完全定理阐述了的不完全定理阐述了n n在任何传统算术领域的数学理论中,有些是在任何传统算术领域的数学理论中,有些是既不能证明有不能被推翻的既不能证明有不能被推翻的n n任何对算术系统的彻底研究都超出了算法的任何对算术

107、系统的彻底研究都超出了算法的能力能力n n对算法的限制的研究欲望似的数学家们设计对算法的限制的研究欲望似的数学家们设计抽象的机器来执行算法,并在理论上研究这抽象的机器来执行算法,并在理论上研究这些假想机器的能力。些假想机器的能力。4.5算法、数据结构与程序算法、数据结构与程序4.5.2数据结构4.5.2 数据结构数据结构:一类定性数学模型一类定性数学模型 1.数据结构的基本概念数据结构的基本概念数据结构的基本概念数据结构的基本概念 oo数学模型有定量模型和定性模型两类之分。数学模型有定量模型和定性模型两类之分。定量模型指的是可以用数值方程表示的一定量模型指的是可以用数值方程表示的一类模型,而定

108、性模型则是指非数值性的数类模型,而定性模型则是指非数值性的数据结构(如表、树和图等)及其运算。据结构(如表、树和图等)及其运算。oo在计算领域中,数据结构(在计算领域中,数据结构(DataStructure)指的是一类定性数学模型,它)指的是一类定性数学模型,它是计算机算法设计的基础,它在计算科学是计算机算法设计的基础,它在计算科学中占有十分重要的地位。中占有十分重要的地位。数据结构的基本概念数据结构的基本概念 oo组成:数据结构是一类定性的数学模型,组成:数据结构是一类定性的数学模型,它由以下它由以下3部分组成部分组成n n逻辑结构逻辑结构n n存储结构(或称物理结构)存储结构(或称物理结构

109、)n n运算运算oo数据逻辑结构的形式化定义数据逻辑结构的形式化定义 DS=其中:其中: D表示数据的集合;表示数据的集合; R表示数据表示数据D上关系的集合上关系的集合。数据数据oo数据(数据(Data)是描述客观事物的数字、字)是描述客观事物的数字、字符以及所有能输人到计算机中并被计算机符以及所有能输人到计算机中并被计算机程序处理的符号的集合。它是计算机加工程序处理的符号的集合。它是计算机加工处理的对象,是信息的载体。例如,一个处理的对象,是信息的载体。例如,一个代数方程求解程序中所用的数据是整数、代数方程求解程序中所用的数据是整数、实数;而一个翻译程序中所用的数据是字实数;而一个翻译程序

110、中所用的数据是字符串。随着计算机软、硬件的发展,计算符串。随着计算机软、硬件的发展,计算机应用领域的扩大,数据的含义也随之拓机应用领域的扩大,数据的含义也随之拓宽了。在多媒体计算机中,描述图象和声宽了。在多媒体计算机中,描述图象和声音的符号都属于数据的范畴。音的符号都属于数据的范畴。数据元素数据元素 oo数据元素(数据元素(数据元素(数据元素(DataElementDataElement)是数据的抽象的基本)是数据的抽象的基本)是数据的抽象的基本)是数据的抽象的基本单元,有时也称为结点(单元,有时也称为结点(单元,有时也称为结点(单元,有时也称为结点(nodenode)或记录)或记录)或记录)

111、或记录(recordrecord)。至于它的具体含义,在不同的情况)。至于它的具体含义,在不同的情况)。至于它的具体含义,在不同的情况)。至于它的具体含义,在不同的情况下可以有不同的含义。它可以是一个字符、一个下可以有不同的含义。它可以是一个字符、一个下可以有不同的含义。它可以是一个字符、一个下可以有不同的含义。它可以是一个字符、一个数或一个记录,也可以是其它更加复杂的数据。数或一个记录,也可以是其它更加复杂的数据。数或一个记录,也可以是其它更加复杂的数据。数或一个记录,也可以是其它更加复杂的数据。例如,一张英文字母表(例如,一张英文字母表(例如,一张英文字母表(例如,一张英文字母表(A A,

112、B B,。,。,。,。C C,Z Z)中的数据元素是字母,可以表示为集合中的数据元素是字母,可以表示为集合中的数据元素是字母,可以表示为集合中的数据元素是字母,可以表示为集合N=AN=A,B B,C C,ZZ。这组元素的数目是有限的,计算。这组元素的数目是有限的,计算。这组元素的数目是有限的,计算。这组元素的数目是有限的,计算机所能处理的数据元素也只能是有限的。机所能处理的数据元素也只能是有限的。机所能处理的数据元素也只能是有限的。机所能处理的数据元素也只能是有限的。oo数据元素也可以是一个统计表中的一个记录,数据元素也可以是一个统计表中的一个记录,数据元素也可以是一个统计表中的一个记录,数据

113、元素也可以是一个统计表中的一个记录,如某班学生的一门课程的成绩单。如某班学生的一门课程的成绩单。如某班学生的一门课程的成绩单。如某班学生的一门课程的成绩单。 数据的逻辑结构数据的逻辑结构 oo逻辑结构:描述计算机的数据之间的逻辑关系。oo实际上,逻辑结构就是数据结构中定义的关系集合R,反映的是数据元素间的逻辑关系,它无需考虑数据在计算机中的具体存储方式,是独立于计算机的。数据的存储结构数据的存储结构 oo数据的存储结构是指在反映数据逻辑关系的数据的存储结构是指在反映数据逻辑关系的原则下,数据在存储器中的存储方式。原则下,数据在存储器中的存储方式。n n顺序存储结构:借助元素在存储器中的相顺序存

114、储结构:借助元素在存储器中的相对位置来表示数据元素的逻辑关系。对位置来表示数据元素的逻辑关系。n n链式存储结构:借助指针来表示数据元素链式存储结构:借助指针来表示数据元素之间的逻辑关系,通常在数据元素上增加之间的逻辑关系,通常在数据元素上增加一个或多个指针类型的属性来实现这种表一个或多个指针类型的属性来实现这种表示方式。示方式。数据的存储结构数据的存储结构 oo顺序存储结构简单,存储空间使用较紧凑,可以节省存放指针所需的大量空间;但另一方面它要求连续的存储空间,当数据元素的数目不固定,譬如说需要不断扩充时,则必须按最大要求空间设计(即数组上限),这就会有大量空间在当前闲置不用,造成浪费,而且

115、这最大要求空间也往往很难事先估计。数据的存储结构数据的存储结构 oo链接存储结构则不要求连续存储空间,使用较灵活,应用面也较广。缺点是结点指针要占用额外的存储空间。但从另一方面看,对于采用链接存储结构的数据结构来说,其将来数据元素的扩充可以不必事先为它保留专用的备用空间,就这个意义上说,反而是节省了存储空间。数据的存储结构数据的存储结构 oo与逻辑结构相反,存储结构依赖于实体的计算机,无论在形式上还是在顺序上都可能和数据的逻辑结构不同,它与所使用的存储设备以及采用的存储方法密切相关。oo数据结构研究的内容着重在数据的逻辑结构,但也必然涉及到其存储结构。常用的几种数据结构操作常用的几种数据结构操

116、作oo常用的有以下几种:常用的有以下几种: (1 1)检检检检索索索索检检检检索索索索就就就就是是是是在在在在给给给给定定定定的的的的数数数数据据据据结结结结构构构构中中中中,找找找找出出出出满满满满足足足足一一一一定定定定条条条条件件件件的的的的数数数数据据据据元元元元素素素素,这这这这个个个个条条条条件件件件往往往往 往往往往是是是是某某某某个个个个或或或或某几个数据项的值。某几个数据项的值。某几个数据项的值。某几个数据项的值。 (2 2)排排排排序序序序根根根根据据据据某某某某一一一一给给给给定定定定的的的的条条条条件件件件,将将将将数数数数据据据据结结结结构构构构中中中中的的的的所有数

117、据元素重新排列顺序。所有数据元素重新排列顺序。所有数据元素重新排列顺序。所有数据元素重新排列顺序。 (3 3)插插插插入入入入在在在在一一一一个个个个给给给给定定定定的的的的数数数数据据据据结结结结构构构构中中中中,根根根根据据据据某某某某些些些些条条条条件,将一个数据元素插入到一个合适件,将一个数据元素插入到一个合适件,将一个数据元素插入到一个合适件,将一个数据元素插入到一个合适 的位置。的位置。的位置。的位置。 (4 4)删删删删除除除除根根根根据据据据一一一一定定定定的的的的条条条条件件件件,将将将将某某某某个个个个数数数数据据据据元元元元素素素素从从从从数数数数据结构中删除。据结构中删

118、除。据结构中删除。据结构中删除。(5 5)修改修改数据结构中某个指定数据元素的值。)修改修改数据结构中某个指定数据元素的值。)修改修改数据结构中某个指定数据元素的值。)修改修改数据结构中某个指定数据元素的值。4.5.2 4.5.2 数据结构:一类定性数学数据结构:一类定性数学模型模型 2. 常用的几种数据结构常用的几种数据结构 线性表线性表线性表线性表oo线性表是线性表是n个数据元素的有限序列,即(个数据元素的有限序列,即(X1,X2,X3,Xi,Xn)oo基本操作基本操作插入、删除和存取数据元素插入、删除和存取数据元素oo几种特殊的线性表几种特殊的线性表n n后进先出(后进先出(后进先出(后

119、进先出(LastInFirstOutLastInFirstOut,简称简称简称简称LIFOLIFO)的线的线的线的线性表。它的所有插入、删除和存取都是在线性表性表。它的所有插入、删除和存取都是在线性表性表。它的所有插入、删除和存取都是在线性表性表。它的所有插入、删除和存取都是在线性表的表尾进行的。的表尾进行的。的表尾进行的。的表尾进行的。n n先进先出(先进先出(先进先出(先进先出(FirstInFirstOutFirstInFirstOut,简称简称简称简称FIFOFIFO)的线的线的线的线性表。它的所有插入都是在线性表的一端进行的,性表。它的所有插入都是在线性表的一端进行的,性表。它的所有

120、插入都是在线性表的一端进行的,性表。它的所有插入都是在线性表的一端进行的,而所有的删除和存取又都在线性表的另一端进行;而所有的删除和存取又都在线性表的另一端进行;而所有的删除和存取又都在线性表的另一端进行;而所有的删除和存取又都在线性表的另一端进行; n n限定所有插入、删除和存取都在表的两端进行的限定所有插入、删除和存取都在表的两端进行的限定所有插入、删除和存取都在表的两端进行的限定所有插入、删除和存取都在表的两端进行的线性表。线性表。线性表。线性表。 数组数组数组数组oo线性表的推广形式之一。线性表的推广形式之一。oo如在一个如在一个m n的二维数组中,每个元素的二维数组中,每个元素Ai,

121、j都分别属于两个线性表,即都分别属于两个线性表,即(Ai,1,Ai,2,Ai,n)和(和(A1,j,A2,j,Am,j)。)。树(树(树(树(TreeTree)oo由由n(n0)个结点组成的有限集合。若个结点组成的有限集合。若n=0,则称为空树,任何一个非空树均满足以下则称为空树,任何一个非空树均满足以下两个条件:两个条件:n n仅有一个称为根的结点;仅有一个称为根的结点;n n当当n0时,其余结点可分为时,其余结点可分为m(m0)个互不相交的有限集合,个互不相交的有限集合,其中每个集合又是一棵树,并称为其中每个集合又是一棵树,并称为根的子树。根的子树。oo上图的树有上图的树有1212个结点,

122、个结点,A A是根结点,该树又可再分为是根结点,该树又可再分为若干不相交的子树,如若干不相交的子树,如T1=BT1=B,E E,F F,KK,T2=CT2=C,GG,T3=DT3=D,H H,I I,J J,LL等。图等。图4.44.4所示的树中有所示的树中有1212个结点,个结点,A A是根结点,该树又可再分为若干不相交的是根结点,该树又可再分为若干不相交的子树,如子树,如T1=BT1=B,E E,F F,KK,T2=CT2=C,GG,T3=DT3=D,H H,I I,J J,LL等。等。 二叉树二叉树二叉树二叉树oon(n0)个个结结点点组组成成的的有有限限集集合合,它它或或者者是是空空集

123、集(n 0),或或者者由由一一个个结结点点及及两两棵棵互互不不相相交交的的子子树树组组成成,且且这这两两个个子子树树有有左左、右之分,其次序不能任意颠倒。右之分,其次序不能任意颠倒。图图图图oo由结点和连接这些结点的边所组成的集合。oo图的形式化定义为: G=其中: V是一个非空结点的集合; E是连结结点的边的集合。例例G=其中其中V=A,B,C,D, E=(A,B),(A,C),(B,D),(B,C),(D,C),(A,D)4.5算法、过程与程序算法、过程与程序4.5.4程序概念概念概念概念oo一般地说,对任何一个问题,如果有了解决一般地说,对任何一个问题,如果有了解决该问题的算法,就可以编

124、制相应的程序。所该问题的算法,就可以编制相应的程序。所谓谓程序,是一种事先编制好了具有特殊功能程序,是一种事先编制好了具有特殊功能的指令序列。的指令序列。其中,指令既可以是机器指令,其中,指令既可以是机器指令,汇编语言指令,也可以是高级语言的语句命汇编语言指令,也可以是高级语言的语句命令,甚至还可以是用自然语言描述的运算、令,甚至还可以是用自然语言描述的运算、操作命令。当然,用自然语言编写程序是计操作命令。当然,用自然语言编写程序是计算机科学进入非常高级的阶段的标志之一,算机科学进入非常高级的阶段的标志之一,有赖于自然语言理解取得重大突破,目前看有赖于自然语言理解取得重大突破,目前看来还是一个

125、十分遥远的设想。来还是一个十分遥远的设想。概念概念概念概念oo从广义上讲,程序可以认为是一种行动方案从广义上讲,程序可以认为是一种行动方案或工作步骤。例如:或工作步骤。例如:n n某个会议的日程安排某个会议的日程安排n n一条旅游路线的设计一条旅游路线的设计n n手工小制作的说明书等手工小制作的说明书等oo程序:一种处理事务的时间顺序和处理步骤。程序:一种处理事务的时间顺序和处理步骤。n n组成计算机程序的基本单位是组成计算机程序的基本单位是指令指令n n计算机程序就是按照工作步骤事先编计算机程序就是按照工作步骤事先编排好的、具有特殊功能的排好的、具有特殊功能的指令序列指令序列。一个程序具有一

126、个单一的、不可分的结构,它规定了某个数据结构上的一个算法。瑞士著名计算机科学家尼可莱沃思(NikiklausWirth)在1976年曾提出这样一个公式:算法算法+数据结构数据结构=程序程序这这一一公公式式仅仅可可以以作作为为一一种种参参考考,不不能能作作为为教学中的定义。教学中的定义。由此看来,我们前面提到的算法和数据结构是计算机程序的两个最基本的概念。算法是程序的核心,它在程序编制、软件开发,乃至在整个计算机科学中都占据重要地位。数据结构是加工的对象,一个程序要进行计算或处理总是以某些数据为对象的,而要设计一个好的程序就需将这些松散的数据按某种要求组成一种数据结构。然而,随着计算机科学的发展

127、,人们现在已经意识到程序除了以上两个主要要素外,还应包括程序的设计方法以及相应的语言工具和计算环境。概念概念概念概念oo程序这一概念的出现,得益于人类长期的生程序这一概念的出现,得益于人类长期的生活实践,程序设计也不神秘。但是,程序设活实践,程序设计也不神秘。但是,程序设计是一种高智力的活动,不同的人对同一事计是一种高智力的活动,不同的人对同一事物的处理可以设计出完全不同的程序。我们物的处理可以设计出完全不同的程序。我们每一个人的生活经历已经告诉自己,知识和每一个人的生活经历已经告诉自己,知识和阅历(经验)是处事(设计程序)的基础。阅历(经验)是处事(设计程序)的基础。正因为如此,在计算机发展

128、的早期,程序设正因为如此,在计算机发展的早期,程序设计被认为是一个与个人经历、思想和技艺相计被认为是一个与个人经历、思想和技艺相联系的一种技艺和技巧。后来,软件开发规联系的一种技艺和技巧。后来,软件开发规模的扩大和开发方式的变化,程序设计才开模的扩大和开发方式的变化,程序设计才开始被当成一门科学来对待。始被当成一门科学来对待。概念概念概念概念oo既然程序如此重要,又为人类经常使用,就既然程序如此重要,又为人类经常使用,就有必要对程序及其运行的规律进行深入的研有必要对程序及其运行的规律进行深入的研究。于是,对程序各种性质如程序的结构、究。于是,对程序各种性质如程序的结构、程序的正确性、程序的运行

129、效率等的研究产程序的正确性、程序的运行效率等的研究产生了计算机科学十分重要的一个方向生了计算机科学十分重要的一个方向程序程序理论。理论。4.6高级语言、程序设计技术高级语言、程序设计技术与方法与方法4.6.1高级语言高级语言高级语言高级语言高级语言oo虽然与机器语言相比,汇编语言的产生是一个很虽然与机器语言相比,汇编语言的产生是一个很大的进步,但是用它来进行程序设计仍然比较困大的进步,但是用它来进行程序设计仍然比较困难。于是人们着手对它进行改进。一是发展宏汇难。于是人们着手对它进行改进。一是发展宏汇编,即用一条宏指令代替若干条汇编指令,从而编,即用一条宏指令代替若干条汇编指令,从而提高编程效率

130、。现在人们使用的汇编语言,大多提高编程效率。现在人们使用的汇编语言,大多数都是宏汇编语言。二是创建高级语言,使编程数都是宏汇编语言。二是创建高级语言,使编程更加方便。更加方便。oo所谓高级程序设计语言(简称高级语言)是指用所谓高级程序设计语言(简称高级语言)是指用于描述计算机程序的类自然语言。这种语言只是于描述计算机程序的类自然语言。这种语言只是自然语言的一个很小的子集,在语法结构上比较自然语言的一个很小的子集,在语法结构上比较简单而且规范,在语义上较少二义性,能够以比简单而且规范,在语义上较少二义性,能够以比较准确、易读的形式描述各种计算机程序。较准确、易读的形式描述各种计算机程序。高级语言

131、的分类高级语言的分类高级语言的分类高级语言的分类按语言的特点,可以将高级语言划分为:按语言的特点,可以将高级语言划分为:oo过程式语言(如过程式语言(如CobolCobol,ForturnForturn,AlgolAlgol,PascalPascal,AdaAda,C C)oo函数式语言(如函数式语言(如LispLisp)oo数据流语言(如数据流语言(如SISALSISAL,VALVAL)oo面向对象语言(如面向对象语言(如SmalltalkSmalltalk,CLUCLU,C+C+)oo逻辑语言(如逻辑语言(如PrologProlog)oo字符串语言(如字符串语言(如SNOBOLSNOBOL

132、)oo并发程序设计语言(如并发程序设计语言(如Concurrent PascalConcurrent Pascal,Modula 2Modula 2)等等高级语言的形式化高级语言的形式化高级语言的形式化高级语言的形式化 20世纪世纪50年代年代oo美美国国语语言言学学家家乔乔姆姆斯斯基基(NoamChomsky)关于语言分层的理论,关于语言分层的理论,oo巴巴科科斯斯(Backus)、瑙瑙尔尔(Naur)的的关关于于“上上下下文文无无关关方方法法表表示示形形式式”的的研研究究成成果果推推动了语法形式化的研究。动了语法形式化的研究。oo其其结结果果是是,在在ALGOL60的的文文本本设设计计中中

133、第第一一次次使使用用了了BNF范范式式来来表表示示语语法法,并并且且第第一一次次在在语语言言文文本本中中明明确确提提出出应应将将语语法法和和语语义义区区分分开开来。来。高级语言的形式化高级语言的形式化高级语言的形式化高级语言的形式化oo20世世纪纪50年年代代至至60年年代代间间,面面向向语语法法的的编编译译自自动动化化理理论论得得到到了了很很大大发发展展,使使语语法法形形式式化化研研究究的成果达到实用化的水平。的成果达到实用化的水平。oo语语法法形形式式化化问问题题基基本本解解决决以以后后,人人们们逐逐步步把把注注意意力力集集中中到到语语义义形形式式化化的的研研究究方方面面,20世世纪纪60

134、年代,相继诞生了年代,相继诞生了n n操作语义学操作语义学n n指称语义学指称语义学n n公理语义学公理语义学n n代数语义学等语义学理论代数语义学等语义学理论数据类型的抽象数据类型的抽象数据类型的抽象数据类型的抽象oo相对于汇编语言和机器语言,高级语言的相对于汇编语言和机器语言,高级语言的数据数据类型类型的抽象层次有了很大地提高,出现了的抽象层次有了很大地提高,出现了n n整型整型n n实型实型n n字符型字符型n n布尔型布尔型n n用户自定义类型用户自定义类型n n抽象数据类型抽象数据类型oo数据类型的抽象数据类型的抽象极大地方便了用户对数据的抽极大地方便了用户对数据的抽象描述,为实现软

135、件设计的工程化奠定了基础。象描述,为实现软件设计的工程化奠定了基础。高级语言中有关抽象、理论和设计高级语言中有关抽象、理论和设计高级语言中有关抽象、理论和设计高级语言中有关抽象、理论和设计3 3个形态的主要内容个形态的主要内容个形态的主要内容个形态的主要内容 抽象理论设计常用的符号:数字(09),大小写字母(AZ、az),括号,运算符(+,*,/)等;用高级语言对算法进行的描述;语言的分类方法;各种数据类型的抽象实现模型;词法分析、编译、解释和代码优化的方法;词法分析器、扫描器、编译器组件和编译器的自动生成方法形式语言和自动机理论;形式语义学:操作、指称、公理、代数、并发和分布式程序的形式语义

136、特定语言:过程式的COBOL,FORTURN,ALGOL,Pascal,Ada,C),函数式的(LISP),数据流的(SISAL,VAL),面向对象的(Smalltalk,C+),逻辑的(Prolog),字符串(SNOBOL),和并发(ConcurrentPascal,Modula2)等语言;词法分析器和扫描器的产生器(如YACC,LEX),编译器产生器;语法和语义检查,成型、调试和追踪程序4.6高级语言、程序设计技术高级语言、程序设计技术与方法与方法4.6.2程序设计技术与方法程序设计技术程序设计技术程序设计技术程序设计技术oo为提高计算机的效率和可靠性,围绕程序的为提高计算机的效率和可靠性

137、,围绕程序的设计、描述、构造、分析、测试和验证等方设计、描述、构造、分析、测试和验证等方面,发展了许多的技术,统称为程序设计技面,发展了许多的技术,统称为程序设计技术。术。oo不同的程序设计方法与技术,都是从不同的不同的程序设计方法与技术,都是从不同的角度对程序及其设计和产生过程的特性和规角度对程序及其设计和产生过程的特性和规律进行观察,经抽象、分析和总结之后得出律进行观察,经抽象、分析和总结之后得出的。的。程序设计方法与技术程序设计方法与技术程序设计方法与技术程序设计方法与技术oo自顶向下逐步求精的程序设计方法与技术自顶向下逐步求精的程序设计方法与技术oo自底向上的程序设计方法与技术自底向上

138、的程序设计方法与技术oo基于程序推导的程序设计方法与技术基于程序推导的程序设计方法与技术oo基于程序变换的程序设计方法与技术基于程序变换的程序设计方法与技术oo面向对象的程序设计方法与技术面向对象的程序设计方法与技术oo函数式程序设计技术函数式程序设计技术oo逻辑程序设计技术逻辑程序设计技术oo程序验证技术程序验证技术oo并发程序技术并发程序技术oo。程序设计语言是一门科学程序设计语言是一门科学程序设计语言是一门科学程序设计语言是一门科学o对程序结构本质的深入研究促进了对程序质对程序结构本质的深入研究促进了对程序质量的认识量的认识o开发程序的效率和质量取决于程序设计方法开发程序的效率和质量取决

139、于程序设计方法和技术和技术o多年的研究发展了许多程序设计方法和技术。多年的研究发展了许多程序设计方法和技术。如自顶向下逐步求精的程序设计方法、自底如自顶向下逐步求精的程序设计方法、自底向上的程序设计方法、程序推导的设计方法、向上的程序设计方法、程序推导的设计方法、程序变换的设计方法、函数式程序设计技术、程序变换的设计方法、函数式程序设计技术、逻辑程序设计技术、面向对象的程序设计技逻辑程序设计技术、面向对象的程序设计技术、程序验证技术、约束程序设计技术、并术、程序验证技术、约束程序设计技术、并发程序设计技术等。发程序设计技术等。程序设计语言是一门科学程序设计语言是一门科学程序设计语言是一门科学程

140、序设计语言是一门科学o例如,对于许多问题的计算,可以用类似于例如,对于许多问题的计算,可以用类似于计算函数的方法来进行,也可以用表(一种计算函数的方法来进行,也可以用表(一种数据结构)处理的方法进行,甚至还可以用数据结构)处理的方法进行,甚至还可以用逻辑公式演绎推导的方法进行,在实现技术逻辑公式演绎推导的方法进行,在实现技术上,既可以用递归技术计算,也可以用迭代上,既可以用递归技术计算,也可以用迭代技术或其它技术进行计算。技术或其它技术进行计算。程序设计语言是一门科学程序设计语言是一门科学程序设计语言是一门科学程序设计语言是一门科学o作为一门科学,高级语言和程序设计确实对作为一门科学,高级语言

141、和程序设计确实对学科的发展产生了巨大的影响。程序设计方学科的发展产生了巨大的影响。程序设计方法和技术在各个时期的发展不仅直接导致了法和技术在各个时期的发展不仅直接导致了一大批风格各异的高级语言的诞生,而且许一大批风格各异的高级语言的诞生,而且许多新思想、新概念、新方法和新技术不仅在多新思想、新概念、新方法和新技术不仅在语言中得到体现,同时渗透到了计算机科学语言中得到体现,同时渗透到了计算机科学的各个方向,从理论、硬件、软件到应用等的各个方向,从理论、硬件、软件到应用等多方面深刻影响了学科的发展。多方面深刻影响了学科的发展。o对高级语言和程序设计的掌握是计算机科学对高级语言和程序设计的掌握是计算

142、机科学专业的基本功之一。专业的基本功之一。4.7软件与硬件软件与硬件4.7.1硬件硬件的概念硬件的概念硬件的概念硬件的概念oo计计算算机机硬硬件件是是构构成成计计算算机机系系统统的的所所有有物物理理器器件件、部部件件、设设备备,以以及及相相应应的的工工作作原原理理与与设设计计、制制造造、检检测测等等技技术术的的总总称称。广广义义的的硬硬件件包包含含硬硬件件本本身身及及其其工工程程技技术术两两部部分分。其其中中:语音等方式进入计算机语音等方式进入计算机n n计计算算机机系系统统的的物物理理元元器器件件包包括括:集集成成电电路路、印印制制电电路路板板,以以及及其其他他磁磁性性元元件件、电电子子元元

143、件等。件等。n n计计算算机机系系统统的的部部件件和和设设备备包包括括:控控制制器器、运算器、存储器、输入输出设备、电源等。运算器、存储器、输入输出设备、电源等。硬件的概念硬件的概念硬件的概念硬件的概念oo硬硬件件工工程程技技术术包包括括:印印制制电电路路板板制制造造、高高密密度度组组装装、抗抗环环境境干干扰扰、抗抗恶恶劣劣环环境境破破坏坏等等技技术术,以以及及在在设设计计和和制制造造过过程程中中为为提提高高计计算算机机性能所采取的措施等。性能所采取的措施等。4.7软件与硬件软件与硬件4.7.2软件软件的概念软件的概念软件的概念软件的概念oo软件是与程序密切相关的一个概念,在计算机发展的初期,

144、硬件设计和生产是主要问题,那时的软件就是程序。后来,随着计算技术的发展,传统软件的生产方式已不适应发展的需要,于是人们将工程学的基本原理和方法引入软件设计和生产中。oo现在计算机软件一般指计算机系统中的程序及其文档,也可以指在研究、开发、维护,以及使用上述含义下的软件所涉及的理论、方法、技术所构成的分支学科。软件的定义软件的定义软件的定义软件的定义o从计算机(硬件裸机)到计算机系统从计算机(硬件裸机)到计算机系统o从计算机系统到计算机体系结构从计算机系统到计算机体系结构oo软件是与程序密切相关的一个概念,在计算机发展的初期,硬件设计和生产是主要问题,那时的软件就是程序。后来,随着计算技术的发展

145、,传统软件的生产方式已不适应发展的需要,于是人们将工程学的基本原理和方法引入软件设计和生产中。软件的定义软件的定义软件的定义软件的定义o软件是一个发展的概念,早期软件和程序几软件是一个发展的概念,早期软件和程序几乎是同义词。后来,软件的概念在程序的基乎是同义词。后来,软件的概念在程序的基础上得到了延伸。础上得到了延伸。1983年,年,IEEE对软件给出对软件给出了一个较为新颖的定义,指出:了一个较为新颖的定义,指出:软件是计算软件是计算机程序、方法、规范及其相应的文稿以及在机程序、方法、规范及其相应的文稿以及在计算机上运行时所必须的数据。计算机上运行时所必须的数据。软件的分类软件的分类软件的分

146、类软件的分类oo软软件件一一般般分分为为系系统统软软件件、支支撑撑软软件件、应应用用软软件件3类。类。n n系系统统软软件件是是计计算算机机系系统统中中最最靠靠近近硬硬件件层层次次的的软软件件。如如操操作作系系统统、编编译译程程序序、汇汇编编程程序序、数数据据库库管管理理系系统统、软软硬硬件件故故障障诊诊断断程程序序、子子程程序序库库、各各种种软软件件开开发发工工具和软件包等属于系统软件。具和软件包等属于系统软件。n n支支撑撑软软件件是是支支撑撑其其他他软软件件的的开开发发与与维维护护的的软软件件。如如数数据据库库管管理理系系统统、网网络络软软件件、各种接口软件和开发工具等。各种接口软件和开

147、发工具等。n n应应用用软软件件是是特特定定应应用用领领域域的的专专用用软软件件。如商业会计软件、教学软件等。如商业会计软件、教学软件等。软件的概念软件的概念软件的概念软件的概念oo操操作作系系统统-一一种种系系统统软软件件,它它负负责责管管理理计计算算机机系系统统中中的的各各种种资资源源并并控控制制各各类类程程序序的的运运行行。它它通通过过接接受受来来自自用用户户的的操操作作命命令令,按按照照用用户户的的要要求求对对计计算算机机的的工工作作进进行行控控制制。计计算算机机配配上操作系统之后,能够提高效率,便于使用。上操作系统之后,能够提高效率,便于使用。o系统软件和应用软件迄今并没有严格的定义

148、。系统软件和应用软件迄今并没有严格的定义。4.7软件与硬件软件与硬件 计算机就是由计算机硬件和计算机软件组成的。硬件是计算机的“躯体”,软件是计算机的“灵魂”。 4.8计算机图形学、图像处理计算机图形学、图像处理与模式识别与模式识别4.8.1计算机图形学oo国际标准化组织(ISO)的定义:计算机图形学是研究通过计算机将数据转换为图形,并在专门显示设备上显示的原理、方法和技术的学科。oo计算机图形学是建立在传统的图学理论、应用数学和计算机科学基础上的一门边缘学科。基本概念基本概念基本概念基本概念oo广义的概念oo几何要素几何属性点、线、面、体oo非几何要素视觉属性明暗、灰度、色彩、纹理、透明性、

149、线型、线宽图形的构成要素图形的构成要素图形的构成要素图形的构成要素oo计算机对图形数据处理的硬件和软件oo围绕着生成、表示物体的图形的准确性-真实性-实时性oo算法可大致分为以下几类: -基于图形设备的基本图形元素的生成算法基于图形设备的基本图形元素的生成算法基于图形设备的基本图形元素的生成算法基于图形设备的基本图形元素的生成算法 -图形的变换和裁剪图形的变换和裁剪图形的变换和裁剪图形的变换和裁剪 -自由曲线和曲面自由曲线和曲面自由曲线和曲面自由曲线和曲面计算几何计算几何计算几何计算几何 -真实感图形的生成算法真实感图形的生成算法真实感图形的生成算法真实感图形的生成算法 -三维几何造型技术三维

150、几何造型技术三维几何造型技术三维几何造型技术 -山、水、花、草、树木、云、烟、火焰、雪景等模糊复杂山、水、花、草、树木、云、烟、火焰、雪景等模糊复杂山、水、花、草、树木、云、烟、火焰、雪景等模糊复杂山、水、花、草、树木、云、烟、火焰、雪景等模糊复杂景物的生成景物的生成景物的生成景物的生成分形几何分形几何分形几何分形几何 -三维或高维数据场的可视化三维或高维数据场的可视化三维或高维数据场的可视化三维或高维数据场的可视化 -图形的并行处理图形的并行处理图形的并行处理图形的并行处理 -虚拟现实环境虚拟现实环境虚拟现实环境虚拟现实环境实时交互式三维图形处理实时交互式三维图形处理实时交互式三维图形处理实

151、时交互式三维图形处理研究内容研究内容研究内容研究内容oo图形用户界面(GUI)oo计算机辅助设计与制造工业领域oo计算机动画商业领域(广告设计、电脑游戏、卡通动画片、影视特技)oo计算机艺术艺术领域oo过程控制(工业、交通等领域设备运行监控)oo系统环境模拟(如飞行模拟舱等)oo事务和商务数据的图形显示oo地形地貌和自然资源的图形显示(GIS、GPS)oo科学计算的可视化oo多媒体应用图形学的应用图形学的应用图形学的应用图形学的应用4.8计算机图形学、图像处理计算机图形学、图像处理与模式识别与模式识别4.8.2图像处理oo数字图象处理旨在对图象进行各种加工以改善图象的视觉效果。oo主要研究对客

152、观世界中已经存在的物体映像处理成新的数字化图像,如医学图像处理、卫星遥感图像处理、照相图像处理等。oo主要关心的是如何滤掉噪音,图像压缩、传输和还原,图像质量提高等。4.8计算机图形学、图像处理计算机图形学、图像处理与模式识别与模式识别4.8.3模式识别oo模式识别主要研究如何分析和识别各种图像,找出其中图形数据蕴含的内在联系或构建图像的抽象模型。oo如高速公路上的车辆拍照的识别、人脸部的识别、数字水印等。与相与相与相与相关学关学关学关学科的科的科的科的关系关系关系关系图像处理图像处理计计算算机机图图形形学学模模式式识识别别图图像像计算几何计算几何特特征征数数据据几几何何模模型型CAD/CAM

153、计算机艺术计算机艺术计算机动画计算机动画计算机视觉计算机视觉4.9人工智能第第4章章 计算学科中的计算学科中的基本基本概念概念 oo人工智能就是研究智能计算机及其系统,以模仿和执行人类的某些智力功能,如判断、推理、规划、设计、思考、学习、识别等,解决过去人类专家才能处理好的复杂问题。oo人工智能的“思维法则”方法中,强调的是正确的推论。作出正确推论有时也是理性智能体的部分功能。基本概念基本概念基本概念基本概念oo人工智能领域中的所谓逻辑主义就是希望通过编制具有逻辑能力的程序来创造智能系统。oo问题:-难以获得非形式化的知识并得到逻辑符号表示所需的形式化表达;-”原则上”可以解决一个问题与实际解

154、决问题这两者之间存在巨大的差别。基本概念基本概念基本概念基本概念oo1、像人一样思考的系统-有 头 脑 的 机 器 : 计 算 机 能 够 思 考 。(Haugeland,1985)-使之能够进行与人类的思维相关的活动,如 决 策 、 问 题 求 解 、 学 习 等 。(Bellman,1978)oo2理性地思考的系统-通过对计算模型的使用来进行心智能力的研究。(Charniak,1985)-对使得知觉、推理和行动成为可能的计算的研究。(Winston,1992)人们对人工智能的解释人们对人工智能的解释人们对人工智能的解释人们对人工智能的解释oo3像人一样行动的系统-一种技艺,创造机器来执行人

155、需要智能才能完成的功能。(Kurzweil,1990)-研究如何让计算机能够做到那些目前人比计算机做得更好的事情。(Rich,Knight,1991)oo4理性地行动的系统-计算智能是对设计智能化智能体的研究。(Poole等人,1998)-AI.关心的是人工制品中的智能行为。(尼尔森(Nilsson),1998)人们对人工智能的解释人们对人工智能的解释人们对人工智能的解释人们对人工智能的解释oo哲学哲学(公元前(公元前428428年年-现在)现在) -形式化规则能用来抽取合理结论吗?形式化规则能用来抽取合理结论吗? -精神的意识是如何从物质的大脑产生出精神的意识是如何从物质的大脑产生出来的?来

156、的? -知识从哪里来?知识从哪里来? -知识是如何导致行动的?知识是如何导致行动的?人工智能研究的基础人工智能研究的基础人工智能研究的基础人工智能研究的基础oo数学数学(约(约800800年年-现在)现在) - -什么是抽取合理结论的形式化规则?什么是抽取合理结论的形式化规则? - -什么可以计算?什么可以计算? - -我们如何用不确定的知识进行推理?我们如何用不确定的知识进行推理?oo经济学经济学(17761776年年现在)现在) -我们如何决策以获得最大收益?我们如何决策以获得最大收益? -我们在他人不合作的情况下如何做到这样我们在他人不合作的情况下如何做到这样? -我们在收益遥遥无期的情

157、况下如何做到这我们在收益遥遥无期的情况下如何做到这样?样? 人工智能研究的基础人工智能研究的基础人工智能研究的基础人工智能研究的基础oo神经科学神经科学(18611861年年-现在)现在) -头脑是如何处理信息的?头脑是如何处理信息的?oo心理学心理学(18791879年年现在)现在) -人类和动物如何思考和行动?人类和动物如何思考和行动?oo计算机工程计算机工程(19401940年年-现在)现在) -我们如何才能制造出能干的计算机?我们如何才能制造出能干的计算机?oo控制论控制论(19481948年年现在)现在) -人工制品怎样才能在自己的控制下运转?人工制品怎样才能在自己的控制下运转?oo

158、语言学语言学(19571957年年现在)现在) -语言和思维是怎样联系起来的?语言和思维是怎样联系起来的?人工智能研究的基础人工智能研究的基础人工智能研究的基础人工智能研究的基础oo知识表示(知识表示(知识表示(知识表示(KnoweledgePresentationnKnoweledgePresentationn) oo问题求解(问题求解(问题求解(问题求解(ProblemsolvingProblemsolving) oo模式识别(模式识别(模式识别(模式识别(PatternRecognitionPatternRecognition) oo自动定理证明自动定理证明自动定理证明自动定理证明(Au

159、tomaticTheoremProving)(AutomaticTheoremProving)oo自动程序设计(自动程序设计(自动程序设计(自动程序设计(AutomationProgrammingAutomationProgramming) oo自然语言处理(自然语言处理(自然语言处理(自然语言处理(NaturalLanguageProcessingNaturalLanguageProcessing)oo专家系统(专家系统(专家系统(专家系统(ExpertSystermsExpertSysterms) oo机器学习(机器学习(机器学习(机器学习(MachineLearningMachineLe

160、arning) oo机器人学(机器人学(机器人学(机器人学(RoboticsRobotics) oo人工神经网络(人工神经网络(人工神经网络(人工神经网络(ArtificialNueralNetworkArtificialNueralNetwork) oo计算机视觉计算机视觉计算机视觉计算机视觉(ComputerVision)(ComputerVision)oo博奕(博奕(博奕(博奕(GamePlagingGamePlaging)人工智能的应用研究领域人工智能的应用研究领域人工智能的应用研究领域人工智能的应用研究领域4.10计算机组织与体系结构计算机组织与体系结构第第4章章 计算学科中的计算学

161、科中的基本基本概念概念 oo内容包括从计算机系统的逐个设计、制造到计算机的系列化和软件的兼容性。ooIBM 360系 统 标 志 着 计 算 机 体 系 结 构(Architecture)研究的开端(1964年)。oo计算机体系结构是使用机器语言编写程序的用户可以看到的一个机器的抽象结构,而对这一结构实现的硬件组成属于计算机组成原理研究的范畴。oo随随着着大大规规模模和和超超大大规规模模集集成成电电路路(LSI/VLSILSI/VLSI)技技术术的的成成熟熟,一一方方面面器器件件速速度度和和可可靠靠性性在在不不断断提提高高,目目前前已已逼逼近近极极限限,另另一一方方面面器器件件的的体体积积和和

162、价价格格在在持持续续下下降降,这这极极大大地地增增强强了了计计算算机机的的性性能能。然然而而,高高质质量的器件不是产生高性能计算机的唯一因素。量的器件不是产生高性能计算机的唯一因素。oo虽虽然然,今今日日大大多多数数计计算算机机都都是是图图灵灵冯冯 诺诺依依曼曼型型存存储储程程序序式式电电子子数数字字计计算算机机,但但人人们们早早已已认认识识到到计计算算机机不不仅仅仅仅是是一一个个硬硬件件组组织织的的问问题题。一一个个现现代代的的计计算算机机系系统统一一般般被被认认为为是是由由存存储储器器、处处理理器器、功功能能部部件件、互互联联网网络络、汇汇编编程程序序、编编译译程程序序、操操作作系系统统、

163、外外部部设备、通信通道等内容组合而成的。设备、通信通道等内容组合而成的。硬件的概念硬件的概念硬件的概念硬件的概念oo早期计算机系统研究与开发的两个基本特点:早期计算机系统研究与开发的两个基本特点:n n硬硬件件和和软软件件的的研研究究与与开开发发基基本本上上是是独独立立进进行的;行的;n n硬硬件件的的研研究究与与开开发发更更多多的的是是从从计计算算机机组组成成原原理理上上去去关关心心各各部部件件中中分分离离元元器器件件及及其其相相互互之之间间的的联联接接关关系系,关关心心各各部部件件的的内内部部构构造和外部特性。造和外部特性。oo集成电路的发展改变了专业人员的认识。oo计算机CPU的速度和存

164、储器的容量成倍增长,各种多功能部件不断引入,如何设计和配置计算机系统使其具有更高的性能价格比,适应不同用户的要求,成为亟待解决的问题。oo集成电路的发展也使许多专业人员可以不再关心各部件的内部细节,而只须考虑如何以一种统一的观点从硬件器件和一些软件系统出发,通过组合配置,设计功能更强、性能价格比更高、更可靠的计算机系统。于是,计算机体系结构应运而生。oo典典型型的的、有有助助于于常常人人理理解解计计算算机机体体系系结结构构的的方方向向是是所所谓谓的的计计算算机机网网络络系系统统。用用户户面面对对计计算算机机系系统统网网络络进进行行开开发发是是十十分分困困难难的的,因因为为,他他不不可可能能熟熟

165、悉悉网网上上每每一一种种通通信信资资源源的的配配置置情情况况,而而且且也也不不了了解解每每一一种种通通信信资资源源的的基基本本操操作作方方法法,更更不不可可能能考考虑虑通通信信出出错错的的情情况况以以及及如如何何纠纠错错。显显然然,对对于于用用户户来来说说,需需要要有有一一种种能能够够屏屏蔽蔽计计算算机机硬硬件件系系统统技技术术细细节节,仅仅对对用用户户提提供供功功能能透透明明的的系系统统层层,使使用用户户看看到到的的和和实实际际使使用用的的是是一一个个与与使使用用者者思思想想方方式式、使使用用习习惯惯比比较较接接近近,无无须须具具体体关关心心网网络络计计算算机机通通信信时时一一些些十十分分繁

166、繁琐琐的的技技术细节的分布式计算机系统。术细节的分布式计算机系统。oo硬件的互联结构和软件结构及相互关系形成的计算机系统的总体结构,支持这种结构的基本算法,还有以总体结构为基础的面向用户的程序设计语言等内容构成了计算机体系结构的技术范畴。4.12并行计算机、通道与并并行计算机、通道与并行计算行计算第第4章章 计算学科中的计算学科中的基本基本概念概念 oo单CPU计算机多功能部件多寄存器计算机流水线向量计算机阵列式计算机多处理器并行计算机多处理机并行计算机多计算机网络并行计算机系统。计算机的组成结构变迁计算机的组成结构变迁计算机的组成结构变迁计算机的组成结构变迁并行处理的概念并行处理的概念并行处

167、理的概念并行处理的概念oo并并行行处处理理要要求求在在计计算算机机上上并并行行地地运运行行许许多多程程序序。根根据据使使用用的的计计算算机机系系统统的的不不同同,我我们们可可以在四个程序的级别上提出并行处理的问题:以在四个程序的级别上提出并行处理的问题:n n作业或程序级并行作业或程序级并行n n任务或过程级并行任务或过程级并行n n指令级并行指令级并行n n指令内部级并行。指令内部级并行。oo不同的并行处理思想和技术,产生了不同的并行计算机系统。从使用方便的角度考虑,用户更希望看到的是系统提供作业或程序级并行,这样用户可以不必考虑实现并行的细节。而从实际计算提高效率的角度考虑,用户更希望系统

168、已经实现了指令级并行或指令内部级并行。并行处理的概念并行处理的概念并行处理的概念并行处理的概念oo面对众多的并行计算机系统,我们应该怎么来认识和区别它们的系统结构呢?ooM.J.Flynn在1966年提出了一种著名的、也是现今比较常用的系统结构分类方法。他将计算机系统的系统结构分为四类,分别是:n n单指令流单数据流计算机(SISD)n n单指令流多数据流计算机(SIMD)n n多指令流单数据流计算机(MISD)n n多指令流多数据流计算机(MIMD)并行处理的概念并行处理的概念并行处理的概念并行处理的概念oo由多机系统技术的扩展及网络互连与通信技术的引入,发展了分布式网络计算机系统,提出了分

169、布式计算机体系结构、分布式算法与分布式并行处理的概念等。oo并行计算机系统的出现,带来了信息并行化处理的概念。并行处理是信息处理的一种有效形式,它着重于发掘计算过程中的并发事件。并行处理的概念并行处理的概念并行处理的概念并行处理的概念oo并发性包含宏观上的并行性,包含同时性以及微观上的流水线处理。并行事件可在同一时间间隔内在多个资源(如多个处理器)里发生;同时事件可在同一时刻上发生,流水线事件可在部分重叠的时间内于一个(或多个)资源里出现。oo并发通常是指宏观上一个资源里并行发生了两个或两个以上的事件,但在微观上是顺序发生的,而并行通常是指多个资源里微观上同时发生了两个或两个以上事件。显然,一

170、组事件是并行的也是并发的,但一组事件是并发的却不一定是并行的。并行处理的概念并行处理的概念并行处理的概念并行处理的概念oo-通道是数据或信息传送的通路oo利用并行计算机系统进行数据与信息的并行处理称为并行计算。从处理对象的角度划分,并行计算分为数值并行计算和非数值并行计算。oo与顺序计算类似,并行计算也分成几个步骤:研究并行计算方法,研究并行算法,设计并行程序,调试与运行,分析结果。通道的概念通道的概念通道的概念通道的概念oo由于许多问题的计算已经有了计算方法,而这些计算方法中隐含了大量的并行性,稍作变化就可支持并行算法和并行程序设计,而且,由于各种并行计算机的系统结构不同,各处理器和各多功能

171、部件之间在体现算法时的相互作用不同,算法不能通用。oo因此,除了并行计算机体系结构的研究外,当前和今后相当长的一个时期内并行处理的一个工作重点将是研究各种并行与分布式计算机系统上的并行算法或分布式算法。通道的概念通道的概念通道的概念通道的概念网络的基本概念网络的基本概念网络的基本概念网络的基本概念o随着计算科学及其应用的高速发展,用户对软硬件和随着计算科学及其应用的高速发展,用户对软硬件和信息资源共享的需求和一大类问题本身具有地域上分信息资源共享的需求和一大类问题本身具有地域上分布的特点,促进了计算机网络的发展。布的特点,促进了计算机网络的发展。o所谓所谓计算机网络是使用通信设备和通信线路将一

172、组地计算机网络是使用通信设备和通信线路将一组地理上分布的相同(称为同质)或不同(称为异质)的理上分布的相同(称为同质)或不同(称为异质)的计算机、终端及其附属设备按照某种方式互联起来得计算机、终端及其附属设备按照某种方式互联起来得到的一个计算机硬件系统到的一个计算机硬件系统,也叫网络计算机。在这种,也叫网络计算机。在这种计算机硬件系统的基础上,通过开发能协调各台计算计算机硬件系统的基础上,通过开发能协调各台计算机系统工作的通信系统或更进一步的网络操作系统,机系统工作的通信系统或更进一步的网络操作系统,就能使一组计算机实现软硬件资源共享、协同计算,就能使一组计算机实现软硬件资源共享、协同计算,合

173、作求解一个问题。由这种通信系统或网络操作系统合作求解一个问题。由这种通信系统或网络操作系统连同网络计算机一起,就形成了网络计算机系统。连同网络计算机一起,就形成了网络计算机系统。网络的分类网络的分类网络的分类网络的分类o按照数据传输范围和实现技术的不同,计算机网按照数据传输范围和实现技术的不同,计算机网络存在络存在局域计算机网络局域计算机网络和和广域计算机网络广域计算机网络之分。之分。局域计算机网络是一个数据通信系统,其传输范局域计算机网络是一个数据通信系统,其传输范围在中等地理区域,使用中等或高速数据传输速围在中等地理区域,使用中等或高速数据传输速率,使用专用数据通信线或总线进行通信,可联率

174、,使用专用数据通信线或总线进行通信,可联接大量独立设备,在物理通信通道上互相通信。接大量独立设备,在物理通信通道上互相通信。o广域计算机网络把不同城市、不同国家中的计算广域计算机网络把不同城市、不同国家中的计算机或计算机网络通过分级互联技术联接起来,其机或计算机网络通过分级互联技术联接起来,其传输范围可达到相当远的距离。目前最常见的是传输范围可达到相当远的距离。目前最常见的是使用公用或专用电话线通信,主干网和一些局域使用公用或专用电话线通信,主干网和一些局域网使用可进行数字通信的光纤光缆数据通信专用网使用可进行数字通信的光纤光缆数据通信专用线。线。网络的结构网络的结构网络的结构网络的结构o网络

175、互联的拓扑结构是计算机网络的重要特性。网络互联的拓扑结构是计算机网络的重要特性。网络的拓扑结构是一种抽象的由点和线组成的图。网络的拓扑结构是一种抽象的由点和线组成的图。网络上的每台计算机用一个结点表示,机器与机网络上的每台计算机用一个结点表示,机器与机器之间的链路用线和路径表示,于是,图论构成器之间的链路用线和路径表示,于是,图论构成了网络计算机体系结构中一些基本算法研究中数了网络计算机体系结构中一些基本算法研究中数学描述的理论基础。学描述的理论基础。o网络的结构一般有:主从型、环型、星型、等网络的结构一般有:主从型、环型、星型、等网络的协议网络的协议网络的协议网络的协议o支持计算机网络的重要

176、技术是通信,即实现计算支持计算机网络的重要技术是通信,即实现计算机之间信息传输的一种技术方式。网络通信的核机之间信息传输的一种技术方式。网络通信的核心内容是通信协议。所谓通信协议是网络通信中心内容是通信协议。所谓通信协议是网络通信中一组约定的集合,由它确定了经由通信网络传输一组约定的集合,由它确定了经由通信网络传输的信息或存储在报文和数据库中的信息的格式和的信息或存储在报文和数据库中的信息的格式和控制方式。研究通信协议主要是为了在网络计算控制方式。研究通信协议主要是为了在网络计算机系统中实现可靠的、高效的数据交换,差错控机系统中实现可靠的、高效的数据交换,差错控制,信息编码,线路利用,同步,使

177、通信数据具制,信息编码,线路利用,同步,使通信数据具有透明性。有透明性。 网络上连接着大量的计算机系统,每台计算机系统网络上连接着大量的计算机系统,每台计算机系统上可能有多个用户在同时使用计算机与其它网上用户上可能有多个用户在同时使用计算机与其它网上用户进行通信,而网络通信线路通常设计成公用资源,这进行通信,而网络通信线路通常设计成公用资源,这样,网络通信为了实现可靠的数据交换,因需要做许样,网络通信为了实现可靠的数据交换,因需要做许多具体的操作运算而变得十分复杂。由于从用户发送多具体的操作运算而变得十分复杂。由于从用户发送或接收可以识别的符号信息到实际在正确的通信线路或接收可以识别的符号信息

178、到实际在正确的通信线路上传递物理信息之间存在转换、线路利用、分组交换、上传递物理信息之间存在转换、线路利用、分组交换、差错纠正等一系列的操作,为了便于协议的有效实现差错纠正等一系列的操作,为了便于协议的有效实现和对不同的用户开放,最大限度地实现线路的有效利和对不同的用户开放,最大限度地实现线路的有效利用,有必要对网络计算机系统进行通信结构分层。于用,有必要对网络计算机系统进行通信结构分层。于是产生了网络协议层。每一层包含一组通信功能和相是产生了网络协议层。每一层包含一组通信功能和相应的层间通信协议,支持通信双方在不同的层间进行应的层间通信协议,支持通信双方在不同的层间进行通信,并提供了实现通信

179、的具体思想和方法。通信,并提供了实现通信的具体思想和方法。网络的协议网络的协议网络的协议网络的协议 按照按照ISOISO的建议,网络结构模型是开放系统互连模型的建议,网络结构模型是开放系统互连模型OSIOSI(七层协议),包括物理层,数据链路层,网络层,(七层协议),包括物理层,数据链路层,网络层,传输层,会话层,表示层,应用层共七层,产生了七传输层,会话层,表示层,应用层共七层,产生了七层协议。层协议。 开放系统开放系统A A 开放系统开放系统B B 应用层协议应用层协议 应用层应用层 应用层应用层 表示层协议表示层协议 表示层表示层 表示层表示层 会话层协议会话层协议 会话层会话层 会话层

180、会话层 传输层协议传输层协议 传输层传输层 传输层传输层 网络层协议网络层协议 网络层网络层 网络层网络层 数据链路层协议数据链路层协议 数据链路层数据链路层数据链路层数据链路层 物理层协议物理层协议 物理层物理层 物理层物理层 物理传输介质物理传输介质 网络的协议网络的协议网络的协议网络的协议网络的网络的网络的网络的OSIOSI协议协议协议协议o物理层协议实现物理上互连系统间位流信息的透物理层协议实现物理上互连系统间位流信息的透明传输,即实现了一位(组)数据在两个通信实明传输,即实现了一位(组)数据在两个通信实体之间的可靠传送通信,它描述了经通信介质在体之间的可靠传送通信,它描述了经通信介质

181、在数据链路实体之间建立、维护和拆除物理连接。数据链路实体之间建立、维护和拆除物理连接。o数据链路层协议主要是对高层屏蔽传输介质的特数据链路层协议主要是对高层屏蔽传输介质的特性,为网络通信实体之间提供建立、维护和释放性,为网络通信实体之间提供建立、维护和释放数据链路连接的功能和手段,实现无差错的数据数据链路连接的功能和手段,实现无差错的数据以帧为单位的可靠传送。以帧为单位的可靠传送。o网络层协议主要是为通信子网与高层结构之间提网络层协议主要是为通信子网与高层结构之间提供界面连接,其主要任务是对通信子网实现路径供界面连接,其主要任务是对通信子网实现路径选择,实现通信实体之间端选择,实现通信实体之间

182、端- -端的透明的数据传送,端的透明的数据传送,对高层屏蔽了数据传送经过的路径。对高层屏蔽了数据传送经过的路径。 网络的网络的网络的网络的OSIOSI协议协议协议协议o传输层协议也称为主机传输层协议也称为主机-主机层协议,它为会主机层协议,它为会话层的通信实体之间提供透明的数据传送,其话层的通信实体之间提供透明的数据传送,其主要任务是接收会话实体送来的数据,根据需主要任务是接收会话实体送来的数据,根据需要把它们分成若干比较小的单元,保证所有数要把它们分成若干比较小的单元,保证所有数据单元经下面三层正确地到达另一个会话实体。据单元经下面三层正确地到达另一个会话实体。o会话层协议也称进程会话层协议

183、也称进程-进程层协议,它通过协进程层协议,它通过协议提供的一组命令为网上两个进程之间的通信议提供的一组命令为网上两个进程之间的通信建立会话连接和释放会话连接,并管理它们在建立会话连接和释放会话连接,并管理它们在该连接上的对话。该连接上的对话。网络的网络的网络的网络的OSIOSI协议协议协议协议o表示层协议以对应用实体有意义的形式提供有表示层协议以对应用实体有意义的形式提供有关信息表示的服务。这些服务有文本压缩、代关信息表示的服务。这些服务有文本压缩、代码转换、数据加密与解密、文件格式变换、信码转换、数据加密与解密、文件格式变换、信息格式变换、终端属性的转换等。息格式变换、终端属性的转换等。o应

184、用层协议是用户访问网络的接口层,直接为应用层协议是用户访问网络的接口层,直接为正在通信的端点用户的应用进程服务,如电子正在通信的端点用户的应用进程服务,如电子邮件、远程操作访问、虚拟终端等。邮件、远程操作访问、虚拟终端等。o关于协议详细的实现技术,其主要的基础是分关于协议详细的实现技术,其主要的基础是分布式算法,今后,同学们有可能学习这些内容。布式算法,今后,同学们有可能学习这些内容。o网络信息安全、加密、病毒、高性能计算与通网络信息安全、加密、病毒、高性能计算与通信、信息高速公路、数字地球信、信息高速公路、数字地球4.15CC1991报告提取的核心概念第第4章章 计算学科中的核计算学科中的核

185、 心概念心概念oo核心概念是核心概念是CC1991报告首次提出的,是具有报告首次提出的,是具有普遍性、持久性的重要思想、原则和方法。普遍性、持久性的重要思想、原则和方法。它的基本特征有:它的基本特征有:n n在学科中多处出现;在学科中多处出现;n n在在各各分分支支领领域域及及抽抽象象、理理论论和和设设计计的的各个层面上都有很多示例;各个层面上都有很多示例;n n在技术上有高度的独立性;在技术上有高度的独立性;n n一般都在数学、科学和工程中出现。一般都在数学、科学和工程中出现。1.1.绑定绑定绑定绑定(Binding)oo绑定指的是通过将一个对象(或事物)与其某种属性相联系,从而使抽象的概念

186、具体化的过程。例如:将一个进程与一个处理机,一个变量与其类型或值分别联系起来。这种联系的建立,实际上就是建立了某种约束。2.2.大问题的复杂性大问题的复杂性大问题的复杂性大问题的复杂性(ComplexityofLargeProblems)oo大问题的复杂性是指随着问题规模的增长而使问题的复杂性呈非线性增加的效应。这种非线性增加的效应是区分和选择各种现有方法和技术的重要因素。 3. 3. 概念和形式模型概念和形式模型概念和形式模型概念和形式模型(ConceptualandFormatModels)oo概念和形式模型是对一个想法或问题进行形式化、特征化、可视化思维的方法。抽象数据类型、语义数据类型

187、以及指定系统的图形语言,如数据流图和E-R图等都属于概念模型。而逻辑、开关理论和计算理论中的模型大都属于形式模型。概念模型和形式模型以及形式证明是将计算学科各分支统一起来的重要的核心概念。4. 4.一致性和完备性一致性和完备性一致性和完备性一致性和完备性(ConsistencyandCompleteness)oo一一致致性性包包括括用用于于形形式式说说明明的的一一组组公公理理的的一一致致性性、事事实实和和理理论论的的一一致致性性,以以及及一一种种语语言言或或接接口口设设计的内部一致性。计的内部一致性。oo完完备备性性包包括括给给出出的的一一组组公公理理,使使其其能能获获得得预预期期行行为为的的

188、充充分分性性、软软件件和和硬硬件件系系统统功功能能的的充充分分性性,以以及及系系统统处处于于出出错错和和非非预预期期情情况况下下保保持持正正常常行行为的能力等。为的能力等。oo在在计计算算机机系系统统设设计计中中,正正确确性性、健健壮壮性性和和可可靠靠性就是一致性和完备性的具体体现。性就是一致性和完备性的具体体现。5.5.效率效率效率效率(Efficiency)oo效率是关于空间、时间、人力、财力等资源消耗的度量。在计算机软硬件的设计中,要充分考虑某种预期结果所达到的效率,以及一个给定的实现过程较之替代的实现过程的效率。 6 6演化演化(Evolution) 演化指的是系统的结构、状态、特征、

189、行为和功能等随着时间的推移而发生的更改。这里主要是指了解系统更改的事实和意义及应采取的对策。在软件进行更改时,不仅要充分考虑更改对系统各层次造成的冲击,还要充分考虑到软件的有关抽象、技术和系统的适应性问题。7.7.抽象层次抽象层次抽象层次抽象层次(Levels of Abstraction)oo抽象层次指的是通过对不同层次的细节和指标的抽象对一个系统或实体进行表述。在复杂系统的设计中,隐藏细节,对系统各层次进行描述(抽象),从而控制系统的复杂程度。例如,在软件工程中,从规则说明到编码各个阶段(层次)的详细说明,计算机系统的分层思想,计算机网络的分层思想等。8. 8.按空间排序按空间排序按空间排

190、序按空间排序(Ordering in Space)oo按空间排序指的是各种定位方式,如物理上的定位(如网络和存储中的定位),组织方式上的定位(如处理机进程、类型定义和有关操作的定位)以及概念上的定位(如软件的辖域、耦合、内聚等)。按空间排序是计算技术中一个局部性和相邻性的概念。 9.9.按时间排序按时间排序按时间排序按时间排序(Ordering in Time)oo按时间排序指的是事件的执行对时间的依赖性。例如,在具有时态逻辑的系统中,要考虑与时间有关的时序问题;在分布式系统中,要考虑进程同步的时间问题;在依赖于时间的算法执行中,要考虑其基本的组成要素。10.10.重用重用重用重用(Reuse

191、)oo重用指的是在新的环境下,系统中各类实体、技术、概念等可被再次使用的能力。如软件库和硬件部件的重用等。 11.11.安全性安全性安全性安全性(Security)oo安全性指的是计算机软硬件系统对合法用户的响应及对非法请求的抗拒,以保护自己不受外部影响和攻击的能力。如为防止数据的丢失、泄密而在数据库管理系统中提供的口令更换、操作员授权等功能。 12.12.折衷与结论折衷与结论折衷与结论折衷与结论(Tradeoff and Consequences)oo指的是为满足系统的可实施性而对系统设计中的技术、方案所作出的一种合理的取舍。结论是折衷的结论,即选择一种方案代替另一种方案所产生的技术、经济、文化及其他方面的影响。折衷是存在于计算学科领域各层次上的基本事实。如在算法的研究中,要考虑空间和时间的折衷;对于矛盾的设计目标,要考虑诸如易用性和完备性、灵活性和简单性、低成本和高可靠性等方面所采取的折衷等。

展开阅读全文
相关资源
正为您匹配相似的精品文档
相关搜索

最新文档


当前位置:首页 > 建筑/环境 > 施工组织

电脑版 |金锄头文库版权所有
经营许可证:蜀ICP备13022795号 | 川公网安备 51140202000112号