《计算学科中的基本概念课件》由会员分享，可在线阅读，更多相关《计算学科中的基本概念课件（234页珍藏版）》请在金锄头文库上搜索。
1、计算学科中的计算学科中的基本概念基本概念 4.1计算模型与二进制计算模型与二进制4.1.1计算模型与图灵机计算模型与图灵机计算模型与图灵机计算模型与图灵机计算模型与图灵机oo计计算模型：算模型：算模型：算模型：n n刻刻刻刻画画画画计计算算算算这这一一一一概概概概念念念念的的的的一一一一种种种种抽抽抽抽象象象象的的的的形形形形式式式式系系系系统统或或或或数数数数学学学学系系系系统统。n n在在在在计计算算算算科科科科学学学学中中中中，是是是是指指指指具具具具有有有有状状状状态态转转换换特特特特征征征征，能能能能够够对对所所所所处处理理理理的的的的对对象象象象的的的的数数数数据据据据或或或或信信
2、信信息息息息进进行行行行表表表表示示示示、加加加加工工工工、变变化、接收、化、接收、化、接收、化、接收、输输出的数学机器。出的数学机器。出的数学机器。出的数学机器。oo计计算模型的算模型的算模型的算模型的层层次：次：次：次：n n计计算某个（算某个（算某个（算某个（类类）具体）具体）具体）具体问题问题的的的的计计算方法；算方法；算方法；算方法；n n按按按按照照照照计计算算算算方方方方法法法法对对应应的的的的程程程程序序序序完完完完成成成成某某某某类类问问题题特特特特定定定定计计算算算算所需要的平台。所需要的平台。所需要的平台。所需要的平台。n n 在在在在计计算能力上具有某种等价性的形式系算
3、能力上具有某种等价性的形式系算能力上具有某种等价性的形式系算能力上具有某种等价性的形式系统统。n n 计计算模型的模型（一切算模型的模型（一切算模型的模型（一切算模型的模型（一切计计算模型所内含的机理）算模型所内含的机理）算模型所内含的机理）算模型所内含的机理）计算模型与图灵机计算模型与图灵机计算模型与图灵机计算模型与图灵机oo图灵的灵的观点及点及结论：n n凡凡是是能能用用算算法法方方法法解解决决的的问题，也也一一定定能能用用图灵灵机机解解决决；凡凡是是图灵灵机机解解决决不不了了的的问题，任何算法也解决不了。，任何算法也解决不了。oo与与图灵机等价的灵机等价的计算模型：算模型：n n递归函数
4、函数n n-演算演算n nPOST规范系范系统oo图灵灵机机是是从从过程程这一一角角度度来来刻刻画画计算算的的本本质，其其结构构简单、操操作作运运算算规则也也较少少，从从而而为更多的人所理解。更多的人所理解。图灵机图灵机图灵机图灵机oo图灵灵机机由由一一条条两两端端可可无无限限延延长的的带子子、一一个个读写写头以及一以及一组控制控制读写写头工作的命令工作的命令组成，成，图灵机图灵机图灵机图灵机oo写在写在带子上的符号子上的符号为一个有一个有穷字母表：字母表：S0，S1，S2，Sp。n n可以可以认为这个有个有穷字母表字母表仅有有S0、S1两个两个字符，字符，n n其中其中S0可以看作是可以看作
5、是“0”，S1可以看作是可以看作是“1”，n n由由“0”和和“1”组成的字母表可以表示任成的字母表可以表示任何一个数。何一个数。oo由于由于“0”和和“1”只有形式的意只有形式的意义，因此，因此，也可以将也可以将S0改称改称为“白白”，S1改称改称为“黑黑”，甚至，甚至，还可以改称可以改称为“桌子桌子”和和“老虎老虎”，这样改称的目的在于割断与直改称的目的在于割断与直觉的的联系，并系，并加深加深对布布尔域中的域中的值真，假真，假，以及二，以及二进制制机器本机器本质的理解。机器的控制状的理解。机器的控制状态表表为：q1，q2，qm。n n将一个将一个图灵机的初始状灵机的初始状态设为q1，在每一
6、在每一个具体的个具体的图灵机中灵机中还要确定一个要确定一个结束状束状态qw。一个给定机器的一个给定机器的“ “程序程序” ”oo机器内的五元组（qiSjSkR（或L或N）ql）形式的指令集，五元组定义了机器在一个特定状态下读入一个特定字符时所采取的动作。5个元素的含义如下：n nqi表示机器目前所处的状态；n nSj表示机器从方格中读入的符号；n nSk表示机器用来代替Sj写入方格中的符号；n nR、L、N分别表示向右移一格、向左移一格、不移动；n nql表示下一步机器的状态。 oo一个机器一个机器计算的算的结果是从机器停止果是从机器停止时带子上的信子上的信息得到的。容易看出，息得到的。容易看
7、出，q1S2S2Rq3指令和指令和q3S3S3Lq1指令如果同指令如果同时出出现在机器中，当机器在机器中，当机器处于状于状态q1，第一条指令，第一条指令读入的是入的是S2，第二条指，第二条指令令读入的是入的是S3，那么机器会在两个方，那么机器会在两个方块之之间无休无休止地工作。止地工作。oo另外，如果另外，如果q3S2S2Rq4和和q3S2S4Lq6指令同指令同时出出现在机器中，当机器在机器中，当机器处于状于状态q3并在并在带子上子上扫描描到符号到符号S2时，就，就产生了二生了二义性的性的问题，机器就无，机器就无法判定。法判定。例子：例子：例子：例子：oob b表示空格，表示空格，表示空格，表
8、示空格，q q1 1表示机器的初始状表示机器的初始状表示机器的初始状表示机器的初始状态态， q q4 4表示机器的表示机器的表示机器的表示机器的结结束状束状束状束状态态，设带设带子上的子上的子上的子上的输输入信息是入信息是入信息是入信息是1010001010100010，读读入入入入头头位位位位对对准准准准最右最右最右最右边边第一个第一个第一个第一个为为0 0的方格，状的方格，状的方格，状的方格，状态为态为初始状初始状初始状初始状态态q q1 1。规则规则如下：如下：如下：如下：n nq q1 10101L L q q22q q1 11010L L q q33q q1 1 b b b b N
9、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）时，不改变空格符，读写头不动并停机。图灵机的计算能力图灵机的计算能力图灵机的计算能力图灵机的计算能力oo第一第一，把，把图灵机看作灵机看作识别器，即判断器，即判断带子上最子上最初的内容
10、能否被初的内容能否被图灵机所接受。假定灵机所接受。假定图灵机从灵机从左向右左向右扫描完描完带子上的内容后停机子上的内容后停机则为接受，接受，否否则为不接受。不接受。oo例例2一台一台图灵机可以灵机可以设计成成识别下面的序列：下面的序列：1000110,10011101,010101011。图灵机的计算能力图灵机的计算能力图灵机的计算能力图灵机的计算能力oo第二，第二，把把图灵机看作生成器，灵机看作生成器，对给定的定的输入集入集合，考察合，考察输出集合，并研究出集合，并研究输入入输出集合性出集合性质之之间的关系，的关系，这就研究了就研究了图灵机的生成能力。灵机的生成能力。oo例例3设一台一台图灵
11、机的灵机的输入集合入集合为In1n0nnN，可，可设计一台一台图灵机，灵机，对给定的定的输入集合入集合In，得到，得到输出集合出集合Out0n1nnN。其中，。其中，N是全体自然数的集合。是全体自然数的集合。图灵机的计算能力图灵机的计算能力图灵机的计算能力图灵机的计算能力oo第三第三，把，把图灵机看作灵机看作计算器，相当于一个函数。算器，相当于一个函数。图灵机的灵机的输入是函数的自入是函数的自变量的量的值，图灵机的灵机的输出是函数的出是函数的值。例例4图灵机可以灵机可以计算下列函数：算下列函数：(1)s(x)x1；(2)o(x)0；(3)A(0，y)y1，A(x1，0)A(x，1)，A(x1，
12、y1)A(x，A(x1，y)。图灵机的计算能力图灵机的计算能力图灵机的计算能力图灵机的计算能力oo第一和第二个函数第一和第二个函数读者不者不难从从图灵机的定灵机的定义出出发感悟到它感悟到它们是是图灵机可以灵机可以计算的函数，而第算的函数，而第三个函数就比三个函数就比较复复杂，一，一时难于判断。于判断。顺便提便提一下，第三个函数叫做一下，第三个函数叫做阿克曼函数阿克曼函数，它是阿克，它是阿克曼（曼（W.Ackermann）在研究原始）在研究原始递归函数和函数和递归函数的关系函数的关系时给出的。出的。这个函数在个函数在计算理算理论中具有重要价中具有重要价值。oo事事实上，上，图灵机灵机还可以可以计
13、算形式上比第三个函算形式上比第三个函数更复数更复杂的函数。的函数。图灵机的计算能力图灵机的计算能力图灵机的计算能力图灵机的计算能力oo图灵机可以灵机可以计算算n nS(x)x1（后后继函数），函数），n nN(x)0（零函数），零函数），n nUi(n)(x1，x2，xn)xi，1in（投影函数）投影函数）n n上述上述3个函数的任意个函数的任意组合。合。oo从从从从递归论递归论中，我中，我中，我中，我们们知道知道知道知道这这3 3个函数属于个函数属于个函数属于个函数属于初始初始初始初始递归递归函数函数函数函数，n n任何原始任何原始任何原始任何原始递归递归函数都是从函数都是从函数都是从函数都
14、是从这这3 3个初始个初始个初始个初始递归递归函数函数函数函数经经有有有有限次的复合、限次的复合、限次的复合、限次的复合、递归递归和极小化操作得到的。和极小化操作得到的。和极小化操作得到的。和极小化操作得到的。n n从可从可从可从可计计算理算理算理算理论论可知每一个原始可知每一个原始可知每一个原始可知每一个原始递归递归函数都是函数都是函数都是函数都是图图灵灵灵灵机可机可机可机可计计算的。算的。算的。算的。 4.1计算模型与二进制计算模型与二进制4.1.2二进制计算机的数字系统计算机的数字系统计算机的数字系统计算机的数字系统oo计算机采用的是二算机采用的是二进制数字系制数字系统。oo基本符号：基
15、本符号：0、1oo进位原位原则：逢二：逢二进一一oo优点：点：n n易于物理易于物理实现n n二二进制数运算制数运算简单n n机器可靠性高机器可靠性高n n通用性通用性强oo缺点：缺点：对人来人来说可可读性差性差十进制数的表示十进制数的表示十进制数的表示十进制数的表示各位数字与它的各位数字与它的各位数字与它的各位数字与它的权权相乘，其相乘，其相乘，其相乘，其积积相加。相加。相加。相加。例如例如例如例如: :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-
16、1-1+3*10+3*10-2-2 对对于任意的十于任意的十于任意的十于任意的十进进制数：制数：制数：制数：S=S=k kn n*10*10n n+k kn-1n-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
17、为为正整数。小数点的位置不言自明。正整数。小数点的位置不言自明。正整数。小数点的位置不言自明。正整数。小数点的位置不言自明。计算机的数字系统计算机的数字系统计算机的数字系统计算机的数字系统oo计计算机采用的是二算机采用的是二算机采用的是二算机采用的是二进进制数字系制数字系制数字系制数字系统统。二。二。二。二进进制和十制和十制和十制和十进进制一制一制一制一样样，是一种数制，它用于表示数的符号（数，是一种数制，它用于表示数的符号（数，是一种数制，它用于表示数的符号（数，是一种数制，它用于表示数的符号（数字）由于在字）由于在字）由于在字）由于在书书写中的位置不同而具有不同的写中的位置不同而具有不同的
18、写中的位置不同而具有不同的写中的位置不同而具有不同的值值。oo基本符号：基本符号：基本符号：基本符号：0 0、1 1oo进进位原位原位原位原则则：逢二：逢二：逢二：逢二进进一一一一oo优优点：点：点：点：n n易于物理易于物理易于物理易于物理实现实现n n二二二二进进制数运算制数运算制数运算制数运算简单简单n n机器可靠性高机器可靠性高机器可靠性高机器可靠性高n n通用性通用性通用性通用性强强oo缺点：缺点：缺点：缺点：对对人来人来人来人来说说可可可可读读性差性差性差性差二进制数二进制数 Sknkn-1k0.k-mkn2nkn-12n-1k020k-m2-m-mki2iin其中，其中，2称称为
19、二二进制的基数，制的基数，ki0,1,m,n为正整数。正整数。进一步，一步，读者可从十者可从十进制数和二制数和二进制数的一般表示制数的一般表示公式得到启公式得到启发，将，将这种表示推广到更一般的任意种表示推广到更一般的任意进制，制，不同之不同之处只是基数不一只是基数不一样。二进制数二进制数 二二进制制的的运运算算规则比比十十进制制的的运运算算规则简单得得多多。只只要要建建立立两两种种进制制的的数数据据之之间的的转换方方法法，那那么么，二二进制制将将具具有有更更多多的的优势。计算算机机的的理理论基基础是是逻辑和和代代数数。当当二二进制制与与同同样只只使使用用“真真”和和“假假”两两个个值的的逻辑
20、代代数数建建立立了了联系系后后，这就就为计算算机机的的逻辑设计提提供供了了便便利的工具。利的工具。不同进位计数制间的转换不同进位计数制间的转换不同进位计数制间的转换不同进位计数制间的转换 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.2A)16=2*16-1+10*16-2
21、=(0.1640625)10二进制与十进制间的转换二进制与十进制间的转换二进制与十进制间的转换二进制与十进制间的转换 十进制十进制十进制十进制 二进制二进制二进制二进制十十进制整数制整数转换成二成二进制的整数制的整数“除除R取余取余”法，例如：法，例如：268268余余余余 数数数数 23423400低位低位低位低位 2172170 028281 124240 022220 02121000011高位高位高位高位所以所以所以所以 68681010100010010001002 2二进制与十进制间的转换二进制与十进制间的转换二进制与十进制间的转换二进制与十进制间的转换十进制十进制十进制十进制 二
22、进制二进制二进制二进制十十进制小数制小数转换成二成二进制小数制小数“乘乘R取整取整”法，例如：法，例如：高位高位0.31252=0.6250.6252=1.250.252=0.50.52=1.0所以所以0.312510=0.01012不同进位计数制间的转换不同进位计数制间的转换不同进位计数制间的转换不同进位计数制间的转换二、八、十六进制的相互转换二、八、十六进制的相互转换二、八、十六进制的相互转换二、八、十六进制的相互转换oo每位八每位八进制数相当于三位二制数相当于三位二进制数制数oo每位十六每位十六进制数相当于四位二制数相当于四位二进制数制数(1011010.10)2=(001011010.
23、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非数值信息的表示非数值信息的表示非数值信息的表示非数值信息的表示oo西文字符：西文字符：n n
24、ASCII码：用：用7位二位二进制数表示一个字符，制数表示一个字符，最多可以表示最多可以表示27=128个字符个字符n nEBCDIC码：用：用8位二位二进制数表示一个字制数表示一个字符，最多可以表示符，最多可以表示28=256个字符个字符oo汉字：n n应用用较为广泛的是广泛的是国家国家标准信息交准信息交换用用汉字字编码(GB2312-80标准准)，简称国称国标码。是二字是二字节码，用二个七位二，用二个七位二进制数制数编码表表示一个示一个汉字。字。4.2存储程序式计算机的基本存储程序式计算机的基本结构与工作原理结构与工作原理4.2.1冯诺依曼型计算机冯冯冯冯 诺依曼型计算机诺依曼型计算机诺依
25、曼型计算机诺依曼型计算机 图灵机的出灵机的出现为现代代计算机的算机的发明提供了明提供了重要的思想。重要的思想。图灵机的灵机的带子可以看成是子可以看成是计算机算机的存的存储设备，数据可以存，数据可以存储在上面，也可以根在上面，也可以根据需要擦去。据需要擦去。图灵机的命令相当于一灵机的命令相当于一组事先事先设计、存、存储好了的程序，它好了的程序，它们在控制器安排下，在控制器安排下，决定决定读写写头的每一步操作。的每一步操作。这样一种数学机器，一种数学机器，如果不考如果不考虑它的它的实用性，就思想和原理而言，用性，就思想和原理而言，确确实包含了包含了存存储程序程序的重要思想。的重要思想。冯冯冯冯 诺
26、依曼型计算机诺依曼型计算机诺依曼型计算机诺依曼型计算机oo计算算机机程程序序是是指指能能够在在计算算机机系系统中中运运行行的的程序。程序。oo现在在的的计算算机机全全称称为存存储程程序序式式通通用用电子子数数字字计算机。其含算机。其含义是：是：n n在在计算算机机中中各各种种信信息息用用数数字字代代码表表示示，如如指令、数指令、数值型数据、字符、型数据、字符、图像等。像等。n n在在物物理理机机制制上上，数数字字代代码以以数数字字型型信信号号出出现。oo信息表示数字化信息表示数字化-理解理解计算机工作原理的基算机工作原理的基本出本出发点。点。冯冯冯冯 诺依曼型计算机诺依曼型计算机诺依曼型计算机
27、诺依曼型计算机oo目前有两种目前有两种电信号：信号：n n模模拟信信号号：一一种种在在时间上上连续的的信信号号，用用信号的某些参数（如幅信号的某些参数（如幅值）去模）去模拟信息。信息。n n数数字字信信号号：一一种种在在时间上上或或空空间上上不不连续（离散）的信号。（离散）的信号。冯冯冯冯 诺依曼型计算机诺依曼型计算机诺依曼型计算机诺依曼型计算机oo采用数字化方法表示信息的采用数字化方法表示信息的优点：点：n n抗干抗干扰能力能力强，可靠性高。，可靠性高。n n位位数数增增多多则数数的的表表示示范范围扩大大，可可以以表表示示更精确的数字。更精确的数字。n n物理上容易物理上容易实现，并可存，并
28、可存储。n n表示信息的表示信息的类型和范型和范围极其广泛。极其广泛。n n能用能用逻辑代数等数字代数等数字逻辑技技术进行行处理。理。冯冯冯冯 诺依曼型计算机诺依曼型计算机诺依曼型计算机诺依曼型计算机 ooENIAC的的结构构在在很很大大程程度度上上是是依依照照机机电系系统设计的，的，还存在存在重大的重大的线路路结构构等等问题。oo在在图灵灵等等人人工工作作的的影影响响下下，1946年年6月月，美美国国杰杰出出的的数数学学家家冯诺依依曼曼（VonNeumann）及及其其同同事事完完成成了了关关于于“电子子计算算装装置置逻辑结构构设计”的研究的研究报告，告，n n具具体体介介绍了了制制造造电子子
29、计算算机机和和程程序序设计的的新思想：新思想：存存储程序、程序、顺序控制序控制n n至至今今为止止，大大多多数数计算算机机采采用用的的仍仍然然是是冯诺依依曼曼型型计算算机机的的组织结构构，只只是是作作了了一一些些改改进而而已已。因因此此，冯诺依依曼曼被被人人们誉誉为“计算机器之父算机器之父”。冯冯冯冯 诺依曼型计算机的组织结构诺依曼型计算机的组织结构诺依曼型计算机的组织结构诺依曼型计算机的组织结构 输入设备和输出设备输入设备和输出设备输入设备和输出设备输入设备和输出设备输入设备和输出设备oo作用：是将信息作用：是将信息输入入计算机和算机和输出出计算机。算机。oo常常用用的的文文字字输入入设备是
30、是键盘（还有有扫描描仪、穿孔卡片穿孔卡片读入机和鼠入机和鼠标等等专用用输入入设备）n n当当在在键盘上上按按下下一一个个键时，按按下下的的键通通过编码变换成机器可成机器可读的数据形式，的数据形式，n n如如字字符符“A”变换成成ASCII码“1000001”，该编码数据随即存入存数据随即存入存储器等待器等待处理，理，n n通通过与与“1000001”对应的的字字符符点点阵数数据据在在屏幕上屏幕上显示一个字符示一个字符“A”。oo输出出设备有有打打印印机机、显示示器器、绘图仪、磁磁记录设备等。等。存储器存储器存储器存储器存储器oo存储器是一种数据或信息的存储部件，它分成很多存储单元，并按照一定的
31、方式进行排列。每个单元都编了号，称为存储地址。指令和数据存放在存储器中,而且对指令和数据同等对待，都不加区别地送到运算器中运算。指令在存储器中基本上是按执行顺序存储的，由指令计数器指明要执行的指令在存储器中的地址。存储器存储器存储器存储器oo存储器一般分为内存储器与外存储器两大类。内存一般安装在主机板上，根据材料和工作原理的不同，内存可分为随机存储器（RAM）和只读存储器（ROM）两种。控制器和运算器只能接受在内存中存放的指令和数据。oo外存一般安装在主机板之外，例如磁盘就是一种常用的外存。外存上面的信息可长久保存，但这些信息必须读入内存之后才能被控制器和运算器所利用。磁盘按其材料的不同，又可
32、分为软盘和硬盘两种。CPU(CPU(运算器和控制器 ) )central processing unitRegisterRegister、控制单元、控制单元、控制单元、控制单元oo计算机中控制数据操作的算机中控制数据操作的电路并不与主存直路并不与主存直接相接相连n n这些些电路被封装在一起，即路被封装在一起，即CPUooCPU含有自己的存含有自己的存储单元（元（register）n nRegister作作为临时空空间来存来存储CPU所操作的所操作的数，保存算数，保存算术逻辑单元的元的输入与入与输出数据出数据n n控制控制单元元负责将主存中的数据移到将主存中的数据移到register，然后通知算
33、然后通知算术逻辑单元所需要的数据在元所需要的数据在哪个哪个register总线总线总线总线oo总线：CPU与主存之与主存之间用用总线连接，利用接，利用总线n nCPU通通过提供存提供存储单元目元目标地址以及地址以及读信信号来号来选择、读取数据取数据n nCPU通通过提供存提供存储单元目元目标地址以及写信地址以及写信号来放置、写入信号号来放置、写入信号oo谁发明了什么明了什么n n程序存程序存储的概念：由的概念：由宾西法尼西法尼亚大学大学Moore电子工程学院的提出，子工程学院的提出，JohnvonNeumann只是先只是先发表了程序存表了程序存储的概念的概念CPUCPU和主存储器通过总线相连和
34、主存储器通过总线相连和主存储器通过总线相连和主存储器通过总线相连4.3数字逻辑与集成电路数字逻辑与集成电路4.3.1数字逻辑数字逻辑数字逻辑oo数字数字逻辑是数字是数字电路路逻辑设计的的简称，其内称，其内容是容是应用数字用数字电路路进行数字系行数字系统逻辑设计。oo组成成计算机的算机的逻辑部件可分部件可分为组合合逻辑电路路和和时序序逻辑电路两种。路两种。n n组组合合逻辑电逻辑电路路：由与：由与门、或、或门和非和非门等等门电路路组合而成的合而成的逻辑电路。路。n n时序序逻辑电路：由触路：由触发器和器和门电路路组成的成的具有具有记忆能力的能力的逻辑电路。路。门电门电路路路路oo“与与”门电路：
35、两个以上的路：两个以上的输入，一个入，一个输出。出。仅当所有的当所有的输入入为1时，输出才出才为1。P=A B Coo“或或”门电路：两个以上的路：两个以上的输入，一个入，一个输出。出。仅当有一个当有一个输入入为1时，输出就出就为1。P=A+ B+ Coo“非非”门电路：一个路：一个输入，一个入，一个输出。当出。当输入入为1时，输出出为0；输入入为0时，输出出为1。门电门电路路路路“与与”、“或或”、“非非”三种门电路示意图三种门电路示意图PPPABCABCA（a）（b）（c） 4.4机器指令与汇编语言机器指令与汇编语言4.4.1机器指令 机器指令oo为了了实现程序存程序存储的概念，的概念，C
36、PU要能要能识别二二进制制编码的指令的指令oo机器机器语言言指令集合以及指令集合以及编码系系统机器指令机器指令机器指令机器指令oo用用用用计计算机求解一个算机求解一个算机求解一个算机求解一个问题问题，必，必，必，必须须事先事先事先事先编编制好程序。程制好程序。程制好程序。程制好程序。程序是由指令序是由指令序是由指令序是由指令组组成的。每一台成的。每一台成的。每一台成的。每一台计计算机都算机都算机都算机都设计规设计规定了一定了一定了一定了一组组指令集合，称指令集合，称指令集合，称指令集合，称为为机器指令系机器指令系机器指令系机器指令系统统。oo机器指令的格式一般分机器指令的格式一般分机器指令的格
37、式一般分机器指令的格式一般分为为两部分，如下所示：两部分，如下所示：两部分，如下所示：两部分，如下所示： 指令格式：指令格式：指令格式：指令格式： 操作操作操作操作码码地址部分地址部分地址部分地址部分其中，操作其中，操作其中，操作其中，操作码码指出运算的种指出运算的种指出运算的种指出运算的种类类，如，如，如，如， ， ，跳，跳，跳，跳转转等，地址部分用来指示参与运算的数据保存等，地址部分用来指示参与运算的数据保存等，地址部分用来指示参与运算的数据保存等，地址部分用来指示参与运算的数据保存在什么地方，如存在什么地方，如存在什么地方，如存在什么地方，如存储储器的某个地址或某个寄存器等。器的某个地址
38、或某个寄存器等。器的某个地址或某个寄存器等。器的某个地址或某个寄存器等。操作操作操作操作码码和地址部分都用二和地址部分都用二和地址部分都用二和地址部分都用二进进制代制代制代制代码码表示。表示。表示。表示。机器指令机器指令机器指令机器指令oo机器指令一般可根据其功能划分机器指令一般可根据其功能划分为以下几以下几类： (1)控制指令；控制指令；(2)算算术运算指令；运算指令；(3)逻辑运算运算指令；指令；(4)移位操作指令；移位操作指令；(5)传送操作指令；送操作指令；(6)输入入/输出指令。出指令。oo应当注意的是，不同的机器，其指令系当注意的是，不同的机器，其指令系统是是不同的。不同的。oo指
39、令系指令系统的日的日渐增大增大虽然然给用用户的程序的程序设计带来了方便，但也来了方便，但也带来了硬件来了硬件设计复复杂性的性的增加和因增加和因译码、存、存储、寻址等开址等开销的增大而的增大而使运算速度下降。研究使运算速度下降。研究发现，指令系指令系统存在存在着改着改进的必要和可能。的必要和可能。指令系统指令系统指令系统指令系统ooCPU必必须能能够解解码并并执行的机器指令很少行的机器指令很少n n一旦一旦计算机可以算机可以执行一些基本的而且是精行一些基本的而且是精选的操作，加入的操作，加入额外的操作理外的操作理论上是不会上是不会改改变计算机的能力的算机的能力的oo是否充分利用是否充分利用这种特
40、性种特性导致了两种不同的致了两种不同的计算机算机设计：n nCISC(complexinstructionsetcomputer)n nRISC(reducedinstructionsetcomputer)CISCCISCoo最初人最初人们采用的是采用的是进一步增一步增强原有指令的功原有指令的功能，并能，并设置更置更为复复杂的指令的方法的指令的方法oo采用采用这种种设计思路的思路的计算机被称算机被称为复复杂指令指令系系统计算机（算机（CISC）。）。n nCISC的思路是由的思路是由IBM公司提出的，并以公司提出的，并以1964年年IBM研制的研制的IBM360系系统为代表。代表。CISCCI
41、SC缺点缺点缺点缺点oo80%的指令只在的指令只在20%的运行的运行时间里用到；里用到；oo一些指令非常繁一些指令非常繁杂，而，而执行效率甚至比用几行效率甚至比用几条条简单的基本指令的基本指令组合的合的实现还要慢。要慢。oo庞杂的指令系的指令系统也也给超大超大规模集成模集成电路路（VLSI）的的设计带来了困来了困难，n n它不但不利于它不但不利于设计自自动化技化技术的的应用，延用，延长了了设计周期，增加了成本，周期，增加了成本，n n容易增加容易增加设计中出中出现错误的机会，从而降的机会，从而降低了系低了系统的可靠性。的可靠性。RISCRISCoo思路主要是通思路主要是通过减少指令减少指令总数
42、和数和简化指令的化指令的功能来降低硬件功能来降低硬件设计的复的复杂度，从而提高指度，从而提高指令的令的执行速度。行速度。oo优点点:与与CISC技技术相比相比n n简化了指令系化了指令系统，适合超大，适合超大规模集成模集成电路路的的实现；n n提高了机器提高了机器执行的速度和效率；行的速度和效率；n n降低了降低了设计成本，提高了系成本，提高了系统的可靠性；的可靠性；n n提供了直接支持高提供了直接支持高级语言的能力，言的能力，简化了化了编译程序的程序的设计。机器指令机器指令oo机器指令系统每台数字电子计算机在设计中，都规定了一组指令。oo机器语言用机器指令形式编写的程序。oo在裸机级，计算机
43、语言关于算法的描述采用的是实际机器的机器指令，它的符号集是0，1，n n支撑实际机器的理论是图灵机等计算模型；n n在图灵机等计算模型理论的指导下，有关设计形态的主要成果有冯诺依曼型计算机等具体实现思想和技术，以及各类数字电子计算机产品。计算机语言在裸机级所取得的主要成果计算机语言在裸机级所取得的主要成果计算机语言在裸机级所取得的主要成果计算机语言在裸机级所取得的主要成果计算机语言抽象理论设计裸 机级 的主 要内 容和 成果语言的符号集为：0，1；用机器指令对算法进行描述图灵机（过程语言的基础）、波斯特系统（字符串处理语言的基础）、-演算（函数式语言的基础）等计算模型冯诺依曼型计算机等实现技术
44、；数字电子计算机产品4.4机器指令与汇编语言机器指令与汇编语言4.4.2汇编语言汇编语言汇编语言oo汇编语言言实际上是由一上是由一组汇编指令构成的指令构成的语言。每一条言。每一条汇编指令用某个西文字符串的指令用某个西文字符串的缩写来表示其所代表的操作，用符号来代表数写来表示其所代表的操作，用符号来代表数据的二据的二进制、八制、八进制和十制和十进制数字序列。大制数字序列。大多数情况下，一条多数情况下，一条汇编指令指令对应一条机器指一条机器指令，少数令，少数对应几条机器指令。例如，下面是几条机器指令。例如，下面是几条几条汇编指令的操作符，右指令的操作符，右边中文是名称。中文是名称。add 加法加法
45、idiv 有符号除法有符号除法mul 无符无符号乘法号乘法 neg 求求补xchg 交交换test 逻辑比比较jmp 无条件无条件转移移汇编语言汇编语言汇编语言汇编语言oo采采用用字字符符和和十十进制制数数来来代代替替二二进制制代代码的的思思想。想。oo例例3.10对2+6进行行计算的算法描述算的算法描述n n用机器指令用机器指令对“2+6”进行行计算的算法描述：算的算法描述：oo1011000000000110oo0000010000000010oo000000n n汇编语言言对“2+6”进行行计算的算法描述：算的算法描述：ooMOVALMOVAL，6 6ooADDALADDAL，2 2oo
46、MOVVCMOVVC，ALALoo汇编语言言语句与特定的机器指令有一一句与特定的机器指令有一一对应的关系，但是它的关系，但是它毕竟不同于由二竟不同于由二进制制组成的成的机器指令，它机器指令，它还需要需要经汇编程序翻程序翻译为机器机器指令后才能运行。指令后才能运行。oo汇编语言源程序言源程序经汇编程序翻程序翻译成机器指令，成机器指令，再在再在实际的机器中的机器中执行。行。n n就就汇编语言的用言的用户而言，而言，该机器是可以直机器是可以直接接识别汇编语言的，从而言的，从而产生了一个属于生了一个属于抽象形抽象形态的重要概念，即的重要概念，即虚虚拟机机的概念。的概念。n n一般一般说来，来，汇编程序
47、被看成是系程序被看成是系统软件的件的一部分。一部分。 汇编语言汇编语言oo当然，当然，汇编语言在可言在可读性和性和编写程序写程序时仍然仍然是不能令人是不能令人满意的，意的，这导致致进一步一步发展了高展了高级程序程序设计语言。不言。不过，由于高，由于高级语言在使言在使用用时通常通常还是要通是要通过编译程序逐步将高程序逐步将高级语言写的程序翻言写的程序翻译成机器指令的程序，而成机器指令的程序，而这种种翻翻译的的结果往往不如机器指令或果往往不如机器指令或汇编语言写言写的程序效率高，所以，直到今天，不少工程的程序效率高，所以，直到今天，不少工程师在系在系统软件的开件的开发中中还在使用机器指令和在使用机
48、器指令和汇编语言。言。4.5算法、数据结构与程序算法、数据结构与程序求解一个给定的问题，不同的人常编写出不同的然而都是正确的程序，这是为什么呢？这里存在两个层面的问题，一个是与计算方法密切相关的算法问题，另一个是程序设计的技术问题。4.5算法、数据结构与程序算法、数据结构与程序4.5.1算法算法的历史简介算法的历史简介算法的历史简介算法的历史简介 oo公元公元825年，阿拉伯数学家阿科瓦里茨米年，阿拉伯数学家阿科瓦里茨米（AlKhowarizmi）写了著名的波斯教科写了著名的波斯教科书（Persian Textbook），），书中概括了中概括了进行四行四则算算术运算的法运算的法则。n n“算法
49、算法”（Algorithm）一一词就来源于就来源于这位数学家的名字。位数学家的名字。oo后来，后来，韦氏新世界氏新世界词典将其定典将其定义为“解解某种某种问题的任何的任何专门的方法的方法”。oo而据考古学家而据考古学家发现，古巴比，古巴比伦人在人在求解代数求解代数方程方程时，就已，就已经采用了采用了“算法算法”的思想。的思想。丢番图方程的可解性问题丢番图方程的可解性问题丢番图方程的可解性问题丢番图方程的可解性问题 oo古希腊数学家古希腊数学家丢番番图（Diophantus）：代数：代数学之父学之父n n在算在算术（Arithmetica）一一书中提出了中提出了有关有关两个或多个两个或多个变量整
50、数系数方程量整数系数方程的有理的有理数解数解问题。n n对于具有于具有整数系数的不定方程整数系数的不定方程，如果只考，如果只考虑其其整数解整数解，这类方程就叫做方程就叫做丢番番图方程。方程。oo“丢番番图方程可解性方程可解性问题”的的实质为：能否：能否写出一个可以判定写出一个可以判定任意任意丢番番图方程是否可解方程是否可解的算法？的算法？一个未知数的线性丢番图方程的解一个未知数的线性丢番图方程的解一个未知数的线性丢番图方程的解一个未知数的线性丢番图方程的解ooax=b，只只要要a能能整整除除b，就就可可判判定定其其有有整整数解，数解，该整数解即整数解即b/a。两个未知数的线性丢番图方程两个未知
51、数的线性丢番图方程两个未知数的线性丢番图方程两个未知数的线性丢番图方程 的解的解的解的解ooax+by=c，先求出先求出a和和b的最大公因子的最大公因子d，若若d能整除能整除c，则该方程有解（整数解）。方程有解（整数解）。 oo问：方程：方程1313x+26y=52有无整数解？有无整数解？n n答：答：1313和和2626的最大公因子是的最大公因子是1313，1313又可整又可整除除5252，故，故该方程有整数解（如方程有整数解（如x=2，y=1即即方程的解）。方程的解）。oo例例4.24.2问：方程：方程2 2x+4y=15有无整数解？有无整数解？n n答：答：2 2和和4 4的最大公因子是
52、的最大公因子是2 2，2 2不能整除不能整除1515，故，故该方程无整数解。方程无整数解。 两个未知数的线性丢番图方程两个未知数的线性丢番图方程两个未知数的线性丢番图方程两个未知数的线性丢番图方程 的解：的解：的解：的解：欧几里德算法欧几里德算法欧几里德算法欧几里德算法 oo给定定两两个个正正整整数数m和和n，求求它它们的的最最大大公公因因子子，即能同即能同时整除整除m和和n的最大正整数。的最大正整数。oo步步骤如下：如下：n n（1）以以n除除m，并并令令所所得得余余数数为r（r必必小小于于n）；）；n n（2）若若r=0，算算法法结束束，输出出结果果n；否否则，继续步步骤（3）；）；n n
53、（3）将将n置置换为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是是互互质的的”（即即除除1以以外外，
54、m和和n没没有公因子）有公因子）这个命个命题的真假。的真假。oo不不难想象，不同的求解方法将想象，不同的求解方法将产生出不同的生出不同的算法，不同的算法将使我算法，不同的算法将使我们设计出不同的程出不同的程序，而决定序，而决定这个程序功能的本个程序功能的本质是是计算方法算方法及其算法。一般地及其算法。一般地说，对不同不同计算方法算方法过程程的抽象描述就的抽象描述就产生了相生了相应的不同算法，但同的不同算法，但同一算法由不同的人来写程序一算法由不同的人来写程序则完全可能完全可能设计出差出差别很大的程序。很大的程序。oo凭直凭直觉想象想象给出的算法往往不是最好的算法。出的算法往往不是最好的算法。算
55、法算法算法的定义和特征算法的定义和特征 算法的定义和特征算法的定义和特征 算法算法被被认为是是计算科学的核心算科学的核心问题之一。之一。 有关算法的定有关算法的定义不少，其内涵基本上是一致的，不少，其内涵基本上是一致的，其中最其中最为著名的是著名的是计算机科学家克努特在其算机科学家克努特在其经典巨典巨著著计算机程序算机程序设计的的艺术（The Art of Computer Programming）第一卷中）第一卷中对算法的定算法的定义和特性所作的有关描述。和特性所作的有关描述。1算法的一些定义算法的一些定义 oo定定定定风风1 1：给给定定定定问题问题和和和和设备设备，一个算法是用，一个算法
56、是用，一个算法是用，一个算法是用该设备该设备可理可理可理可理解的解的解的解的语语言表示的，解决言表示的，解决言表示的，解决言表示的，解决这这个个个个问题问题的一种方法的精确的一种方法的精确的一种方法的精确的一种方法的精确刻划。特刻划。特刻划。特刻划。特别别，算法具有下列特征属性：，算法具有下列特征属性：，算法具有下列特征属性：，算法具有下列特征属性： (1) (1) 算法算法算法算法应应用于一个具体的用于一个具体的用于一个具体的用于一个具体的输输入集合或入集合或入集合或入集合或问题问题描述将在描述将在描述将在描述将在有有有有穷穷步步步步动动作序列之后得到作序列之后得到作序列之后得到作序列之后得
57、到结结果；果；果；果； (2) (2) 该该序列有一个唯一的初始序列有一个唯一的初始序列有一个唯一的初始序列有一个唯一的初始动动作；作；作；作； (3) (3) 该该序列中的每一个序列中的每一个序列中的每一个序列中的每一个动动作有一个唯一的后作有一个唯一的后作有一个唯一的后作有一个唯一的后继动继动作；作；作；作； (4) (4) 该该序列序列序列序列终终止止止止时时或者得到或者得到或者得到或者得到这这个个个个问题问题的解，或者因的解，或者因的解，或者因的解，或者因该该问题问题不可解而不可解而不可解而不可解而获获得不可解得不可解得不可解得不可解说说明。明。明。明。算法的定义和特征算法的定义和特征
58、1算法的一些定义算法的一些定义 oo定定定定风风1 1：给给定定定定问题问题和和和和设备设备，一个算法是用，一个算法是用，一个算法是用，一个算法是用该设备该设备可理可理可理可理解的解的解的解的语语言表示的，解决言表示的，解决言表示的，解决言表示的，解决这这个个个个问题问题的一种方法的精确的一种方法的精确的一种方法的精确的一种方法的精确刻划。特刻划。特刻划。特刻划。特别别，算法具有下列特征属性：，算法具有下列特征属性：，算法具有下列特征属性：，算法具有下列特征属性： (1) (1) 算法算法算法算法应应用于一个具体的用于一个具体的用于一个具体的用于一个具体的输输入集合或入集合或入集合或入集合或问
59、题问题描述将在描述将在描述将在描述将在有有有有穷穷步步步步动动作序列之后得到作序列之后得到作序列之后得到作序列之后得到结结果；果；果；果； (2) (2) 该该序列有一个唯一的初始序列有一个唯一的初始序列有一个唯一的初始序列有一个唯一的初始动动作；作；作；作； (3) (3) 该该序列中的每一个序列中的每一个序列中的每一个序列中的每一个动动作有一个唯一的后作有一个唯一的后作有一个唯一的后作有一个唯一的后继动继动作；作；作；作； (4) (4) 该该序列序列序列序列终终止止止止时时或者得到或者得到或者得到或者得到这这个个个个问题问题的解，或者因的解，或者因的解，或者因的解，或者因该该问题问题不可
60、解而不可解而不可解而不可解而获获得不可解得不可解得不可解得不可解说说明。明。明。明。算法的定义和特征算法的定义和特征定义定义2（Knuth算法定义）算法定义）一个算法，就是一个有一个算法，就是一个有一个算法，就是一个有一个算法，就是一个有穷规则穷规则的集合，其中之的集合，其中之的集合，其中之的集合，其中之规则规则确定了一个解决某一特定确定了一个解决某一特定确定了一个解决某一特定确定了一个解决某一特定类类型型型型问题问题的运算序列。此外，的运算序列。此外，的运算序列。此外，的运算序列。此外，算法的算法的算法的算法的规则规则序列序列序列序列须满须满足如下五个重要条件（特性）：足如下五个重要条件（特
61、性）：足如下五个重要条件（特性）：足如下五个重要条件（特性）：(1) (1) 有有有有穷穷性。算法必性。算法必性。算法必性。算法必须总须总是在是在是在是在执执行有行有行有行有穷穷步之后步之后步之后步之后结结束；束；束；束；(2) (2) 确定性。算法的每一个步确定性。算法的每一个步确定性。算法的每一个步确定性。算法的每一个步骤骤必必必必须须是确切地定是确切地定是确切地定是确切地定义义的；的；的；的；(3) (3) 输输入。算法有零个或多个入。算法有零个或多个入。算法有零个或多个入。算法有零个或多个输输入；入；入；入；(4) (4) 输输出。算法有一个或多个出。算法有一个或多个出。算法有一个或多
62、个出。算法有一个或多个输输出，即与出，即与出，即与出，即与输输入有某个入有某个入有某个入有某个特定关系的量；特定关系的量；特定关系的量；特定关系的量；(5) (5) 能行性。算法中有待能行性。算法中有待能行性。算法中有待能行性。算法中有待执执行的运算和操作必行的运算和操作必行的运算和操作必行的运算和操作必须须是相是相是相是相当基本的，即是当基本的，即是当基本的，即是当基本的，即是说说，它，它，它，它们们原原原原则则上都是能上都是能上都是能上都是能够够精确地精确地精确地精确地进进行的，行的，行的，行的，而且用笔和而且用笔和而且用笔和而且用笔和纸纸做有做有做有做有穷穷次就可以完成。次就可以完成。次
63、就可以完成。次就可以完成。2 2算法的重要特性算法的重要特性算法的重要特性算法的重要特性oo有有穷性性：一一个个算算法法在在执行行有有穷步步之之后后必必须结束。束。如如在在欧欧几几里里德德算算法法中中，由由于于m和和n均均为正正整整数数，在在步步骤（1）之之后后，r必必小小于于n，若若r0，下下一一次次进行行步步骤（1）时，n的的值已已经减减小小，而而正正整整数数的的递降降序序列列最最后后必必然然要要终止止。因因此此，无无论给定定m和和n的的原原始始值有有多多大大，步步骤（1）的）的执行都是有行都是有穷次。次。2 2算法的重要特性算法的重要特性算法的重要特性算法的重要特性oo确确定定性性：算算
64、法法的的每每一一个个步步骤必必须要要确确切切地地定定义。即即算算法法中中所所有有有有待待执行行的的动作作必必须严格格而而不不含含混地混地进行行规定，不能有歧定，不能有歧义性。性。如如欧欧几几里里德德算算法法中中，步步骤（1）中中明明确确规定定“以以n除除m”，而而不不能能有有类似似“以以n除除m或或以以m除除n”这类有两种可能做法的有两种可能做法的规定。定。oo输入入：算算法法有有零零个个或或多多个个的的输入入，即即在在算算法法开开始之前，始之前，对算法最初算法最初给出的量。出的量。如欧几里德算法中，有两个如欧几里德算法中，有两个输入，即入，即m和和n。2 2算法的重要特性算法的重要特性算法的
65、重要特性算法的重要特性oo输出出：算算法法有有一一个个或或多多个个的的输出出，即即与与输入入有有某某个个特特定定关关系系的的量量，简单地地说就就是是算算法法的的最最终结果。果。如如在在欧欧几几里里德德算算法法中中只只有有一一个个输出出，即即步步骤（2）中的）中的n。oo能能行行性性：算算法法中中有有待待执行行的的运运算算和和操操作作必必须是是相当基本的。相当基本的。如：欧几里德算法最如：欧几里德算法最终得出正确的得出正确的结果。果。2 2算法的重要特性算法的重要特性算法的重要特性算法的重要特性oo输出出：算算法法有有一一个个或或多多个个的的输出出，即即与与输入入有有某某个个特特定定关关系系的的
66、量量，简单地地说就就是是算算法法的的最最终结果。果。如如在在欧欧几几里里德德算算法法中中只只有有一一个个输出出，即即步步骤（2）中的）中的n。oo能能行行性性：算算法法中中有有待待执行行的的运运算算和和操操作作必必须是是相当基本的。相当基本的。如：欧几里德算法最如：欧几里德算法最终得出正确的得出正确的结果。果。2 2算法的重要特性算法的重要特性算法的重要特性算法的重要特性oo有有穷性性和和能能行行性性是是算算法法最最重重要要的的两两个个特特征征。对有有些些问题来来说，如如果果我我们给出出了了一一个个类似似于于算算法法的的有有穷运运算算序序列列，而而它它对某某些些输入入可可能能不不停停机机，那那
67、么么，我我们就就称称这样的的运运算算序序列列为一一个个过程程。算算法法和和过程程都都满足足能能行行性性和和确确定定性性，唯唯一一的的本本质区区别是是算算法法的的执行行必必须终止止，而而过程程则不不然然，它它可可以以永永不不停停止止。需需要要指指出出的的是是，高高级程程序序设计语言言中中也也有有过程程的的概概念念，但但与与这里里所所讲的的过程不同，那里程不同，那里实际上指的是一种子程序。上指的是一种子程序。3算法的形式化定义算法的形式化定义 算法是一个四元算法是一个四元组，即（，即（Q，I，F）。）。其中：其中：（1）Q是是一一个个包包含含子子集集I和和的的集集合合，它它表表示示计算的状算的状态
68、；（2）I表示表示计算的算的输入集合；入集合；（3）表示表示计算的算的输出集合；出集合；（4）F表表示示计算算的的规则，它它是是一一个个由由Q到到它它自自身身的的函函数数，且且具具有有自自反反性性，即即对于于任任何何一一个个元元素素qQ，有有F(q)=q。算法算法算法实例算法实例 例例4.4求求1+2+3+100 设变量量X表表示示加加数数，Y表表示示被被加加数数，用用自自然然语言言将算法描述如下：将算法描述如下：（1）将）将1赋值给X；（2）将将2赋值给Y；（3）将将X与与Y相加，相加，结果存放在果存放在X中；中；（4）将）将Y加加1，结果存放在果存放在Y中；中；（5）若若Y小小于于或或等等
69、于于100，转到到步步骤（3）继续执行；否行；否则，算法，算法结束，束，结果果为X。例例4.5求解调和级数求解调和级数设变量量X表示累加和，表示累加和，变量量I表示循表示循环的次数，自的次数，自然然语言描述算法如下：言描述算法如下：（1）将）将0赋值给X；（2）将将1赋值给I；（3）将将X与与1/I相加，然后把相加，然后把结果存入果存入X；（4）将将I加加1；（5）若）若I大于等于大于等于N，算法算法结束，束，结果果为X；否否则转到步到步骤（3）继续执行。行。例例例例4.64.6求解斐波那契数求解斐波那契数求解斐波那契数求解斐波那契数 0 0，1 1，1 1，2 2，3 3，5 5，8 8，1
70、313，2121，3434， （1 1）oo来来 源源 于于 12021202年年 意意 大大 利利 数数 学学 家家 斐斐 波波 那那 契契（ L.P.Fibonacci） 在在 其其 珠珠 算算 之之 书 （Liber Abaci）中中提提出出的的一一个个“兔兔子子问题”：n n假假设一一对刚出出生生的的兔兔子子一一个个月月后后就就能能长大大，再再过一一个个月月就就能能生生下下一一对兔兔子子，并并且且此此后后每每个个月月都都能能生生一一对兔兔子子，且且新新生生的的兔兔子子在在第二个月后也是每个月生一第二个月后也是每个月生一对兔子。兔子。n n问：一一对兔兔子子一一年年内内可可繁繁殖殖成成多
71、多少少对兔兔子子？oo在在序序列列（1）中中，每每个个数数都都是是它它的的前前两两个个数数之之和和，Fn表表示示这个个序序列列的的第第n个个数数，该序序列列可以形式化的定可以形式化的定义为：n nF0=0，F1=1，Fn+2=Fn+1+Fn，n0oo斐斐波波那那契契数数列列还是是一一个个关关于于加加法法算算法法的的典典型型实例。例。oo设变量量X表示前一个数的表示前一个数的值，即定，即定义中的中的Fn，变量量Y表示当前数的表示当前数的值，即定，即定义中的中的Fn+1，变量量Z表示后一个数的表示后一个数的值，即定，即定义中的中的Fn+2。那那么求解么求解问题的自然的自然语言描述如下：言描述如下：
72、算法设计算法设计算法设计算法设计（1 1）如如如如果果果果=0=0，那那那那么么么么将将将将0 0赋赋值值给给Y Y，并并并并输输出出出出Y Y，转转步步步步骤骤（1111）继续执继续执行；行；行；行；（2 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）将将将
73、将Y Y赋值给赋值给X X；（8 8）将将将将Z Z赋值给赋值给Y Y；（9 9）将将将将Y Y输输出；出；出；出；（1010）将）将）将）将I I加加加加1 1，转转步步步步骤骤（5 5）继续执继续执行；行；行；行；（1111）算法）算法）算法）算法结结束。束。束。束。算法算法算法的表示方法算法的表示方法原语原语原语原语oo一个算法的表达需要使用一些一个算法的表达需要使用一些语言形式言形式n n自然自然语言言“Visitinggrandchildrencanbenerve-racking”,可能即意味着可能即意味着孙子子孙女女导致了致了很多很多问题，也表示去看他，也表示去看他们可能会有可能会
74、有问题n n图形形语言：很少人能言：很少人能够根据折根据折纸图给出的步出的步骤成功地叠出一只成功地叠出一只鸟来，但一个来，但一个专门学学习过折折纸的学生可以的学生可以轻松完成松完成oo当用来描述算法的当用来描述算法的语言并没有被准确定言并没有被准确定义或者没或者没有有给予足予足够信息的信息的时候，交流就会候，交流就会产生生问题原语原语原语原语oo通通过建立一个可以描述算法的意建立一个可以描述算法的意义明确的基明确的基本本块（原原语）集合，）集合，计算机科学即就可以解算机科学即就可以解决上述的勾通决上述的勾通问题oo原原语描述算法需要建立一个描述算法需要建立一个统一的一的细节描述描述级别，原，原
75、语连同一同一组表达了原表达了原语如何表达复如何表达复杂的想法的的想法的规定定组成了一种程序成了一种程序设计语言言oo组成成n n语法：原法：原语的符号表示的符号表示n n语义：表达了原：表达了原语的意的意义1 1自然语言自然语言自然语言自然语言oo缺点缺点n n由由于于自自然然语言言的的歧歧义性性，容容易易导致致算算法法执行的不确定性；行的不确定性；n n自自然然语言言的的语句句一一般般太太长，从从而而导致致了了用自然用自然语言描述的算法太言描述的算法太长；n n由由于于自自然然语言言表表示示的的串串行行性性，因因此此，当当一一个个算算法法中中循循环和和分分支支较多多时就就很很难清清晰地表示出
76、来；晰地表示出来；n n自自然然语言言表表示示的的算算法法不不便便翻翻译成成计算算机机程序程序设计语言理解的言理解的语言。言。2 2流程图流程图流程图流程图 oo它它 采采 用用 美美 国国 国国 家家 标 准准 化化 协 会会ANSI（ AmericanNationalStandardInstitute）规定的一定的一组图形符号来表示算法。形符号来表示算法。n n流流程程图可可以以很很方方便便地地表表示示顺序序、选择和和循循环结构构，而而任任何何程程序序的的逻辑结构构都都可可以用以用顺序、序、选择和循和循环结构来表示，构来表示，n n流程流程图可以表示任何程序的可以表示任何程序的逻辑结构。构
77、。n n用用流流程程图表表示示的的算算法法不不依依赖于于任任何何具具体体的的计算机和算机和计算机程序算机程序设计语言，言，（1 1）求解例）求解例）求解例）求解例4.44.4的算法流程图的算法流程图的算法流程图的算法流程图（2 2）求解例）求解例）求解例）求解例4.54.5的算法流程图的算法流程图的算法流程图的算法流程图 （3 3）求解例）求解例）求解例）求解例4.64.6的算法流程图的算法流程图的算法流程图的算法流程图 3 3伪代码伪代码伪代码伪代码（1 1）求解例）求解例）求解例）求解例4.44.4的伪代码算法描述：的伪代码算法描述：的伪代码算法描述：的伪代码算法描述：BEGIN(BEGI
78、N(算法开始算法开始算法开始算法开始) )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 1YYPrintXPrintX，Y Yfor(i=1;i=n-1;i+)for(i=1;i=n-1;i+) X+YZX+YZYXYXZYZYPrintYPrintY ENDEND4 4计算机程序设计
79、语言计算机程序设计语言计算机程序设计语言计算机程序设计语言 oo计算算机机程程序序设计语言言描描述述的的算算法法（程程序序）是是清晰的、清晰的、简明的，最明的，最终也能由也能由计算机算机处理的。理的。oo缺点：缺点：n n算算法法的的基基本本逻辑流流程程难于于遵遵循循。与与自自然然语言一言一样，程序，程序设计语言也是基于串行的言也是基于串行的n n用用特特定定程程序序设计语言言编写写的的算算法法限限制制了了与与他人的交流，不利于他人的交流，不利于问题的解决；的解决；n n要要花花费大大量量的的时间去去熟熟悉悉和和掌掌握握某某种种特特定定的程序的程序设计语言；言；n n要要求求描描述述计算算步步
80、骤的的细节，而而忽忽视算算法法的的本本质。例例例例4.44.4的计算机程序设计语言（的计算机程序设计语言（的计算机程序设计语言（的计算机程序设计语言（C C语言）的算法描述：语言）的算法描述：语言）的算法描述：语言）的算法描述： main()main() intX,Y;intX,Y;X=1;X=1;Y=2;Y=2;while(Y=100)while(Y=100)X=X+Y;X=X+Y;Y=Y+1;Y=Y+1;printf(%d,X);printf(%d,X); 例例例例4.54.5的计算机程序设计语言（的计算机程序设计语言（的计算机程序设计语言（的计算机程序设计语言（C C语言）的算法描述语言
81、）的算法描述语言）的算法描述语言）的算法描述 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+1;while(I=n);while(I=n);printf(n%f,X);printf(n%f,X);算法算法算法分析算法分析oo在在计算算机机科科学学研研究究中中，事事实上上存存在在一一条条规律律：一一个个问题，当当它它的的描描述述及及
82、其其求求解解方方法法或或求求解解过程程可可以以用用构构造造性性数数学学描描述述，而而且且该问题所所涉涉及及的的论域域为有有穷，或或虽为无无穷但但存存在在有有穷表表示示时，那那么么，这个个问题一一定定能能用用计算算机机来来求解；求解；oo反反过来来，凡凡是是能能用用计算算机机求求解解的的问题，也也一一定定能能对该问题的的求求解解过程程数数学学化化，而而且且这种种数学化是构造性的。数学化是构造性的。算法分析考虑的问题；算法分析考虑的问题；算法分析考虑的问题；算法分析考虑的问题； oo当当一一个个问题的的求求解解获得得了了计算算方方法法和和算算法法时，并并不不等等于于万万事事大大吉吉了了。在在许多多
83、情情况况下下，找找到到求求解解一一个个问题的的算算法法只只是是走走完完了了第第一一步步。至至于于现实是是否否可可以以计算算，则取取决决于于算算法法的的存存在在性性和和计算算的的复复杂性性，即即取取决决于于该问题是是否否存存在在求求解解算算法法，算算法法所所需需要要的的时间和和空空间在在数数量量级上能否被接受。上能否被接受。oo要要注注意意的的是是，有有的的问题虽然然存存在在求求解解问题的的计算算方方法法，但但是是，不不存存在在算算法法。原原因因有有两两种种可可能能：一一是是计算算方方法法可可能能不不是是构构造造性性的的；二二是是虽为构构造造性性的的，但但计算算方方法法不不能能保保证计算算过程在
84、任何初程在任何初值的情况下都能的情况下都能结束。束。算法分析考虑的问题；算法分析考虑的问题；算法分析考虑的问题；算法分析考虑的问题； oo解解一一个个问题，往往往往有有若若干干不不同同的的算算法法，这些些算算法法决决定定着着根根据据该算算法法编写写的的程程序序性性能能的的好好坏坏。那那么么，在在保保证算算法法正正确确性性的的前前提提下下，如如何确定算法的何确定算法的优劣就是一个劣就是一个值得研究的得研究的课题。oo在算法的分析中，一般在算法的分析中，一般应考考虑以下以下3个个问题：（1）算法的算法的时间复复杂度；度；（2）算法的空）算法的空间复复杂度；度；（3）算法是否便于）算法是否便于阅读、
85、修改和、修改和测试。算法分析考虑的问题；算法分析考虑的问题；算法分析考虑的问题；算法分析考虑的问题； oo使使用用计算算机机计算算各各种种问题，需需要要存存储空空间、计算算时间。不不同同的的算算法法计算算所所需需要要的的时间和和空空间是是不不同同的的。所所谓算算法法的的复复杂性性就就是是对算算法法计算算所所需需要要的的时间和和空空间的的一一种种度度量量。由由于于不不同同的的计算算机机千千差差万万别，运运算算速速度度和和字字长可可以以相相差差很很大大，因因此此，不不可可能能用用算算法法在在某某一一台台计算算机机上上计算算所所需需要要的的实际的的时间和和存存储单元元（空空间）去去衡衡量量这个个算算
86、法法的的复复杂性性。那那么么，怎怎样才才能能准准确确刻刻划划算算法法的的计算算复复杂性性呢呢？什么是算法的复杂性呢？什么是算法的复杂性呢？什么是算法的复杂性呢？什么是算法的复杂性呢？oo科科学学家家们采采用用了了与与问题规模模大大小小相相联系系的的一一个个近近似似函函数数（称称为渐近近增增长率率）来来刻刻画画算算法法的的计算算复复杂度度。该函函数数表表示示了了算算法法随随问题规模模大大小小变化化引引起起的的算算法法中中抽抽象象的的基基本本运运算算执行的次数或存行的次数或存储空空间量的量的变化化规律。律。oo例例如如，某某个个计算算问题当当输入入规模模分分别为1，2，3，n时，经分分析析算算法法
87、中中抽抽象象的的基基本本运运算算次次数数分分别为1，4，9，n2，那那么么，就就可可以以用用函函数数n2来来刻刻划划这个个算算法法的的时间复复杂性性，并称并称这个算法的个算法的时间复复杂性度量性度量为 (n2)级。（1 1）算法的时间复杂度；）算法的时间复杂度；）算法的时间复杂度；）算法的时间复杂度； oo有有了了复复杂性性度度量量函函数数，一一旦旦选定定具具体体计算算机机，可可以以根根据据这台台计算算机机对某某个个n值的的实际运运算算速速度度比比较准准确确地地估估算算出出对其其他他的的n值完完成成计算算所所需要的需要的时间。oo于于是是，对各各种种算算法法的的复复杂性性进行行分分析析的的关关
88、键是是要要设法法去去找找出出这样的的函函数数，它它涉涉及及到到与与数数学学密密切切相相关关的的算算法法的的设计原原理理、思思想想和和方方法法，算法分析是具有智力挑算法分析是具有智力挑战性的研究性的研究课题。（1 1）算法的时间复杂度；）算法的时间复杂度；）算法的时间复杂度；）算法的时间复杂度； oo用用T(n)表示，表示，n表示表示问题规模的大小。模的大小。oo使用一个使用一个记号号 n nOrder（数量数量级）的第一个字母，）的第一个字母，n n允允 许 使使 用用 “=”代代 替替 “”。 如如n2+n+1= (n2)（1 1）算法的时间复杂度；）算法的时间复杂度；）算法的时间复杂度；）
89、算法的时间复杂度； （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)常见的大常见的大常见的大常见的大 表示形式有：表示形式有：表示形式有：表示形式有： (1)：称：称为常数常数级； (logn)：称称为对数数级； (n)：称：称
90、为线性性级； (nc)：称：称为多多项式式级； (cn)：称：称为指数指数级； (n!)：称：称为阶乘乘级。在在梵梵天天塔塔问题中中，需需要要移移动的的盘子子次次数数为h(n)=2n-1，则该问题的的算算法法时间复复杂度度表表示示为 (2n)；例例4.4的的算算法法时间复复杂度度表表示示为 (1)；例例4.5的的算算法法时间复复杂度度表表示示为 (n)；例例4.6的算法的算法时间复复杂度表示度表示为 (n)等等。等等。 一一般般而而言言，对于于较复复杂的的算算法法，应将将它它分分成成容容易易估估算算的的几几个个部部分分，然然后后用用 的的求求解解原原则计算算整整个个算算法法的的时间复复杂度度，
91、最最好好不不要要采采用用指指数数级和和阶乘乘级的的算算法法，而而应尽尽可可能能选用用多多项式式级或或线性性级等等时间复复杂度度较小小的的算算法法。另另外外，还要要在在算算法法最最好好、平平均均和和最最坏坏的的情情况况下区下区别执行效率的不同。行效率的不同。在在阶乘乘级的的算算法法中中，如如果果问题规模模n为10，则算算法法时间复复杂度度为10！（3，628，800）。若若要要检验10！种种情情况况，设每每种种情情况况需需要要1毫毫秒秒的的计算算时间，则整整个个计算算将将需需1小小时左左右右。一一般般来来说，如如果果选用用了了阶乘乘级的的算算法法，则当当问题规模模等等于于或或者者大大于于10时，
92、就就要要认真真考考虑算算法的适用性法的适用性问题。算法的空间复杂度算法的空间复杂度算法的空间复杂度算法的空间复杂度oo指算法在指算法在执行行过程中所占存程中所占存储空空间的大小，的大小，oo用用S(n)表示，表示，S为英文英文单词Space的第一个字的第一个字母。与算法的母。与算法的时间复复杂度相同度相同oo算法的空算法的空间复复杂度度S(n)也可表示也可表示为： S(n)= (g(n)。算法算法算法的研究算法的研究算法算法oo算法：定算法：定义一一项工作如何完成的步工作如何完成的步骤的集合的集合n n在一台机器可以完成一个任在一台机器可以完成一个任务之前，必之前，必须找到完成找到完成这个任个
93、任务的算法并且用与机器兼的算法并且用与机器兼容的方式来描述容的方式来描述n n一个与机器兼容的算法的描述一个与机器兼容的算法的描述程序程序oo算法的研究开始是作算法的研究开始是作为数学的一个学科数学的一个学科n n目目标：找到描述特定：找到描述特定类型型问题是如何被解是如何被解决的指令的集合，如决的指令的集合，如Euclidean算法算法n n一旦一个完成任一旦一个完成任务的算法被找到，任的算法被找到，任务的的实现就不再需要就不再需要对算法原理的理解，任算法原理的理解，任务的的实现仅仅是遵循算法的只是是遵循算法的只是过程程n n现有的解决有的解决问题需要的智慧被需要的智慧被编码进了算了算法法算
94、法转化为智慧算法转化为智慧算法转化为智慧算法转化为智慧oo通通过使用算法来得到并使用算法来得到并转化智慧，我化智慧，我们才可才可以构建起可以表以构建起可以表现智慧行智慧行为的机器的机器。n n机器表机器表现的智能等的智能等级受到通受到通过算法算法转化的化的智慧所限制智慧所限制n n如果没有解决如果没有解决问题的算法，意味着的算法，意味着问题的的解决方案超出了机器的能力范解决方案超出了机器的能力范围oo算法的开算法的开发就成了就成了计算机算机领域的一个主要目域的一个主要目标n n如何找到算法如何找到算法一个十分接近于一个十分接近于寻找通用找通用问题解决方案解决方案n n描述描述这个算法个算法转变
95、为一个清晰的指令的一个清晰的指令的集合（程序集合（程序设计语言描述）言描述）计算机技术别用于复杂问题（大型软件系统）计算机技术别用于复杂问题（大型软件系统）计算机技术别用于复杂问题（大型软件系统）计算机技术别用于复杂问题（大型软件系统）oo不不仅仅包括包括实现任任务的的单个算法的开个算法的开发n n还要求要求对组件之件之间的交互的交互进行行设计n n软件工程：借件工程：借鉴了工程了工程领域、域、项目管理目管理领域、人力域、人力资源管理以及程序源管理以及程序语言言设计领域域的的经验执行算法的机器的设计和实现执行算法的机器的设计和实现执行算法的机器的设计和实现执行算法的机器的设计和实现oo数据的存
96、数据的存储oo数据的操作数据的操作oo体系体系结构中涵盖了构中涵盖了对现今技今技术的的讨论n n我我们的目的目标不是去熟知不是去熟知类似当今体系似当今体系结构构是如何用是如何用电路来路来实现这样的的细节问题，那，那将会将会导致致过分陷入分陷入电子工程学科子工程学科n n正如昨天的正如昨天的齿轮驱动的的计算机算机让位于位于电子子设备一一样，今天的，今天的电子技子技术也也许很快也被很快也被其它的技其它的技术所取代所取代理想情况下理想情况下oo希望希望计算机的体系算机的体系结构是我构是我们的有关算法的有关算法过程知程知识的延的延续，并且不，并且不应该被技被技术能力酸限能力酸限制制n n使我使我们的算
97、法知的算法知识在当代机器体系在当代机器体系结构的构的发展背后起推展背后起推动作用，而不作用，而不仅仅是从技是从技术的要求触的要求触发来解来解顶机器的机器的设计oo构建允构建允许使用多个指令序列来代替算法的机使用多个指令序列来代替算法的机器是可能的器是可能的n n这些指令被同些指令被同时执行或者作行或者作为机器于外部世界的接口的设计于计算机的设计紧密相连机器于外部世界的接口的设计于计算机的设计紧密相连机器于外部世界的接口的设计于计算机的设计紧密相连机器于外部世界的接口的设计于计算机的设计紧密相连oo算法是如何机器中的？算法是如何机器中的？oo机器是如何被告知机器是如何被告知执行的是哪一个算法？行
98、的是哪一个算法？计算理论计算理论oo对解决越来越复解决越来越复杂问题的算法的研究的算法的研究n n导致了算法致了算法过程的最程的最终限制限制问题n n如果没有算法可以解决如果没有算法可以解决这个个问题，那么算法，那么算法是不能被机器所解决的，机器是不能被机器所解决的，机器仅仅可以解决可以解决在算法上可解的在算法上可解的问题ooGodel的不完全定理的不完全定理阐述了述了n n在任何在任何传统算算术领域的数学理域的数学理论中，有些是中，有些是既不能既不能证明有不能被推翻的明有不能被推翻的n n任何任何对算算术系系统的的彻底研究都超出了算法的底研究都超出了算法的能力能力n n对算法的限制的研究欲望
99、似的数学家算法的限制的研究欲望似的数学家们设计抽象的机器来抽象的机器来执行算法，并在理行算法，并在理论上研究上研究这些假想机器的能力。些假想机器的能力。4.5算法、数据结构与程序算法、数据结构与程序4.5.2数据结构 数据结构数据结构：一类定性数学模型一类定性数学模型 1.数据结构的基本概念数据结构的基本概念数据结构的基本概念数据结构的基本概念 oo数学模型有定量模型和定性模型两数学模型有定量模型和定性模型两类之分。之分。定量模型指的是可以用数定量模型指的是可以用数值方程表示的一方程表示的一类模型，而定性模型模型，而定性模型则是指非数是指非数值性的数性的数据据结构（如表、构（如表、树和和图等）
100、及其运算。等）及其运算。oo在在计算算领域中，数据域中，数据结构（构（DataStructure）指的是一）指的是一类定性数学模型，它定性数学模型，它是是计算机算法算机算法设计的基的基础，它在，它在计算科学算科学中占有十分重要的地位。中占有十分重要的地位。数据结构的基本概念数据结构的基本概念 oo组成：数据成：数据结构是一构是一类定性的数学模型，定性的数学模型，它由以下它由以下3部分部分组成成n n逻辑结构构n n存存储结构（或称物理构（或称物理结构）构）n n运算运算oo数据数据逻辑结构的形式化定构的形式化定义 DS=其中：其中： D表示数据的集合；表示数据的集合； R表示数据表示数据D上关
101、系的集合上关系的集合。数据数据oo数据（数据（Data）是描述客）是描述客观事物的数字、字事物的数字、字符以及所有能符以及所有能输人到人到计算机中并被算机中并被计算机算机程序程序处理的符号的集合。它是理的符号的集合。它是计算机加工算机加工处理的理的对象，是信息的象，是信息的载体。例如，一个体。例如，一个代数方程求解程序中所用的数据是整数、代数方程求解程序中所用的数据是整数、实数；而一个翻数；而一个翻译程序中所用的数据是字程序中所用的数据是字符串。随着符串。随着计算机算机软、硬件的、硬件的发展，展，计算算机机应用用领域的域的扩大，数据的含大，数据的含义也随之拓也随之拓宽了。在多媒体了。在多媒体计
102、算机中，描述算机中，描述图象和声象和声音的符号都属于数据的范畴。音的符号都属于数据的范畴。数据元素数据元素 oo数据元素（数据元素（数据元素（数据元素（DataElementDataElement）是数据的抽象的基本）是数据的抽象的基本）是数据的抽象的基本）是数据的抽象的基本单单元，有元，有元，有元，有时时也称也称也称也称为结为结点（点（点（点（nodenode）或）或）或）或记录记录（recordrecord）。至于它的具体含）。至于它的具体含）。至于它的具体含）。至于它的具体含义义，在不同的情况，在不同的情况，在不同的情况，在不同的情况下可以有不同的含下可以有不同的含下可以有不同的含下可以
103、有不同的含义义。它可以是一个字符、一个。它可以是一个字符、一个。它可以是一个字符、一个。它可以是一个字符、一个数或一个数或一个数或一个数或一个记录记录，也可以是其它更加复，也可以是其它更加复，也可以是其它更加复，也可以是其它更加复杂杂的数据。的数据。的数据。的数据。例如，一例如，一例如，一例如，一张张英文字母表（英文字母表（英文字母表（英文字母表（A A，B B，。，。，。，。C C，Z Z）中的数据元素是字母，可以表示中的数据元素是字母，可以表示中的数据元素是字母，可以表示中的数据元素是字母，可以表示为为集合集合集合集合N=AN=A，B B，C C，ZZ。这组这组元素的数目是有限的，元素的数
104、目是有限的，元素的数目是有限的，元素的数目是有限的，计计算算算算机所能机所能机所能机所能处处理的数据元素也只能是有限的。理的数据元素也只能是有限的。理的数据元素也只能是有限的。理的数据元素也只能是有限的。oo数据元素也可以是一个数据元素也可以是一个数据元素也可以是一个数据元素也可以是一个统计统计表中的一个表中的一个表中的一个表中的一个记录记录，如某班学生的一如某班学生的一如某班学生的一如某班学生的一门课门课程的成程的成程的成程的成绩单绩单。 数据的逻辑结构数据的逻辑结构 oo逻辑结构：描述计算机的数据之间的逻辑关系。oo实际上，逻辑结构就是数据结构中定义的关系集合R，反映的是数据元素间的逻辑关
105、系，它无需考虑数据在计算机中的具体存储方式，是独立于计算机的。数据的存储结构数据的存储结构 oo数据的存数据的存储结构是指在反映数据构是指在反映数据逻辑关系的关系的原原则下，数据在存下，数据在存储器中的存器中的存储方式。方式。n n顺序存序存储结构：借助元素在存构：借助元素在存储器中的相器中的相对位置来表示数据元素的位置来表示数据元素的逻辑关系。关系。n n链式存式存储结构：借助指构：借助指针来表示数据元素来表示数据元素之之间的的逻辑关系，通常在数据元素上增加关系，通常在数据元素上增加一个或多个指一个或多个指针类型的属性来型的属性来实现这种表种表示方式。示方式。数据的存储结构数据的存储结构 o
106、o顺序存储结构简单，存储空间使用较紧凑，可以节省存放指针所需的大量空间；但另一方面它要求连续的存储空间，当数据元素的数目不固定，譬如说需要不断扩充时，则必须按最大要求空间设计（即数组上限），这就会有大量空间在当前闲置不用，造成浪费，而且这最大要求空间也往往很难事先估计。数据的存储结构数据的存储结构 oo链接存储结构则不要求连续存储空间，使用较灵活，应用面也较广。缺点是结点指针要占用额外的存储空间。但从另一方面看，对于采用链接存储结构的数据结构来说，其将来数据元素的扩充可以不必事先为它保留专用的备用空间，就这个意义上说，反而是节省了存储空间。数据的存储结构数据的存储结构 oo与逻辑结构相反，存储
107、结构依赖于实体的计算机，无论在形式上还是在顺序上都可能和数据的逻辑结构不同，它与所使用的存储设备以及采用的存储方法密切相关。oo数据结构研究的内容着重在数据的逻辑结构，但也必然涉及到其存储结构。常用的几种数据结构操作常用的几种数据结构操作oo常用的有以下几种：常用的有以下几种： （1 1）检检索索索索检检索索索索就就就就是是是是在在在在给给定定定定的的的的数数数数据据据据结结构构构构中中中中，找找找找出出出出满满足足足足一一一一定定定定条条条条件件件件的的的的数数数数据据据据元元元元素素素素，这这个个个个条条条条件件件件往往往往 往往往往是是是是某某某某个个个个或或或或某几个数据某几个数据某几
108、个数据某几个数据项项的的的的值值。 （2 2）排排排排序序序序根根根根据据据据某某某某一一一一给给定定定定的的的的条条条条件件件件，将将将将数数数数据据据据结结构构构构中中中中的的的的所有数据元素重新排列所有数据元素重新排列所有数据元素重新排列所有数据元素重新排列顺顺序。序。序。序。 （3 3）插插插插入入入入在在在在一一一一个个个个给给定定定定的的的的数数数数据据据据结结构构构构中中中中，根根根根据据据据某某某某些些些些条条条条件，将一个数据元素插入到一个合适件，将一个数据元素插入到一个合适件，将一个数据元素插入到一个合适件，将一个数据元素插入到一个合适 的位置。的位置。的位置。的位置。 （
109、4 4）删删除除除除根根根根据据据据一一一一定定定定的的的的条条条条件件件件，将将将将某某某某个个个个数数数数据据据据元元元元素素素素从从从从数数数数据据据据结结构中构中构中构中删删除。除。除。除。（5 5）修改修改数据）修改修改数据）修改修改数据）修改修改数据结结构中某个指定数据元素的构中某个指定数据元素的构中某个指定数据元素的构中某个指定数据元素的值值。4.5.2 4.5.2 数据结构：一类定性数学数据结构：一类定性数学模型模型 2. 常用的几种数据结构常用的几种数据结构 线性表线性表线性表线性表oo线性表是性表是n个数据元素的有限序列，即（个数据元素的有限序列，即（X1，X2，X3，Xi
110、，Xn）oo基本操作基本操作插入、插入、删除和存取数据元素除和存取数据元素oo几种特殊的几种特殊的线性表性表n n后后后后进进先出（先出（先出（先出（LastInFirstOutLastInFirstOut，简简称称称称LIFOLIFO）的的的的线线性表。它的所有插入、性表。它的所有插入、性表。它的所有插入、性表。它的所有插入、删删除和存取都是在除和存取都是在除和存取都是在除和存取都是在线线性表性表性表性表的表尾的表尾的表尾的表尾进进行的。行的。行的。行的。n n先先先先进进先出（先出（先出（先出（FirstInFirstOutFirstInFirstOut，简简称称称称FIFOFIFO）的的
111、的的线线性表。它的所有插入都是在性表。它的所有插入都是在性表。它的所有插入都是在性表。它的所有插入都是在线线性表的一端性表的一端性表的一端性表的一端进进行的，行的，行的，行的，而所有的而所有的而所有的而所有的删删除和存取又都在除和存取又都在除和存取又都在除和存取又都在线线性表的另一端性表的另一端性表的另一端性表的另一端进进行；行；行；行； n n限定所有插入、限定所有插入、限定所有插入、限定所有插入、删删除和存取都在表的两端除和存取都在表的两端除和存取都在表的两端除和存取都在表的两端进进行的行的行的行的线线性表。性表。性表。性表。 数组数组数组数组oo线性表的推广形式之一。性表的推广形式之一。
112、oo如在一个如在一个m n的二的二维数数组中，每个元素中，每个元素Ai,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上
113、上图图的的树树有有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等。等。图图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）个个结点点组成成的的有有限限集
114、集合合，它它或或者者是是空空集集（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一般地一般地说，对任何一个任何一个问题，如果有了解决，如果有了解决该问题的算法，
115、就可以的算法，就可以编制相制相应的程序。所的程序。所谓程序，是一种事先程序，是一种事先编制好了具有特殊功能制好了具有特殊功能的指令序列。的指令序列。其中，指令既可以是机器指令，其中，指令既可以是机器指令，汇编语言指令，也可以是高言指令，也可以是高级语言的言的语句命句命令，甚至令，甚至还可以是用自然可以是用自然语言描述的运算、言描述的运算、操作命令。当然，用自然操作命令。当然，用自然语言言编写程序是写程序是计算机科学算机科学进入非常高入非常高级的的阶段的段的标志之一，志之一，有有赖于自然于自然语言理解取得重大突破，目前看言理解取得重大突破，目前看来来还是一个十分遥是一个十分遥远的的设想。想。概念
116、概念概念概念oo从广从广义上上讲，程序可以，程序可以认为是一种行是一种行动方案方案或工作步或工作步骤。例如：。例如：n n某个会某个会议的日程安排的日程安排n n一条旅游路一条旅游路线的的设计n n手工小制作的手工小制作的说明明书等等oo程序：一种程序：一种处理事理事务的的时间顺序和序和处理步理步骤。n n组成成计算机程序的基本算机程序的基本单位是位是指令指令n n计算机程序就是按照工作步算机程序就是按照工作步骤事先事先编排好的、具有特殊功能的排好的、具有特殊功能的指令序列指令序列。一个程序具有一个单一的、不可分的结构，它规定了某个数据结构上的一个算法。瑞士著名计算机科学家尼可莱沃思（Niki
117、klausWirth）在1976年曾提出这样一个公式：算法算法+数据数据结构构=程序程序这一一公公式式仅可可以以作作为一一种种参参考考，不不能能作作为教学中的定教学中的定义。由此看来，我们前面提到的算法和数据结构是计算机程序的两个最基本的概念。算法是程序的核心，它在程序编制、软件开发，乃至在整个计算机科学中都占据重要地位。数据结构是加工的对象，一个程序要进行计算或处理总是以某些数据为对象的，而要设计一个好的程序就需将这些松散的数据按某种要求组成一种数据结构。然而，随着计算机科学的发展，人们现在已经意识到程序除了以上两个主要要素外，还应包括程序的设计方法以及相应的语言工具和计算环境。概念概念概念
118、概念oo程序程序这一概念的出一概念的出现，得益于人，得益于人类长期的生期的生活活实践，程序践，程序设计也不神秘。但是，程序也不神秘。但是，程序设计是一种高智力的活是一种高智力的活动，不同的人，不同的人对同一事同一事物的物的处理可以理可以设计出完全不同的程序。我出完全不同的程序。我们每一个人的生活每一个人的生活经历已已经告告诉自己，知自己，知识和和阅历（经验）是）是处事（事（设计程序）的基程序）的基础。正因正因为如此，在如此，在计算机算机发展的早期，程序展的早期，程序设计被被认为是一个与个人是一个与个人经历、思想和技、思想和技艺相相联系的一种技系的一种技艺和技巧。后来，和技巧。后来，软件开件开发
119、规模的模的扩大和开大和开发方式的方式的变化，程序化，程序设计才开才开始被当成一始被当成一门科学来科学来对待。待。概念概念概念概念oo既然程序如此重要，又既然程序如此重要，又为人人类经常使用，就常使用，就有必要有必要对程序及其运行的程序及其运行的规律律进行深入的研行深入的研究。于是，究。于是，对程序各种性程序各种性质如程序的如程序的结构、构、程序的正确性、程序的运行效率等的研究程序的正确性、程序的运行效率等的研究产生了生了计算机科学十分重要的一个方向算机科学十分重要的一个方向程序程序理理论。4.6高级语言、程序设计技术高级语言、程序设计技术与方法与方法4.6.1高级语言高级语言高级语言高级语言高
120、级语言oo虽然与机器然与机器语言相比，言相比，汇编语言的言的产生是一个很生是一个很大的大的进步，但是用它来步，但是用它来进行程序行程序设计仍然比仍然比较困困难。于是人。于是人们着手着手对它它进行改行改进。一是。一是发展宏展宏汇编，即用一条宏指令代替若干条，即用一条宏指令代替若干条汇编指令，从而指令，从而提高提高编程效率。程效率。现在人在人们使用的使用的汇编语言，大多言，大多数都是宏数都是宏汇编语言。二是言。二是创建高建高级语言，使言，使编程程更加方便。更加方便。oo所所谓高高级程序程序设计语言（言（简称高称高级语言）是指用言）是指用于描述于描述计算机程序的算机程序的类自然自然语言。言。这种种语
121、言只是言只是自然自然语言的一个很小的子集，在言的一个很小的子集，在语法法结构上比构上比较简单而且而且规范，在范，在语义上上较少二少二义性，能性，能够以比以比较准确、易准确、易读的形式描述各种的形式描述各种计算机程序。算机程序。高级语言的分类高级语言的分类高级语言的分类高级语言的分类按按语言的特点，可以将高言的特点，可以将高级语言划分言划分为：oo过程式程式语言（如言（如Cobol，Forturn，Algol，Pascal，Ada，C）oo函数式函数式语言（如言（如Lisp）oo数据流数据流语言（如言（如SISAL，VAL）oo面向面向对象象语言（如言（如Smalltalk，CLU，C+）oo逻
122、辑语言（如言（如Prolog）oo字符串字符串语言（如言（如SNOBOL）oo并并发程序程序设计语言（如言（如Concurrent Pascal，Modula 2）等等高级语言的形式化高级语言的形式化高级语言的形式化高级语言的形式化 20世世纪50年代年代oo美美国国语言言学学家家乔姆姆斯斯基基（NoamChomsky）关于关于语言分言分层的理的理论，oo巴巴科科斯斯（Backus）、瑙瑙尔（Naur）的的关关于于“上上下下文文无无关关方方法法表表示示形形式式”的的研研究究成成果果推推动了了语法形式化的研究。法形式化的研究。oo其其结果果是是，在在ALGOL60的的文文本本设计中中第第一一次次
123、使使用用了了BNF范范式式来来表表示示语法法，并并且且第第一一次次在在语言言文文本本中中明明确确提提出出应将将语法法和和语义区区分分开开来。来。高级语言的形式化高级语言的形式化高级语言的形式化高级语言的形式化oo20世世纪50年年代代至至60年年代代间，面面向向语法法的的编译自自动化化理理论得得到到了了很很大大发展展，使使语法法形形式式化化研研究究的成果达到的成果达到实用化的水平。用化的水平。oo语法法形形式式化化问题基基本本解解决决以以后后，人人们逐逐步步把把注注意意力力集集中中到到语义形形式式化化的的研研究究方方面面,20世世纪60年代，相年代，相继诞生了生了n n操作操作语义学学n n指
124、称指称语义学学n n公理公理语义学学n n代数代数语义学等学等语义学理学理论数据类型的抽象数据类型的抽象数据类型的抽象数据类型的抽象oo相相对于于汇编语言和机器言和机器语言，高言，高级语言的言的数据数据类型型的抽象的抽象层次有了很大地提高，出次有了很大地提高，出现了了n n整型整型n n实型型n n字符型字符型n n布布尔型型n n用用户自定自定义类型型n n抽象数据抽象数据类型型oo数据数据类型的抽象型的抽象极大地方便了用极大地方便了用户对数据的抽数据的抽象描述，象描述，为实现软件件设计的工程化奠定了基的工程化奠定了基础。高级语言中有关抽象、理论和设计高级语言中有关抽象、理论和设计高级语言中
125、有关抽象、理论和设计高级语言中有关抽象、理论和设计3 3个形态的主要内容个形态的主要内容个形态的主要内容个形态的主要内容 抽象理论设计常用的符号：数字(09)，大小写字母(AZ、az)，括号，运算符(+，*，/)等;用高级语言对算法进行的描述；语言的分类方法；各种数据类型的抽象实现模型；词法分析、编译、解释和代码优化的方法；词法分析器、扫描器、编译器组件和编译器的自动生成方法形式语言和自动机理论；形式语义学：操作、指称、公理、代数、并发和分布式程序的形式语义特定语言：过程式的COBOL，FORTURN，ALGOL，Pascal，Ada，C），函数式的（LISP），数据流的（SISAL，VAL）
126、，面向对象的（Smalltalk，C+），逻辑的（Prolog），字符串（SNOBOL），和并发（ConcurrentPascal，Modula2）等语言；词法分析器和扫描器的产生器（如YACC，LEX），编译器产生器；语法和语义检查，成型、调试和追踪程序4.6高级语言、程序设计技术高级语言、程序设计技术与方法与方法4.6.2程序设计技术与方法程序设计技术程序设计技术程序设计技术程序设计技术oo为提高提高计算机的效率和可靠性，算机的效率和可靠性，围绕程序的程序的设计、描述、构造、分析、描述、构造、分析、测试和和验证等方等方面，面，发展了展了许多的技多的技术，统称称为程序程序设计技技术。oo不同
127、的程序不同的程序设计方法与技方法与技术，都是从不同的，都是从不同的角度角度对程序及其程序及其设计和和产生生过程的特性和程的特性和规律律进行行观察，察，经抽象、分析和抽象、分析和总结之后得出之后得出的。的。程序设计方法与技术程序设计方法与技术程序设计方法与技术程序设计方法与技术oo自自顶向下逐步求精的程序向下逐步求精的程序设计方法与技方法与技术oo自底向上的程序自底向上的程序设计方法与技方法与技术oo基于程序推基于程序推导的程序的程序设计方法与技方法与技术oo基于程序基于程序变换的程序的程序设计方法与技方法与技术oo面向面向对象的程序象的程序设计方法与技方法与技术oo函数式程序函数式程序设计技技
128、术oo逻辑程序程序设计技技术oo程序程序验证技技术oo并并发程序技程序技术oo。程序设计语言是一门科学程序设计语言是一门科学程序设计语言是一门科学程序设计语言是一门科学oo对程序程序结构本构本质的深入研究促的深入研究促进了了对程序程序质量的量的认识oo开开发程序的效率和程序的效率和质量取决于程序量取决于程序设计方法方法和技和技术oo多年的研究多年的研究发展了展了许多程序多程序设计方法和技方法和技术。如自如自顶向下逐步求精的程序向下逐步求精的程序设计方法、自底方法、自底向上的程序向上的程序设计方法、程序推方法、程序推导的的设计方法、方法、程序程序变换的的设计方法、函数式程序方法、函数式程序设计技
129、技术、逻辑程序程序设计技技术、面向、面向对象的程序象的程序设计技技术、程序、程序验证技技术、约束程序束程序设计技技术、并、并发程序程序设计技技术等。等。程序设计语言是一门科学程序设计语言是一门科学程序设计语言是一门科学程序设计语言是一门科学oo例如，例如，对于于许多多问题的的计算，可以用算，可以用类似于似于计算函数的方法来算函数的方法来进行，也可以用表（一种行，也可以用表（一种数据数据结构）构）处理的方法理的方法进行，甚至行，甚至还可以用可以用逻辑公式演公式演绎推推导的方法的方法进行，在行，在实现技技术上，既可以用上，既可以用递归技技术计算，也可以用迭代算，也可以用迭代技技术或其它技或其它技术
130、进行行计算。算。程序设计语言是一门科学程序设计语言是一门科学程序设计语言是一门科学程序设计语言是一门科学oo作作为一一门科学，高科学，高级语言和程序言和程序设计确确实对学科的学科的发展展产生了巨大的影响。程序生了巨大的影响。程序设计方方法和技法和技术在各个在各个时期的期的发展不展不仅直接直接导致了致了一大批一大批风格各异的高格各异的高级语言的言的诞生，而且生，而且许多新思想、新概念、新方法和新技多新思想、新概念、新方法和新技术不不仅在在语言中得到体言中得到体现，同，同时渗透到了渗透到了计算机科学算机科学的各个方向，从理的各个方向，从理论、硬件、硬件、软件到件到应用等用等多方面深刻影响了学科的多
131、方面深刻影响了学科的发展。展。oo对高高级语言和程序言和程序设计的掌握是的掌握是计算机科学算机科学专业的基本功之一。的基本功之一。4.7软件与硬件软件与硬件4.7.1硬件硬件的概念硬件的概念硬件的概念硬件的概念oo计算算机机硬硬件件是是构构成成计算算机机系系统的的所所有有物物理理器器件件、部部件件、设备，以以及及相相应的的工工作作原原理理与与设计、制制造造、检测等等技技术的的总称称。广广义的的硬硬件件包包含含硬硬件件本本身身及及其其工工程程技技术两两部部分分。其其中中：语音等方式音等方式进入入计算机算机n n计算算机机系系统的的物物理理元元器器件件包包括括：集集成成电路路、印印制制电路路板板，
132、以以及及其其他他磁磁性性元元件件、电子子元元件等。件等。n n计算算机机系系统的的部部件件和和设备包包括括：控控制制器器、运算器、存运算器、存储器、器、输入入输出出设备、电源等。源等。硬件的概念硬件的概念硬件的概念硬件的概念oo硬硬件件工工程程技技术包包括括：印印制制电路路板板制制造造、高高密密度度组装装、抗抗环境境干干扰、抗抗恶劣劣环境境破破坏坏等等技技术，以以及及在在设计和和制制造造过程程中中为提提高高计算算机机性能所采取的措施等。性能所采取的措施等。4.7软件与硬件软件与硬件4.7.2软件软件的概念软件的概念软件的概念软件的概念oo软件是与程序密切相关的一个概念，在计算机发展的初期，硬件
133、设计和生产是主要问题，那时的软件就是程序。后来，随着计算技术的发展，传统软件的生产方式已不适应发展的需要，于是人们将工程学的基本原理和方法引入软件设计和生产中。oo现在计算机软件一般指计算机系统中的程序及其文档，也可以指在研究、开发、维护，以及使用上述含义下的软件所涉及的理论、方法、技术所构成的分支学科。软件的定义软件的定义软件的定义软件的定义oo从从计算机（硬件裸机）到算机（硬件裸机）到计算机系算机系统oo从从计算机系算机系统到到计算机体系算机体系结构构oo软件是与程序密切相关的一个概念，在计算机发展的初期，硬件设计和生产是主要问题，那时的软件就是程序。后来，随着计算技术的发展，传统软件的生
134、产方式已不适应发展的需要，于是人们将工程学的基本原理和方法引入软件设计和生产中。软件的定义软件的定义软件的定义软件的定义oo软件是一个件是一个发展的概念，早期展的概念，早期软件和程序几件和程序几乎是同乎是同义词。后来，。后来，软件的概念在程序的基件的概念在程序的基础上得到了延伸。上得到了延伸。1983年，年，IEEE对软件件给出出了一个了一个较为新新颖的定的定义，指出：，指出：软件是件是计算算机程序、方法、机程序、方法、规范及其相范及其相应的文稿以及在的文稿以及在计算机上运行算机上运行时所必所必须的数据。的数据。软件的分类软件的分类软件的分类软件的分类oo软件件一一般般分分为系系统软件件、支支
135、撑撑软件件、应用用软件件3类。n n系系统软件件是是计算算机机系系统中中最最靠靠近近硬硬件件层次次的的软件件。如如操操作作系系统、编译程程序序、汇编程程序序、数数据据库管管理理系系统、软硬硬件件故故障障诊断断程程序序、子子程程序序库、各各种种软件件开开发工工具和具和软件包等属于系件包等属于系统软件。件。n n支支撑撑软件件是是支支撑撑其其他他软件件的的开开发与与维护的的软件件。如如数数据据库管管理理系系统、网网络软件件、各种接口各种接口软件和开件和开发工具等。工具等。n n应用用软件件是是特特定定应用用领域域的的专用用软件件。如商如商业会会计软件、教学件、教学软件等。件等。软件的概念软件的概念
136、软件的概念软件的概念oo操操作作系系统-一一种种系系统软件件，它它负责管管理理计算算机机系系统中中的的各各种种资源源并并控控制制各各类程程序序的的运运行行。它它通通过接接受受来来自自用用户的的操操作作命命令令，按按照照用用户的的要要求求对计算算机机的的工工作作进行行控控制制。计算算机机配配上操作系上操作系统之后，能之后，能够提高效率，便于使用。提高效率，便于使用。oo系系统软件和件和应用用软件迄今并没有件迄今并没有严格的定格的定义。4.7软件与硬件软件与硬件计算机就是由计算机硬件和计算机软件组成的。硬件是计算机的“躯体”，软件是计算机的“灵魂”。4.8计算机图形学、图像处理计算机图形学、图像处
137、理与模式识别与模式识别4.8.1计算机图形学oo国际标准化组织(ISO)的定义：计算机图形学是研究通过计算机将数据转换为图形，并在专门显示设备上显示的原理、方法和技术的学科。oo计算机图形学是建立在传统的图学理论、应用数学和计算机科学基础上的一门边缘学科。基本概念基本概念基本概念基本概念oo广义的概念oo几何要素几何属性点、线、面、体oo非几何要素视觉属性明暗、灰度、色彩、纹理、透明性、线型、线宽图形的构成要素图形的构成要素图形的构成要素图形的构成要素oo计算机对图形数据处理的硬件和软件oo围绕着生成、表示物体的图形的准确性-真实性-实时性oo算法可大致分为以下几类： -基于基于基于基于图图形
138、形形形设备设备的基本的基本的基本的基本图图形元素的生成算法形元素的生成算法形元素的生成算法形元素的生成算法 -图图形的形的形的形的变换变换和裁剪和裁剪和裁剪和裁剪 -自由曲自由曲自由曲自由曲线线和曲面和曲面和曲面和曲面计计算几何算几何算几何算几何 -真真真真实实感感感感图图形的生成算法形的生成算法形的生成算法形的生成算法 -三三三三维维几何造型技几何造型技几何造型技几何造型技术术 -山、水、花、草、山、水、花、草、山、水、花、草、山、水、花、草、树树木、云、烟、火焰、雪景等模糊复木、云、烟、火焰、雪景等模糊复木、云、烟、火焰、雪景等模糊复木、云、烟、火焰、雪景等模糊复杂杂景物的生成景物的生成景
139、物的生成景物的生成分形几何分形几何分形几何分形几何 -三三三三维维或高或高或高或高维维数据数据数据数据场场的可的可的可的可视视化化化化 -图图形的并行形的并行形的并行形的并行处处理理理理 -虚虚虚虚拟现实环拟现实环境境境境实时实时交互式三交互式三交互式三交互式三维图维图形形形形处处理理理理研究内容研究内容研究内容研究内容oo图形用户界面（GUI)oo计算机辅助设计与制造工业领域oo计算机动画商业领域（广告设计、电脑游戏、卡通动画片、影视特技）oo计算机艺术艺术领域oo过程控制（工业、交通等领域设备运行监控)oo系统环境模拟(如飞行模拟舱等）oo事务和商务数据的图形显示oo地形地貌和自然资源的图
140、形显示（GIS、GPS)oo科学计算的可视化oo多媒体应用图形学的应用图形学的应用图形学的应用图形学的应用4.8计算机图形学、图像处理计算机图形学、图像处理与模式识别与模式识别4.8.2图像处理oo数字图象处理旨在对图象进行各种加工以改善图象的视觉效果。oo主要研究对客观世界中已经存在的物体映像处理成新的数字化图像，如医学图像处理、卫星遥感图像处理、照相图像处理等。oo主要关心的是如何滤掉噪音，图像压缩、传输和还原，图像质量提高等。4.8计算机图形学、图像处理计算机图形学、图像处理与模式识别与模式识别4.8.3模式识别oo模式识别主要研究如何分析和识别各种图像，找出其中图形数据蕴含的内在联系或
141、构建图像的抽象模型。oo如高速公路上的车辆拍照的识别、人脸部的识别、数字水印等。与相与相与相与相关学关学关学关学科的科的科的科的关系关系关系关系图像处理图像处理计计算算机机图图形形学学模模式式识识别别图图像像计算几何计算几何特特征征数数据据几几何何模模型型CAD/CAM计算机艺术计算机艺术计算机动画计算机动画计算机视觉计算机视觉4.9人工智能第第4章章 计算学科中的计算学科中的基本基本概念概念 oo人工智能就是研究智能计算机及其系统，以模仿和执行人类的某些智力功能，如判断、推理、规划、设计、思考、学习、识别等，解决过去人类专家才能处理好的复杂问题。oo人工智能的“思维法则”方法中，强调的是正确
142、的推论。作出正确推论有时也是理性智能体的部分功能。基本概念基本概念基本概念基本概念oo人工智能领域中的所谓逻辑主义就是希望通过编制具有逻辑能力的程序来创造智能系统。oo问题：-难以获得非形式化的知识并得到逻辑符号表示所需的形式化表达；-”原则上”可以解决一个问题与实际解决问题这两者之间存在巨大的差别。基本概念基本概念基本概念基本概念oo1、像人一样思考的系统-有 头 脑 的 机 器 ： 计 算 机 能 够 思 考 。(Haugeland，1985）-使之能够进行与人类的思维相关的活动，如 决 策 、 问 题 求 解 、 学 习 等 。（Bellman,1978)oo2理性地思考的系统-通过对计
143、算模型的使用来进行心智能力的研究。（Charniak,1985)-对使得知觉、推理和行动成为可能的计算的研究。（Winston,1992)人们对人工智能的解释人们对人工智能的解释人们对人工智能的解释人们对人工智能的解释oo3像人一样行动的系统-一种技艺，创造机器来执行人需要智能才能完成的功能。(Kurzweil，1990）-研究如何让计算机能够做到那些目前人比计算机做得更好的事情。（Rich,Knight,1991)oo4理性地行动的系统-计算智能是对设计智能化智能体的研究。（Poole等人,1998)-AI.关心的是人工制品中的智能行为。（尼尔森（Nilsson）,1998)人们对人工智能的
144、解释人们对人工智能的解释人们对人工智能的解释人们对人工智能的解释oo哲学哲学（公元前（公元前428年年-现在）在）-形式化形式化规则能用来抽取合理能用来抽取合理结论吗？ -精神的意精神的意识是如何从物是如何从物质的大的大脑产生出生出来的？来的？-知知识从哪里来？从哪里来？-知知识是如何是如何导致行致行动的？的？人工智能研究的基础人工智能研究的基础人工智能研究的基础人工智能研究的基础oo数学数学（约800年年-现在）在） -什么是抽取合理什么是抽取合理结论的形式化的形式化规则？ -什么可以什么可以计算？算？ -我我们如何用不确定的知如何用不确定的知识进行推理？行推理？oo经济学学（1776年年现
145、在）在）-我我们如何决策以如何决策以获得最大收益？得最大收益？-我我们在他人不合作的情况下如何做到在他人不合作的情况下如何做到这样？-我我们在收益遥遥无期的情况下如何做到在收益遥遥无期的情况下如何做到这样？人工智能研究的基础人工智能研究的基础人工智能研究的基础人工智能研究的基础oo神神经科学科学（1861年年-现在）在）-头脑是如何是如何处理信息的？理信息的？oo心理学心理学（1879年年现在）在）-人人类和和动物如何思考和行物如何思考和行动？oo计算机工程算机工程（1940年年-现在）在）-我我们如何才能制造出能干的如何才能制造出能干的计算机？算机？oo控制控制论（1948年年现在）在）-人
146、工制品怎人工制品怎样才能在自己的控制下运才能在自己的控制下运转？oo语言学言学（1957年年现在）在）-语言和思言和思维是怎是怎样联系起来的？系起来的？人工智能研究的基础人工智能研究的基础人工智能研究的基础人工智能研究的基础oo知知知知识识表示（表示（表示（表示（KnoweledgePresentationnKnoweledgePresentationn） oo问题问题求解（求解（求解（求解（ProblemsolvingProblemsolving） oo模式模式模式模式识别识别（PatternRecognitionPatternRecognition） oo自自自自动动定理定理定理定理证证明
147、明明明(AutomaticTheoremProving)(AutomaticTheoremProving)oo自自自自动动程序程序程序程序设计设计（AutomationProgrammingAutomationProgramming） oo自然自然自然自然语语言言言言处处理（理（理（理（NaturalLanguageProcessingNaturalLanguageProcessing）oo专专家系家系家系家系统统（ExpertSystermsExpertSysterms） oo机器学机器学机器学机器学习习（MachineLearningMachineLearning） oo机器人学（机器人学
148、（机器人学（机器人学（RoboticsRobotics） oo人工神人工神人工神人工神经经网网网网络络（ArtificialNueralNetworkArtificialNueralNetwork） oo计计算机算机算机算机视觉视觉(ComputerVision)(ComputerVision)oo博奕（博奕（博奕（博奕（GamePlagingGamePlaging）人工智能的应用研究领域人工智能的应用研究领域人工智能的应用研究领域人工智能的应用研究领域4.10计算机组织与体系结构计算机组织与体系结构第第4章章 计算学科中的计算学科中的基本基本概念概念 oo内容包括从计算机系统的逐个设计、制造
149、到计算机的系列化和软件的兼容性。ooIBM 360系 统 标 志 着 计 算 机 体 系 结 构（Architecture）研究的开端（1964年）。oo计算机体系结构是使用机器语言编写程序的用户可以看到的一个机器的抽象结构，而对这一结构实现的硬件组成属于计算机组成原理研究的范畴。oo随随着着大大规规模模和和超超大大规规模模集集成成电电路路（LSI/VLSILSI/VLSI）技技术术的的成成熟熟，一一方方面面器器件件速速度度和和可可靠靠性性在在不不断断提提高高，目目前前已已逼逼近近极极限限，另另一一方方面面器器件件的的体体积积和和价价格格在在持持续续下下降降，这这极极大大地地增增强强了了计计算
150、算机机的的性性能能。然然而而，高高质质量的器件不是量的器件不是产产生高性能生高性能计计算机的唯一因素。算机的唯一因素。oo虽虽然然，今今日日大大多多数数计计算算机机都都是是图图灵灵冯冯 诺诺依依曼曼型型存存储储程程序序式式电电子子数数字字计计算算机机，但但人人们们早早已已认认识识到到计计算算机机不不仅仅仅仅是是一一个个硬硬件件组组织织的的问问题题。一一个个现现代代的的计计算算机机系系统统一一般般被被认认为为是是由由存存储储器器、处处理理器器、功功能能部部件件、互互联联网网络络、汇汇编编程程序序、编编译译程程序序、操操作作系系统统、外外部部设备设备、通信通道等内容、通信通道等内容组组合而成的。合
151、而成的。硬件的概念硬件的概念硬件的概念硬件的概念oo早期早期计算机系算机系统研究与开研究与开发的两个基本特点：的两个基本特点：n n硬硬件件和和软件件的的研研究究与与开开发基基本本上上是是独独立立进行的；行的；n n硬硬件件的的研研究究与与开开发更更多多的的是是从从计算算机机组成成原原理理上上去去关关心心各各部部件件中中分分离离元元器器件件及及其其相相互互之之间的的联接接关关系系，关关心心各各部部件件的的内内部部构构造和外部特性。造和外部特性。oo集成电路的发展改变了专业人员的认识。oo计算机CPU的速度和存储器的容量成倍增长，各种多功能部件不断引入，如何设计和配置计算机系统使其具有更高的性能
152、价格比，适应不同用户的要求，成为亟待解决的问题。oo集成电路的发展也使许多专业人员可以不再关心各部件的内部细节，而只须考虑如何以一种统一的观点从硬件器件和一些软件系统出发，通过组合配置，设计功能更强、性能价格比更高、更可靠的计算机系统。于是，计算机体系结构应运而生。oo典典型型的的、有有助助于于常常人人理理解解计计算算机机体体系系结结构构的的方方向向是是所所谓谓的的计计算算机机网网络络系系统统。用用户户面面对对计计算算机机系系统统网网络络进进行行开开发发是是十十分分困困难难的的，因因为为，他他不不可可能能熟熟悉悉网网上上每每一一种种通通信信资资源源的的配配置置情情况况，而而且且也也不不了了解解
153、每每一一种种通通信信资资源源的的基基本本操操作作方方法法，更更不不可可能能考考虑虑通通信信出出错错的的情情况况以以及及如如何何纠纠错错。显显然然，对对于于用用户户来来说说，需需要要有有一一种种能能够够屏屏蔽蔽计计算算机机硬硬件件系系统统技技术术细细节节，仅仅对对用用户户提提供供功功能能透透明明的的系系统统层层，使使用用户户看看到到的的和和实实际际使使用用的的是是一一个个与与使使用用者者思思想想方方式式、使使用用习习惯惯比比较较接接近近，无无须须具具体体关关心心网网络络计计算算机机通通信信时时一一些些十十分分繁繁琐琐的的技技术细节术细节的分布式的分布式计计算机系算机系统统。oo硬件的互联结构和软
154、件结构及相互关系形成的计算机系统的总体结构，支持这种结构的基本算法，还有以总体结构为基础的面向用户的程序设计语言等内容构成了计算机体系结构的技术范畴。4.12并行计算机、通道与并并行计算机、通道与并行计算行计算第第4章章 计算学科中的计算学科中的基本基本概念概念 oo单CPU计算机多功能部件多寄存器计算机流水线向量计算机阵列式计算机多处理器并行计算机多处理机并行计算机多计算机网络并行计算机系统。计算机的组成结构变迁计算机的组成结构变迁计算机的组成结构变迁计算机的组成结构变迁并行处理的概念并行处理的概念并行处理的概念并行处理的概念oo并并行行处理理要要求求在在计算算机机上上并并行行地地运运行行许
155、多多程程序序。根根据据使使用用的的计算算机机系系统的的不不同同，我我们可可以在四个程序的以在四个程序的级别上提出并行上提出并行处理的理的问题：n n作作业或程序或程序级并行并行n n任任务或或过程程级并行并行n n指令指令级并行并行n n指令内部指令内部级并行。并行。oo不同的并行处理思想和技术，产生了不同的并行计算机系统。从使用方便的角度考虑，用户更希望看到的是系统提供作业或程序级并行，这样用户可以不必考虑实现并行的细节。而从实际计算提高效率的角度考虑，用户更希望系统已经实现了指令级并行或指令内部级并行。并行处理的概念并行处理的概念并行处理的概念并行处理的概念oo面对众多的并行计算机系统，我
156、们应该怎么来认识和区别它们的系统结构呢？ooM.J.Flynn在1966年提出了一种著名的、也是现今比较常用的系统结构分类方法。他将计算机系统的系统结构分为四类，分别是：n n单指令流单数据流计算机（SISD）n n单指令流多数据流计算机（SIMD）n n多指令流单数据流计算机（MISD）n n多指令流多数据流计算机（MIMD）并行处理的概念并行处理的概念并行处理的概念并行处理的概念oo由多机系统技术的扩展及网络互连与通信技术的引入，发展了分布式网络计算机系统，提出了分布式计算机体系结构、分布式算法与分布式并行处理的概念等。oo并行计算机系统的出现，带来了信息并行化处理的概念。并行处理是信息处
157、理的一种有效形式，它着重于发掘计算过程中的并发事件。并行处理的概念并行处理的概念并行处理的概念并行处理的概念oo并发性包含宏观上的并行性，包含同时性以及微观上的流水线处理。并行事件可在同一时间间隔内在多个资源（如多个处理器）里发生；同时事件可在同一时刻上发生，流水线事件可在部分重叠的时间内于一个（或多个）资源里出现。oo并发通常是指宏观上一个资源里并行发生了两个或两个以上的事件，但在微观上是顺序发生的，而并行通常是指多个资源里微观上同时发生了两个或两个以上事件。显然，一组事件是并行的也是并发的，但一组事件是并发的却不一定是并行的。并行处理的概念并行处理的概念并行处理的概念并行处理的概念oo-通
158、道是数据或信息传送的通路oo利用并行计算机系统进行数据与信息的并行处理称为并行计算。从处理对象的角度划分，并行计算分为数值并行计算和非数值并行计算。oo与顺序计算类似，并行计算也分成几个步骤：研究并行计算方法，研究并行算法，设计并行程序，调试与运行，分析结果。通道的概念通道的概念通道的概念通道的概念oo由于许多问题的计算已经有了计算方法，而这些计算方法中隐含了大量的并行性，稍作变化就可支持并行算法和并行程序设计，而且，由于各种并行计算机的系统结构不同，各处理器和各多功能部件之间在体现算法时的相互作用不同，算法不能通用。oo因此，除了并行计算机体系结构的研究外，当前和今后相当长的一个时期内并行处
159、理的一个工作重点将是研究各种并行与分布式计算机系统上的并行算法或分布式算法。通道的概念通道的概念通道的概念通道的概念网络的基本概念网络的基本概念网络的基本概念网络的基本概念oo随着随着随着随着计计算科学及其算科学及其算科学及其算科学及其应应用的高速用的高速用的高速用的高速发发展，用展，用展，用展，用户对软户对软硬件和硬件和硬件和硬件和信息信息信息信息资资源共享的需求和一大源共享的需求和一大源共享的需求和一大源共享的需求和一大类问题类问题本身具有地域上分本身具有地域上分本身具有地域上分本身具有地域上分布的特点，促布的特点，促布的特点，促布的特点，促进进了了了了计计算机网算机网算机网算机网络络的的
160、的的发发展。展。展。展。oo所所所所谓谓计计算机网算机网算机网算机网络络是使用通信是使用通信是使用通信是使用通信设备设备和通信和通信和通信和通信线线路将一路将一路将一路将一组组地地地地理上分布的相同（称理上分布的相同（称理上分布的相同（称理上分布的相同（称为为同同同同质质）或不同（称）或不同（称）或不同（称）或不同（称为为异异异异质质）的）的）的）的计计算机、算机、算机、算机、终终端及其附属端及其附属端及其附属端及其附属设备设备按照某种方式互按照某种方式互按照某种方式互按照某种方式互联联起来得起来得起来得起来得到的一个到的一个到的一个到的一个计计算机硬件系算机硬件系算机硬件系算机硬件系统统，也
161、叫网，也叫网，也叫网，也叫网络计络计算机。在算机。在算机。在算机。在这这种种种种计计算机硬件系算机硬件系算机硬件系算机硬件系统统的基的基的基的基础础上，通上，通上，通上，通过过开开开开发发能能能能协调协调各台各台各台各台计计算算算算机系机系机系机系统统工作的通信系工作的通信系工作的通信系工作的通信系统统或更或更或更或更进进一步的网一步的网一步的网一步的网络络操作系操作系操作系操作系统统，就能使一就能使一就能使一就能使一组计组计算机算机算机算机实现软实现软硬件硬件硬件硬件资资源共享、源共享、源共享、源共享、协协同同同同计计算，算，算，算，合作求解一个合作求解一个合作求解一个合作求解一个问题问题。
162、由。由。由。由这这种通信系种通信系种通信系种通信系统统或网或网或网或网络络操作系操作系操作系操作系统统连连同网同网同网同网络计络计算机一起，就形成了网算机一起，就形成了网算机一起，就形成了网算机一起，就形成了网络计络计算机系算机系算机系算机系统统。网络的分类网络的分类网络的分类网络的分类oo按照数据按照数据传输范范围和和实现技技术的不同，的不同，计算机网算机网络存在存在局域局域计算机网算机网络和和广域广域计算机网算机网络之分。之分。局域局域计算机网算机网络是一个数据通信系是一个数据通信系统，其，其传输范范围在中等地理区域，使用中等或高速数据在中等地理区域，使用中等或高速数据传输速速率，使用率，
163、使用专用数据通信用数据通信线或或总线进行通信，可行通信，可联接大量独立接大量独立设备，在物理通信通道上互相通信。，在物理通信通道上互相通信。oo广域广域计算机网算机网络把不同城市、不同国家中的把不同城市、不同国家中的计算算机或机或计算机网算机网络通通过分分级互互联技技术联接起来，其接起来，其传输范范围可达到相当可达到相当远的距离。目前最常的距离。目前最常见的是的是使用公用或使用公用或专用用电话线通信，主干网和一些局域通信，主干网和一些局域网使用可网使用可进行数字通信的光行数字通信的光纤光光缆数据通信数据通信专用用线。网络的结构网络的结构网络的结构网络的结构oo网网络互互联的拓扑的拓扑结构是构是
164、计算机网算机网络的重要特性。的重要特性。网网络的拓扑的拓扑结构是一种抽象的由点和构是一种抽象的由点和线组成的成的图。网网络上的每台上的每台计算机用一个算机用一个结点表示，机器与机点表示，机器与机器之器之间的的链路用路用线和路径表示，于是，和路径表示，于是，图论构成构成了网了网络计算机体系算机体系结构中一些基本算法研究中数构中一些基本算法研究中数学描述的理学描述的理论基基础。oo网网络的的结构一般有：主从型、构一般有：主从型、环型、星型、等型、星型、等网络的协议网络的协议网络的协议网络的协议oo支持支持计算机网算机网络的重要技的重要技术是通信，即是通信，即实现计算算机之机之间信息信息传输的一种技
165、的一种技术方式。网方式。网络通信的核通信的核心内容是通信心内容是通信协议。所。所谓通信通信协议是网是网络通信中通信中一一组约定的集合，由它确定了定的集合，由它确定了经由通信网由通信网络传输的信息或存的信息或存储在在报文和数据文和数据库中的信息的格式和中的信息的格式和控制方式。研究通信控制方式。研究通信协议主要是主要是为了在网了在网络计算算机系机系统中中实现可靠的、高效的数据交可靠的、高效的数据交换，差，差错控控制，信息制，信息编码，线路利用，同步，使通信数据具路利用，同步，使通信数据具有透明性。有透明性。 网网络上上连接着大量的接着大量的计算机系算机系统，每台，每台计算机系算机系统上可能有多个
166、用上可能有多个用户在同在同时使用使用计算机与其它网上用算机与其它网上用户进行通信，而网行通信，而网络通信通信线路通常路通常设计成公用成公用资源，源，这样，网，网络通信通信为了了实现可靠的数据交可靠的数据交换，因需要做，因需要做许多具体的操作运算而多具体的操作运算而变得十分复得十分复杂。由于从用。由于从用户发送送或接收可以或接收可以识别的符号信息到的符号信息到实际在正确的通信在正确的通信线路路上上传递物理信息之物理信息之间存在存在转换、线路利用、分路利用、分组交交换、差差错纠正等一系列的操作，正等一系列的操作，为了便于了便于协议的有效的有效实现和和对不同的用不同的用户开放，最大限度地开放，最大限
167、度地实现线路的有效利路的有效利用，有必要用，有必要对网网络计算机系算机系统进行通信行通信结构分构分层。于。于是是产生了网生了网络协议层。每一。每一层包含一包含一组通信功能和相通信功能和相应的的层间通信通信协议，支持通信双方在不同的，支持通信双方在不同的层间进行行通信，并提供了通信，并提供了实现通信的具体思想和方法。通信的具体思想和方法。网络的协议网络的协议网络的协议网络的协议 按照按照ISO的建的建议，网，网络结构模型是开放系构模型是开放系统互互连模型模型OSI（七（七层协议），包括物理），包括物理层，数据，数据链路路层，网，网络层，传输层，会，会话层，表示，表示层，应用用层共七共七层，产生了
168、七生了七层协议。 开放系统开放系统A A 开放系统开放系统B B 应用层协议应用层协议 应用层应用层 应用层应用层 表示层协议表示层协议 表示层表示层 表示层表示层 会话层协议会话层协议 会话层会话层 会话层会话层 传输层协议传输层协议 传输层传输层 传输层传输层 网络层协议网络层协议 网络层网络层 网络层网络层 数据链路层协议数据链路层协议 数据链路层数据链路层数据链路层数据链路层 物理层协议物理层协议 物理层物理层 物理层物理层 物理传输介质物理传输介质 网络的协议网络的协议网络的协议网络的协议网络的网络的网络的网络的OSIOSI协议协议协议协议oo物理物理层协议实现物理上互物理上互连系系
169、统间位流信息的透位流信息的透明明传输，即，即实现了一位（了一位（组）数据在两个通信）数据在两个通信实体之体之间的可靠的可靠传送通信，它描述了送通信，它描述了经通信介通信介质在在数据数据链路路实体之体之间建立、建立、维护和拆除物理和拆除物理连接。接。oo数据数据链路路层协议主要是主要是对高高层屏蔽屏蔽传输介介质的特的特性，性，为网网络通信通信实体之体之间提供建立、提供建立、维护和和释放放数据数据链路路连接的功能和手段，接的功能和手段，实现无差无差错的数据的数据以以帧为单位的可靠位的可靠传送。送。oo网网络层协议主要是主要是为通信子网与高通信子网与高层结构之构之间提提供界面供界面连接，其主要任接，
170、其主要任务是是对通信子网通信子网实现路径路径选择，实现通信通信实体之体之间端端-端的透明的数据端的透明的数据传送，送，对高高层屏蔽了数据屏蔽了数据传送送经过的路径。的路径。 网络的网络的网络的网络的OSIOSI协议协议协议协议oo传输层协议也称也称为主机主机-主机主机层协议，它，它为会会话层的通信的通信实体之体之间提供透明的数据提供透明的数据传送，其送，其主要任主要任务是接收会是接收会话实体送来的数据，根据需体送来的数据，根据需要把它要把它们分成若干比分成若干比较小的小的单元，保元，保证所有数所有数据据单元元经下面三下面三层正确地到达另一个会正确地到达另一个会话实体。体。oo会会话层协议也称也
171、称进程程-进程程层协议，它通，它通过协议提供的一提供的一组命令命令为网上两个网上两个进程之程之间的通信的通信建立会建立会话连接和接和释放会放会话连接，并管理它接，并管理它们在在该连接上的接上的对话。网络的网络的网络的网络的OSIOSI协议协议协议协议oo表示表示层协议以以对应用用实体有意体有意义的形式提供有的形式提供有关信息表示的服关信息表示的服务。这些服些服务有文本有文本压缩、代、代码转换、数据加密与解密、文件格式、数据加密与解密、文件格式变换、信、信息格式息格式变换、终端属性的端属性的转换等。等。oo应用用层协议是用是用户访问网网络的接口的接口层，直接，直接为正在通信的端点用正在通信的端点
172、用户的的应用用进程服程服务，如，如电子子邮件、件、远程操作程操作访问、虚、虚拟终端等。端等。oo关于关于协议详细的的实现技技术，其主要的基，其主要的基础是分是分布式算法，今后，同学布式算法，今后，同学们有可能学有可能学习这些内容。些内容。oo网网络信息安全、加密、病毒、高性能信息安全、加密、病毒、高性能计算与通算与通信、信息高速公路、数字地球信、信息高速公路、数字地球4.15CC1991报告提取的核心概念第第4章章 计算学科中的核计算学科中的核 心概念心概念oo核心概念是核心概念是CC1991报告首次提出的，是具有告首次提出的，是具有普遍性、持久性的重要思想、原普遍性、持久性的重要思想、原则和
173、方法。和方法。它的基本特征有：它的基本特征有：n n在学科中多在学科中多处出出现；n n在在各各分分支支领域域及及抽抽象象、理理论和和设计的的各个各个层面上都有很多示例；面上都有很多示例；n n在技在技术上有高度的独立性；上有高度的独立性；n n一般都在数学、科学和工程中出一般都在数学、科学和工程中出现。1.1.绑定绑定绑定绑定（BindingBinding）oo绑定指的是通过将一个对象（或事物）与其某种属性相联系，从而使抽象的概念具体化的过程。例如：将一个进程与一个处理机，一个变量与其类型或值分别联系起来。这种联系的建立，实际上就是建立了某种约束。2.2.大问题的复杂性大问题的复杂性大问题的
174、复杂性大问题的复杂性（ComplexityofLargeProblemsComplexityofLargeProblems）oo大问题的复杂性是指随着问题规模的增长而使问题的复杂性呈非线性增加的效应。这种非线性增加的效应是区分和选择各种现有方法和技术的重要因素。3. 3. 概念和形式模型概念和形式模型概念和形式模型概念和形式模型（ConceptualandFormatModelsConceptualandFormatModels）oo概念和形式模型是对一个想法或问题进行形式化、特征化、可视化思维的方法。抽象数据类型、语义数据类型以及指定系统的图形语言，如数据流图和E-R图等都属于概念模型。而逻
175、辑、开关理论和计算理论中的模型大都属于形式模型。概念模型和形式模型以及形式证明是将计算学科各分支统一起来的重要的核心概念。4. 4.一致性和完备性一致性和完备性一致性和完备性一致性和完备性（ConsistencyandCompletenessConsistencyandCompleteness）oo一一致致性性包包括括用用于于形形式式说明明的的一一组公公理理的的一一致致性性、事事实和和理理论的的一一致致性性，以以及及一一种种语言言或或接接口口设计的内部一致性。的内部一致性。oo完完备性性包包括括给出出的的一一组公公理理，使使其其能能获得得预期期行行为的的充充分分性性、软件件和和硬硬件件系系统功
176、功能能的的充充分分性性，以以及及系系统处于于出出错和和非非预期期情情况况下下保保持持正正常常行行为的能力等。的能力等。oo在在计算算机机系系统设计中中，正正确确性性、健健壮壮性性和和可可靠靠性就是一致性和完性就是一致性和完备性的具体体性的具体体现。5.5.效率效率效率效率（EfficiencyEfficiency）oo效率是关于空间、时间、人力、财力等资源消耗的度量。在计算机软硬件的设计中，要充分考虑某种预期结果所达到的效率，以及一个给定的实现过程较之替代的实现过程的效率。 6 6演化演化（EvolutionEvolution） 演化指的是系统的结构、状态、特征、行为和功能等随着时间的推移而发
177、生的更改。这里主要是指了解系统更改的事实和意义及应采取的对策。在软件进行更改时，不仅要充分考虑更改对系统各层次造成的冲击，还要充分考虑到软件的有关抽象、技术和系统的适应性问题。7.7.抽象层次抽象层次抽象层次抽象层次（Levels of AbstractionLevels of Abstraction）oo抽象层次指的是通过对不同层次的细节和指标的抽象对一个系统或实体进行表述。在复杂系统的设计中，隐藏细节，对系统各层次进行描述（抽象），从而控制系统的复杂程度。例如，在软件工程中，从规则说明到编码各个阶段（层次）的详细说明，计算机系统的分层思想，计算机网络的分层思想等。8. 8.按空间排序按空间
178、排序按空间排序按空间排序（Ordering in SpaceOrdering in Space）oo按空间排序指的是各种定位方式，如物理上的定位（如网络和存储中的定位），组织方式上的定位（如处理机进程、类型定义和有关操作的定位）以及概念上的定位（如软件的辖域、耦合、内聚等）。按空间排序是计算技术中一个局部性和相邻性的概念。 9.9.按时间排序按时间排序按时间排序按时间排序（Ordering in TimeOrdering in Time）oo按时间排序指的是事件的执行对时间的依赖性。例如，在具有时态逻辑的系统中，要考虑与时间有关的时序问题；在分布式系统中，要考虑进程同步的时间问题；在依赖于时间
179、的算法执行中，要考虑其基本的组成要素。10.10.重用重用重用重用（ReuseReuse）oo重用指的是在新的环境下，系统中各类实体、技术、概念等可被再次使用的能力。如软件库和硬件部件的重用等。 11.11.安全性安全性安全性安全性（SecuritySecurity）oo安全性指的是计算机软硬件系统对合法用户的响应及对非法请求的抗拒，以保护自己不受外部影响和攻击的能力。如为防止数据的丢失、泄密而在数据库管理系统中提供的口令更换、操作员授权等功能。 12.12.折衷与结论折衷与结论折衷与结论折衷与结论（Tradeoff and ConsequencesTradeoff and Consequences）oo指的是为满足系统的可实施性而对系统设计中的技术、方案所作出的一种合理的取舍。结论是折衷的结论，即选择一种方案代替另一种方案所产生的技术、经济、文化及其他方面的影响。折衷是存在于计算学科领域各层次上的基本事实。如在算法的研究中，要考虑空间和时间的折衷；对于矛盾的设计目标，要考虑诸如易用性和完备性、灵活性和简单性、低成本和高可靠性等方面所采取的折衷等。
