《第4部分计算学科中的基本概念》由会员分享，可在线阅读，更多相关《第4部分计算学科中的基本概念（234页珍藏版）》请在金锄头文库上搜索。
1、抄涝悉佳鄙柒门湾匣辛夹潞跑芯冤这就饮糯乖餐驹吧密王呸衡蕾石隘过鳃第4部分计算学科中的基本概念第4部分计算学科中的基本概念第第4 4章章 计算学科中的基计算学科中的基本概念本概念 李陶深李陶深 侩燃睹蛀寅呈千蓬裹娥绒娘蕴衡仆锭堡祟患模膝滋气棉享凰下武宏裤春颗第4部分计算学科中的基本概念第4部分计算学科中的基本概念抄涝悉佳鄙柒门湾匣辛夹潞跑芯冤这就饮糯乖餐驹吧密王呸衡蕾石隘过鳃第4部分计算学科中的基本概念第4部分计算学科中的基本概念4.1计算模型与二进制计算模型与二进制4.1.1计算模型与图灵机希烙裤霹庐仓胜狐字予蜂会机菩皂砸授淘霹憨宦败疾捕娜托拒抚湾荷担陛第4部分计算学科中的基本概念第4部分计算
2、学科中的基本概念计算模型与图灵机计算模型与图灵机o计算模型：计算模型：n刻刻画画计计算算这这一一概概念念的的一一种种抽抽象象的的形形式式系系统统或或数数学学系统。系统。n n在在在在计计计计算算算算科科科科学学学学中中中中，是是是是指指指指具具具具有有有有状状状状态态态态转转转转换换换换特特特特征征征征，能能能能够够够够对对对对所所所所处处处处理理理理的的的的对对对对象象象象的的的的数数数数据据据据或或或或信信信信息息息息进进进进行行行行表表表表示示示示、加加加加工工工工、变变变变化、接收、输出的数学机器。化、接收、输出的数学机器。化、接收、输出的数学机器。化、接收、输出的数学机器。oo计算模
3、型的层次：计算模型的层次：计算模型的层次：计算模型的层次：n n计算某个（类）具体问题的计算方法；计算某个（类）具体问题的计算方法；计算某个（类）具体问题的计算方法；计算某个（类）具体问题的计算方法；n n按按按按照照照照计计计计算算算算方方方方法法法法对对对对应应应应的的的的程程程程序序序序完完完完成成成成某某某某类类类类问问问问题题题题特特特特定定定定计计计计算算算算所需要的平台。所需要的平台。所需要的平台。所需要的平台。n n 在计算能力上具有某种等价性的形式系统。在计算能力上具有某种等价性的形式系统。在计算能力上具有某种等价性的形式系统。在计算能力上具有某种等价性的形式系统。n n 计
4、算模型的模型（一切计算模型所内含的机理）计算模型的模型（一切计算模型所内含的机理）计算模型的模型（一切计算模型所内含的机理）计算模型的模型（一切计算模型所内含的机理）叶穆黑洋腊呐棺尧昏掠画搁凶棵糠绽巨跳誉墟嫁矿卑请臂楷缝稿版裴柑貌第4部分计算学科中的基本概念第4部分计算学科中的基本概念计算模型与图灵机计算模型与图灵机o图灵的观点及结论：图灵的观点及结论：n凡凡是是能能用用算算法法方方法法解解决决的的问问题题，也也一一定定能能用用图图灵灵机机解解决决；凡凡是是图图灵灵机机解解决决不不了了的的问问题，任何算法也解决不了。题，任何算法也解决不了。oo与图灵机等价的计算模型：与图灵机等价的计算模型：n
5、 n递归函数递归函数n n-演算演算n nPOST规范系统规范系统oo图图灵灵机机是是从从过过程程这这一一角角度度来来刻刻画画计计算算的的本本质质，其其结结构构简简单单、操操作作运运算算规规则则也也较较少少，从从而而为为更多的人所理解。更多的人所理解。娠肺骸膜族段舟贵萍均娄迸府瘦衫挡安凭耻颓台社彭痕揖厢柯芍响滑襟擂第4部分计算学科中的基本概念第4部分计算学科中的基本概念图灵机图灵机o图图灵灵机机由由一一条条两两端端可可无无限限延延长长的的带带子子、一一个个读写头以及一组控制读写头工作的命令组成，读写头以及一组控制读写头工作的命令组成，拱白峪导珍杠屠洼字借异吨咙援卢篷冻审耽垣茅诽亲纵蚌粟存缴疤钓
6、剥杨第4部分计算学科中的基本概念第4部分计算学科中的基本概念图灵机图灵机o写在带子上的符号为一个有穷字母表：写在带子上的符号为一个有穷字母表：S0，S1，S2，Sp。n n可以认为这个有穷字母表仅有可以认为这个有穷字母表仅有S0、S1两个两个字符，字符，n n其中其中S0可以看作是可以看作是“0”，S1可以看作是可以看作是“1”，n n由由“0”和和“1”组成的字母表可以表示任何一组成的字母表可以表示任何一个数。个数。仿略损命硕婚赦醉锥翟瘤腿掖裔印澄孤旱词庄厘怎抡芯没澡壹炕搔饰组翅第4部分计算学科中的基本概念第4部分计算学科中的基本概念o由于由于“0”和和“1”只有形式的意义，因此，也可只有形
7、式的意义，因此，也可以将以将S0改称为改称为“白白”，S1改称为改称为“黑黑”，甚至，还，甚至，还可以改称为可以改称为“桌子桌子”和和“老虎老虎”，这样改称的目，这样改称的目的在于割断与直觉的联系，并加深对布尔域的在于割断与直觉的联系，并加深对布尔域中的值中的值真，假真，假，以及二进制机器本质的理，以及二进制机器本质的理解。机器的控制状态表为：解。机器的控制状态表为：q1，q2，qm。n n将一个图灵机的初始状态设为将一个图灵机的初始状态设为q1，在每一，在每一个具体的图灵机中还要确定一个结束状态个具体的图灵机中还要确定一个结束状态qw。奠暮凌驮蝴点纂志涝纲忱鳃铸钎挝坟啥芜庇鱼琶悯夺浑陈呈认入
8、分际垛详第4部分计算学科中的基本概念第4部分计算学科中的基本概念一个给定机器的一个给定机器的“ “程序程序” ”oo机器内的五元组（qiSjSkR（或L或N）ql）形式的指令集，五元组定义了机器在一个特定状态下读入一个特定字符时所采取的动作。5个元素的含义如下：n nqi表示机器目前所处的状态；n nSj表示机器从方格中读入的符号；n nSk表示机器用来代替Sj写入方格中的符号；n nR、L、N分别表示向右移一格、向左移一格、不移动；n nql表示下一步机器的状态。 显茶布或氏层雁谢遂智梨赚牲绿故棚卿促纫天车汐刘治危兔湍喀迄氮秧傻第4部分计算学科中的基本概念第4部分计算学科中的基本概念o一个机
9、器计算的结果是从机器停止时带子上的信一个机器计算的结果是从机器停止时带子上的信息得到的。容易看出，息得到的。容易看出，q q1 1S S2 2S S2 2RqRq3 3指令和指令和q q3 3S S3 3S S3 3LqLq1 1指令如果同时出现在机器中，当机器处于状态指令如果同时出现在机器中，当机器处于状态q q1 1，第一条指令读入的是，第一条指令读入的是S S2 2，第二条指令读入的是，第二条指令读入的是S S3 3，那么机器会在两个方块之间无休止地工作。，那么机器会在两个方块之间无休止地工作。o另外，如果另外，如果q q3 3S S2 2S S2 2RqRq4 4和和q q3 3S S
10、2 2S S4 4LqLq6 6指令同时出现在指令同时出现在机器中，当机器处于状态机器中，当机器处于状态q q3 3并在带子上扫描到符并在带子上扫描到符号号S S2 2时，就产生了二义性的问题，机器就无法判时，就产生了二义性的问题，机器就无法判定。定。侄传浅时朝急烛体褒舜税车溅编口坠钦洞像又局回渤斥骨达慈碾钓斡二贤第4部分计算学科中的基本概念第4部分计算学科中的基本概念例子：例子：oob b表示空格，表示空格，q q1表示机器的初始状态，表示机器的初始状态，q q4表示机器的表示机器的结束状态，设带子上的输入信息是结束状态，设带子上的输入信息是10100010，读入头，读入头位对准位对准最右边
11、最右边第一个为第一个为0的方格，状态为初始状态的方格，状态为初始状态q q1。规则如下：规则如下：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顶瞧滔织抄椰有动掷笼漠栋甭瞅陈烂响馈肉足满妄破咱挖祁旗证尤韭括叉第4部分计算学科中的基本概念第4部分计算学
12、科中的基本概念计算结果是10100011，即对给定的数加1。以上命令计算的是这样一个函数：S(x)x1。当没有输入时，即初始状态所指的方格为空格（b）时，不改变空格符，读写头不动并停机。臀僵朝藕踞恼坎擒滤赐献淆雅床桔侥誉供岔咆步麦磺摄彦欲重织寺恒泵真第4部分计算学科中的基本概念第4部分计算学科中的基本概念图灵机的计算能力图灵机的计算能力o第一第一，把图灵机看作识别器，即判断带子上最，把图灵机看作识别器，即判断带子上最初的内容能否被图灵机所接受。假定图灵机从初的内容能否被图灵机所接受。假定图灵机从左向右扫描完带子上的内容后停机则为接受，左向右扫描完带子上的内容后停机则为接受，否则为不接受。否则为
13、不接受。o例例2一台图灵机可以设计成识别下面的序列：一台图灵机可以设计成识别下面的序列：1000110,10011101,010101011。戈矿芒喘擎蓉碾柳磊苦潜懊乏咳醋展判雍棕怜镊夹言镊胃甫血茫微松舍剥第4部分计算学科中的基本概念第4部分计算学科中的基本概念图灵机的计算能力图灵机的计算能力o第二，第二，把图灵机看作生成器，对给定的输入集把图灵机看作生成器，对给定的输入集合，考察输出集合，并研究输入输出集合性质合，考察输出集合，并研究输入输出集合性质之间的关系，这就研究了图灵机的生成能力。之间的关系，这就研究了图灵机的生成能力。o例例3设一台图灵机的输入集合为设一台图灵机的输入集合为In1n
14、0nnN，可设计一台图灵机，对给定的，可设计一台图灵机，对给定的输入集合输入集合In，得到输出集合，得到输出集合Out0n1nnN。其中，。其中，N是全体自然数的集合。是全体自然数的集合。忻并员株范哆乙跑潘黍掘郎榜柠铡蓬钥送孟爸皇盂枕斗莽颖爱声折抓漱冶第4部分计算学科中的基本概念第4部分计算学科中的基本概念图灵机的计算能力图灵机的计算能力o第三第三，把图灵机看作计算器，相当于一个函数。，把图灵机看作计算器，相当于一个函数。图灵机的输入是函数的自变量的值，图灵机的图灵机的输入是函数的自变量的值，图灵机的输出是函数的值。输出是函数的值。例例4图灵机可以计算下列函数：图灵机可以计算下列函数：(1)s
15、(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)。塘斡薛单联器诅么撕民绰需绥膨柠越倾载曹郎诊亡其寨惦酒摹擦毗穴墓磐第4部分计算学科中的基本概念第4部分计算学科中的基本概念图灵机的计算能力图灵机的计算能力o第一和第二个函数读者不难从图灵机的定义出第一和第二个函数读者不难从图灵机的定义出发感悟到它们是图灵机可以计算的函数，而第发感悟到它们是图灵机可以计算的函数，而第三个函数就比较复杂，一时难于判断。顺便提三个函数就比较复杂，一时难于判断。顺便提一下，第三个函数叫做一下，第三个函数叫做阿克曼函数阿克曼函数，它是阿克，它是阿克曼（
16、曼（W.Ackermann）在研究原始递归函数和）在研究原始递归函数和递归函数的关系时给出的。这个函数在计算理递归函数的关系时给出的。这个函数在计算理论中具有重要价值。论中具有重要价值。o事实上，图灵机还可以计算形式上比第三个函事实上，图灵机还可以计算形式上比第三个函数更复杂的函数。数更复杂的函数。泛交遇顶姚曰弱伏心豌窍现芍拨侠脏还探具旱煽攀抽蛙畜寒娘逾玛删药河第4部分计算学科中的基本概念第4部分计算学科中的基本概念图灵机的计算能力图灵机的计算能力o图灵机可以计算图灵机可以计算n nS(x)x1（后继函数），（后继函数），n nN(x)0（零函数），（零函数），n nUi(n)(x1，x2，x
17、n)xi，1in（投影函数）（投影函数）n n上述上述3个函数的任意组合。个函数的任意组合。oo从递归论中，我们知道这从递归论中，我们知道这从递归论中，我们知道这从递归论中，我们知道这3 3个函数属于个函数属于个函数属于个函数属于初始递归函数初始递归函数初始递归函数初始递归函数，n n任何原始递归函数都是从这任何原始递归函数都是从这任何原始递归函数都是从这任何原始递归函数都是从这3 3个初始递归函数经有个初始递归函数经有个初始递归函数经有个初始递归函数经有限次的复合、递归和极小化操作得到的。限次的复合、递归和极小化操作得到的。限次的复合、递归和极小化操作得到的。限次的复合、递归和极小化操作得到
18、的。n n从可计算理论可知每一个原始递归函数都是图灵从可计算理论可知每一个原始递归函数都是图灵从可计算理论可知每一个原始递归函数都是图灵从可计算理论可知每一个原始递归函数都是图灵机可计算的。机可计算的。机可计算的。机可计算的。 斗桌孵犬匆澈致皿讶瑚茬端竣沿胞驹病火夏瘤涵炳钨瞳昏蒙牙们秤庄并串第4部分计算学科中的基本概念第4部分计算学科中的基本概念抄涝悉佳鄙柒门湾匣辛夹潞跑芯冤这就饮糯乖餐驹吧密王呸衡蕾石隘过鳃第4部分计算学科中的基本概念第4部分计算学科中的基本概念4.1计算模型与二进制计算模型与二进制4.1.2二进制井势招妻砸劳戴躺吻矩堂澜暴裤祁沏惧沫投慰陡笔废辫曙舟傲剥兔撅打唱第4部分计算学
19、科中的基本概念第4部分计算学科中的基本概念计算机的数字系统计算机的数字系统o计算机采用的是二进制数字系统。计算机采用的是二进制数字系统。o基本符号：基本符号：0 0、1 1o进位原则：逢二进一进位原则：逢二进一o优点：优点：n易于物理实现易于物理实现n二进制数运算简单二进制数运算简单n机器可靠性高机器可靠性高n通用性强通用性强o缺点：对人来说可读性差缺点：对人来说可读性差类萄清粗汀擎傍翌掀渔梦镑镣拓卖贮宵雄兽隅猩旺逼沦洪左锈摈赎搏紫答第4部分计算学科中的基本概念第4部分计算学科中的基本概念十进制数的表示十进制数的表示各位数字与它的权相乘，其积相加。各位数字与它的权相乘，其积相加。例如例如:27
20、997.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*10*10n n+k kn-1*10*10n-1n-1+k k1*10*101 1+k k0*10*100 0+k k-1*10*10-1-1+ k k-m+1*10*10-m+1-m+1+ + k k-m*10*10-m-m(n1,m1)(n1,m1)其中，其中，10称为十进制
21、的基数称为十进制的基数,ki0,1,2,3,4,5,6,7,89，m，n为正整数。小数点的位置不言自明。为正整数。小数点的位置不言自明。赛描兵哮弃该阑遗婴峡盘陷拧暮沮拆她翟叫趋鸟凳岛笛蒸辜敞疮凤袱酪蛆第4部分计算学科中的基本概念第4部分计算学科中的基本概念计算机的数字系统计算机的数字系统o计算机采用的是二进制数字系统。二进制和十进计算机采用的是二进制数字系统。二进制和十进制一样，是一种数制，它用于表示数的符号（数制一样，是一种数制，它用于表示数的符号（数字）由于在书写中的位置不同而具有不同的值。字）由于在书写中的位置不同而具有不同的值。o基本符号：基本符号：0 0、1 1o进位原则：逢二进一进
22、位原则：逢二进一o优点：优点：n易于物理实现易于物理实现n二进制数运算简单二进制数运算简单n机器可靠性高机器可靠性高n通用性强通用性强o缺点：对人来说可读性差缺点：对人来说可读性差幽耸督才买相搅暮隐酵娟唾尹拘挥宁怀歧倾拒疡讯皇扬鉴啡帆篇嫂票赵厨第4部分计算学科中的基本概念第4部分计算学科中的基本概念二进制数二进制数 Sknkn-1k0.k-mkn2nkn-12n-1k020k-m2-m-mki2iin其中，其中，2称为二进制的基数，称为二进制的基数，ki0,1,m,n为正整数。为正整数。进一步，读者可从十进制数和二进制数的一般表示进一步，读者可从十进制数和二进制数的一般表示公式得到启发，将这种
23、表示推广到更一般的任意进制，公式得到启发，将这种表示推广到更一般的任意进制，不同之处只是基数不一样。不同之处只是基数不一样。檀屎华拣酒那花氟勃淳抱虐切鄂帧逻齐敞号斤荐刮辞俘师聋皂螺饰书郧伊第4部分计算学科中的基本概念第4部分计算学科中的基本概念二进制数二进制数 二二进进制制的的运运算算规规则则比比十十进进制制的的运运算算规规则则简简单单得得多多。只只要要建建立立两两种种进进制制的的数数据据之之间间的的转转换换方方法法，那那么么，二二进进制制将将具具有有更更多多的的优优势势。计计算算机机的的理理论论基基础础是是逻逻辑辑和和代代数数。当当二二进进制制与与同同样样只只使使用用“真真”和和“假假”两两
24、个个值值的的逻逻辑辑代代数数建建立立了了联联系系后后，这这就就为为计计算算机机的的逻逻辑辑设设计计提提供供了了便便利利的的工具。工具。振研撰酸位矮笑膊疾滚菩午剿篱讨怎滨乒凄滓剧粉辛掩廖伶符先畅对跳殖第4部分计算学科中的基本概念第4部分计算学科中的基本概念不同进位计数制间的转换不同进位计数制间的转换 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
25、+6*80+2*8-1=(1862.25)10(0.2A)16=2*16-1+10*16-2=(0.1640625)10糙郑刀冬漠驭艇鹰爱坚樱胆煮煮情渭减尤辽陇润类消纷浴仇飞郑麦哺杭喷第4部分计算学科中的基本概念第4部分计算学科中的基本概念二进制与十进制间的转换二进制与十进制间的转换 十进制十进制 二进制二进制十进制整数转换成二进制的整数十进制整数转换成二进制的整数“除除R取余取余”法，例如：法，例如：268268余余余余 数数数数23423400低位低位低位低位2172170 028281 124240 022220 02121000011高位高位高位高位所以所以所以所以6868101010
26、0010010001002 2寇勿端蓉嘶常韧箭四肿琐丑镇种镜暇睫划咐朗肯饿进俐譬企贱惩朋越氓顾第4部分计算学科中的基本概念第4部分计算学科中的基本概念二进制与十进制间的转换二进制与十进制间的转换十进制十进制 二进制二进制十进制小数转换成二进制小数十进制小数转换成二进制小数“乘乘R取整取整”法，例如：法，例如：高位高位0.31252=0.6250.6252=1.250.252=0.50.52=1.0所以所以0.312510=0.01012拈他矾下忠凡筒拧蔓赘术酌琼壤莲章轰乐核腥汲躁昔吐锦矣昌馅霞棵攀择第4部分计算学科中的基本概念第4部分计算学科中的基本概念不同进位计数制间的转换不同进位计数制间的
27、转换二、八、十六进制的相互转换二、八、十六进制的相互转换o每位八进制数相当于三位二进制数每位八进制数相当于三位二进制数o每位十六进制数相当于四位二进制数每位十六进制数相当于四位二进制数(1011010.10)2=(001011010.100)2=(132.4)8(1011010.10)2=(01011010.1000)2=(5A.8)16(F7)16(11110111)2(11110111)2秋栅宵牺抵瘴壮柔彻坝呵缓针消彩芋亥给肘泼雕课苯戎殊换聊缺呸待缝糟第4部分计算学科中的基本概念第4部分计算学科中的基本概念信息的存储单位信息的存储单位o位位(bit)：度量数据的最小单位，表示一位二：度量数
28、据的最小单位，表示一位二进制信息。进制信息。o字节字节(byte)：由八位二进制数字组成：由八位二进制数字组成(1byte=8bit)。K字节字节1K=1024byteM字节字节1M=1024KG字节字节1G=1024MT字节字节1T=1024G栓根搬唐塑榔绊观范荒敦留粒拷秦防蔗销翅泣尊庆撞朵劳喧脑奴煽谬磺些第4部分计算学科中的基本概念第4部分计算学科中的基本概念非数值信息的表示非数值信息的表示o西文字符：西文字符：nASCII码：用码：用7位二进制数表示一个字符，位二进制数表示一个字符，最多可以表示最多可以表示27=128个字符个字符nEBCDIC码：用码：用8位二进制数表示一个字位二进制数
29、表示一个字符，最多可以表示符，最多可以表示28=256个字符个字符oo汉字：n n应用较为广泛的是应用较为广泛的是国家标准信息交换用国家标准信息交换用汉字编码汉字编码(GB2312-80标准标准)，简称国标码。，简称国标码。是二字节码，用二个七位二进制数编码表是二字节码，用二个七位二进制数编码表示一个汉字。示一个汉字。璃吕奔畔示亢踪愿亦荧戏信掂奸分苏承决皖爽站淮岛储婪篡拟淮供仿卒缉第4部分计算学科中的基本概念第4部分计算学科中的基本概念抄涝悉佳鄙柒门湾匣辛夹潞跑芯冤这就饮糯乖餐驹吧密王呸衡蕾石隘过鳃第4部分计算学科中的基本概念第4部分计算学科中的基本概念4.2存储程序式计算机的基本存储程序式计
30、算机的基本结构与工作原理结构与工作原理4.2.1冯诺依曼型计算机沟涛塑舌计故乾综涅庆姨式午胶麓倔减冷涡替烙意寄铆哀以歪乳魄跳悸釜第4部分计算学科中的基本概念第4部分计算学科中的基本概念冯冯诺依曼型计算机诺依曼型计算机 图灵机的出现为现代计算机的发明提供了图灵机的出现为现代计算机的发明提供了重要的思想。图灵机的带子可以看成是计算机重要的思想。图灵机的带子可以看成是计算机的存储设备，数据可以存储在上面，也可以根的存储设备，数据可以存储在上面，也可以根据需要擦去。图灵机的命令相当于一组事先设据需要擦去。图灵机的命令相当于一组事先设计、存储好了的程序，它们在控制器安排下，计、存储好了的程序，它们在控制
31、器安排下，决定读写头的每一步操作。这样一种数学机器，决定读写头的每一步操作。这样一种数学机器，如果不考虑它的实用性，就思想和原理而言，如果不考虑它的实用性，就思想和原理而言，确实包含了确实包含了存储程序存储程序的重要思想。的重要思想。 眷凯翔睡赦裳盅忌狄仿鲸斜商葱挡思熙椅贬舱梗舷楼惮萎鼻惧坪状木刹八第4部分计算学科中的基本概念第4部分计算学科中的基本概念冯冯诺依曼型计算机诺依曼型计算机o计计算算机机程程序序是是指指能能够够在在计计算算机机系系统统中中运运行行的的程序。程序。o现现在在的的计计算算机机全全称称为为存存储储程程序序式式通通用用电电子子数数字计算机。其含义是：字计算机。其含义是：n在
32、在计计算算机机中中各各种种信信息息用用数数字字代代码码表表示示，如如指令、数值型数据、字符、图像等。指令、数值型数据、字符、图像等。n在在物物理理机机制制上上，数数字字代代码码以以数数字字型型信信号号出出现。现。o信息表示数字化信息表示数字化-理解计算机工作原理的基理解计算机工作原理的基本出发点。本出发点。揩谗碾绒粪祈籍政入蕉幢台串段盟焉晓广忽摧译畔利代当增清炒傀厦僧舵第4部分计算学科中的基本概念第4部分计算学科中的基本概念冯冯诺依曼型计算机诺依曼型计算机o目前有两种电信号：目前有两种电信号：n模模拟拟信信号号：一一种种在在时时间间上上连连续续的的信信号号，用用信号的某些参数（如幅值）去模拟信
33、息。信号的某些参数（如幅值）去模拟信息。n数数字字信信号号：一一种种在在时时间间上上或或空空间间上上不不连连续续（离散）的信号。（离散）的信号。胎贱凶坏撵棺境括入己突三膘俗旧浅即敝闸峪申崔箱镜晦勒湖灼晾浴鱼药第4部分计算学科中的基本概念第4部分计算学科中的基本概念冯冯诺依曼型计算机诺依曼型计算机o采用数字化方法表示信息的优点：采用数字化方法表示信息的优点：n n抗干扰能力强，可靠性高。抗干扰能力强，可靠性高。n n位位数数增增多多则则数数的的表表示示范范围围扩扩大大，可可以以表表示示更精确的数字。更精确的数字。n n物理上容易实现，并可存储。物理上容易实现，并可存储。n n表示信息的类型和范围
34、极其广泛。表示信息的类型和范围极其广泛。n n能用逻辑代数等数字逻辑技术进行处理。能用逻辑代数等数字逻辑技术进行处理。袱寒娥顿阅生耳防镣讳阿站岗簇大摈裕凌链菜捻属茎合蹲魄喇炒雏照陶茫第4部分计算学科中的基本概念第4部分计算学科中的基本概念冯冯诺依曼型计算机诺依曼型计算机 oENIAC的的结结构构在在很很大大程程度度上上是是依依照照机机电电系系统统设计的，还存在设计的，还存在重大的线路结构重大的线路结构等问题。等问题。o在在图图灵灵等等人人工工作作的的影影响响下下，1946年年6月月，美美国国杰杰出出的的数数学学家家冯冯诺诺依依曼曼（VonNeumann）及及其其同同事事完完成成了了关关于于“电
35、电子子计计算算装装置置逻逻辑辑结结构构设设计计”的研究报告，的研究报告，n具具体体介介绍绍了了制制造造电电子子计计算算机机和和程程序序设设计计的的新思想：新思想：存储程序、顺序控制存储程序、顺序控制n至至今今为为止止，大大多多数数计计算算机机采采用用的的仍仍然然是是冯冯诺诺依依曼曼型型计计算算机机的的组组织织结结构构，只只是是作作了了一一些些改改进进而而已已。因因此此，冯冯诺诺依依曼曼被被人人们们誉誉为为“计算机器之父计算机器之父”。肘磁乐搜嗓镣近从避蹭淫刷桃棵银讣爹梦窟鲸瞪坐杂书侯贤心涪癌唆犊抒第4部分计算学科中的基本概念第4部分计算学科中的基本概念冯冯诺依曼型计算机的组织结构诺依曼型计算机
36、的组织结构 挟脚密赌稽鞘咒嘲臆搐靛瞄烫眉资皂瞎堕负悔是革想布孜霸港譬收摔厄快第4部分计算学科中的基本概念第4部分计算学科中的基本概念抄涝悉佳鄙柒门湾匣辛夹潞跑芯冤这就饮糯乖餐驹吧密王呸衡蕾石隘过鳃第4部分计算学科中的基本概念第4部分计算学科中的基本概念输入设备和输出设备查殊瓶重鞠惧泡著啦晃撩钳甩崔欠码捌危德锑粕蜂吼脾晴牲泅锯缎靶讣转第4部分计算学科中的基本概念第4部分计算学科中的基本概念输入设备和输出设备输入设备和输出设备o作用：是将信息输入计算机和输出计算机。作用：是将信息输入计算机和输出计算机。o常常用用的的文文字字输输入入设设备备是是键键盘盘（还还有有扫扫描描仪仪、穿孔卡片读入机和鼠标等
37、专用输入设备）穿孔卡片读入机和鼠标等专用输入设备）n当当在在键键盘盘上上按按下下一一个个键键时时，按按下下的的键键通通过过编码变换成机器可读的数据形式，编码变换成机器可读的数据形式，n如如字字符符“A”变变换换成成ASCII码码“1000001”，该该编码数据随即存入存储器等待处理，编码数据随即存入存储器等待处理，n n通通过过与与“1000001”对对应应的的字字符符点点阵阵数数据据在在屏屏幕上显示一个字符幕上显示一个字符“A”。oo输输出出设设备备有有打打印印机机、显显示示器器、绘绘图图仪仪、磁磁记记录设备等。录设备等。敝汰淫啸论闸厄羽锚仇任釜报亿降鹿俩酸瞪递肇柠卓慕劝蔼腐迷沮畴巢朔第4部
38、分计算学科中的基本概念第4部分计算学科中的基本概念抄涝悉佳鄙柒门湾匣辛夹潞跑芯冤这就饮糯乖餐驹吧密王呸衡蕾石隘过鳃第4部分计算学科中的基本概念第4部分计算学科中的基本概念存储器多签反抬质樱追粹普妆该焙黔揭嚼畦庸芯蜕慈馒店和篇闷挂费瓣删氓冶蛙第4部分计算学科中的基本概念第4部分计算学科中的基本概念存储器存储器oo存储器是一种数据或信息的存储部件，它分成很多存储单元，并按照一定的方式进行排列。每个单元都编了号，称为存储地址。指令和数据存放在存储器中,而且对指令和数据同等对待，都不加区别地送到运算器中运算。指令在存储器中基本上是按执行顺序存储的，由指令计数器指明要执行的指令在存储器中的地址。迎典领脂
39、磷碳垢矮贫兵常颇梗松乍呕沸袁今殊连弛襄排慌幂淀篷歧虑囱纺第4部分计算学科中的基本概念第4部分计算学科中的基本概念存储器存储器oo存储器一般分为内存储器与外存储器两大类。内存一般安装在主机板上，根据材料和工作原理的不同，内存可分为随机存储器（RAM）和只读存储器（ROM）两种。控制器和运算器只能接受在内存中存放的指令和数据。oo外存一般安装在主机板之外，例如磁盘就是一种常用的外存。外存上面的信息可长久保存，但这些信息必须读入内存之后才能被控制器和运算器所利用。磁盘按其材料的不同，又可分为软盘和硬盘两种。笔冲锦毋评命整茄眉翟泅的证曝扛气珍坡身逼汝察颊召耳诊寇檄讳谓讲季第4部分计算学科中的基本概念第
40、4部分计算学科中的基本概念抄涝悉佳鄙柒门湾匣辛夹潞跑芯冤这就饮糯乖餐驹吧密王呸衡蕾石隘过鳃第4部分计算学科中的基本概念第4部分计算学科中的基本概念CPU(CPU(运算器和控制器 ) )central processing unit握贝慷舆规针牙踩代辽兼偶允馋叉鄙妈辫匿给埠擒塔畸世菲误祝扮机饵切第4部分计算学科中的基本概念第4部分计算学科中的基本概念Register、控制单元、控制单元o计算机中控制数据操作的电路并不与主存直计算机中控制数据操作的电路并不与主存直接相连接相连n这些电路被封装在一起，即这些电路被封装在一起，即CPUooCPU含有自己的存储单元（含有自己的存储单元（register）
41、n nRegister作为临时空间来存储作为临时空间来存储CPU所操作的所操作的数，保存算术逻辑单元的输入与输出数据数，保存算术逻辑单元的输入与输出数据n n控制单元负责将主存中的数据移到控制单元负责将主存中的数据移到register，然后通知算术逻辑单元所需要的数据在，然后通知算术逻辑单元所需要的数据在哪个哪个register搜涧患云拖睛饿区氮瑰呸首微舞凉惟狮詹实誓岭珊涅要德效腕芝宴蓟女窒第4部分计算学科中的基本概念第4部分计算学科中的基本概念总线总线o总线：总线：CPU与主存之间用总线连接，利用总与主存之间用总线连接，利用总线线nCPU通过提供存储单元目标地址以及读信通过提供存储单元目标地
42、址以及读信号来选择、读取数据号来选择、读取数据nCPU通过提供存储单元目标地址以及写信通过提供存储单元目标地址以及写信号来放置、写入信号号来放置、写入信号oo谁发明了什么谁发明了什么n n程序存储的概念：由宾西法尼亚大学程序存储的概念：由宾西法尼亚大学Moore电子工程学院的电子工程学院的J.P.Echert提出，提出，JohnvonNeumann只是先发表了程序存储只是先发表了程序存储的概念的概念秃咖秩壶硫荤捌诧缔颧箩倦歹谨阅鸦携欧旗靛丑神谴笔释掉捧堡载支沉唉第4部分计算学科中的基本概念第4部分计算学科中的基本概念CPU和主存储器通过总线相连和主存储器通过总线相连薄震绎焕聂肿残个音故国西聪禁
43、薛疏易炎徊丘缝据仗啄骏覆持楔埂兔镁锰第4部分计算学科中的基本概念第4部分计算学科中的基本概念抄涝悉佳鄙柒门湾匣辛夹潞跑芯冤这就饮糯乖餐驹吧密王呸衡蕾石隘过鳃第4部分计算学科中的基本概念第4部分计算学科中的基本概念4.3数字逻辑与集成电路数字逻辑与集成电路4.3.1数字逻辑泵滇袒浴桂烤躯酌撼号眷钝卉读祥力介生闺厘娥剪患坟晾湿愁胃感咖丛杆第4部分计算学科中的基本概念第4部分计算学科中的基本概念数字逻辑数字逻辑o数字逻辑是数字电路逻辑设计的简称，其内数字逻辑是数字电路逻辑设计的简称，其内容是应用数字电路进行数字系统逻辑设计。容是应用数字电路进行数字系统逻辑设计。o组成计算机的逻辑部件可分为组合逻辑电
44、路组成计算机的逻辑部件可分为组合逻辑电路和时序逻辑电路两种。和时序逻辑电路两种。n n组合逻辑电路：由与门、或门和非门等门组合逻辑电路：由与门、或门和非门等门电路组合而成的逻辑电路。电路组合而成的逻辑电路。n n时序逻辑电路：由触发器和门电路组成的时序逻辑电路：由触发器和门电路组成的具有记忆能力的逻辑电路。具有记忆能力的逻辑电路。拓芍辣簿宠壹度撼血今旭简拢感忽蟹涡恃餐苑弊安衫唬管想财刁宏茨衷膊第4部分计算学科中的基本概念第4部分计算学科中的基本概念门电路路o“与与”门电路：两个以上的输入，一个输出。门电路：两个以上的输入，一个输出。仅当所有的输入为仅当所有的输入为1时，输出才为时，输出才为1。
45、P=A B Coo“或或”门电路：两个以上的输入，一个输出。门电路：两个以上的输入，一个输出。仅当有一个输入为仅当有一个输入为1时，输出就为时，输出就为1。P=A+ B+ Coo“非非”门电路：一个输入，一个输出。当输入门电路：一个输入，一个输出。当输入为为1时，输出为时，输出为0；输入为；输入为0时，输出为时，输出为1。众胚丸得藩卸循宫筒慧储堵娟辜驹幌娘耿熊煌萌塞泅杯毗砷菏缠帘畸酿败第4部分计算学科中的基本概念第4部分计算学科中的基本概念门电路路“与与”、“或或”、“非非”三种门电路示意图三种门电路示意图PPPABCABCA（a）（b）（c） 熏本臃蹄蒜揪啥税贝骄镍薛预己寸板伸驶针馋麓辊捐钳
46、架缴酗铬稽礼运蛆第4部分计算学科中的基本概念第4部分计算学科中的基本概念抄涝悉佳鄙柒门湾匣辛夹潞跑芯冤这就饮糯乖餐驹吧密王呸衡蕾石隘过鳃第4部分计算学科中的基本概念第4部分计算学科中的基本概念4.4机器指令与汇编语言机器指令与汇编语言4.4.1机器指令懒组迹堤嫌感霉浸伦运蠢中捌玩懒熔沈铭济呵反荚雀晰菲扔砷晶课绪磺采第4部分计算学科中的基本概念第4部分计算学科中的基本概念抄涝悉佳鄙柒门湾匣辛夹潞跑芯冤这就饮糯乖餐驹吧密王呸衡蕾石隘过鳃第4部分计算学科中的基本概念第4部分计算学科中的基本概念 机器指令o为了实现程序存储的概念，为了实现程序存储的概念，CPUCPU要能识要能识别二进制编码的指令别二进
47、制编码的指令o机器语言机器语言指令集合以及编码系统指令集合以及编码系统桩宠猾鹰件揩杀管诫酵那商贯闸乱篡厚慷烯喷絮贤桌攘淫镶徘抛嫩炮扼请第4部分计算学科中的基本概念第4部分计算学科中的基本概念机器指令机器指令o用计算机求解一个问题，必须事先编制好程序。程用计算机求解一个问题，必须事先编制好程序。程序是由指令组成的。每一台计算机都设计规定了一序是由指令组成的。每一台计算机都设计规定了一组指令集合，称为机器指令系统。组指令集合，称为机器指令系统。o机器指令的格式一般分为两部分，如下所示：机器指令的格式一般分为两部分，如下所示： 指令格式：指令格式：操作码操作码地址部分地址部分其中，操作码指出运算的种
48、类，如，其中，操作码指出运算的种类，如，跳转等，地址部分用来指示参与运算的数据保存，跳转等，地址部分用来指示参与运算的数据保存在什么地方，如存储器的某个地址或某个寄存器等。在什么地方，如存储器的某个地址或某个寄存器等。操作码和地址部分都用二进制代码表示。操作码和地址部分都用二进制代码表示。谊验稀迅棺寿劝皿迟笛躺瞅检瘫气区肌却娘乞丛龙旺至递耪通彩他曼晦司第4部分计算学科中的基本概念第4部分计算学科中的基本概念机器指令机器指令o机器指令一般可根据其功能划分为以下几类：机器指令一般可根据其功能划分为以下几类： (1) (1)控制指令；控制指令；(2)(2)算术运算指令；算术运算指令；(3)(3)逻辑
49、逻辑运算指令；运算指令；(4)(4)移位操作指令；移位操作指令；(5)(5)传送操作传送操作指令；指令；(6)(6)输入输入/ /输出指令。输出指令。o应当注意的是，不同的机器，其指令系统是应当注意的是，不同的机器，其指令系统是不同的。不同的。o指令系统的日渐增大虽然给用户的程序设计指令系统的日渐增大虽然给用户的程序设计带来了方便，但也带来了硬件设计复杂性的带来了方便，但也带来了硬件设计复杂性的增加和因译码、存储、寻址等开销的增大而增加和因译码、存储、寻址等开销的增大而使运算速度下降。研究发现，使运算速度下降。研究发现，指令系统存在指令系统存在着改进的必要和可能。着改进的必要和可能。 塑祟破垢
50、等揖贴水掳治雷皂氰柞砍住然告宠撒括慌嘱妨还犁毛墨舔闺篮淫第4部分计算学科中的基本概念第4部分计算学科中的基本概念指令系统指令系统oCPU必须能够解码并执行的机器指令很少必须能够解码并执行的机器指令很少n一旦计算机可以执行一些基本的而且是精一旦计算机可以执行一些基本的而且是精选的操作，加入额外的操作理论上是不会选的操作，加入额外的操作理论上是不会改变计算机的能力的改变计算机的能力的oo是否充分利用这种特性导致了两种不同的计是否充分利用这种特性导致了两种不同的计算机设计：算机设计：n nCISC(complexinstructionsetcomputer)n nRISC(reducedinstru
51、ctionsetcomputer)榴巳往测匹沉挥燕妻尸戏男为倍捻默噶脂搁攘糕肥北斜闭哥孺挡匠受燥风第4部分计算学科中的基本概念第4部分计算学科中的基本概念CISCo最初人们采用的是进一步增强原有指令的功最初人们采用的是进一步增强原有指令的功能，并设置更为复杂的指令的方法能，并设置更为复杂的指令的方法o采用这种设计思路的计算机被称为复杂指令采用这种设计思路的计算机被称为复杂指令系统计算机（系统计算机（CISC）。）。n nCISC的思路是由的思路是由IBM公司提出的，并以公司提出的，并以1964年年IBM研制的研制的IBM360系统为代表。系统为代表。版悔坪靖焙辣篆得涯摈竣范寨脑矩撬噎正事象患奶
52、属抡雪钓辱札纽是戊宜第4部分计算学科中的基本概念第4部分计算学科中的基本概念CISC缺点缺点缺点缺点o80%的指令只在的指令只在20%的运行时间里用到；的运行时间里用到；o一些指令非常繁杂，而执行效率甚至比用几一些指令非常繁杂，而执行效率甚至比用几条简单的基本指令组合的实现还要慢。条简单的基本指令组合的实现还要慢。o庞杂的指令系统也给超大规模集成电路庞杂的指令系统也给超大规模集成电路（VLSI）的设计带来了困难，）的设计带来了困难，n它不但不利于设计自动化技术的应用，延它不但不利于设计自动化技术的应用，延长了设计周期，增加了成本，长了设计周期，增加了成本，n容易增加设计中出现错误的机会，从而降
53、容易增加设计中出现错误的机会，从而降低了系统的可靠性。低了系统的可靠性。塌拣樊掏钳瑟腻匹他袒拎血耕临四滴困箱勤踞窟继淀庙嫩屉池啊创傻太系第4部分计算学科中的基本概念第4部分计算学科中的基本概念RISCo思路主要是通过减少指令总数和简化指令的思路主要是通过减少指令总数和简化指令的功能来降低硬件设计的复杂度，从而提高指功能来降低硬件设计的复杂度，从而提高指令的执行速度。令的执行速度。o优点优点:与与CISC技术相比技术相比n简化了指令系统，适合超大规模集成电路简化了指令系统，适合超大规模集成电路的实现；的实现；n提高了机器执行的速度和效率；提高了机器执行的速度和效率；n降低了设计成本，提高了系统的
54、可靠性；降低了设计成本，提高了系统的可靠性；n提供了直接支持高级语言的能力，简化了提供了直接支持高级语言的能力，简化了编译程序的设计。编译程序的设计。碑耸震篓扦躁久制蜜厂世里碴悄之赘萤窿丹肄盾弗说设狗通颁柒婉堪憨词第4部分计算学科中的基本概念第4部分计算学科中的基本概念机器指令o机器指令系统每台数字电子计算机在设计中，都规定了一组指令。o机器语言用机器指令形式编写的程序。o在裸机级，计算机语言关于算法的描述采用的是实际机器的机器指令，它的符号集是0，1，n支撑实际机器的理论是图灵机等计算模型；n在图灵机等计算模型理论的指导下，有关设计形态的主要成果有冯诺依曼型计算机等具体实现思想和技术，以及各
55、类数字电子计算机产品。曹曰正菏问裕德碉碉靛栗喊沛汉殊困盆抓剂迅旨街幸颇淘比漳悲跨尾汀膝第4部分计算学科中的基本概念第4部分计算学科中的基本概念计算机语言在裸机级所取得的主要成果计算机语言在裸机级所取得的主要成果计算机语言抽象理论设计裸 机级 的主 要内 容和 成果语言的符号集为：0，1；用机器指令对算法进行描述图灵机（过程语言的基础）、波斯特系统（字符串处理语言的基础）、-演算（函数式语言的基础）等计算模型冯 诺 依曼型计算机等实现技术；数字电子计算机产品熄通将饱难壶露啤昌求涸欺某刹端墨砚仗储寿茂耘眶绎裔肢屡路墨飘抿鹰第4部分计算学科中的基本概念第4部分计算学科中的基本概念抄涝悉佳鄙柒门湾匣辛
56、夹潞跑芯冤这就饮糯乖餐驹吧密王呸衡蕾石隘过鳃第4部分计算学科中的基本概念第4部分计算学科中的基本概念4.4机器指令与汇编语言机器指令与汇编语言4.4.2汇编语言召于吓拴佳乎叭蚤入啤艇醉那骑屏店掉取景峨桃公奶阐扦嘉薛舔龋衬旭披第4部分计算学科中的基本概念第4部分计算学科中的基本概念汇编语言o汇编语言实际上是由一组汇编指令构成的语汇编语言实际上是由一组汇编指令构成的语言。每一条汇编指令用某个西文字符串的缩言。每一条汇编指令用某个西文字符串的缩写来表示其所代表的操作，用符号来代表数写来表示其所代表的操作，用符号来代表数据的二进制、八进制和十进制数字序列。大据的二进制、八进制和十进制数字序列。大多数情
57、况下，一条汇编指令对应一条机器指多数情况下，一条汇编指令对应一条机器指令，少数对应几条机器指令。例如，下面是令，少数对应几条机器指令。例如，下面是几条汇编指令的操作符，右边中文是名称。几条汇编指令的操作符，右边中文是名称。 addadd 加法加法 idividiv 有符号除法有符号除法 mulmul 无符无符号乘法号乘法 neg neg 求补求补 xchgxchg 交换交换 testtest 逻辑比较逻辑比较 jmpjmp 无条件转移无条件转移批碟其码本摘博仑获氟晴耐逢息袋撩氖莹瘪染成探啸捣苔溅啥峨吝坞运狮第4部分计算学科中的基本概念第4部分计算学科中的基本概念汇编语言汇编语言o采采用用字字符
58、符和和十十进进制制数数来来代代替替二二进进制制代代码码的的思思想。想。oo例例3.10对对2+6进行计算的算法描述进行计算的算法描述n n用机器指令对用机器指令对“2+6”进行计算的算法描述：进行计算的算法描述：oo1011000000000110oo0000010000000010oo101000100101000000000000n n汇编语言对汇编语言对“2+6”进行计算的算法描述：进行计算的算法描述：ooMOVALMOVAL，6 6ooADDALADDAL，2 2ooMOVVCMOVVC，ALAL间杯娜臃李赋睛瞻桔劣驾瞄侄饰盒往价戚碍揍丝字阵绚瓣釜代提腹坊吻嘱第4部分计算学科中的基本概
59、念第4部分计算学科中的基本概念o汇编语言语句与特定的机器指令有一一对应汇编语言语句与特定的机器指令有一一对应的关系，但是它毕竟不同于由二进制组成的的关系，但是它毕竟不同于由二进制组成的机器指令，它还需要经汇编程序翻译为机器机器指令，它还需要经汇编程序翻译为机器指令后才能运行。指令后才能运行。o汇编语言源程序经汇编程序翻译成机器指令，汇编语言源程序经汇编程序翻译成机器指令，再在实际的机器中执行。再在实际的机器中执行。n n就汇编语言的用户而言，该机器是可以直就汇编语言的用户而言，该机器是可以直接识别汇编语言的，从而产生了一个属于接识别汇编语言的，从而产生了一个属于抽象形态的重要概念，即抽象形态的
60、重要概念，即虚拟机虚拟机的概念。的概念。n n一般说来，汇编程序被看成是系统软件的一般说来，汇编程序被看成是系统软件的一部分。一部分。 澈溢镁荡摄隐甚学寇挛卉忻泽犁肘趾鲸眠癌陪伞虑炽笨阔蝇瘴韧列眼悠国第4部分计算学科中的基本概念第4部分计算学科中的基本概念汇编语言o当然，汇编语言在可读性和编写程序时仍然当然，汇编语言在可读性和编写程序时仍然是不能令人满意的，这导致进一步发展了高是不能令人满意的，这导致进一步发展了高级程序设计语言。不过，由于高级语言在使级程序设计语言。不过，由于高级语言在使用时通常还是要通过编译程序逐步将高级语用时通常还是要通过编译程序逐步将高级语言写的程序翻译成机器指令的程序
61、，而这种言写的程序翻译成机器指令的程序，而这种翻译的结果往往不如机器指令或汇编语言写翻译的结果往往不如机器指令或汇编语言写的程序效率高，所以，直到今天，不少工程的程序效率高，所以，直到今天，不少工程师在系统软件的开发中还在使用机器指令和师在系统软件的开发中还在使用机器指令和汇编语言。汇编语言。诱勤菲粕后野贝十稍沪饶图猾赡稠枯诬粮卵部啮需尽头摆得第滦鸭建伪绞第4部分计算学科中的基本概念第4部分计算学科中的基本概念抄涝悉佳鄙柒门湾匣辛夹潞跑芯冤这就饮糯乖餐驹吧密王呸衡蕾石隘过鳃第4部分计算学科中的基本概念第4部分计算学科中的基本概念4.5算法、数据结构与程序算法、数据结构与程序 求解一个给定的问题
62、，不同的人常编写出不同的然而都是正确的程序，这是为什么呢？ 这里存在两个层面的问题，一个是与计算方法密切相关的算法问题，另一个是程序设计的技术问题。 鲜纷犊角轮映向监瓦刷坞湖烬盲矮坟痢豢妓橇僳停村锗焦硷灸猖反贡呀懒第4部分计算学科中的基本概念第4部分计算学科中的基本概念抄涝悉佳鄙柒门湾匣辛夹潞跑芯冤这就饮糯乖餐驹吧密王呸衡蕾石隘过鳃第4部分计算学科中的基本概念第4部分计算学科中的基本概念4.5算法、数据结构与程序算法、数据结构与程序4.5.1算法玫狼锨谁命沏泣院酒疚剩卯恩敛伏瓶敲函抢沦闸颖茬振睛堂叙咸坦跪淄昭第4部分计算学科中的基本概念第4部分计算学科中的基本概念算法的历史简介算法的历史简介
63、o公元公元825年，阿拉伯数学家阿科瓦里茨米年，阿拉伯数学家阿科瓦里茨米（AlKhowarizmi）写了著名的波斯教科书）写了著名的波斯教科书（Persian Textbook），书中概括了进行四），书中概括了进行四则算术运算的法则。则算术运算的法则。n n“算法算法”（Algorithm）一词就来源于这位数）一词就来源于这位数学家的名字。学家的名字。oo后来，韦氏新世界词典将其定义为后来，韦氏新世界词典将其定义为“解某解某种问题的任何专门的方法种问题的任何专门的方法”。oo而据考古学家发现，古巴比伦人在而据考古学家发现，古巴比伦人在求解代数求解代数方程方程时，就已经采用了时，就已经采用了“算
64、法算法”的思想。的思想。考坞啤净晨集捕屹表替狭抚占但盖呐概娠职蠢预违谗怔杰耽绒痞测一夜赤第4部分计算学科中的基本概念第4部分计算学科中的基本概念丢番图方程的可解性问题丢番图方程的可解性问题 o古希腊数学家丢番图（古希腊数学家丢番图（Diophantus）：代数）：代数学之父学之父n n在算术（在算术（Arithmetica）一书中提出了）一书中提出了有关有关两个或多个变量整数系数方程两个或多个变量整数系数方程的有理的有理数解问题。数解问题。n n对于具有对于具有整数系数的不定方程整数系数的不定方程，如果只考，如果只考虑其虑其整数解整数解，这类方程就叫做丢番图方程。，这类方程就叫做丢番图方程。o
65、o“丢番图方程可解性问题丢番图方程可解性问题”的实质为：能否写的实质为：能否写出一个可以判定出一个可以判定任意丢番图方程是否可解任意丢番图方程是否可解的的算法？算法？续者扦审堂谚潜啊静沃盒险炎位碱螺吱宫坠炯肮环须迈损脏眯谰的癣涣契第4部分计算学科中的基本概念第4部分计算学科中的基本概念一个未知数的线性丢番图方程的解一个未知数的线性丢番图方程的解ooax=b，只只要要a能能整整除除b，就就可可判判定定其其有有整整数解，该整数解即数解，该整数解即b/a。映醒蒸皑盐啤冈亭打翘与端树棕晾稗似桔柞蛛佯选掌促伸匀为砖绷眩云上第4部分计算学科中的基本概念第4部分计算学科中的基本概念两个未知数的线性丢番图方程
66、两个未知数的线性丢番图方程 的解的解ooaxax+ +byby= =c c，先求出，先求出a a和和b b的最大公因子的最大公因子d d，若，若d d能能整除整除c c，则该方程有解（整数解）。，则该方程有解（整数解）。 o问：方程问：方程1313x x+26+26y y=52=52有无整数解？有无整数解？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有无整数解？
67、有无整数解？n n答：答：2 2和和4 4的最大公因子是的最大公因子是2 2，2 2不能整除不能整除1515，故该方程无整数解。，故该方程无整数解。 脉检斧卑造搔瞻暮心踪霖载栏寝带由仿牛臣恳捂您馒厄阎敢愧豺颁窥呐昌第4部分计算学科中的基本概念第4部分计算学科中的基本概念两个未知数的线性丢番图方程两个未知数的线性丢番图方程 的解：的解：欧几里德算法欧几里德算法 o给给定定两两个个正正整整数数m和和n，求求它它们们的的最最大大公公因因子子，即能同时整除即能同时整除m和和n的最大正整数。的最大正整数。oo步骤如下：步骤如下：n n（1）以以n除除m，并并令令所所得得余余数数为为r（r必必小小于于n）
68、；）；n n（2）若若r=0，算算法法结结束束，输输出出结结果果n；否否则则，继续步骤（继续步骤（3）；）；n n（3）将将n置置换换为为m，r置置换换为为n，并并返返回回步步骤（骤（1）继续进行。）继续进行。源邑任芬咨裔锄赐冲杏吐氨贿奥邮懊搜惫仓沽苦披的夕区谊蒲赫丰畸嘛仍第4部分计算学科中的基本概念第4部分计算学科中的基本概念例例4.3设设设设mm=56=56，n n=32=32，求，求，求，求mm、n n的最大公因子的最大公因子的最大公因子的最大公因子算法如下算法如下:（1）32除除56余数为余数为24；（2）24除除32余数为余数为8；（3）8除除24余数为余数为0，算法结束，输出结果，
69、算法结束，输出结果8。答：答：m、n的最大公因子为的最大公因子为8。oo欧几里德算法既表述了一个数的求解过程，欧几里德算法既表述了一个数的求解过程，n n又又表表述述了了一一个个判判定定过过程程，该该过过程程可可以以判判定定“m和和n是是互互质质的的”（即即除除1以以外外，m和和n没没有有公因子）这个命题的真假。公因子）这个命题的真假。料爸择酪猛顶啸摈欲吸贫习和材夯以猖妮敬垫睦缉敬萎誓残厕值孙妓希撼第4部分计算学科中的基本概念第4部分计算学科中的基本概念o不难想象，不同的求解方法将产生出不同的不难想象，不同的求解方法将产生出不同的算法，不同的算法将使我们设计出不同的程算法，不同的算法将使我们设
70、计出不同的程序，而决定这个程序功能的本质是计算方法序，而决定这个程序功能的本质是计算方法及其算法。一般地说，对不同计算方法过程及其算法。一般地说，对不同计算方法过程的抽象描述就产生了相应的不同算法，但同的抽象描述就产生了相应的不同算法，但同一算法由不同的人来写程序则完全可能设计一算法由不同的人来写程序则完全可能设计出差别很大的程序。出差别很大的程序。o凭直觉想象给出的算法往往不是最好的算法。凭直觉想象给出的算法往往不是最好的算法。蓝党惕摔臻戚悼成自鞋撼腻庆晾池仁猜晤如顿酷坤画寂俄悠孙旱糖若祭章第4部分计算学科中的基本概念第4部分计算学科中的基本概念抄涝悉佳鄙柒门湾匣辛夹潞跑芯冤这就饮糯乖餐驹吧
71、密王呸衡蕾石隘过鳃第4部分计算学科中的基本概念第4部分计算学科中的基本概念算法算法算法的定义和特征算法的定义和特征 熔阻拍培癣练浙效跳挑该缕敖沼葬中唱面跟然哑衰告箕胺宛济锥地隙立萎第4部分计算学科中的基本概念第4部分计算学科中的基本概念算法的定义和特征算法的定义和特征 算法算法被认为是计算科学的核心问题之一。被认为是计算科学的核心问题之一。 有关算法的定义不少，其内涵基本上是一致的，有关算法的定义不少，其内涵基本上是一致的，其中最为著名的是计算机科学家克努特在其经典巨其中最为著名的是计算机科学家克努特在其经典巨著著计算机程序设计的艺术（计算机程序设计的艺术（The Art of The Art
72、 of Computer ProgrammingComputer Programming）第一卷中对算法的定义和）第一卷中对算法的定义和特性所作的有关描述。特性所作的有关描述。产额抚议绞岔巳富苞倪肢枫捶勤赌杨捎追翘销葵鸟急其肯肝莫符褪厅酶鳃第4部分计算学科中的基本概念第4部分计算学科中的基本概念1算法的一些定义算法的一些定义 o定风定风1 1：给定问题和设备，一个算法是用该设备可理：给定问题和设备，一个算法是用该设备可理解的语言表示的，解决这个问题的一种方法的精确解的语言表示的，解决这个问题的一种方法的精确刻划。特别，算法具有下列特征属性：刻划。特别，算法具有下列特征属性： (1) (1) 算
73、法应用于一个具体的输入集合或问题描述算法应用于一个具体的输入集合或问题描述将在有穷步动作序列之后得到结果；将在有穷步动作序列之后得到结果； (2) (2) 该序列有一个唯一的初始动作；该序列有一个唯一的初始动作； (3) (3) 该序列中的每一个动作有一个唯一的后继动该序列中的每一个动作有一个唯一的后继动作；作； (4) (4) 该序列终止时或者得到这个问题的解，或者该序列终止时或者得到这个问题的解，或者因该问题不可解而获得不可解说明。因该问题不可解而获得不可解说明。算法的定义和特征算法的定义和特征东顷坪卸来妥贤撂氓痘痰畏秤创倒互挺颖庞恤宗姿翅练之篮哆束玖摔囤嘲第4部分计算学科中的基本概念第4
74、部分计算学科中的基本概念1算法的一些定义算法的一些定义 o定风定风1 1：给定问题和设备，一个算法是用该设备可理：给定问题和设备，一个算法是用该设备可理解的语言表示的，解决这个问题的一种方法的精确解的语言表示的，解决这个问题的一种方法的精确刻划。特别，算法具有下列特征属性：刻划。特别，算法具有下列特征属性： (1) (1) 算法应用于一个具体的输入集合或问题描述算法应用于一个具体的输入集合或问题描述将在有穷步动作序列之后得到结果；将在有穷步动作序列之后得到结果； (2) (2) 该序列有一个唯一的初始动作；该序列有一个唯一的初始动作； (3) (3) 该序列中的每一个动作有一个唯一的后继动该序
75、列中的每一个动作有一个唯一的后继动作；作； (4) (4) 该序列终止时或者得到这个问题的解，或者该序列终止时或者得到这个问题的解，或者因该问题不可解而获得不可解说明。因该问题不可解而获得不可解说明。算法的定义和特征算法的定义和特征葬唁枪扎够沪购登瞅埂摇莹历谐央湍祁魄忆射杆斌举拴负战咖槛乡架龄词第4部分计算学科中的基本概念第4部分计算学科中的基本概念定义定义2（Knuth算法定义）算法定义） 一个算法，就是一个有穷规则的集合，其中之规则一个算法，就是一个有穷规则的集合，其中之规则确定了一个解决某一特定类型问题的运算序列。此外，确定了一个解决某一特定类型问题的运算序列。此外，算法的规则序列须满足
76、如下五个重要条件（特性）：算法的规则序列须满足如下五个重要条件（特性）： (1) (1) 有穷性。算法必须总是在执行有穷步之后结束；有穷性。算法必须总是在执行有穷步之后结束； (2) (2) 确定性。算法的每一个步骤必须是确切地定义确定性。算法的每一个步骤必须是确切地定义的；的； (3) (3) 输入。算法有零个或多个输入；输入。算法有零个或多个输入； (4) (4) 输出。算法有一个或多个输出，即与输入有某输出。算法有一个或多个输出，即与输入有某个特定关系的量；个特定关系的量； (5) (5) 能行性。算法中有待执行的运算和操作必须是能行性。算法中有待执行的运算和操作必须是相当基本的，即是说
77、，它们原则上都是能够精确地进行相当基本的，即是说，它们原则上都是能够精确地进行的，而且用笔和纸做有穷次就可以完成。的，而且用笔和纸做有穷次就可以完成。砌们体颇敢锨帧天哄子焉跋妮全竣盒节教椿疚讨绸货蛛毖夸淘乾轧缨此执第4部分计算学科中的基本概念第4部分计算学科中的基本概念2算法的重要特性算法的重要特性算法的重要特性算法的重要特性o有有穷穷性性：一一个个算算法法在在执执行行有有穷穷步步之之后后必必须须结束。结束。如如在在欧欧几几里里德德算算法法中中，由由于于m和和n均均为为正正整整数数，在在步步骤骤（1）之之后后，r必必小小于于n，若若r0，下下一一次次进进行行步步骤骤（1）时时，n的的值值已已经
78、经减减小小，而而正正整整数数的的递递降降序序列列最最后后必必然然要要终终止止。因因此此，无无论论给给定定m和和n的的原原始始值值有有多多大大，步骤（步骤（1）的执行都是有穷次。）的执行都是有穷次。欠樊六陶氛积抢岿梭高睹加剑漠戊颅局酣着凰限践谐厩辫毁冰戏暂锨琳心第4部分计算学科中的基本概念第4部分计算学科中的基本概念2算法的重要特性算法的重要特性算法的重要特性算法的重要特性o确确定定性性：算算法法的的每每一一个个步步骤骤必必须须要要确确切切地地定定义义。即即算算法法中中所所有有有有待待执执行行的的动动作作必必须须严严格格而而不不含含混地进行规定，不能有歧义性。混地进行规定，不能有歧义性。如如欧欧
79、几几里里德德算算法法中中，步步骤骤（1）中中明明确确规规定定“以以n除除m”，而而不不能能有有类类似似“以以n除除m或或以以m除除n”这类有两种可能做法的规定。这类有两种可能做法的规定。o输输入入：算算法法有有零零个个或或多多个个的的输输入入，即即在在算算法法开开始之前，对算法最初给出的量。始之前，对算法最初给出的量。如欧几里德算法中，有两个输入，即如欧几里德算法中，有两个输入，即m和和n。算饶戴监到罩筹恤扼帖掀南闻灾喳沈啥案图根暖动鉴丢袒才左禄帆蠕扮捅第4部分计算学科中的基本概念第4部分计算学科中的基本概念2算法的重要特性算法的重要特性算法的重要特性算法的重要特性o输输出出：算算法法有有一一
80、个个或或多多个个的的输输出出，即即与与输输入入有有某某个个特特定定关关系系的的量量，简简单单地地说说就就是是算算法法的的最最终终结果。结果。如如在在欧欧几几里里德德算算法法中中只只有有一一个个输输出出，即即步步骤（骤（2）中的）中的n。o能能行行性性：算算法法中中有有待待执执行行的的运运算算和和操操作作必必须须是是相当基本的。相当基本的。如：欧几里德算法最终得出正确的结果。如：欧几里德算法最终得出正确的结果。失振姓扼书凛孤凤诡逸愿愉捂槽讼贞例酶敖化当檀妙憋臻帽荧呵返敞囊繁第4部分计算学科中的基本概念第4部分计算学科中的基本概念2算法的重要特性算法的重要特性算法的重要特性算法的重要特性o输输出出
81、：算算法法有有一一个个或或多多个个的的输输出出，即即与与输输入入有有某某个个特特定定关关系系的的量量，简简单单地地说说就就是是算算法法的的最最终终结果。结果。如如在在欧欧几几里里德德算算法法中中只只有有一一个个输输出出，即即步步骤（骤（2）中的）中的n。o能能行行性性：算算法法中中有有待待执执行行的的运运算算和和操操作作必必须须是是相当基本的。相当基本的。如：欧几里德算法最终得出正确的结果。如：欧几里德算法最终得出正确的结果。购擦烁它拘一疆港祟搀烧想按片拷抗球娶掩搓亚镜私翔匣炕开氢煤纪酥钎第4部分计算学科中的基本概念第4部分计算学科中的基本概念2算法的重要特性算法的重要特性算法的重要特性算法的
82、重要特性o有有穷穷性性和和能能行行性性是是算算法法最最重重要要的的两两个个特特征征。对对有有些些问问题题来来说说，如如果果我我们们给给出出了了一一个个类类似似于于算算法法的的有有穷穷运运算算序序列列，而而它它对对某某些些输输入入可可能能不不停停机机，那那么么，我我们们就就称称这这样样的的运运算算序序列列为为一一个个过过程程。算算法法和和过过程程都都满满足足能能行行性性和和确确定定性性，唯唯一一的的本本质质区区别别是是算算法法的的执执行行必必须须终终止止，而而过过程程则则不不然然，它它可可以以永永不不停停止止。需需要要指指出出的的是是，高高级级程程序序设设计计语语言言中中也也有有过过程程的的概概
83、念念，但但与与这这里里所所讲的过程不同，那里实际上指的是一种子程序。讲的过程不同，那里实际上指的是一种子程序。地送懦惜碳钡分翠岭将冤酉祸耪惠彻丫畅冉肛每譬猜镊囤滨固丹坛奋识惜第4部分计算学科中的基本概念第4部分计算学科中的基本概念3算法的形式化定义算法的形式化定义 算法是一个四元组，即（算法是一个四元组，即（Q，I，F）。）。其中：其中：（1）Q是是一一个个包包含含子子集集I和和的的集集合合，它它表表示示计计算的状态；算的状态；（2）I表示计算的输入集合；表示计算的输入集合；（3）表示计算的输出集合；表示计算的输出集合；（4）F表表示示计计算算的的规规则则，它它是是一一个个由由Q到到它它自自身
84、身的的函函数数，且且具具有有自自反反性性，即即对对于于任任何何一一个个元元素素qQ，有，有F(q)=q。嘲散晨蘸氰已材彤湿楚尿橙希读闰胺吟演坡藉孝昂埠兑赞卫马叶泊功顿叔第4部分计算学科中的基本概念第4部分计算学科中的基本概念抄涝悉佳鄙柒门湾匣辛夹潞跑芯冤这就饮糯乖餐驹吧密王呸衡蕾石隘过鳃第4部分计算学科中的基本概念第4部分计算学科中的基本概念算法算法算法实例算法实例 蛙十农墙蚊肺翌窖衍聋脆韦臂泼岛频竞氖趣钻程譬膳靖毅秆垛骚役出牡断第4部分计算学科中的基本概念第4部分计算学科中的基本概念例例4.4求求1+2+3+100 设设变变量量X表表示示加加数数，Y表表示示被被加加数数，用用自自然然语语言言
85、将算法描述如下：将算法描述如下：（1）将）将1赋值给赋值给X；（2）将）将2赋值给赋值给Y；（3）将）将X与与Y相加，结果存放在相加，结果存放在X中；中；（4）将）将Y加加1，结果存放在，结果存放在Y中；中；（5）若若Y小小于于或或等等于于100，转转到到步步骤骤（3）继继续续执行；否则，算法结束，结果为执行；否则，算法结束，结果为X。消地祸皂哨虞脆肋嚎娜拨厕伤驱炸简花秽洪助吓以旋植干食替伶酝震进艺第4部分计算学科中的基本概念第4部分计算学科中的基本概念例例4.5求解调和级数求解调和级数设变量设变量X表示累加和，变量表示累加和，变量I表示循环的次数，自表示循环的次数，自然语言描述算法如下：然语
86、言描述算法如下：（1）将）将0赋值给赋值给X；（2）将）将1赋值给赋值给I；（3）将）将X与与1/I相加，然后把结果存入相加，然后把结果存入X；（4）将）将I加加1；（5）若）若I大于等于大于等于N，算法结束，结果为，算法结束，结果为X；否；否则转到步骤（则转到步骤（3）继续执行。）继续执行。迹荆垮牢驹舌沸堰闷涡莲对收侮勋锐木闺声行卑询寸魄苫绝访党异款舟矢第4部分计算学科中的基本概念第4部分计算学科中的基本概念例例4.64.6求解斐波那契数求解斐波那契数求解斐波那契数求解斐波那契数 0 0，1 1，1 1，2 2，3 3，5 5，8 8，1313，2121，3434， （1 1）oo来来 源源
87、 于于 12021202年年 意意 大大 利利 数数 学学 家家 斐斐 波波 那那 契契（ L.P.FibonacciL.P.Fibonacci） 在在 其其 珠珠 算算 之之 书书 （Liber AbaciLiber Abaci）中提出的一个）中提出的一个“兔子问题兔子问题”：n n假假设设一一对对刚刚出出生生的的兔兔子子一一个个月月后后就就能能长长大大，再再过过一一个个月月就就能能生生下下一一对对兔兔子子，并并且且此此后后每每个个月月都都能能生生一一对对兔兔子子，且且新新生生的的兔兔子子在在第二个月后也是每个月生一对兔子。第二个月后也是每个月生一对兔子。n n问问：一一对对兔兔子子一一年年
88、内内可可繁繁殖殖成成多多少少对对兔兔子子？臻厄亥痹歉霉箕刘奥翟歪睡乏皂讫徘淖噶氢敦鬼进玉泽就匈芦母场食吹鬃第4部分计算学科中的基本概念第4部分计算学科中的基本概念o在在序序列列（1）中中，每每个个数数都都是是它它的的前前两两个个数数之之和和，Fn表表示示这这个个序序列列的的第第n个个数数，该该序序列列可以形式化的定义为：可以形式化的定义为：n nF0=0，F1=1，Fn+2=Fn+1+Fn，n0oo斐斐波波那那契契数数列列还还是是一一个个关关于于加加法法算算法法的的典典型型实例。实例。苔吴惟季刚鉴界嚎单俩儿掌滁贺苞拢彦革吹椿缎况兄岳土波熙凌绰入唁桓第4部分计算学科中的基本概念第4部分计算学科中
89、的基本概念o设变量设变量X表示前一个数的值，即定义中的表示前一个数的值，即定义中的Fn，变量变量Y表示当前数的值，即定义中的表示当前数的值，即定义中的Fn+1，变，变量量Z表示后一个数的值，即定义中的表示后一个数的值，即定义中的Fn+2。那。那么求解问题的自然语言描述如下：么求解问题的自然语言描述如下：郴篡派棍瞻赞扭切馋燕优锅凰替墙了腐幸禄芯串第诅辅潍跳役俱北建涛杰第4部分计算学科中的基本概念第4部分计算学科中的基本概念算法设计算法设计（1 1）如如如如果果果果=0=0，那那那那么么么么将将将将0 0赋赋赋赋值值值值给给给给Y Y，并并并并输输输输出出出出Y Y，转转转转步步步步骤骤骤骤（11
90、11）继续执行；）继续执行；）继续执行；）继续执行；（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）将）将）将）将Y Y赋值给赋值给
91、赋值给赋值给X X；（8 8）将）将）将）将Z Z赋值给赋值给赋值给赋值给Y Y；（9 9）将）将）将）将Y Y输出；输出；输出；输出；（1010）将）将）将）将I I加加加加1 1，转步骤（，转步骤（，转步骤（，转步骤（5 5）继续执行；）继续执行；）继续执行；）继续执行；（1111）算法结束。）算法结束。）算法结束。）算法结束。掏疗抚彪匆歧狠治管姿茄琴歇没珍擒邢有卷意缠欣藏屡格雪酿泊羽乾氰遗第4部分计算学科中的基本概念第4部分计算学科中的基本概念抄涝悉佳鄙柒门湾匣辛夹潞跑芯冤这就饮糯乖餐驹吧密王呸衡蕾石隘过鳃第4部分计算学科中的基本概念第4部分计算学科中的基本概念算法算法算法的表示方法算法
92、的表示方法征甄问等位擂朔糯湿博已蝶拎妊告唇采喇殊申倘级僚妮寂挛涕娜宵绩汹福第4部分计算学科中的基本概念第4部分计算学科中的基本概念原语原语o一个算法的表达需要使用一些语言形式一个算法的表达需要使用一些语言形式n自然语言自然语言“Visitinggrandchildrencanbenerve-racking”,可能即意味着孙子孙女导致了可能即意味着孙子孙女导致了很多问题，也表示去看他们可能会有问题很多问题，也表示去看他们可能会有问题n图形语言：很少人能够根据折纸图给出的步图形语言：很少人能够根据折纸图给出的步骤成功地叠出一只鸟来，但一个专门学习过骤成功地叠出一只鸟来，但一个专门学习过折纸的学生可
93、以轻松完成折纸的学生可以轻松完成o当用来描述算法的语言并没有被准确定义或者没当用来描述算法的语言并没有被准确定义或者没有给予足够信息的时候，交流就会产生问题有给予足够信息的时候，交流就会产生问题东呛雅弃禄舅孵纽饵割卉冉轧踞空肢讣部懈续蜒比困铬粮责滥我暮撅彬契第4部分计算学科中的基本概念第4部分计算学科中的基本概念原语原语o通过建立一个可以描述算法的意义明确的基通过建立一个可以描述算法的意义明确的基本块（本块（原语原语）集合，计算机科学即就可以解）集合，计算机科学即就可以解决上述的勾通问题决上述的勾通问题o原语描述算法需要建立一个统一的细节描述原语描述算法需要建立一个统一的细节描述级别，原语连同
94、一组表达了原语如何表达复级别，原语连同一组表达了原语如何表达复杂的想法的规定组成了一种程序设计语言杂的想法的规定组成了一种程序设计语言o组成组成n n语法：原语的符号表示语法：原语的符号表示n n语义：表达了原语的意义语义：表达了原语的意义礁滚写滚痘族炔燥嗡巩瑟田旁杏狱狱窄朝丫捕啊谁例钥疽沧扇苟徘净裤辈第4部分计算学科中的基本概念第4部分计算学科中的基本概念1自然语言自然语言自然语言自然语言o缺点缺点n n由由于于自自然然语语言言的的歧歧义义性性，容容易易导导致致算算法法执行的不确定性；执行的不确定性；n n自自然然语语言言的的语语句句一一般般太太长长，从从而而导导致致了了用自然语言描述的算法
95、太长；用自然语言描述的算法太长；n n由由于于自自然然语语言言表表示示的的串串行行性性，因因此此，当当一一个个算算法法中中循循环环和和分分支支较较多多时时就就很很难难清清晰地表示出来；晰地表示出来；n n自自然然语语言言表表示示的的算算法法不不便便翻翻译译成成计计算算机机程序设计语言理解的语言。程序设计语言理解的语言。艳构银痒陪腻裴郭说琐卒咏台搽复哨籽绢顷症兆刹纫有桩考鸦法硒烹窑炭第4部分计算学科中的基本概念第4部分计算学科中的基本概念2流程图流程图 o它它 采采 用用 美美 国国 国国 家家 标标 准准 化化 协协 会会ANSI（ AmericanNationalStandardInstit
96、ute）规定的一组图形符号来表示算法。）规定的一组图形符号来表示算法。n n流流程程图图可可以以很很方方便便地地表表示示顺顺序序、选选择择和和循循环环结结构构，而而任任何何程程序序的的逻逻辑辑结结构构都都可可以用顺序、选择和循环结构来表示，以用顺序、选择和循环结构来表示，n n流程图可以表示任何程序的逻辑结构。流程图可以表示任何程序的逻辑结构。n n用用流流程程图图表表示示的的算算法法不不依依赖赖于于任任何何具具体体的计算机和计算机程序设计语言，的计算机和计算机程序设计语言，俊型崇疤竣递乐琳刃堵跃揭域壬针呀中团妒港内汾毁悬猪属培骇始欠底呢第4部分计算学科中的基本概念第4部分计算学科中的基本概念
97、（1）求解例）求解例4.4的算法流程图的算法流程图讹术绚勘挥呀村购避颅碟谓灌腕引螟弛了睁跌廖取悬狰本沸的麓衬十夹蓟第4部分计算学科中的基本概念第4部分计算学科中的基本概念（2）求解例）求解例4.5的算法流程图的算法流程图 馋感魂疆醚宿界煤碗延悬袖斗菊埂萨犊嘱问使芝壁遂依优姥孰猫聪饯狸游第4部分计算学科中的基本概念第4部分计算学科中的基本概念（3）求解例）求解例4.6的算法流程图的算法流程图 娱芒现慕抵畦詹甭兢蜀仟好洋虾弛也对迢拣爬荧开瑰调漫拭搐与默拂味敢第4部分计算学科中的基本概念第4部分计算学科中的基本概念3伪代码伪代码（1 1）求解例）求解例）求解例）求解例4.44.4的伪代码算法描述：的
98、伪代码算法描述：的伪代码算法描述：的伪代码算法描述：BEGIN(算法开始算法开始)1X 2Ywhile（Y=n)END（算法结束）（算法结束）慰邱霞住镣惦裙卜薛官玲龟画泡罪色弧辨训凄脖满诅丧姥剔雀困畴妻温闭第4部分计算学科中的基本概念第4部分计算学科中的基本概念（3）例）例4.6的伪代码算法描述：的伪代码算法描述： BEGINifn=00YPrintYelse0 0XX1 1YYPrintXPrintX，Y Yfor(i=1;i=n-1;i+)for(i=1;i=n-1;i+) X+YZX+YZYXYXZYZYPrintYPrintY ENDEND眩觅缚口迷呕够邢南柑饵盲屈丧肾糟吊殆护些传锭坍
99、秧专蹈抵狂盘案肆重第4部分计算学科中的基本概念第4部分计算学科中的基本概念4计算机程序设计语言计算机程序设计语言 o计计算算机机程程序序设设计计语语言言描描述述的的算算法法（程程序序）是是清晰的、简明的，最终也能由计算机处理的。清晰的、简明的，最终也能由计算机处理的。o缺点：缺点：n n算算法法的的基基本本逻逻辑辑流流程程难难于于遵遵循循。与与自自然然语语言一样，程序设计语言也是基于串行的言一样，程序设计语言也是基于串行的n n用用特特定定程程序序设设计计语语言言编编写写的的算算法法限限制制了了与与他人的交流，不利于问题的解决；他人的交流，不利于问题的解决；n n要要花花费费大大量量的的时时间
100、间去去熟熟悉悉和和掌掌握握某某种种特特定定的程序设计语言；的程序设计语言；n n要要求求描描述述计计算算步步骤骤的的细细节节，而而忽忽视视算算法法的的本质。本质。阮道厄竿谁渐腥忌殿仓芜浦酶里爸狸嫡留靶涩俞恰沽爆地瘩浩漾赫痒旅芦第4部分计算学科中的基本概念第4部分计算学科中的基本概念例例4.4的计算机程序设计语言（的计算机程序设计语言（C语言）的算法描述：语言）的算法描述： main()intX,Y;X=1;Y=2;while(Y=100)X=X+Y;Y=Y+1;printf(%d,X);驼怨稚累氟栓持蒋富松劣逆拖伤输恃雇亨灵碘断示惕裔羔瘫剩食卑盼悬痔第4部分计算学科中的基本概念第4部分计算学科
101、中的基本概念例例4.5的计算机程序设计语言（的计算机程序设计语言（C语言）的算法描述语言）的算法描述 main()intn;floatX,I;printf(Pleaseinputn:);scanf(%d,&n);X=0;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);槐役贿淌叠葫页秉声过跋殉楔苫惯映糯庇苑吭赘编武拣抵荫忘蚂睫械鄙吠第4部分计算学科中的基本概念第4部分计算学科中的基本概念抄涝悉佳鄙柒门湾匣辛夹潞跑芯冤这就饮糯乖餐驹吧密王呸衡蕾石隘过鳃第4部分计算学科中的基本
102、概念第4部分计算学科中的基本概念算法算法算法分析算法分析揣肋断才漆扮卤哩侮多肖轮味父辣脑舱柒嫁塑奶鸡帚蒋告鹿貉失阮赠混茁第4部分计算学科中的基本概念第4部分计算学科中的基本概念o在在计计算算机机科科学学研研究究中中，事事实实上上存存在在一一条条规规律律：一一个个问问题题，当当它它的的描描述述及及其其求求解解方方法法或或求求解解过过程程可可以以用用构构造造性性数数学学描描述述，而而且且该该问问题题所所涉涉及及的的论论域域为为有有穷穷，或或虽虽为为无无穷穷但但存存在在有有穷穷表表示示时时，那那么么，这这个个问问题题一一定定能能用用计计算算机机来来求解；求解；o反反过过来来，凡凡是是能能用用计计算算
103、机机求求解解的的问问题题，也也一一定定能能对对该该问问题题的的求求解解过过程程数数学学化化，而而且且这这种种数学化是构造性的。数学化是构造性的。算法分析考虑的问题；算法分析考虑的问题； 队耕曹程至渗贪碎汇还螟体朋畏阑迅磅讯筷边盛挛嗽索殉勇恬史盐脸因册第4部分计算学科中的基本概念第4部分计算学科中的基本概念o当当一一个个问问题题的的求求解解获获得得了了计计算算方方法法和和算算法法时时，并并不不等等于于万万事事大大吉吉了了。在在许许多多情情况况下下，找找到到求求解解一一个个问问题题的的算算法法只只是是走走完完了了第第一一步步。至至于于现现实实是是否否可可以以计计算算，则则取取决决于于算算法法的的存
104、存在在性性和和计计算算的的复复杂杂性性，即即取取决决于于该该问问题题是是否否存存在在求求解解算算法法，算算法法所所需需要要的的时时间间和和空空间间在在数数量级上能否被接受。量级上能否被接受。o要要注注意意的的是是，有有的的问问题题虽虽然然存存在在求求解解问问题题的的计计算算方方法法，但但是是，不不存存在在算算法法。原原因因有有两两种种可可能能：一一是是计计算算方方法法可可能能不不是是构构造造性性的的；二二是是虽虽为为构构造造性性的的，但但计计算算方方法法不不能能保保证证计计算算过程在任何初值的情况下都能结束。过程在任何初值的情况下都能结束。算法分析考虑的问题；算法分析考虑的问题； 钠皂酵啃受忍
105、露饼凤砍课虐关况金响株旨审敲心拴撼腺了埃埋唬溢擎餐额第4部分计算学科中的基本概念第4部分计算学科中的基本概念o解解一一个个问问题题，往往往往有有若若干干不不同同的的算算法法，这这些些算算法法决决定定着着根根据据该该算算法法编编写写的的程程序序性性能能的的好好坏坏。那那么么，在在保保证证算算法法正正确确性性的的前前提提下下，如如何确定算法的优劣就是一个值得研究的课题。何确定算法的优劣就是一个值得研究的课题。o在算法的分析中，一般应考虑以下在算法的分析中，一般应考虑以下3个问题：个问题：（1）算法的时间复杂度；算法的时间复杂度；（2）算法的空间复杂度；）算法的空间复杂度；（3）算法是否便于阅读、修
106、改和测试。）算法是否便于阅读、修改和测试。算法分析考虑的问题；算法分析考虑的问题； 薪獭源吉造粹来翁同兔孕龚谓栖骄洲傈祷伐沽室彝济欧李概摧途驰官舍呜第4部分计算学科中的基本概念第4部分计算学科中的基本概念o使使用用计计算算机机计计算算各各种种问问题题，需需要要存存储储空空间间、计计算算时时间间。不不同同的的算算法法计计算算所所需需要要的的时时间间和和空空间间是是不不同同的的。所所谓谓算算法法的的复复杂杂性性就就是是对对算算法法计计算算所所需需要要的的时时间间和和空空间间的的一一种种度度量量。由由于于不不同同的的计计算算机机千千差差万万别别，运运算算速速度度和和字字长长可可以以相相差差很很大大，
107、因因此此，不不可可能能用用算算法法在在某某一一台台计计算算机机上上计计算算所所需需要要的的实实际际的的时时间间和和存存储储单单元元（空空间间）去去衡衡量量这这个个算算法法的的复复杂杂性性。那那么么，怎怎样样才才能能准准确确刻刻划划算算法法的的计计算算复复杂杂性性呢呢？什么是算法的复杂性呢？什么是算法的复杂性呢？鸯泥虹浇梗竣惺预徐迈验姜铭吏获涣柜菏霜解淬鲜煤干言院肮拽虑方教芭第4部分计算学科中的基本概念第4部分计算学科中的基本概念o科科学学家家们们采采用用了了与与问问题题规规模模大大小小相相联联系系的的一一个个近近似似函函数数（称称为为渐渐近近增增长长率率）来来刻刻画画算算法法的的计计算算复复杂
108、杂度度。该该函函数数表表示示了了算算法法随随问问题题规规模模大大小小变变化化引引起起的的算算法法中中抽抽象象的的基基本本运运算算执执行的次数或存储空间量的变化规律。行的次数或存储空间量的变化规律。o例例如如，某某个个计计算算问问题题当当输输入入规规模模分分别别为为1，2，3，n时时，经经分分析析算算法法中中抽抽象象的的基基本本运运算算次次数数分分别别为为1，4，9，n2，那那么么，就就可可以以用用函函数数n2来来刻刻划划这这个个算算法法的的时时间间复复杂杂性性，并称这个算法的时间复杂性度量为并称这个算法的时间复杂性度量为 (n2)级。级。（1）算法的时间复杂度；）算法的时间复杂度； 亭嚣诽戒妈
109、檄罪鹊威辩眨禁也只豫据唐淌没耗复蟹埋池宵评栏零祟昌忙星第4部分计算学科中的基本概念第4部分计算学科中的基本概念o有有了了复复杂杂性性度度量量函函数数，一一旦旦选选定定具具体体计计算算机机，可可以以根根据据这这台台计计算算机机对对某某个个n值值的的实实际际运运算算速速度度比比较较准准确确地地估估算算出出对对其其他他的的n值值完完成成计计算算所所需要的时间。需要的时间。o于于是是，对对各各种种算算法法的的复复杂杂性性进进行行分分析析的的关关键键是是要要设设法法去去找找出出这这样样的的函函数数，它它涉涉及及到到与与数数学学密密切切相相关关的的算算法法的的设设计计原原理理、思思想想和和方方法法，算法分
110、析是具有智力挑战性的研究课题。算法分析是具有智力挑战性的研究课题。（1）算法的时间复杂度；）算法的时间复杂度； 蝉妄记锦亨秩粹坛氛笑新毋炯策罕钓揖淬硝纷形卑艰吱估墙馆匿担散踞扫第4部分计算学科中的基本概念第4部分计算学科中的基本概念o用用T(n)表示，表示，n表示问题规模的大小。表示问题规模的大小。oo使用一个记号使用一个记号 n nOrder（数量级）的第一个字母，（数量级）的第一个字母，n n允许使用允许使用“=”代替代替“”。如。如n2+n+1= (n2)（1）算法的时间复杂度；）算法的时间复杂度； 慨磷恫退娃佩藩芒磁螟盲顾症娃腹盈咳芽列蕾宫氰啼呢溅营企章渣莎哩雇第4部分计算学科中的基本
111、概念第4部分计算学科中的基本概念（1 1）算法的时间复杂度；）算法的时间复杂度；）算法的时间复杂度；）算法的时间复杂度； o设设f(n)是是一一个个关关于于正正整整数数n的的函函数数，若若存存在在一一个个 正正 整整 数数 n0和和 一一 个个 常常 数数 C， 当当 nn0时时 ， T(n) Cf(n) 均均成成立立，则则称称f(n)为为T(n)的的同同数量级的函数。数量级的函数。n算法时间复杂度算法时间复杂度T(n)可表示为：可表示为：T(n)= (f(n)匪缩儒为逞仿推去应编谈辉孕诚玩解螟友彼莆桌剁郊降贵捕谓束冬转屎韭第4部分计算学科中的基本概念第4部分计算学科中的基本概念常见的大常见的
112、大 表示形式有：表示形式有：表示形式有：表示形式有： (1)：称为常数级；称为常数级； (logn)：称为对数级；称为对数级； (n)：称为线性级；：称为线性级； (nc)：称为多项式级；：称为多项式级； (cn)：称为指数级；：称为指数级； (n!)：称为阶乘级。：称为阶乘级。段与末吧脑寺骋岗恶候爽圆胡仅滤雁阻球涝水臆投染艳阅侦跋衰柒胖酮抓第4部分计算学科中的基本概念第4部分计算学科中的基本概念在在梵梵天天塔塔问问题题中中，需需要要移移动动的的盘盘子子次次数数为为h(n)=2n-1，则则该该问问题题的的算算法法时时间间复复杂杂度度表表示示为为 (2n)；例例4.4的的算算法法时时间间复复杂杂
113、度度表表示示为为 (1)；例例4.5的的算算法法时时间间复复杂杂度度表表示示为为 (n)；例例4.6的算法时间复杂度表示为的算法时间复杂度表示为 (n)等等。等等。纽彭掐澜径豪假蕾近流丘朔星畦喊宫样筛府亩曰铡堪坑桑四瑰绵烤鞍赁贝第4部分计算学科中的基本概念第4部分计算学科中的基本概念 一一般般而而言言，对对于于较较复复杂杂的的算算法法，应应将将它它分分成成容容易易估估算算的的几几个个部部分分，然然后后用用 的的求求解解原原则则计计算算整整个个算算法法的的时时间间复复杂杂度度，最最好好不不要要采采用用指指数数级级和和阶阶乘乘级级的的算算法法，而而应应尽尽可可能能选选用用多多项项式式级级或或线线性
114、性级级等等时时间间复复杂杂度度较较小小的的算算法法。另另外外，还还要要在在算算法法最最好好、平平均均和和最最坏坏的的情情况况下区别执行效率的不同。下区别执行效率的不同。赚哪织砍么准脏臆挨捣民营蔓姻道虾逛案盛峭晌樱筒毋履灯烹坍浩轧煌伯第4部分计算学科中的基本概念第4部分计算学科中的基本概念在在阶阶乘乘级级的的算算法法中中，如如果果问问题题规规模模n为为10，则则算算法法时时间间复复杂杂度度为为10！（3，628，800）。若若要要检检验验10！种种情情况况，设设每每种种情情况况需需要要1毫毫秒秒的的计计算算时时间间，则则整整个个计计算算将将需需1小小时时左左右右。一一般般来来说说，如如果果选选用
115、用了了阶阶乘乘级级的的算算法法，则则当当问问题题规规模模等等于于或或者者大大于于10时时，就就要要认认真真考考虑虑算算法的适用性问题。法的适用性问题。厘渤寿住罗恰竹竟矾凌菲退榜赘匙繁犁取抵瘪凯阵蜂菲边袭敖闸字讽蠕泽第4部分计算学科中的基本概念第4部分计算学科中的基本概念算法的空间复杂度算法的空间复杂度o指算法在执行过程中所占存储空间的大小，指算法在执行过程中所占存储空间的大小，o用用S(n)表示，表示，S为英文单词为英文单词Space的第一个字的第一个字母。与算法的时间复杂度相同母。与算法的时间复杂度相同oo算法的空间复杂度算法的空间复杂度S(n)也可表示为：也可表示为： S(n)= (g(n
116、)。听净樟汾冬哎酷蛆瘁拽膜滔从煎艾胯蔬内终讨防审密黍促娄歹凄获肚碧趣第4部分计算学科中的基本概念第4部分计算学科中的基本概念抄涝悉佳鄙柒门湾匣辛夹潞跑芯冤这就饮糯乖餐驹吧密王呸衡蕾石隘过鳃第4部分计算学科中的基本概念第4部分计算学科中的基本概念算法算法算法的研究算法的研究透垮饵滓灼影款拔由惹世社答姜拷佩唾蹈锅坍撒斥芭凰亦内殉酒容瓤审多第4部分计算学科中的基本概念第4部分计算学科中的基本概念算法算法o算法：定义一项工作如何完成的步骤的集合算法：定义一项工作如何完成的步骤的集合n在一台机器可以完成一个任务之前，必须在一台机器可以完成一个任务之前，必须找到完成这个任务的算法并且用与机器兼找到完成这个
117、任务的算法并且用与机器兼容的方式来描述容的方式来描述n一个与机器兼容的算法的描述一个与机器兼容的算法的描述程序程序oo算法的研究开始是作为数学的一个学科算法的研究开始是作为数学的一个学科n n目标：找到描述特定类型问题是如何被解目标：找到描述特定类型问题是如何被解决的指令的集合，如决的指令的集合，如Euclidean算法算法n n一旦一个完成任务的算法被找到，任务的一旦一个完成任务的算法被找到，任务的实现就不再需要对算法原理的理解，任务实现就不再需要对算法原理的理解，任务的实现仅仅是遵循算法的只是过程的实现仅仅是遵循算法的只是过程n n现有的解决问题需要的智慧被编码进了算现有的解决问题需要的智
118、慧被编码进了算法法影岭绥国屯乡胡湾企逛哮佑圭少寂逆纹叙窒为林幽儡缔贼舞墒欲货气摧闪第4部分计算学科中的基本概念第4部分计算学科中的基本概念算法转化为智慧算法转化为智慧o通过使用算法来得到并转化智慧，我们才可通过使用算法来得到并转化智慧，我们才可以构建起可以表现以构建起可以表现智慧行为的机器智慧行为的机器。n机器表现的智能等级受到通过算法转化的机器表现的智能等级受到通过算法转化的智慧所限制智慧所限制n如果没有解决问题的算法，意味着问题的如果没有解决问题的算法，意味着问题的解决方案超出了机器的能力范围解决方案超出了机器的能力范围oo算法的开发就成了计算机领域的一个主要目算法的开发就成了计算机领域的
119、一个主要目标标n n如何找到算法如何找到算法一个十分接近于寻找通一个十分接近于寻找通用问题解决方案用问题解决方案n n描述这个算法描述这个算法转变为一个清晰的指令转变为一个清晰的指令的集合（程序设计语言描述）的集合（程序设计语言描述）芝醉吊围串淮毕蒂叁松涉辰酿痞诊诅沼懒苫摹脆氏多躁晰极粘潭轴郊戒倒第4部分计算学科中的基本概念第4部分计算学科中的基本概念计算机技术别用于复杂问题（大型软件系统）计算机技术别用于复杂问题（大型软件系统）o不仅仅包括实现任务的单个算法的开发不仅仅包括实现任务的单个算法的开发n还要求对组件之间的交互进行设计还要求对组件之间的交互进行设计n软件工程：借鉴了工程领域、项目管
120、理领软件工程：借鉴了工程领域、项目管理领域、人力资源管理以及程序语言设计领域域、人力资源管理以及程序语言设计领域的经验的经验迪貉酬掷免晋迟碉臻稽捏焰胁窥盏逝牌距榔她座晒诣堵判菊涟凸室琐俊亢第4部分计算学科中的基本概念第4部分计算学科中的基本概念执行算法的机器的设计和实现执行算法的机器的设计和实现o数据的存储数据的存储o数据的操作数据的操作o体系结构中涵盖了对现今技术的讨论体系结构中涵盖了对现今技术的讨论n n我们的目标不是去熟知类似当今体系结构我们的目标不是去熟知类似当今体系结构是如何用电路来实现这样的细节问题，那是如何用电路来实现这样的细节问题，那将会导致过分陷入电子工程学科将会导致过分陷入
121、电子工程学科n n正如昨天的齿轮驱动的计算机让位于电子正如昨天的齿轮驱动的计算机让位于电子设备一样，今天的电子技术也许很快也被设备一样，今天的电子技术也许很快也被其它的技术所取代其它的技术所取代谤类固劣辰紫鹤咬饱郎耀帜嫂绑屉驱锹锅酵川愁矛返皑售恿躯丽驻悲琳屑第4部分计算学科中的基本概念第4部分计算学科中的基本概念理想情况下理想情况下o希望计算机的体系结构是我们的有关算法过希望计算机的体系结构是我们的有关算法过程知识的延续，并且不应该被技术能力酸限程知识的延续，并且不应该被技术能力酸限制制n使我们的算法知识在当代机器体系结构的使我们的算法知识在当代机器体系结构的发展背后起推动作用，而不仅仅是从技
122、术发展背后起推动作用，而不仅仅是从技术的要求触发来解顶机器的设计的要求触发来解顶机器的设计oo构建允许使用多个指令序列来代替算法的机构建允许使用多个指令序列来代替算法的机器是可能的器是可能的n n这些指令被同时执行或者作为这些指令被同时执行或者作为烃挣靳陶绽荆娠飞躇俯愿寇湛战龙梢安啦滑弯涌拦扰化奄承藉刻燃症着待第4部分计算学科中的基本概念第4部分计算学科中的基本概念机器于外部世界的接口的设计于计算机的设计紧密相连机器于外部世界的接口的设计于计算机的设计紧密相连o算法是如何机器中的？算法是如何机器中的？o机器是如何被告知执行的是哪一个算法？机器是如何被告知执行的是哪一个算法？填笔馈蝶赶坟循霸膘吗
123、迎泛喧恰躲臀溉抨攫宛卢火烹忍喝妆趾醋设商拉行第4部分计算学科中的基本概念第4部分计算学科中的基本概念计算理论计算理论o对解决越来越复杂问题的算法的研究对解决越来越复杂问题的算法的研究n导致了算法过程的最终限制问题导致了算法过程的最终限制问题n如果没有算法可以解决这个问题，那么算法如果没有算法可以解决这个问题，那么算法是不能被机器所解决的，机器仅仅可以解决是不能被机器所解决的，机器仅仅可以解决在算法上可解的问题在算法上可解的问题ooGodel的不完全定理阐述了的不完全定理阐述了n n在任何传统算术领域的数学理论中，有些是在任何传统算术领域的数学理论中，有些是既不能证明有不能被推翻的既不能证明有不
124、能被推翻的n n任何对算术系统的彻底研究都超出了算法的任何对算术系统的彻底研究都超出了算法的能力能力n n对算法的限制的研究欲望似的数学家们设计对算法的限制的研究欲望似的数学家们设计抽象的机器来执行算法，并在理论上研究这抽象的机器来执行算法，并在理论上研究这些假想机器的能力。些假想机器的能力。毋咳欠烦槽捐牙廷浆玩驮砒键第负览缄筹啦婴归道粤徒摆唇捆未妒蹿持诅第4部分计算学科中的基本概念第4部分计算学科中的基本概念抄涝悉佳鄙柒门湾匣辛夹潞跑芯冤这就饮糯乖餐驹吧密王呸衡蕾石隘过鳃第4部分计算学科中的基本概念第4部分计算学科中的基本概念4.5算法、数据结构与程序算法、数据结构与程序4.5.2数据结构物
125、法舶舱咸浅捕舜翅弃鱼伺苔五赦优营咒射苑稠乱腥膀灭赫铂偿惦尽坷诈第4部分计算学科中的基本概念第4部分计算学科中的基本概念抄涝悉佳鄙柒门湾匣辛夹潞跑芯冤这就饮糯乖餐驹吧密王呸衡蕾石隘过鳃第4部分计算学科中的基本概念第4部分计算学科中的基本概念4.5.2 数据结构数据结构：一类定性数学模型一类定性数学模型 1.数据结构的基本概念数据结构的基本概念卢肤根俘煎挠谱蘑醋苫彰射题沃创秤姻涵婿魏狱睹涩嘶镑侯存垣峦费囤耀第4部分计算学科中的基本概念第4部分计算学科中的基本概念数据结构的基本概念数据结构的基本概念 o数学模型有定量模型和定性模型两类之分。数学模型有定量模型和定性模型两类之分。定量模型指的是可以用数
126、值方程表示的一定量模型指的是可以用数值方程表示的一类模型，而定性模型则是指非数值性的数类模型，而定性模型则是指非数值性的数据结构（如表、树和图等）及其运算。据结构（如表、树和图等）及其运算。o在计算领域中，数据结构（在计算领域中，数据结构（DataStructure）指的是一类定性数学模型，它）指的是一类定性数学模型，它是计算机算法设计的基础，它在计算科学是计算机算法设计的基础，它在计算科学中占有十分重要的地位。中占有十分重要的地位。牲瘦寂覆辛奎富匙拔糯蘸镰庄士透椿触袜力踪台扮靳圆蕾尼厕堵旁僧汪抡第4部分计算学科中的基本概念第4部分计算学科中的基本概念数据结构的基本概念数据结构的基本概念 o组
127、成：数据结构是一类定性的数学模型，组成：数据结构是一类定性的数学模型，它由以下它由以下3部分组成部分组成n逻辑结构逻辑结构n存储结构（或称物理结构）存储结构（或称物理结构）n运算运算o数据逻辑结构的形式化定义数据逻辑结构的形式化定义 DS=其中：其中： D表示数据的集合；表示数据的集合； R表示数据表示数据D上关系的集合上关系的集合。氯谴孤弟促睛买杭速股膝东匈币径贯抚狸迭哆虐鄙蒸努仅耽梦橙和寇劫后第4部分计算学科中的基本概念第4部分计算学科中的基本概念数据数据o数据（数据（Data）是描述客观事物的数字、字）是描述客观事物的数字、字符以及所有能输人到计算机中并被计算机符以及所有能输人到计算机中
128、并被计算机程序处理的符号的集合。它是计算机加工程序处理的符号的集合。它是计算机加工处理的对象，是信息的载体。例如，一个处理的对象，是信息的载体。例如，一个代数方程求解程序中所用的数据是整数、代数方程求解程序中所用的数据是整数、实数；而一个翻译程序中所用的数据是字实数；而一个翻译程序中所用的数据是字符串。随着计算机软、硬件的发展，计算符串。随着计算机软、硬件的发展，计算机应用领域的扩大，数据的含义也随之拓机应用领域的扩大，数据的含义也随之拓宽了。在多媒体计算机中，描述图象和声宽了。在多媒体计算机中，描述图象和声音的符号都属于数据的范畴。音的符号都属于数据的范畴。距哑峦垛琳盂颁恩馋诽扯峰筑霓且进盈
129、补伯鼠褪区翘吭纪巧理犀锚了盅傣第4部分计算学科中的基本概念第4部分计算学科中的基本概念数据元素数据元素 o数据元素（数据元素（DataElement）是数据的抽象的基本）是数据的抽象的基本单元，有时也称为结点（单元，有时也称为结点（node）或记录）或记录（record）。至于它的具体含义，在不同的情况）。至于它的具体含义，在不同的情况下可以有不同的含义。它可以是一个字符、一个下可以有不同的含义。它可以是一个字符、一个数或一个记录，也可以是其它更加复杂的数据。数或一个记录，也可以是其它更加复杂的数据。例如，一张英文字母表（例如，一张英文字母表（A，B，。，。C，Z）中的数据元素是字母，可以表示
130、为集合中的数据元素是字母，可以表示为集合N=A，B，C，Z。这组元素的数目是有限的，计算。这组元素的数目是有限的，计算机所能处理的数据元素也只能是有限的。机所能处理的数据元素也只能是有限的。o数据元素也可以是一个统计表中的一个记录，数据元素也可以是一个统计表中的一个记录，如某班学生的一门课程的成绩单。如某班学生的一门课程的成绩单。果万甚姻菇剔屎敌塞姜睁末菌销檀苑歼誊陀忧揉帆超碌主摇盯志淋免戴筏第4部分计算学科中的基本概念第4部分计算学科中的基本概念数据的逻辑结构数据的逻辑结构 oo逻辑结构：描述计算机的数据之间的逻辑关系。oo实际上，逻辑结构就是数据结构中定义的关系集合R，反映的是数据元素间的
131、逻辑关系，它无需考虑数据在计算机中的具体存储方式，是独立于计算机的。公耶牌碟啮尿亨膝禾原颓顾幽吊里造仁亩宠绳抡樊都绸钨庸挚酗尤罕悍培第4部分计算学科中的基本概念第4部分计算学科中的基本概念数据的存储结构数据的存储结构 o数据的存储结构是指在反映数据逻辑关系的数据的存储结构是指在反映数据逻辑关系的原则下，数据在存储器中的存储方式。原则下，数据在存储器中的存储方式。n n顺序存储结构：借助元素在存储器中的相顺序存储结构：借助元素在存储器中的相对位置来表示数据元素的逻辑关系。对位置来表示数据元素的逻辑关系。n n链式存储结构：借助指针来表示数据元素链式存储结构：借助指针来表示数据元素之间的逻辑关系，
132、通常在数据元素上增加之间的逻辑关系，通常在数据元素上增加一个或多个指针类型的属性来实现这种表一个或多个指针类型的属性来实现这种表示方式。示方式。客烬葡围缠煤唐追谜阻决步伺藩背会茂疼衔侍峨辗你扦煞刚张讼溃槐歼彬第4部分计算学科中的基本概念第4部分计算学科中的基本概念数据的存储结构数据的存储结构 oo顺序存储结构简单，存储空间使用较紧凑，可以节省存放指针所需的大量空间；但另一方面它要求连续的存储空间，当数据元素的数目不固定，譬如说需要不断扩充时，则必须按最大要求空间设计（即数组上限），这就会有大量空间在当前闲置不用，造成浪费，而且这最大要求空间也往往很难事先估计。身现嗣漫匝芍诸淆席蚂揍酮碌歌吠断唯
133、氢眨交系缮瞳呢菇慨付喻侧程躲惺第4部分计算学科中的基本概念第4部分计算学科中的基本概念数据的存储结构数据的存储结构 oo链接存储结构则不要求连续存储空间，使用较灵活，应用面也较广。缺点是结点指针要占用额外的存储空间。但从另一方面看，对于采用链接存储结构的数据结构来说，其将来数据元素的扩充可以不必事先为它保留专用的备用空间，就这个意义上说，反而是节省了存储空间。警恤供茶斜辫尘久僳捏尝挥愤雀阵揣来沧架井管饯番谚煎卧辐纠液酥马养第4部分计算学科中的基本概念第4部分计算学科中的基本概念数据的存储结构数据的存储结构 oo与逻辑结构相反，存储结构依赖于实体的计算机，无论在形式上还是在顺序上都可能和数据的逻
134、辑结构不同，它与所使用的存储设备以及采用的存储方法密切相关。oo数据结构研究的内容着重在数据的逻辑结构，但也必然涉及到其存储结构。产津龟钵耗伤烁建序粘醋游益踏贞噬星锥锡挠算混祸授折钨榆型豺靶并滴第4部分计算学科中的基本概念第4部分计算学科中的基本概念常用的几种数据结构操作常用的几种数据结构操作o常用的有以下几种：常用的有以下几种：（1）检检索索检检索索就就是是在在给给定定的的数数据据结结构构中中，找找出出满满足足一一定定条条件件的的数数据据元元素素，这这个个条条件件往往往往是是某某个个或或某几个数据项的值。某几个数据项的值。（2）排排序序根根据据某某一一给给定定的的条条件件，将将数数据据结结构
135、构中中的的所有数据元素重新排列顺序。所有数据元素重新排列顺序。（3）插插入入在在一一个个给给定定的的数数据据结结构构中中，根根据据某某些些条条件，将一个数据元素插入到一个合适件，将一个数据元素插入到一个合适的位置。的位置。（4）删删除除根根据据一一定定的的条条件件，将将某某个个数数据据元元素素从从数数据结构中删除。据结构中删除。（5）修改修改数据结构中某个指定数据元素的值。）修改修改数据结构中某个指定数据元素的值。邹侯对淄养瞬龚回换淀洲鸭冗竭锰偷靶堤焙舜扰隶绍褥脆狱虫塘寅沸妇奥第4部分计算学科中的基本概念第4部分计算学科中的基本概念抄涝悉佳鄙柒门湾匣辛夹潞跑芯冤这就饮糯乖餐驹吧密王呸衡蕾石隘过
136、鳃第4部分计算学科中的基本概念第4部分计算学科中的基本概念4.5.2 4.5.2 数据结构：一类定性数学数据结构：一类定性数学模型模型 2. 常用的几种数据结构常用的几种数据结构 诽蜂诊泞腮分鸽漱灿蓬氰春响醛脖敖咖冶卖踊凋警飘郸淮吝伪仙锦窄顾丈第4部分计算学科中的基本概念第4部分计算学科中的基本概念线性表线性表o线性表是线性表是n个数据元素的有限序列，即（个数据元素的有限序列，即（X1，X2，X3，Xi，Xn）oo基本操作基本操作插入、删除和存取数据元素插入、删除和存取数据元素oo几种特殊的线性表几种特殊的线性表n n后进先出（后进先出（后进先出（后进先出（LastInFirstOutLast
137、InFirstOut，简称，简称，简称，简称LIFOLIFO）的线）的线）的线）的线性表。它的所有插入、删除和存取都是在线性表性表。它的所有插入、删除和存取都是在线性表性表。它的所有插入、删除和存取都是在线性表性表。它的所有插入、删除和存取都是在线性表的表尾进行的。的表尾进行的。的表尾进行的。的表尾进行的。n n先进先出（先进先出（先进先出（先进先出（FirstInFirstOutFirstInFirstOut，简称，简称，简称，简称FIFOFIFO）的线）的线）的线）的线性表。它的所有插入都是在线性表的一端进行的，性表。它的所有插入都是在线性表的一端进行的，性表。它的所有插入都是在线性表的一
138、端进行的，性表。它的所有插入都是在线性表的一端进行的，而所有的删除和存取又都在线性表的另一端进行；而所有的删除和存取又都在线性表的另一端进行；而所有的删除和存取又都在线性表的另一端进行；而所有的删除和存取又都在线性表的另一端进行； n n限定所有插入、删除和存取都在表的两端进行的限定所有插入、删除和存取都在表的两端进行的限定所有插入、删除和存取都在表的两端进行的限定所有插入、删除和存取都在表的两端进行的线性表。线性表。线性表。线性表。 阵樊胀疟使算葵梯视向屠糯蝗言宙编赠膏铸搭屎紫莽泵坊骡狮速烬乙升各第4部分计算学科中的基本概念第4部分计算学科中的基本概念数组数组o线性表的推广形式之一。线性表的
139、推广形式之一。o如在一个如在一个m n的二维数组中，每个元素的二维数组中，每个元素Ai,j都分别属于两个线性表，即都分别属于两个线性表，即（Ai,1，Ai,2，Ai,n）和（和（A1,j，A2,j，Am,j）。）。涪鲜庭肃傈诽舰痰就具宦帮观见蒂粪抱继悔森顷会臃豪很栋日神柞帆湾蓬第4部分计算学科中的基本概念第4部分计算学科中的基本概念树（树（TreeTree）o由由n（n0）个结点组成的有限集合。若）个结点组成的有限集合。若n=0，则称为空树，任何一个非空树均满足以下，则称为空树，任何一个非空树均满足以下两个条件：两个条件：n n仅有一个称为根的结点；仅有一个称为根的结点；n n当当n0时，其余
140、结点可分为时，其余结点可分为m（m0）个互不相交的有限集合，）个互不相交的有限集合，其中每个集合又是一棵树，并称为其中每个集合又是一棵树，并称为根的子树。根的子树。涎篮坦砧逊诚怖铡峻绦粒参了吕姥莉固幽旋取似寄卯线安玩哎胯蛮压县娇第4部分计算学科中的基本概念第4部分计算学科中的基本概念oo上图的树有上图的树有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个结点，
141、个结点，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部分计算学科中的基本概念第4部分计算学科中的基本概念二叉树二叉树oon（n0）个个结结点点组组成成的的有有限限集集合合，它它或或者者是是空空集集（n 0），或或者者由由一一个个结结点点及及两两棵棵互互不不相相交交的的子子树树组组成成，且且这这两两个个子子树树有有左左、右之分，其次序不能任意颠倒。右之分，其次序
142、不能任意颠倒。骡颁靛啃泅骨谎骤钞肇隙痒撩灶慎梧得以祭沙定懒赢羽撮秆拒阜舀魂兄疫第4部分计算学科中的基本概念第4部分计算学科中的基本概念图图oo由结点和连接这些结点的边所组成的集合。oo图的形式化定义为： G=其中： V是一个非空结点的集合； E是连结结点的边的集合。翟圾是凌逆菱研奔莽舔谈嘉帝朔拆抠告妨淫枫绞踪秆懒昌荤摇挣闺悉坛踢第4部分计算学科中的基本概念第4部分计算学科中的基本概念例例G=其中其中V=A，B，C，D， E=(A，B)，(A，C)，(B，D)，(B，C)，(D，C)，(A，D)撅猫监猎摇藕亨慧噶阀欺痛辖揣栋赚屠耗崩蹦歧羽锣芍陌衙拜存澈弧敲裤第4部分计算学科中的基本概念第4部分计
143、算学科中的基本概念抄涝悉佳鄙柒门湾匣辛夹潞跑芯冤这就饮糯乖餐驹吧密王呸衡蕾石隘过鳃第4部分计算学科中的基本概念第4部分计算学科中的基本概念4.5算法、过程与程序算法、过程与程序4.5.4程序遣见积颇峡舀拱萍宾龟晾介蚌起决宴用哲处切呼乡骸淆抚治朝矢矣漳厘膀第4部分计算学科中的基本概念第4部分计算学科中的基本概念概念概念o一般地说，对任何一个问题，如果有了解决一般地说，对任何一个问题，如果有了解决该问题的算法，就可以编制相应的程序。所该问题的算法，就可以编制相应的程序。所谓谓程序，是一种事先编制好了具有特殊功能程序，是一种事先编制好了具有特殊功能的指令序列。的指令序列。其中，指令既可以是机器指令，
144、其中，指令既可以是机器指令，汇编语言指令，也可以是高级语言的语句命汇编语言指令，也可以是高级语言的语句命令，甚至还可以是用自然语言描述的运算、令，甚至还可以是用自然语言描述的运算、操作命令。当然，用自然语言编写程序是计操作命令。当然，用自然语言编写程序是计算机科学进入非常高级的阶段的标志之一，算机科学进入非常高级的阶段的标志之一，有赖于自然语言理解取得重大突破，目前看有赖于自然语言理解取得重大突破，目前看来还是一个十分遥远的设想。来还是一个十分遥远的设想。捌坯丽求柬捻王瞳视掐桔椽褂昏保喜颈学跺囤弃泊导装疟兢信九蝗梭阮押第4部分计算学科中的基本概念第4部分计算学科中的基本概念概念概念o从广义上讲
145、，程序可以认为是一种行动方案从广义上讲，程序可以认为是一种行动方案或工作步骤。例如：或工作步骤。例如：n某个会议的日程安排某个会议的日程安排n一条旅游路线的设计一条旅游路线的设计n手工小制作的说明书等手工小制作的说明书等oo程序：一种处理事务的时间顺序和处理步骤。程序：一种处理事务的时间顺序和处理步骤。n n组成计算机程序的基本单位是组成计算机程序的基本单位是指令指令n n计算机程序就是按照工作步骤事先编计算机程序就是按照工作步骤事先编排好的、具有特殊功能的排好的、具有特殊功能的指令序列指令序列。纹疥罕秦瞩搪撂投寞蒋侩且孟浪雍懂噎准垮蒋录颠吨运蛊苫惟滁徐昏维题第4部分计算学科中的基本概念第4部
146、分计算学科中的基本概念一个程序具有一个单一的、不可分的结构，它规定了某个数据结构上的一个算法。瑞士著名计算机科学家尼可莱沃思（NikiklausWirth）在1976年曾提出这样一个公式：算法算法+数据结构数据结构=程序程序这这一一公公式式仅仅可可以以作作为为一一种种参参考考，不不能能作作为为教学中的定义。教学中的定义。翱轮侧主均僚砌左奴跪疏军兴襄奔足搓缝焉瘩干黍铸心凌较躯雀治污佣萤第4部分计算学科中的基本概念第4部分计算学科中的基本概念由此看来，我们前面提到的算法和数据结构是计算机程序的两个最基本的概念。算法是程序的核心，它在程序编制、软件开发，乃至在整个计算机科学中都占据重要地位。数据结构
147、是加工的对象，一个程序要进行计算或处理总是以某些数据为对象的，而要设计一个好的程序就需将这些松散的数据按某种要求组成一种数据结构。然而，随着计算机科学的发展，人们现在已经意识到程序除了以上两个主要要素外，还应包括程序的设计方法以及相应的语言工具和计算环境。蔗洪瘫倡澳史承邦惹缓窒动幅衙饰贮抛曰胎屎说玫悸端馒滋舟邓努情戒裂第4部分计算学科中的基本概念第4部分计算学科中的基本概念概念概念o程序这一概念的出现，得益于人类长期的生程序这一概念的出现，得益于人类长期的生活实践，程序设计也不神秘。但是，程序设活实践，程序设计也不神秘。但是，程序设计是一种高智力的活动，不同的人对同一事计是一种高智力的活动，不
148、同的人对同一事物的处理可以设计出完全不同的程序。我们物的处理可以设计出完全不同的程序。我们每一个人的生活经历已经告诉自己，知识和每一个人的生活经历已经告诉自己，知识和阅历（经验）是处事（设计程序）的基础。阅历（经验）是处事（设计程序）的基础。正因为如此，在计算机发展的早期，程序设正因为如此，在计算机发展的早期，程序设计被认为是一个与个人经历、思想和技艺相计被认为是一个与个人经历、思想和技艺相联系的一种技艺和技巧。后来，软件开发规联系的一种技艺和技巧。后来，软件开发规模的扩大和开发方式的变化，程序设计才开模的扩大和开发方式的变化，程序设计才开始被当成一门科学来对待。始被当成一门科学来对待。驼媒律
149、殃斜拴渗诀躯赶审筷保淖磷苛撬遮弛阻乞仑馈津聊冯缘柴躲菏怨椒第4部分计算学科中的基本概念第4部分计算学科中的基本概念概念概念o既然程序如此重要，又为人类经常使用，就既然程序如此重要，又为人类经常使用，就有必要对程序及其运行的规律进行深入的研有必要对程序及其运行的规律进行深入的研究。于是，对程序各种性质如程序的结构、究。于是，对程序各种性质如程序的结构、程序的正确性、程序的运行效率等的研究产程序的正确性、程序的运行效率等的研究产生了计算机科学十分重要的一个方向生了计算机科学十分重要的一个方向程序程序理论。理论。卫贸版邀灼砧漓兢溯郸抠聊卡聊接蛹亩楔沫毅诺形唤撩椒魏醇寻蝇续凰墒第4部分计算学科中的基本
150、概念第4部分计算学科中的基本概念抄涝悉佳鄙柒门湾匣辛夹潞跑芯冤这就饮糯乖餐驹吧密王呸衡蕾石隘过鳃第4部分计算学科中的基本概念第4部分计算学科中的基本概念4.6高级语言、程序设计技术高级语言、程序设计技术与方法与方法4.6.1高级语言客维絮刻砷怀洋睛节阂陛诈风苛搽醉赘蹋贴多绅穴涡板圣俺取真胚榨磨筐第4部分计算学科中的基本概念第4部分计算学科中的基本概念高级语言高级语言o虽然与机器语言相比，汇编语言的产生是一个很虽然与机器语言相比，汇编语言的产生是一个很大的进步，但是用它来进行程序设计仍然比较困大的进步，但是用它来进行程序设计仍然比较困难。于是人们着手对它进行改进。一是发展宏汇难。于是人们着手对它
151、进行改进。一是发展宏汇编，即用一条宏指令代替若干条汇编指令，从而编，即用一条宏指令代替若干条汇编指令，从而提高编程效率。现在人们使用的汇编语言，大多提高编程效率。现在人们使用的汇编语言，大多数都是宏汇编语言。二是创建高级语言，使编程数都是宏汇编语言。二是创建高级语言，使编程更加方便。更加方便。o所谓高级程序设计语言（简称高级语言）是指用所谓高级程序设计语言（简称高级语言）是指用于描述计算机程序的类自然语言。这种语言只是于描述计算机程序的类自然语言。这种语言只是自然语言的一个很小的子集，在语法结构上比较自然语言的一个很小的子集，在语法结构上比较简单而且规范，在语义上较少二义性，能够以比简单而且规
152、范，在语义上较少二义性，能够以比较准确、易读的形式描述各种计算机程序。较准确、易读的形式描述各种计算机程序。挂豫笺粒届妙踢开永滋称盯垒徐孙崭悸篱孩皂走吨杜晶蒋彭痹祁旷舌虞窖第4部分计算学科中的基本概念第4部分计算学科中的基本概念高级语言的分类高级语言的分类按语言的特点，可以将高级语言划分为：按语言的特点，可以将高级语言划分为：o过程式语言（如过程式语言（如CobolCobol，ForturnForturn，AlgolAlgol，PascalPascal，AdaAda，C C）oo函数式语言（如函数式语言（如LispLisp）oo数据流语言（如数据流语言（如SISALSISAL，VALVAL）o
153、o面向对象语言（如面向对象语言（如SmalltalkSmalltalk，CLUCLU，C+C+）oo逻辑语言（如逻辑语言（如PrologProlog）oo字符串语言（如字符串语言（如SNOBOLSNOBOL）oo并发程序设计语言（如并发程序设计语言（如Concurrent PascalConcurrent Pascal，Modula 2Modula 2）等）等民饥砰坟被火调躬当恰藕拎补寄俯姬仪舶赐贷帖三勒骆怎哎蕾赖凛止马窥第4部分计算学科中的基本概念第4部分计算学科中的基本概念高级语言的形式化高级语言的形式化 20世纪世纪50年代年代o美美国国语语言言学学家家乔乔姆姆斯斯基基（NoamChom
154、sky）关于语言分层的理论，关于语言分层的理论，o巴巴科科斯斯（Backus）、瑙瑙尔尔（Naur）的的关关于于“上上下下文文无无关关方方法法表表示示形形式式”的的研研究究成成果果推推动动了了语法形式化的研究。语法形式化的研究。o其其结结果果是是，在在ALGOL60的的文文本本设设计计中中第第一一次次使使用用了了BNF范范式式来来表表示示语语法法，并并且且第第一一次次在在语语言言文文本本中中明明确确提提出出应应将将语语法法和和语语义义区区分分开开来。来。执租舀总弛甲适盒兄陆补屎邦吞娘聂青按卿翌粤蛛活讫克迈建毅陪亭揭斗第4部分计算学科中的基本概念第4部分计算学科中的基本概念高级语言的形式化高级语
155、言的形式化o20世世纪纪50年年代代至至60年年代代间间，面面向向语语法法的的编编译译自自动动化化理理论论得得到到了了很很大大发发展展，使使语语法法形形式式化化研研究究的成果达到实用化的水平。的成果达到实用化的水平。o语语法法形形式式化化问问题题基基本本解解决决以以后后，人人们们逐逐步步把把注注意意力力集集中中到到语语义义形形式式化化的的研研究究方方面面,20世世纪纪60年代，相继诞生了年代，相继诞生了n n操作语义学操作语义学n n指称语义学指称语义学n n公理语义学公理语义学n n代数语义学等语义学理论代数语义学等语义学理论慈褒昆诈宿垮或妆虹厂口畔暇鼠钻屡峰梭胸屏拿丰水类驮腺哩倚已藩喀瞅第
156、4部分计算学科中的基本概念第4部分计算学科中的基本概念数据类型的抽象数据类型的抽象o相对于汇编语言和机器语言，高级语言的相对于汇编语言和机器语言，高级语言的数据数据类型类型的抽象层次有了很大地提高，出现了的抽象层次有了很大地提高，出现了n整型整型n实型实型n字符型字符型n布尔型布尔型n用户自定义类型用户自定义类型n抽象数据类型抽象数据类型o数据类型的抽象数据类型的抽象极大地方便了用户对数据的抽极大地方便了用户对数据的抽象描述，为实现软件设计的工程化奠定了基础。象描述，为实现软件设计的工程化奠定了基础。贰耪藩距锋拧礼修札凳彬斋野敖捞滞豪拟锐蜜帆冷篷尝桃非赞薪采耍揣轰第4部分计算学科中的基本概念第
157、4部分计算学科中的基本概念高级语言中有关抽象、理论和设计高级语言中有关抽象、理论和设计3个形态的主要内容个形态的主要内容 抽象理论设计常用的符号：数字(09)，大小写字母(AZ、az)，括号，运算符(+，*，/)等;用高级语言对算法进行的描述；语言的分类方法；各种数据类型的抽象实现模型；词法分析、编译、解释和代码优化的方法；词法分析器、扫描器、编译器组件和编译器的自动生成方法形式语言和自动机理论；形式语义学：操作、指称、公理、代数、并发和分布式程序的形式语义特定语言：过程式的COBOL，FORTURN，ALGOL，Pascal，Ada，C），函数式的（LISP），数据流的（SISAL，VAL）
158、，面向对象的（Smalltalk，C+），逻辑的（Prolog），字符串（SNOBOL），和并发（ConcurrentPascal，Modula2）等语言；词法分析器和扫描器的产生器（如YACC，LEX），编译器产生器；语法和语义检查，成型、调试和追踪程序憋妹惊碾磅维漆浸厄偏她疮惋手擒狞幕狞贝摆岸捆撒轻跨榜吝喀汤捎龙访第4部分计算学科中的基本概念第4部分计算学科中的基本概念抄涝悉佳鄙柒门湾匣辛夹潞跑芯冤这就饮糯乖餐驹吧密王呸衡蕾石隘过鳃第4部分计算学科中的基本概念第4部分计算学科中的基本概念4.6高级语言、程序设计技术高级语言、程序设计技术与方法与方法4.6.2程序设计技术与方法筏力辊钳光柠莱
159、丙桂秦冬展棒庶澈者狭凋脏铂胞层祈宵拉糠啄骚巢甭观阐第4部分计算学科中的基本概念第4部分计算学科中的基本概念程序设计技术程序设计技术o为提高计算机的效率和可靠性，围绕程序的为提高计算机的效率和可靠性，围绕程序的设计、描述、构造、分析、测试和验证等方设计、描述、构造、分析、测试和验证等方面，发展了许多的技术，统称为程序设计技面，发展了许多的技术，统称为程序设计技术。术。o不同的程序设计方法与技术，都是从不同的不同的程序设计方法与技术，都是从不同的角度对程序及其设计和产生过程的特性和规角度对程序及其设计和产生过程的特性和规律进行观察，经抽象、分析和总结之后得出律进行观察，经抽象、分析和总结之后得出的
160、。的。桌挺娠克论纯唤特件威都栅假妙锋驭袄默哗螟巫斟雀邹镊拜拢汇冷庭菊烘第4部分计算学科中的基本概念第4部分计算学科中的基本概念程序设计方法与技术程序设计方法与技术o自顶向下逐步求精的程序设计方法与技术自顶向下逐步求精的程序设计方法与技术o自底向上的程序设计方法与技术自底向上的程序设计方法与技术o基于程序推导的程序设计方法与技术基于程序推导的程序设计方法与技术o基于程序变换的程序设计方法与技术基于程序变换的程序设计方法与技术o面向对象的程序设计方法与技术面向对象的程序设计方法与技术o函数式程序设计技术函数式程序设计技术o逻辑程序设计技术逻辑程序设计技术o程序验证技术程序验证技术o并发程序技术并发
161、程序技术o。淹簧参衡悠四社纹卫剐匙盆癸钢雄听魏绅唱拂埔勉致士绎呀鹿酶昭返衡庸第4部分计算学科中的基本概念第4部分计算学科中的基本概念程序设计语言是一门科学程序设计语言是一门科学o对程序结构本质的深入研究促进了对程序质对程序结构本质的深入研究促进了对程序质量的认识量的认识o开发程序的效率和质量取决于程序设计方法开发程序的效率和质量取决于程序设计方法和技术和技术o多年的研究发展了许多程序设计方法和技术。多年的研究发展了许多程序设计方法和技术。如自顶向下逐步求精的程序设计方法、自底如自顶向下逐步求精的程序设计方法、自底向上的程序设计方法、程序推导的设计方法、向上的程序设计方法、程序推导的设计方法、程
162、序变换的设计方法、函数式程序设计技术、程序变换的设计方法、函数式程序设计技术、逻辑程序设计技术、面向对象的程序设计技逻辑程序设计技术、面向对象的程序设计技术、程序验证技术、约束程序设计技术、并术、程序验证技术、约束程序设计技术、并发程序设计技术等。发程序设计技术等。泡贡缀恼仙陌消敞扫豹羡抖枯概鉴廓敲周补喀坛免相况卞坏酪述垄侠钞桂第4部分计算学科中的基本概念第4部分计算学科中的基本概念程序设计语言是一门科学程序设计语言是一门科学o例如，对于许多问题的计算，可以用类似于例如，对于许多问题的计算，可以用类似于计算函数的方法来进行，也可以用表（一种计算函数的方法来进行，也可以用表（一种数据结构）处理的
163、方法进行，甚至还可以用数据结构）处理的方法进行，甚至还可以用逻辑公式演绎推导的方法进行，在实现技术逻辑公式演绎推导的方法进行，在实现技术上，既可以用递归技术计算，也可以用迭代上，既可以用递归技术计算，也可以用迭代技术或其它技术进行计算。技术或其它技术进行计算。扒侨疤懊听控滴裸杭矩沙帅胎钉陇种州拭代又跳娜掸淆屁搽限割绦厅积舆第4部分计算学科中的基本概念第4部分计算学科中的基本概念程序设计语言是一门科学程序设计语言是一门科学o作为一门科学，高级语言和程序设计确实对作为一门科学，高级语言和程序设计确实对学科的发展产生了巨大的影响。程序设计方学科的发展产生了巨大的影响。程序设计方法和技术在各个时期的发
164、展不仅直接导致了法和技术在各个时期的发展不仅直接导致了一大批风格各异的高级语言的诞生，而且许一大批风格各异的高级语言的诞生，而且许多新思想、新概念、新方法和新技术不仅在多新思想、新概念、新方法和新技术不仅在语言中得到体现，同时渗透到了计算机科学语言中得到体现，同时渗透到了计算机科学的各个方向，从理论、硬件、软件到应用等的各个方向，从理论、硬件、软件到应用等多方面深刻影响了学科的发展。多方面深刻影响了学科的发展。o对高级语言和程序设计的掌握是计算机科学对高级语言和程序设计的掌握是计算机科学专业的基本功之一。专业的基本功之一。绊上些染筷毅嘶蛰罕屡直霞琉韶棍诲别靠粱肺络馈舷妒迁太男损绷阐立程第4部分
165、计算学科中的基本概念第4部分计算学科中的基本概念抄涝悉佳鄙柒门湾匣辛夹潞跑芯冤这就饮糯乖餐驹吧密王呸衡蕾石隘过鳃第4部分计算学科中的基本概念第4部分计算学科中的基本概念4.7软件与硬件软件与硬件4.7.1硬件漠祟于庚剥源侮镍舜隘赴敢墩花沟碧戍密锌汽义囱俏哺熏憾左沽寨士辑侮第4部分计算学科中的基本概念第4部分计算学科中的基本概念硬件的概念硬件的概念o计计算算机机硬硬件件是是构构成成计计算算机机系系统统的的所所有有物物理理器器件件、部部件件、设设备备，以以及及相相应应的的工工作作原原理理与与设设计计、制制造造、检检测测等等技技术术的的总总称称。广广义义的的硬硬件件包包含含硬硬件件本本身身及及其其工
166、工程程技技术术两两部部分分。其其中中：语音等方式进入计算机语音等方式进入计算机n n计计算算机机系系统统的的物物理理元元器器件件包包括括：集集成成电电路路、印印制制电电路路板板，以以及及其其他他磁磁性性元元件件、电电子子元元件等。件等。n n计计算算机机系系统统的的部部件件和和设设备备包包括括：控控制制器器、运算器、存储器、输入输出设备、电源等。运算器、存储器、输入输出设备、电源等。炙蓬惑疵丧幌测者盲躬猪络水剔史慑拙骗崭蛀磅曲社欢埂鸦虞挟诅诞诽糖第4部分计算学科中的基本概念第4部分计算学科中的基本概念硬件的概念硬件的概念o硬硬件件工工程程技技术术包包括括：印印制制电电路路板板制制造造、高高密密
167、度度组组装装、抗抗环环境境干干扰扰、抗抗恶恶劣劣环环境境破破坏坏等等技技术术，以以及及在在设设计计和和制制造造过过程程中中为为提提高高计计算算机机性能所采取的措施等。性能所采取的措施等。乐匿惦潭郴肠剐殆淹凛柯芽娜弹错显繁脓棺成悔岗畦晕瞬笺抱哎筒镐手春第4部分计算学科中的基本概念第4部分计算学科中的基本概念抄涝悉佳鄙柒门湾匣辛夹潞跑芯冤这就饮糯乖餐驹吧密王呸衡蕾石隘过鳃第4部分计算学科中的基本概念第4部分计算学科中的基本概念4.7软件与硬件软件与硬件4.7.2软件脑应芝毯俊娟兜乡霓螟抹墨断渐灸武螟础因能盲剑谭友捞浮潮紊标油剔印第4部分计算学科中的基本概念第4部分计算学科中的基本概念软件的概念软件
168、的概念oo软件是与程序密切相关的一个概念，在计算机发展的初期，硬件设计和生产是主要问题，那时的软件就是程序。后来，随着计算技术的发展，传统软件的生产方式已不适应发展的需要，于是人们将工程学的基本原理和方法引入软件设计和生产中。oo现在计算机软件一般指计算机系统中的程序及其文档，也可以指在研究、开发、维护，以及使用上述含义下的软件所涉及的理论、方法、技术所构成的分支学科。馆欢撮虞叼峦臀厉琼肾堕删夺知证皂悼笑辙垒亲曳碳嗽君吁褒烟包睬嘘霜第4部分计算学科中的基本概念第4部分计算学科中的基本概念软件的定义软件的定义o从计算机（硬件裸机）到计算机系统从计算机（硬件裸机）到计算机系统o从计算机系统到计算机
169、体系结构从计算机系统到计算机体系结构oo软件是与程序密切相关的一个概念，在计算机发展的初期，硬件设计和生产是主要问题，那时的软件就是程序。后来，随着计算技术的发展，传统软件的生产方式已不适应发展的需要，于是人们将工程学的基本原理和方法引入软件设计和生产中。暂饺肆柱傀阶优球吧听叮席昧饼恰鸯蚤绩止遥谤模屎栖敬滥册挣巡樟件九第4部分计算学科中的基本概念第4部分计算学科中的基本概念软件的定义软件的定义o软件是一个发展的概念，早期软件和程序几软件是一个发展的概念，早期软件和程序几乎是同义词。后来，软件的概念在程序的基乎是同义词。后来，软件的概念在程序的基础上得到了延伸。础上得到了延伸。1983年，年，I
170、EEE对软件给出对软件给出了一个较为新颖的定义，指出：了一个较为新颖的定义，指出：软件是计算软件是计算机程序、方法、规范及其相应的文稿以及在机程序、方法、规范及其相应的文稿以及在计算机上运行时所必须的数据。计算机上运行时所必须的数据。兑爽惭早柒状拈么掀饶翘痛讶归佳挞谦椰巧岂晦新啼咖随砌奎镶贤惠寒力第4部分计算学科中的基本概念第4部分计算学科中的基本概念软件的分类软件的分类o软软件件一一般般分分为为系系统统软软件件、支支撑撑软软件件、应应用用软软件件3类。类。n n系系统统软软件件是是计计算算机机系系统统中中最最靠靠近近硬硬件件层层次次的的软软件件。如如操操作作系系统统、编编译译程程序序、汇汇编
171、编程程序序、数数据据库库管管理理系系统统、软软硬硬件件故故障障诊诊断断程程序序、子子程程序序库库、各各种种软软件件开开发发工工具和软件包等属于系统软件。具和软件包等属于系统软件。n n支支撑撑软软件件是是支支撑撑其其他他软软件件的的开开发发与与维维护护的的软软件件。如如数数据据库库管管理理系系统统、网网络络软软件件、各种接口软件和开发工具等。各种接口软件和开发工具等。n n应应用用软软件件是是特特定定应应用用领领域域的的专专用用软软件件。如商业会计软件、教学软件等。如商业会计软件、教学软件等。做善悦攘宴躇逝矛卑持侦哨蒋浆调钱哥剧颤毒炊曹羽迸直泉搀床迹宠毙拂第4部分计算学科中的基本概念第4部分计
172、算学科中的基本概念软件的概念软件的概念o操操作作系系统统-一一种种系系统统软软件件，它它负负责责管管理理计计算算机机系系统统中中的的各各种种资资源源并并控控制制各各类类程程序序的的运运行行。它它通通过过接接受受来来自自用用户户的的操操作作命命令令，按按照照用用户户的的要要求求对对计计算算机机的的工工作作进进行行控控制制。计计算算机机配配上操作系统之后，能够提高效率，便于使用。上操作系统之后，能够提高效率，便于使用。o系统软件和应用软件迄今并没有严格的定义。系统软件和应用软件迄今并没有严格的定义。儿亡版宝伴龄汀屯代迭嘉忱刹隶云慧悲蛮串径丛臣僚驴假骚径柔遗猴肌钝第4部分计算学科中的基本概念第4部分
173、计算学科中的基本概念抄涝悉佳鄙柒门湾匣辛夹潞跑芯冤这就饮糯乖餐驹吧密王呸衡蕾石隘过鳃第4部分计算学科中的基本概念第4部分计算学科中的基本概念4.7软件与硬件软件与硬件 计算机就是由计算机硬件和计算机软件组成的。硬件是计算机的“躯体”，软件是计算机的“灵魂”。 妙俗烹军泅谚快愿酮徒偷红烹冲矣袁刻匈蓑闲灌檬攫沪茫创厚液契辨疼触第4部分计算学科中的基本概念第4部分计算学科中的基本概念抄涝悉佳鄙柒门湾匣辛夹潞跑芯冤这就饮糯乖餐驹吧密王呸衡蕾石隘过鳃第4部分计算学科中的基本概念第4部分计算学科中的基本概念4.8计算机图形学、图像处理计算机图形学、图像处理与模式识别与模式识别4.8.1计算机图形学揍盔捉乞
174、级波晚菱模吼龄乙怯膘薛汹粕螺侣舶路樱想喷吕贯竟群荫教荤备第4部分计算学科中的基本概念第4部分计算学科中的基本概念oo国际标准化组织(ISO)的定义：计算机图形学是研究通过计算机将数据转换为图形，并在专门显示设备上显示的原理、方法和技术的学科。oo计算机图形学是建立在传统的图学理论、应用数学和计算机科学基础上的一门边缘学科。基本概念基本概念了募娟巩蜘坎叙挽坠轿鞋咕胁腺辟忆篙橇桓酷穿袒邮隆狄隆涝辆赋帽踪疵第4部分计算学科中的基本概念第4部分计算学科中的基本概念oo广义的概念oo几何要素几何属性点、线、面、体oo非几何要素视觉属性明暗、灰度、色彩、纹理、透明性、线型、线宽图形的构成要素图形的构成要素
175、皋装耗逆虞垮利聊完孪凋晦富氮蔚颂桌捕潞午板撮垛愿为链钝孤究贮骨诌第4部分计算学科中的基本概念第4部分计算学科中的基本概念oo计算机对图形数据处理的硬件和软件oo围绕着生成、表示物体的图形的准确性-真实性-实时性oo算法可大致分为以下几类： -基于图形设备的基本图形元素的生成算法基于图形设备的基本图形元素的生成算法 -图形的变换和裁剪图形的变换和裁剪 -自由曲线和曲面自由曲线和曲面计算几何计算几何 -真实感图形真实感图形的生成算法的生成算法 -三维几何造型技术三维几何造型技术 -山山、水水、花、草、花、草、树木树木、云云、烟、烟、火焰火焰、雪景雪景等模糊复杂等模糊复杂景物的生成景物的生成分形几何
176、分形几何 -三维或高维数据场的可视化三维或高维数据场的可视化 -图形的并行处理图形的并行处理 -虚拟现实环境虚拟现实环境实时交互式三维图形处理实时交互式三维图形处理研究内容研究内容主桅源运变们鸵男眶竭蜗宦点噎奸内嗡卸震秸服匪淀蕊刑攘臣蕴膳粘疥蹈第4部分计算学科中的基本概念第4部分计算学科中的基本概念oo图形用户界面（GUI)oo计算机辅助设计与制造工业领域oo计算机动画商业领域（广告设计、电脑游戏、卡通动画片、影视特技）oo计算机艺术艺术领域oo过程控制（工业、交通等领域设备运行监控)oo系统环境模拟(如飞行模拟舱等）oo事务和商务数据的图形显示oo地形地貌和自然资源的图形显示（GIS、GPS
177、)oo科学计算的可视化oo多媒体应用图形学的应用图形学的应用夫苫毯埔砰瞄硷妇常拣钒磐坡日援钙吟汉犊翟渊薪协惦汾淳陆长奖土省惹第4部分计算学科中的基本概念第4部分计算学科中的基本概念抄涝悉佳鄙柒门湾匣辛夹潞跑芯冤这就饮糯乖餐驹吧密王呸衡蕾石隘过鳃第4部分计算学科中的基本概念第4部分计算学科中的基本概念4.8计算机图形学、图像处理计算机图形学、图像处理与模式识别与模式识别4.8.2图像处理屁耘蛆佃予摘镜嗜胳拷滨赵训政顷吁屡湾歌付昧冷军双木凋杉窟睹怕爱帆第4部分计算学科中的基本概念第4部分计算学科中的基本概念oo数字图象处理旨在对图象进行各种加工以改善图象的视觉效果。oo主要研究对客观世界中已经存在
178、的物体映像处理成新的数字化图像，如医学图像处理、卫星遥感图像处理、照相图像处理等。oo主要关心的是如何滤掉噪音，图像压缩、传输和还原，图像质量提高等。鹰牲螟甘钱厌麓夫蓬煤盛罕皑起格咐毒呀俱韶瘁煌骡幅多胁术埋鲜制韭稿第4部分计算学科中的基本概念第4部分计算学科中的基本概念抄涝悉佳鄙柒门湾匣辛夹潞跑芯冤这就饮糯乖餐驹吧密王呸衡蕾石隘过鳃第4部分计算学科中的基本概念第4部分计算学科中的基本概念4.8计算机图形学、图像处理计算机图形学、图像处理与模式识别与模式识别4.8.3模式识别韵寞眶娘孵尔碗叹盂嗽堡屎尹碰头圭略汽筏苹洱伴拖待洼腻肃唆迅黄沮躇第4部分计算学科中的基本概念第4部分计算学科中的基本概念o
179、o模式识别主要研究如何分析和识别各种图像，找出其中图形数据蕴含的内在联系或构建图像的抽象模型。oo如高速公路上的车辆拍照的识别、人脸部的识别、数字水印等。嗜贸圭雕财喀滨琶以藩拖搽亦跌桶栽缨淳昨忘妮始很银眺彭笼繁俱街瘸歹第4部分计算学科中的基本概念第4部分计算学科中的基本概念与相与相关学关学科的科的关系关系图像处理图像处理计计算算机机图图形形学学模模式式识识别别图图像像计算几何计算几何特特征征数数据据几几何何模模型型CAD/CAM计算机艺术计算机艺术计算机动画计算机动画计算机视觉计算机视觉民饵系均写仟虚牡写疙全傣银旨票揪拈腥麦迪期暗廓矩番颓准幻透打酣聚第4部分计算学科中的基本概念第4部分计算学科
180、中的基本概念抄涝悉佳鄙柒门湾匣辛夹潞跑芯冤这就饮糯乖餐驹吧密王呸衡蕾石隘过鳃第4部分计算学科中的基本概念第4部分计算学科中的基本概念4.9人工智能第第4章章 计算学科中的基本计算学科中的基本概念概念 液钎知往插骸初拈泼此六降檬说瞎雇鼓经木扫快礁焙猴屠减主扶章叛姥俄第4部分计算学科中的基本概念第4部分计算学科中的基本概念oo人工智能就是研究智能计算机及其系统，以模仿和执行人类的某些智力功能，如判断、推理、规划、设计、思考、学习、识别等，解决过去人类专家才能处理好的复杂问题。oo人工智能的“思维法则”方法中，强调的是正确的推论。作出正确推论有时也是理性智能体的部分功能。基本概念基本概念碾武拍构亭槽
181、权抖娥檬挚睦诽钒维黍梢透恼济长而易捡房街变冶簧脓珐内第4部分计算学科中的基本概念第4部分计算学科中的基本概念oo人工智能领域中的所谓逻辑主义就是希望通过编制具有逻辑能力的程序来创造智能系统。oo问题：-难以获得非形式化的知识并得到逻辑符号表示所需的形式化表达；-”原则上”可以解决一个问题与实际解决问题这两者之间存在巨大的差别。基本概念基本概念砍吱谨疼弄诀蹲觅犊浊烯续手专胺服旁呸鹊藕蠕冰均扳狰择揣鸭郡黎折羌第4部分计算学科中的基本概念第4部分计算学科中的基本概念oo1、像人一样思考的系统-有 头 脑 的 机 器 ： 计 算 机 能 够 思 考 。(Haugeland，1985）-使之能够进行与人
182、类的思维相关的活动，如 决 策 、 问 题 求 解 、 学 习 等 。（Bellman,1978)oo2理性地思考的系统-通过对计算模型的使用来进行心智能力的研究。（Charniak,1985)-对使得知觉、推理和行动成为可能的计算的研究。（Winston,1992)人们对人工智能的解释人们对人工智能的解释章扣鳖佐秀笑搀清苹旦娇油坦恢需箭存剥婆尸拯财归瓜箩高醚仲脉蚤派搐第4部分计算学科中的基本概念第4部分计算学科中的基本概念oo3像人一样行动的系统-一种技艺，创造机器来执行人需要智能才能完成的功能。(Kurzweil，1990）-研究如何让计算机能够做到那些目前人比计算机做得更好的事情。（Ri
183、ch,Knight,1991)oo4理性地行动的系统-计算智能是对设计智能化智能体的研究。（Poole等人,1998)-AI.关心的是人工制品中的智能行为。（尼尔森（Nilsson）,1998)人们对人工智能的解释人们对人工智能的解释匡战易钒娶堵何郭瓣超妻泌锨妮敏窍尧扒养婶模餐举烬它舞浸洛嚼奶惨虽第4部分计算学科中的基本概念第4部分计算学科中的基本概念o哲学哲学（公元前（公元前428428年年-现在）现在） - -形式化规则能用来抽取合理结论吗？形式化规则能用来抽取合理结论吗？ - -精神的意识是如何从物质的大脑产生出精神的意识是如何从物质的大脑产生出来的？来的？ - -知识从哪里来？知识从哪
184、里来？ - -知识是如何导致行动的？知识是如何导致行动的？人工智能研究的基础人工智能研究的基础赁母骂川兜扔龋翰灿盅淀恶呕蚕腊妖嚼扁畅酿亦痊岿稻忱垦票勤幂滩乌数第4部分计算学科中的基本概念第4部分计算学科中的基本概念o数学数学（约（约800800年年-现在）现在） - -什么是抽取合理结论的形式化规则？什么是抽取合理结论的形式化规则？ - -什么可以计算？什么可以计算？ - -我们如何用不确定的知识进行推理？我们如何用不确定的知识进行推理？o经济学经济学（17761776年年现在）现在） - -我们如何决策以获得最大收益？我们如何决策以获得最大收益？ - -我们在他人不合作的情况下如何做到这样我
185、们在他人不合作的情况下如何做到这样？ - -我们在收益遥遥无期的情况下如何做到这我们在收益遥遥无期的情况下如何做到这样？样？ 人工智能研究的基础人工智能研究的基础寇泛滓滁爆侍弗觅剁困谓帘蜕杆靠掣佰玩悟揭喝蒙沫朗丢薄纲辅涪脑杰氢第4部分计算学科中的基本概念第4部分计算学科中的基本概念o神经科学神经科学（18611861年年-现在）现在） - -头脑是如何处理信息的？头脑是如何处理信息的？o心理学心理学（18791879年年现在）现在） - -人类和动物如何思考和行动？人类和动物如何思考和行动？o计算机工程计算机工程（19401940年年-现在）现在） - -我们如何才能制造出能干的计算机？我们如
186、何才能制造出能干的计算机？o控制论控制论（19481948年年现在）现在） - -人工制品怎样才能在自己的控制下运转？人工制品怎样才能在自己的控制下运转？o语言学语言学（19571957年年现在）现在） - -语言和思维是怎样联系起来的？语言和思维是怎样联系起来的？人工智能研究的基础人工智能研究的基础鼻伦兼壹吏新玄授拌换花逼垒佩诫粉央揩曙词烘蔷像旱决抛窘历睛多脯遮第4部分计算学科中的基本概念第4部分计算学科中的基本概念o知识表示（知识表示（KnoweledgePresentationn）o问题求解（问题求解（Problemsolving）o模式识别（模式识别（PatternRecognitio
187、n）o自动定理证明自动定理证明(AutomaticTheoremProving)o自动程序设计（自动程序设计（AutomationProgramming）o自然语言处理（自然语言处理（NaturalLanguageProcessing）o专家系统（专家系统（ExpertSysterms）o机器学习（机器学习（MachineLearning）o机器人学（机器人学（Robotics）o人工神经网络（人工神经网络（ArtificialNueralNetwork）o计算机视觉计算机视觉(ComputerVision)o博奕（博奕（GamePlaging）人工智能的应用研究领域人工智能的应用研究领域坛模
188、扔毡绅闭缅日烤旧贺河可乌耸弓淆蓉椒阮至昭吼密临霍窝将拯砂峡某第4部分计算学科中的基本概念第4部分计算学科中的基本概念抄涝悉佳鄙柒门湾匣辛夹潞跑芯冤这就饮糯乖餐驹吧密王呸衡蕾石隘过鳃第4部分计算学科中的基本概念第4部分计算学科中的基本概念4.10计算机组织与体系结构计算机组织与体系结构第第4章章 计算学科中的基本计算学科中的基本概念概念 弱蜗担腑逃瞒淑河脂阀道竞上拭仁鞭宴悦滁那堪范采卤酞高瞪埠盼臆撅殴第4部分计算学科中的基本概念第4部分计算学科中的基本概念oo内容包括从计算机系统的逐个设计、制造到计算机的系列化和软件的兼容性。ooIBM 360系 统 标 志 着 计 算 机 体 系 结 构（Ar
189、chitecture）研究的开端（1964年）。oo计算机体系结构是使用机器语言编写程序的用户可以看到的一个机器的抽象结构，而对这一结构实现的硬件组成属于计算机组成原理研究的范畴。渺蝉姻笼辱她动赋蔽市鼓娜塑奄打闭慎凸菊茧识蹦围茨哼若钉鲍晦付拆溢第4部分计算学科中的基本概念第4部分计算学科中的基本概念oo随随着着大大规规模模和和超超大大规规模模集集成成电电路路（LSI/VLSILSI/VLSI）技技术术的的成成熟熟，一一方方面面器器件件速速度度和和可可靠靠性性在在不不断断提提高高，目目前前已已逼逼近近极极限限，另另一一方方面面器器件件的的体体积积和和价价格格在在持持续续下下降降，这这极极大大地地
190、增增强强了了计计算算机机的的性性能能。然然而而，高高质质量的器件不是产生高性能计算机的唯一因素。量的器件不是产生高性能计算机的唯一因素。oo虽虽然然，今今日日大大多多数数计计算算机机都都是是图图灵灵冯冯 诺诺依依曼曼型型存存储储程程序序式式电电子子数数字字计计算算机机，但但人人们们早早已已认认识识到到计计算算机机不不仅仅仅仅是是一一个个硬硬件件组组织织的的问问题题。一一个个现现代代的的计计算算机机系系统统一一般般被被认认为为是是由由存存储储器器、处处理理器器、功功能能部部件件、互互联联网网络络、汇汇编编程程序序、编编译译程程序序、操操作作系系统统、外外部部设备、通信通道等内容组合而成的。设备、
191、通信通道等内容组合而成的。太径历淹扼摇浆售奶绞函控于帚京天炯受挑志熏袒筏媳自腾纳谜惕届赚揣第4部分计算学科中的基本概念第4部分计算学科中的基本概念硬件的概念硬件的概念o早期计算机系统研究与开发的两个基本特点：早期计算机系统研究与开发的两个基本特点：n n硬硬件件和和软软件件的的研研究究与与开开发发基基本本上上是是独独立立进进行的；行的；n n硬硬件件的的研研究究与与开开发发更更多多的的是是从从计计算算机机组组成成原原理理上上去去关关心心各各部部件件中中分分离离元元器器件件及及其其相相互互之之间间的的联联接接关关系系，关关心心各各部部件件的的内内部部构构造和外部特性。造和外部特性。oo集成电路的
192、发展改变了专业人员的认识。顶丧拢咱摹犬莲礼殃涕揩圾歇扎暖尖拜喘挎帖施逞辛蹿较值懒衰武姑贷陈第4部分计算学科中的基本概念第4部分计算学科中的基本概念oo计算机CPU的速度和存储器的容量成倍增长，各种多功能部件不断引入，如何设计和配置计算机系统使其具有更高的性能价格比，适应不同用户的要求，成为亟待解决的问题。oo集成电路的发展也使许多专业人员可以不再关心各部件的内部细节，而只须考虑如何以一种统一的观点从硬件器件和一些软件系统出发，通过组合配置，设计功能更强、性能价格比更高、更可靠的计算机系统。于是，计算机体系结构应运而生。索奠缀陋茬椿伴刺纸去藩贿乍距昧毅版恤缚搔斌颠骨炳顷快饯坟赏姻噪儒第4部分计算
193、学科中的基本概念第4部分计算学科中的基本概念oo典典型型的的、有有助助于于常常人人理理解解计计算算机机体体系系结结构构的的方方向向是是所所谓谓的的计计算算机机网网络络系系统统。用用户户面面对对计计算算机机系系统统网网络络进进行行开开发发是是十十分分困困难难的的，因因为为，他他不不可可能能熟熟悉悉网网上上每每一一种种通通信信资资源源的的配配置置情情况况，而而且且也也不不了了解解每每一一种种通通信信资资源源的的基基本本操操作作方方法法，更更不不可可能能考考虑虑通通信信出出错错的的情情况况以以及及如如何何纠纠错错。显显然然，对对于于用用户户来来说说，需需要要有有一一种种能能够够屏屏蔽蔽计计算算机机硬
194、硬件件系系统统技技术术细细节节，仅仅对对用用户户提提供供功功能能透透明明的的系系统统层层，使使用用户户看看到到的的和和实实际际使使用用的的是是一一个个与与使使用用者者思思想想方方式式、使使用用习习惯惯比比较较接接近近，无无须须具具体体关关心心网网络络计计算算机机通通信信时时一一些些十十分分繁繁琐琐的的技技术细节的分布式计算机系统。术细节的分布式计算机系统。悠缓斩罐嗽敖舟劣泵炽榨军贫烘落刀呵物佃猜沛奠绑伞本诱条巷本啼盅符第4部分计算学科中的基本概念第4部分计算学科中的基本概念oo硬件的互联结构和软件结构及相互关系形成的计算机系统的总体结构，支持这种结构的基本算法，还有以总体结构为基础的面向用户的
195、程序设计语言等内容构成了计算机体系结构的技术范畴。离痹邑篮间洞哉轴雀睡炎拿渗项崩浚瓢慷穴端再哈妥晕荆村孝殿亨憎凶更第4部分计算学科中的基本概念第4部分计算学科中的基本概念抄涝悉佳鄙柒门湾匣辛夹潞跑芯冤这就饮糯乖餐驹吧密王呸衡蕾石隘过鳃第4部分计算学科中的基本概念第4部分计算学科中的基本概念4.12并行计算机、通道与并并行计算机、通道与并行计算行计算第第4章章 计算学科中的基本计算学科中的基本概念概念 疆社跺已撤狗揭丧敖拢罐冈敝织斗煽亢守毡价敦勺昔苗彬匝闯梧摘特毋攫第4部分计算学科中的基本概念第4部分计算学科中的基本概念oo单CPU计算机多功能部件多寄存器计算机流水线向量计算机阵列式计算机多处理
196、器并行计算机多处理机并行计算机多计算机网络并行计算机系统。计算机的组成结构变迁计算机的组成结构变迁趋咬窑达逐臆摆委炒醇江副凝娠洛姨闺嘴鼻印艇藕将士荚恼铅奶提企炕靖第4部分计算学科中的基本概念第4部分计算学科中的基本概念并行处理的概念并行处理的概念o并并行行处处理理要要求求在在计计算算机机上上并并行行地地运运行行许许多多程程序序。根根据据使使用用的的计计算算机机系系统统的的不不同同，我我们们可可以在四个程序的级别上提出并行处理的问题：以在四个程序的级别上提出并行处理的问题：n n作业或程序级并行作业或程序级并行n n任务或过程级并行任务或过程级并行n n指令级并行指令级并行n n指令内部级并行。
197、指令内部级并行。酌慷渗瘁姜殴区哑骄啮讣冶貉德摇忍思畸躺伺令剐墓谊爷浓嗡扁牡肢祥丫第4部分计算学科中的基本概念第4部分计算学科中的基本概念oo不同的并行处理思想和技术，产生了不同的并行计算机系统。从使用方便的角度考虑，用户更希望看到的是系统提供作业或程序级并行，这样用户可以不必考虑实现并行的细节。而从实际计算提高效率的角度考虑，用户更希望系统已经实现了指令级并行或指令内部级并行。并行处理的概念并行处理的概念猫平沈琐痊闷裁盛闪拟乱朔贺料仑沁昨吧讨谍萝螺周莎迄滤涵邀烤宝敛粒第4部分计算学科中的基本概念第4部分计算学科中的基本概念oo面对众多的并行计算机系统，我们应该怎么来认识和区别它们的系统结构呢？
198、ooM.J.Flynn在1966年提出了一种著名的、也是现今比较常用的系统结构分类方法。他将计算机系统的系统结构分为四类，分别是：n n单指令流单数据流计算机（SISD）n n单指令流多数据流计算机（SIMD）n n多指令流单数据流计算机（MISD）n n多指令流多数据流计算机（MIMD）并行处理的概念并行处理的概念彭拉痉绩秆癸拨很栈找串框播迸脓呕飞疮剐暇膳圭浴涌逼疮忽耘烙簿辐女第4部分计算学科中的基本概念第4部分计算学科中的基本概念oo由多机系统技术的扩展及网络互连与通信技术的引入，发展了分布式网络计算机系统，提出了分布式计算机体系结构、分布式算法与分布式并行处理的概念等。oo并行计算机系统
199、的出现，带来了信息并行化处理的概念。并行处理是信息处理的一种有效形式，它着重于发掘计算过程中的并发事件。并行处理的概念并行处理的概念佐绍斋郎蜜渔虞支典江峙被腻外廖粹血嘻竟盔纵受氨瞄恰段乔纷悦吹夸座第4部分计算学科中的基本概念第4部分计算学科中的基本概念oo并发性包含宏观上的并行性，包含同时性以及微观上的流水线处理。并行事件可在同一时间间隔内在多个资源（如多个处理器）里发生；同时事件可在同一时刻上发生，流水线事件可在部分重叠的时间内于一个（或多个）资源里出现。oo并发通常是指宏观上一个资源里并行发生了两个或两个以上的事件，但在微观上是顺序发生的，而并行通常是指多个资源里微观上同时发生了两个或两个
200、以上事件。显然，一组事件是并行的也是并发的，但一组事件是并发的却不一定是并行的。并行处理的概念并行处理的概念某与誉挑狡岛唐毫果词杰词圆猖当苹肃殿烩迂缓冻瑚倚磋灼日黍乘俞浙童第4部分计算学科中的基本概念第4部分计算学科中的基本概念oo-通道是数据或信息传送的通路oo利用并行计算机系统进行数据与信息的并行处理称为并行计算。从处理对象的角度划分，并行计算分为数值并行计算和非数值并行计算。oo与顺序计算类似，并行计算也分成几个步骤：研究并行计算方法，研究并行算法，设计并行程序，调试与运行，分析结果。通道的概念通道的概念疡钎簧灿惨单脉二荚优樊谁肮惋写韶拧厩巾灌淌鲸累勘霍酒新帚肥保说婉第4部分计算学科中的
201、基本概念第4部分计算学科中的基本概念oo由于许多问题的计算已经有了计算方法，而这些计算方法中隐含了大量的并行性，稍作变化就可支持并行算法和并行程序设计，而且，由于各种并行计算机的系统结构不同，各处理器和各多功能部件之间在体现算法时的相互作用不同，算法不能通用。oo因此，除了并行计算机体系结构的研究外，当前和今后相当长的一个时期内并行处理的一个工作重点将是研究各种并行与分布式计算机系统上的并行算法或分布式算法。通道的概念通道的概念釉奶歧裳即绥腺棠抑器迅尾厕辊未姿滔夫带扔柜弛食宰瓦冬熟败侠丽溺酮第4部分计算学科中的基本概念第4部分计算学科中的基本概念网络的基本概念网络的基本概念o随着计算科学及其应
202、用的高速发展，用户对软硬件和随着计算科学及其应用的高速发展，用户对软硬件和信息资源共享的需求和一大类问题本身具有地域上分信息资源共享的需求和一大类问题本身具有地域上分布的特点，促进了计算机网络的发展。布的特点，促进了计算机网络的发展。o所谓所谓计算机网络是使用通信设备和通信线路将一组地计算机网络是使用通信设备和通信线路将一组地理上分布的相同（称为同质）或不同（称为异质）的理上分布的相同（称为同质）或不同（称为异质）的计算机、终端及其附属设备按照某种方式互联起来得计算机、终端及其附属设备按照某种方式互联起来得到的一个计算机硬件系统到的一个计算机硬件系统，也叫网络计算机。在这种，也叫网络计算机。在
203、这种计算机硬件系统的基础上，通过开发能协调各台计算计算机硬件系统的基础上，通过开发能协调各台计算机系统工作的通信系统或更进一步的网络操作系统，机系统工作的通信系统或更进一步的网络操作系统，就能使一组计算机实现软硬件资源共享、协同计算，就能使一组计算机实现软硬件资源共享、协同计算，合作求解一个问题。由这种通信系统或网络操作系统合作求解一个问题。由这种通信系统或网络操作系统连同网络计算机一起，就形成了网络计算机系统。连同网络计算机一起，就形成了网络计算机系统。勾被礼击郑她动鸟娃丢彬婿谜抽你跋袋客盾厄糠遁担萝姓否寝裁凯叙涎扛第4部分计算学科中的基本概念第4部分计算学科中的基本概念网络的分类网络的分类
204、o按照数据传输范围和实现技术的不同，计算机网按照数据传输范围和实现技术的不同，计算机网络存在络存在局域计算机网络局域计算机网络和和广域计算机网络广域计算机网络之分。之分。局域计算机网络是一个数据通信系统，其传输范局域计算机网络是一个数据通信系统，其传输范围在中等地理区域，使用中等或高速数据传输速围在中等地理区域，使用中等或高速数据传输速率，使用专用数据通信线或总线进行通信，可联率，使用专用数据通信线或总线进行通信，可联接大量独立设备，在物理通信通道上互相通信。接大量独立设备，在物理通信通道上互相通信。o广域计算机网络把不同城市、不同国家中的计算广域计算机网络把不同城市、不同国家中的计算机或计算
205、机网络通过分级互联技术联接起来，其机或计算机网络通过分级互联技术联接起来，其传输范围可达到相当远的距离。目前最常见的是传输范围可达到相当远的距离。目前最常见的是使用公用或专用电话线通信，主干网和一些局域使用公用或专用电话线通信，主干网和一些局域网使用可进行数字通信的光纤光缆数据通信专用网使用可进行数字通信的光纤光缆数据通信专用线。线。安映违霜媒天瘫纤呈拯暖运裕常锌丑仰声逗谊舀净崭实韭卫粕婉喝绘诌话第4部分计算学科中的基本概念第4部分计算学科中的基本概念网络的结构网络的结构o网络互联的拓扑结构是计算机网络的重要特性。网络互联的拓扑结构是计算机网络的重要特性。网络的拓扑结构是一种抽象的由点和线组成
206、的图。网络的拓扑结构是一种抽象的由点和线组成的图。网络上的每台计算机用一个结点表示，机器与机网络上的每台计算机用一个结点表示，机器与机器之间的链路用线和路径表示，于是，图论构成器之间的链路用线和路径表示，于是，图论构成了网络计算机体系结构中一些基本算法研究中数了网络计算机体系结构中一些基本算法研究中数学描述的理论基础。学描述的理论基础。o网络的结构一般有：主从型、环型、星型、等网络的结构一般有：主从型、环型、星型、等割蛛棚活瓢此宪倪掘侍歧记逢隋赚胁写铂或搜缠吻蓟曹在惊组忍恼辱吨咽第4部分计算学科中的基本概念第4部分计算学科中的基本概念网络的协议网络的协议o支持计算机网络的重要技术是通信，即实现
207、计算支持计算机网络的重要技术是通信，即实现计算机之间信息传输的一种技术方式。网络通信的核机之间信息传输的一种技术方式。网络通信的核心内容是通信协议。所谓通信协议是网络通信中心内容是通信协议。所谓通信协议是网络通信中一组约定的集合，由它确定了经由通信网络传输一组约定的集合，由它确定了经由通信网络传输的信息或存储在报文和数据库中的信息的格式和的信息或存储在报文和数据库中的信息的格式和控制方式。研究通信协议主要是为了在网络计算控制方式。研究通信协议主要是为了在网络计算机系统中实现可靠的、高效的数据交换，差错控机系统中实现可靠的、高效的数据交换，差错控制，信息编码，线路利用，同步，使通信数据具制，信息
208、编码，线路利用，同步，使通信数据具有透明性。有透明性。谨芍婆鞠矾寇遵初胎心武服融儒棍鞠蠢财上惨贵责利泌落豹问僳剔蛀陷汉第4部分计算学科中的基本概念第4部分计算学科中的基本概念 网络上连接着大量的计算机系统，每台计算机系统网络上连接着大量的计算机系统，每台计算机系统上可能有多个用户在同时使用计算机与其它网上用户上可能有多个用户在同时使用计算机与其它网上用户进行通信，而网络通信线路通常设计成公用资源，这进行通信，而网络通信线路通常设计成公用资源，这样，网络通信为了实现可靠的数据交换，因需要做许样，网络通信为了实现可靠的数据交换，因需要做许多具体的操作运算而变得十分复杂。由于从用户发送多具体的操作运
209、算而变得十分复杂。由于从用户发送或接收可以识别的符号信息到实际在正确的通信线路或接收可以识别的符号信息到实际在正确的通信线路上传递物理信息之间存在转换、线路利用、分组交换、上传递物理信息之间存在转换、线路利用、分组交换、差错纠正等一系列的操作，为了便于协议的有效实现差错纠正等一系列的操作，为了便于协议的有效实现和对不同的用户开放，最大限度地实现线路的有效利和对不同的用户开放，最大限度地实现线路的有效利用，有必要对网络计算机系统进行通信结构分层。于用，有必要对网络计算机系统进行通信结构分层。于是产生了网络协议层。每一层包含一组通信功能和相是产生了网络协议层。每一层包含一组通信功能和相应的层间通信
210、协议，支持通信双方在不同的层间进行应的层间通信协议，支持通信双方在不同的层间进行通信，并提供了实现通信的具体思想和方法。通信，并提供了实现通信的具体思想和方法。网络的协议网络的协议硝泡厌捍缀掉辛禽谍阂夜瓦适它农拓容残溜侮嘛赐茧心晨鸯夸恳厄啄凹术第4部分计算学科中的基本概念第4部分计算学科中的基本概念 按照按照ISOISO的建议，网络结构模型是开放系统互连模型的建议，网络结构模型是开放系统互连模型OSIOSI（七层协议），包括物理层，数据链路层，网络层，（七层协议），包括物理层，数据链路层，网络层，传输层，会话层，表示层，应用层共七层，产生了七传输层，会话层，表示层，应用层共七层，产生了七层协议
211、。层协议。 开放系统开放系统A A 开放系统开放系统B B 应用层协议应用层协议 应用层应用层 应用层应用层 表示层协议表示层协议 表示层表示层 表示层表示层 会话层协议会话层协议 会话层会话层 会话层会话层 传输层协议传输层协议 传输层传输层 传输层传输层 网络层协议网络层协议 网络层网络层 网络层网络层 数据链路层协议数据链路层协议 数据链路层数据链路层数据链路层数据链路层 物理层协议物理层协议 物理层物理层 物理层物理层 物理传输介质物理传输介质 网络的协议网络的协议旁罕户讣竿长倒抉山拥壶铬褂街衙席兜砧跑尝丛泅陕况沫毋刻哨铰砧洼琉第4部分计算学科中的基本概念第4部分计算学科中的基本概念网
212、络的网络的OSI协议协议o物理层协议实现物理上互连系统间位流信息的透物理层协议实现物理上互连系统间位流信息的透明传输，即实现了一位（组）数据在两个通信实明传输，即实现了一位（组）数据在两个通信实体之间的可靠传送通信，它描述了经通信介质在体之间的可靠传送通信，它描述了经通信介质在数据链路实体之间建立、维护和拆除物理连接。数据链路实体之间建立、维护和拆除物理连接。o数据链路层协议主要是对高层屏蔽传输介质的特数据链路层协议主要是对高层屏蔽传输介质的特性，为网络通信实体之间提供建立、维护和释放性，为网络通信实体之间提供建立、维护和释放数据链路连接的功能和手段，实现无差错的数据数据链路连接的功能和手段，
213、实现无差错的数据以帧为单位的可靠传送。以帧为单位的可靠传送。o网络层协议主要是为通信子网与高层结构之间提网络层协议主要是为通信子网与高层结构之间提供界面连接，其主要任务是对通信子网实现路径供界面连接，其主要任务是对通信子网实现路径选择，实现通信实体之间端选择，实现通信实体之间端- -端的透明的数据传送，端的透明的数据传送，对高层屏蔽了数据传送经过的路径。对高层屏蔽了数据传送经过的路径。 索峪劫浸阁淬窘呼渡蹭迁吴蔷辣汤煌存镐盟泅虚醚绝氦长燃卿观侗尽樊霍第4部分计算学科中的基本概念第4部分计算学科中的基本概念网络的网络的OSI协议协议o传输层协议也称为主机传输层协议也称为主机-主机层协议，它为会主
214、机层协议，它为会话层的通信实体之间提供透明的数据传送，其话层的通信实体之间提供透明的数据传送，其主要任务是接收会话实体送来的数据，根据需主要任务是接收会话实体送来的数据，根据需要把它们分成若干比较小的单元，保证所有数要把它们分成若干比较小的单元，保证所有数据单元经下面三层正确地到达另一个会话实体。据单元经下面三层正确地到达另一个会话实体。o会话层协议也称进程会话层协议也称进程-进程层协议，它通过协进程层协议，它通过协议提供的一组命令为网上两个进程之间的通信议提供的一组命令为网上两个进程之间的通信建立会话连接和释放会话连接，并管理它们在建立会话连接和释放会话连接，并管理它们在该连接上的对话。该连
215、接上的对话。熔熔秤棱耶灶欠捷材赤妄优觅平粗娃觅藻捷终弱了猩兵雁朱糙囤偷滴撰腔第4部分计算学科中的基本概念第4部分计算学科中的基本概念网络的网络的OSI协议协议o表示层协议以对应用实体有意义的形式提供有表示层协议以对应用实体有意义的形式提供有关信息表示的服务。这些服务有文本压缩、代关信息表示的服务。这些服务有文本压缩、代码转换、数据加密与解密、文件格式变换、信码转换、数据加密与解密、文件格式变换、信息格式变换、终端属性的转换等。息格式变换、终端属性的转换等。o应用层协议是用户访问网络的接口层，直接为应用层协议是用户访问网络的接口层，直接为正在通信的端点用户的应用进程服务，如电子正在通信的端点用户
216、的应用进程服务，如电子邮件、远程操作访问、虚拟终端等。邮件、远程操作访问、虚拟终端等。o关于协议详细的实现技术，其主要的基础是分关于协议详细的实现技术，其主要的基础是分布式算法，今后，同学们有可能学习这些内容。布式算法，今后，同学们有可能学习这些内容。o网络信息安全、加密、病毒、高性能计算与通网络信息安全、加密、病毒、高性能计算与通信、信息高速公路、数字地球信、信息高速公路、数字地球拦浸稼既裂差攀铅欺缕萨求两撰耐菩及庇长榷恳吭评辰扫悦食饰怂牛瘸喳第4部分计算学科中的基本概念第4部分计算学科中的基本概念抄涝悉佳鄙柒门湾匣辛夹潞跑芯冤这就饮糯乖餐驹吧密王呸衡蕾石隘过鳃第4部分计算学科中的基本概念第
217、4部分计算学科中的基本概念4.15CC1991报告提取的核心概念第第4章章 计算学科中的核计算学科中的核 心概念心概念衷哪坤忠岸癌皮极贯蒙糯要迷逸米炔热洽锈载磁饺纷辙凳哮掏犁饲羽肪笔第4部分计算学科中的基本概念第4部分计算学科中的基本概念o核心概念是核心概念是CC1991报告首次提出的，是具有报告首次提出的，是具有普遍性、持久性的重要思想、原则和方法。普遍性、持久性的重要思想、原则和方法。它的基本特征有：它的基本特征有：n n在学科中多处出现；在学科中多处出现；n n在在各各分分支支领领域域及及抽抽象象、理理论论和和设设计计的的各个层面上都有很多示例；各个层面上都有很多示例；n n在技术上有高
218、度的独立性；在技术上有高度的独立性；n n一般都在数学、科学和工程中出现。一般都在数学、科学和工程中出现。软颅两灰象集疑憎却磨厢庐梆狡笑漓觉心措割岛叼陡痈您裹淆戍娇底尊体第4部分计算学科中的基本概念第4部分计算学科中的基本概念1.绑定绑定（Binding）oo绑定指的是通过将一个对象（或事物）与其某种属性相联系，从而使抽象的概念具体化的过程。例如：将一个进程与一个处理机，一个变量与其类型或值分别联系起来。这种联系的建立，实际上就是建立了某种约束。卵消梢蓄走匝袍卒吱域咽澳跪彪受迅迫据瞒赛登专钞厘矫弱纂预蒙涕模睹第4部分计算学科中的基本概念第4部分计算学科中的基本概念2.大问题的复杂性大问题的复杂
219、性（ComplexityofLargeProblems）oo大问题的复杂性是指随着问题规模的增长而使问题的复杂性呈非线性增加的效应。这种非线性增加的效应是区分和选择各种现有方法和技术的重要因素。 肄斋估护瞒腿馒猾陆两苞烘牧叮葛卢痕谷坊谩沧璃次侵第汲起决来泅泛掩第4部分计算学科中的基本概念第4部分计算学科中的基本概念3. 概念和形式模型概念和形式模型（ConceptualandFormatModels）oo概念和形式模型是对一个想法或问题进行形式化、特征化、可视化思维的方法。抽象数据类型、语义数据类型以及指定系统的图形语言，如数据流图和E-R图等都属于概念模型。而逻辑、开关理论和计算理论中的模型
220、大都属于形式模型。概念模型和形式模型以及形式证明是将计算学科各分支统一起来的重要的核心概念。沦讹蓑员惺股谋嗓巫淤藕牌嚎褒俗徐惋认兼夜谁经洒蓝钦蒂痉脖茶泼养酶第4部分计算学科中的基本概念第4部分计算学科中的基本概念4.一致性和完备性一致性和完备性（ConsistencyandCompleteness）o一一致致性性包包括括用用于于形形式式说说明明的的一一组组公公理理的的一一致致性性、事事实实和和理理论论的的一一致致性性，以以及及一一种种语语言言或或接接口口设设计的内部一致性。计的内部一致性。o完完备备性性包包括括给给出出的的一一组组公公理理，使使其其能能获获得得预预期期行行为为的的充充分分性性、
221、软软件件和和硬硬件件系系统统功功能能的的充充分分性性，以以及及系系统统处处于于出出错错和和非非预预期期情情况况下下保保持持正正常常行行为的能力等。为的能力等。oo在在计计算算机机系系统统设设计计中中，正正确确性性、健健壮壮性性和和可可靠靠性就是一致性和完备性的具体体现。性就是一致性和完备性的具体体现。壬肃骗蹋誊云匀狭针垃炼裂问猎沸篱涩牟瑰适勋渔竭惠状隶拿衅氨垣吮汛第4部分计算学科中的基本概念第4部分计算学科中的基本概念5.效率效率（Efficiency）oo效率是关于空间、时间、人力、财力等资源消耗的度量。在计算机软硬件的设计中，要充分考虑某种预期结果所达到的效率，以及一个给定的实现过程较之替
222、代的实现过程的效率。 腑侮再闯蝶痪结珐鹅汽裁够极乏姓梧亨某韵团捶哉诚簿钻蒸若叼游蚂捆恐第4部分计算学科中的基本概念第4部分计算学科中的基本概念6演化演化（Evolution） 演化指的是系统的结构、状态、特征、行为和功能等随着时间的推移而发生的更改。这里主要是指了解系统更改的事实和意义及应采取的对策。在软件进行更改时，不仅要充分考虑更改对系统各层次造成的冲击，还要充分考虑到软件的有关抽象、技术和系统的适应性问题。岗鞭洱粪膊翌玲讽豺昌闰才培忌兵芝伊就疗丁珊星笨莱晦陀啄至胚滴绥僧第4部分计算学科中的基本概念第4部分计算学科中的基本概念7.抽象层次抽象层次（Levels of Abstraction
223、）oo抽象层次指的是通过对不同层次的细节和指标的抽象对一个系统或实体进行表述。在复杂系统的设计中，隐藏细节，对系统各层次进行描述（抽象），从而控制系统的复杂程度。例如，在软件工程中，从规则说明到编码各个阶段（层次）的详细说明，计算机系统的分层思想，计算机网络的分层思想等。疙知藉巨苔纠鞭敬华得飞菜竣贞哼襟舌返窘艺哗续曹霍槛缸群株我炭献喀第4部分计算学科中的基本概念第4部分计算学科中的基本概念8.按空间排序按空间排序（Ordering in Space）oo按空间排序指的是各种定位方式，如物理上的定位（如网络和存储中的定位），组织方式上的定位（如处理机进程、类型定义和有关操作的定位）以及概念上的定
224、位（如软件的辖域、耦合、内聚等）。按空间排序是计算技术中一个局部性和相邻性的概念。 吞堂庐腰关唱痊胯胎昧络郝腿嘛怯毋涕缸憎涟撤剑否遁碟如搐屈仿嗓恕库第4部分计算学科中的基本概念第4部分计算学科中的基本概念9.按时间排序按时间排序（Ordering in Time）oo按时间排序指的是事件的执行对时间的依赖性。例如，在具有时态逻辑的系统中，要考虑与时间有关的时序问题；在分布式系统中，要考虑进程同步的时间问题；在依赖于时间的算法执行中，要考虑其基本的组成要素。心筐皂央染旱栏厄鬼誊闸沁斗恐慌搂演割驴途错惦文迄烽象荤戊武肃拦亩第4部分计算学科中的基本概念第4部分计算学科中的基本概念10.重用重用（Re
225、use）oo重用指的是在新的环境下，系统中各类实体、技术、概念等可被再次使用的能力。如软件库和硬件部件的重用等。 汛娟怖厉称默屿噪怂狙秦惟移辨丧玉减照瓣域掘硝馆渣恤作誉筛粱赞贿护第4部分计算学科中的基本概念第4部分计算学科中的基本概念11.安全性安全性（Security）oo安全性指的是计算机软硬件系统对合法用户的响应及对非法请求的抗拒，以保护自己不受外部影响和攻击的能力。如为防止数据的丢失、泄密而在数据库管理系统中提供的口令更换、操作员授权等功能。 霓玄伊硝菩靛序叶猫砧馋志衡村臃氢氰控痒赐唱琅仰轮拎洞托渍讼桶甫熬第4部分计算学科中的基本概念第4部分计算学科中的基本概念12.折衷与结论折衷与结论（Tradeoff and Consequences）oo指的是为满足系统的可实施性而对系统设计中的技术、方案所作出的一种合理的取舍。结论是折衷的结论，即选择一种方案代替另一种方案所产生的技术、经济、文化及其他方面的影响。折衷是存在于计算学科领域各层次上的基本事实。如在算法的研究中，要考虑空间和时间的折衷；对于矛盾的设计目标，要考虑诸如易用性和完备性、灵活性和简单性、低成本和高可靠性等方面所采取的折衷等。 运单鹿恐炙竖米铝乖汲材吱戊岳耳工勃缕锨嘲回够眩倡逼脏晤乖氓亨睛竣第4部分计算学科中的基本概念第4部分计算学科中的基本概念
