《第4章计算学科中的核心概念》由会员分享，可在线阅读，更多相关《第4章计算学科中的核心概念（79页珍藏版）》请在金锄头文库上搜索。
1、第4章计算学科中的核心概念Stillwatersrundeep.流静水深流静水深,人静心深人静心深Wherethereislife,thereishope。有生命必有希望。有生命必有希望第第4章计算学科中的核章计算学科中的核 心概念心概念4.1 算法算法的历史简介算法的历史简介算法的历史简介算法的历史简介 oo公元公元825年，阿拉伯数学家阿科瓦里茨米年，阿拉伯数学家阿科瓦里茨米（AlKhowarizmi）写了著名的波斯教科书写了著名的波斯教科书（Persian Textbook），），书中概括了进行四书中概括了进行四则算术运算的法则。则算术运算的法则。n n“ “算法算法算法算法” ”（Al
2、gorithmAlgorithm）一词就来源于这位数学家一词就来源于这位数学家一词就来源于这位数学家一词就来源于这位数学家的名字。的名字。的名字。的名字。oo后来，韦氏新世界词典将其定义为后来，韦氏新世界词典将其定义为“解某解某种问题的任何专门的方法种问题的任何专门的方法”。oo而据考古学家发现，古巴比伦人在而据考古学家发现，古巴比伦人在求解代数方求解代数方程程时，就已经采用了时，就已经采用了“算法算法”的思想。的思想。丢番图方程的可解性问题丢番图方程的可解性问题丢番图方程的可解性问题丢番图方程的可解性问题 oo古希腊数学家丢番图（古希腊数学家丢番图（Diophantus）：代数：代数学之父学
3、之父n n在算术（在算术（在算术（在算术（ArithmeticaArithmetica）一书中提出了有关一书中提出了有关一书中提出了有关一书中提出了有关两两两两个或多个变量整数系数方程个或多个变量整数系数方程个或多个变量整数系数方程个或多个变量整数系数方程的有理数解问题。的有理数解问题。的有理数解问题。的有理数解问题。n n对于具有对于具有对于具有对于具有整数系数的不定方程整数系数的不定方程整数系数的不定方程整数系数的不定方程，如果只考虑其，如果只考虑其，如果只考虑其，如果只考虑其整数整数整数整数解解解解，这类方程就叫做丢番图方程。，这类方程就叫做丢番图方程。，这类方程就叫做丢番图方程。，这类
4、方程就叫做丢番图方程。oo“丢番图方程可解性问题丢番图方程可解性问题”的实质为：能否写的实质为：能否写出一个可以判定出一个可以判定任意丢番图方程是否可解任意丢番图方程是否可解的算的算法？法？一个未知数的线性丢番图方程的解一个未知数的线性丢番图方程的解一个未知数的线性丢番图方程的解一个未知数的线性丢番图方程的解ooaxax= =b b，只只要要a a能能整整除除b b，就就可可判判定定其其有有整整数数解，该整数解即解，该整数解即b b/ /a a。两个未知数的线性丢番图方程两个未知数的线性丢番图方程两个未知数的线性丢番图方程两个未知数的线性丢番图方程 的解的解的解的解ooaxax+ +byby=
5、 =c c，先求出先求出a a和和b b的最大公因子的最大公因子d d，若若d d能能整除整除c c，则该方程有解（整数解）。则该方程有解（整数解）。 oo问：方程问：方程1313x x+26+26y y=52=52有无整数解？有无整数解？n n答：答：答：答：13131313和和和和26262626的最大公因子是的最大公因子是的最大公因子是的最大公因子是13131313，13131313又可整除又可整除又可整除又可整除52525252，故，故，故，故该方程有整数解（如该方程有整数解（如该方程有整数解（如该方程有整数解（如x x x x=2=2=2=2，y y y y=1=1=1=1即方程的解
6、）。即方程的解）。即方程的解）。即方程的解）。oo例例4.2 4.2 问：方程问：方程2 2x x+4+4y y=15=15有无整数解？有无整数解？n n答：答：答：答：2 2 2 2和和和和4 4 4 4的最大公因子是的最大公因子是的最大公因子是的最大公因子是2 2 2 2，2 2 2 2不能整除不能整除不能整除不能整除15151515，故该方，故该方，故该方，故该方程无整数解。程无整数解。程无整数解。程无整数解。 两个未知数的线性丢番图方程两个未知数的线性丢番图方程两个未知数的线性丢番图方程两个未知数的线性丢番图方程 的解：的解：的解：的解：欧几里德算法欧几里德算法欧几里德算法欧几里德算法
7、 oo给给定定两两个个正正整整数数m和和n，求求它它们们的的最最大大公公因因子子，即能同时整除即能同时整除m和和n的最大正整数。的最大正整数。oo步骤如下：步骤如下：n n（1 1）以）以）以）以n n除除除除mm，并令所得余数为并令所得余数为并令所得余数为并令所得余数为r r（r r必小于必小于必小于必小于n n）；）；）；）；n n（2 2）若若若若r r=0=0，算算算算法法法法结结结结束束束束，输输输输出出出出结结结结果果果果n n；否否否否则则则则，继继继继续续续续步骤（步骤（步骤（步骤（3 3）；）；）；）；n n（3 3）将将将将n n置置置置换换换换为为为为mm，r r置置置置
8、换换换换为为为为n n，并并并并返返返返回回回回步步步步骤骤骤骤（1 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又又又又表表表表述述述述了了了了一一一一个个个个判判判判定
9、定定定过过过过程程程程，该该该该过过过过程程程程可可可可以以以以判判判判定定定定“ “mm和和和和n n是是是是互互互互质质质质的的的的” ”（即即即即除除除除1 1以以以以外外外外，mm和和和和n n没没没没有有有有公公公公因因因因子子子子）这这这这个个个个命题的真假。命题的真假。命题的真假。命题的真假。算法算法算法的定义和特征算法的定义和特征 1算法的非形式化定义算法的非形式化定义 oo一个算法，就是一个有穷规则的集合，其中之一个算法，就是一个有穷规则的集合，其中之规则规定了一个解决某一特定类型问题的运算规则规定了一个解决某一特定类型问题的运算序列。序列。 算法的定义和特征算法的定义和特征
10、2 2算法的重要特性算法的重要特性算法的重要特性算法的重要特性oo有穷性：一个算法在执行有穷步之后必须结束。有穷性：一个算法在执行有穷步之后必须结束。oo确确定定性性：算算法法的的每每一一个个步步骤骤必必须须要要确确切切地地定定义义。即即算算法法中中所所有有有有待待执执行行的的动动作作必必须须严严格格而而不不含含混地进行规定，不能有歧义性。混地进行规定，不能有歧义性。oo输输入入：算算法法有有零零个个或或多多个个的的输输入入，即即在在算算法法开开始之前，对算法最初给出的量。始之前，对算法最初给出的量。oo输输出出：算算法法有有一一个个或或多多个个的的输输出出，即即与与输输入入有有某某个个特特定
11、定关关系系的的量量，简简单单地地说说就就是是算算法法的的最最终终结果。结果。oo能能行行性性：算算法法中中有有待待执执行行的的运运算算和和操操作作必必须须是是相当基本的，相当基本的，3算法的形式化定义算法的形式化定义 算法是一个四元组，即（算法是一个四元组，即（Q，I，F）。）。其中：其中：（1）Q是是一一个个包包含含子子集集I和和的的集集合合，它它表表示示计计算算的状态；的状态；（2）I表示计算的输入集合；表示计算的输入集合；（3）表示计算的输出集合；表示计算的输出集合；（4）F表表示示计计算算的的规规则则，它它是是一一个个由由Q到到它它自自身身的的函函数数，且且具具有有自自反反性性，即即对
12、对于于任任何何一一个个元元素素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小小于于或或等等于于100，转转到到步步骤骤（3）继继续续执执行；否则，算法结束，结果为行；否则，算法结束，结果为X。例例4.5求解调和级数求解调和级数设变量设变量X表示累加和，变量表示累加和，
13、变量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，1313，2121，3434， （1 1）oo来来 源源 于于 12021202年年 意意 大大 利利 数数 学学
14、家家 斐斐 波波 那那 契契（L.P.FibonacciL.P.Fibonacci）在在其其珠珠算算之之书书（Liber Liber AbaciAbaci）中提出的一个中提出的一个“兔子问题兔子问题”：n n假假假假设设设设一一一一对对对对刚刚刚刚出出出出生生生生的的的的兔兔兔兔子子子子一一一一个个个个月月月月后后后后就就就就能能能能长长长长大大大大，再再再再过过过过一一一一个个个个月月月月就就就就能能能能生生生生下下下下一一一一对对对对兔兔兔兔子子子子，并并并并且且且且此此此此后后后后每每每每个个个个月月月月都都都都能能能能生生生生一一一一对对对对兔兔兔兔子子子子，且且且且新新新新生生生生的
15、的的的兔兔兔兔子子子子在在在在第第第第二二二二个个个个月月月月后后后后也也也也是是是是每每每每个个个个月月月月生生生生一对兔子。一对兔子。一对兔子。一对兔子。n n问：一对兔子一年内可繁殖成多少对兔子？问：一对兔子一年内可繁殖成多少对兔子？问：一对兔子一年内可繁殖成多少对兔子？问：一对兔子一年内可繁殖成多少对兔子？oo在在序序列列（1）中中，每每个个数数都都是是它它的的前前两两个个数数之之和和，Fn表表示示这这个个序序列列的的第第n个个数数，该该序序列列可可以以形式化的定义为：形式化的定义为：n nF F0 0=0=0，F F1 1=1=1，F Fn n+2+2= =F Fn n+1+1+ +
16、F Fn n，n n00oo斐斐波波那那契契数数列列还还是是一一个个关关于于加加法法算算法法的的典典型型实例。实例。oo设变量设变量X表示前一个数的值，即定义中的表示前一个数的值，即定义中的Fn，变量变量Y表示当前数的值，即定义中的表示当前数的值，即定义中的Fn+1，变量变量Z表示后一个数的值，即定义中的表示后一个数的值，即定义中的Fn+2。那么求那么求解问题的自然语言描述如下：解问题的自然语言描述如下：算法设计算法设计算法设计算法设计（1 1）如如如如果果果果=0=0，那那那那么么么么将将将将0 0赋赋赋赋值值值值给给给给Y Y，并并并并输输输输出出出出Y Y，转转转转步步步步骤骤骤骤（11
17、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赋值给赋值给赋值给赋值给X X；（8 8）
18、将将将将Z Z赋值给赋值给赋值给赋值给Y Y；（9 9）将将将将Y Y输出；输出；输出；输出；（1010）将）将）将）将I I加加加加1 1，转步骤（，转步骤（，转步骤（，转步骤（5 5）继续执行；）继续执行；）继续执行；）继续执行；（1111）算法结束。）算法结束。）算法结束。）算法结束。算法算法算法的表示方法算法的表示方法原语原语原语原语oo一个算法的表达需要使用一些语言形式一个算法的表达需要使用一些语言形式n n自然语言自然语言自然语言自然语言“ “VisitinggrandchildrencanbeVisitinggrandchildrencanbenerve-racking”,ner
19、ve-racking”,可能即意味着孙子孙女导致了很可能即意味着孙子孙女导致了很可能即意味着孙子孙女导致了很可能即意味着孙子孙女导致了很多问题，也表示去看他们可能会有问题多问题，也表示去看他们可能会有问题多问题，也表示去看他们可能会有问题多问题，也表示去看他们可能会有问题n n图形语言：很少人能够根据折纸图给出的步骤成图形语言：很少人能够根据折纸图给出的步骤成图形语言：很少人能够根据折纸图给出的步骤成图形语言：很少人能够根据折纸图给出的步骤成功地叠出一只鸟来，但一个专门学习过折纸的学功地叠出一只鸟来，但一个专门学习过折纸的学功地叠出一只鸟来，但一个专门学习过折纸的学功地叠出一只鸟来，但一个专门
20、学习过折纸的学生可以轻松完成生可以轻松完成生可以轻松完成生可以轻松完成oo当用来描述算法的语言并没有被准确定义或当用来描述算法的语言并没有被准确定义或者没有给予足够信息的时候，交流就会产生者没有给予足够信息的时候，交流就会产生问题问题原语原语原语原语oo通过建立一个可以描述算法的意义明确的基本通过建立一个可以描述算法的意义明确的基本块（块（原语原语）集合，计算机科学即就可以解决上）集合，计算机科学即就可以解决上述的勾通问题述的勾通问题oo原语描述算法需要建立一个统一的细节描述级原语描述算法需要建立一个统一的细节描述级别，原语连同一组表达了原语如何表达复杂的别，原语连同一组表达了原语如何表达复杂
21、的想法的规定组成了一种程序设计语言想法的规定组成了一种程序设计语言oo组成组成n n语法：原语的符号表示语法：原语的符号表示语法：原语的符号表示语法：原语的符号表示n n语义：表达了原语的意义语义：表达了原语的意义语义：表达了原语的意义语义：表达了原语的意义1 1自然语言自然语言自然语言自然语言oo缺点缺点n n由由由由于于于于自自自自然然然然语语语语言言言言的的的的歧歧歧歧义义义义性性性性，容容容容易易易易导导导导致致致致算算算算法法法法执执执执行行行行的的的的不确定性；不确定性；不确定性；不确定性；n n自自自自然然然然语语语语言言言言的的的的语语语语句句句句一一一一般般般般太太太太长长长
22、长，从从从从而而而而导导导导致致致致了了了了用用用用自自自自然然然然语言描述的算法太长；语言描述的算法太长；语言描述的算法太长；语言描述的算法太长；n n由由由由于于于于自自自自然然然然语语语语言言言言表表表表示示示示的的的的串串串串行行行行性性性性，因因因因此此此此，当当当当一一一一个个个个算算算算法中循环和分支较多时就很难清晰地表示出来；法中循环和分支较多时就很难清晰地表示出来；法中循环和分支较多时就很难清晰地表示出来；法中循环和分支较多时就很难清晰地表示出来；n n自自自自然然然然语语语语言言言言表表表表示示示示的的的的算算算算法法法法不不不不便便便便翻翻翻翻译译译译成成成成计计计计算算
23、算算机机机机程程程程序序序序设设设设计语言理解的语言。计语言理解的语言。计语言理解的语言。计语言理解的语言。 2 2流程图流程图流程图流程图 oo它它 采采 用用 美美 国国 国国 家家 标标 准准 化化 协协 会会ANSI（ AmericanNationalStandardInstitute）规定的一组图形符号来表示算法。规定的一组图形符号来表示算法。n n流流流流程程程程图图图图可可可可以以以以很很很很方方方方便便便便地地地地表表表表示示示示顺顺顺顺序序序序、选选选选择择择择和和和和循循循循环环环环结结结结构构构构，而而而而任任任任何何何何程程程程序序序序的的的的逻逻逻逻辑辑辑辑结结结结构
24、构构构都都都都可可可可以以以以用用用用顺顺顺顺序序序序、选选选选择择择择和和和和循循循循环结构来表示，环结构来表示，环结构来表示，环结构来表示，n n流程图可以表示任何程序的逻辑结构。流程图可以表示任何程序的逻辑结构。流程图可以表示任何程序的逻辑结构。流程图可以表示任何程序的逻辑结构。n n用用用用流流流流程程程程图图图图表表表表示示示示的的的的算算算算法法法法不不不不依依依依赖赖赖赖于于于于任任任任何何何何具具具具体体体体的的的的计计计计算算算算机机机机和计算机程序设计语言，和计算机程序设计语言，和计算机程序设计语言，和计算机程序设计语言，（1 1）求解例）求解例）求解例）求解例4.44.4
25、的算法流程图的算法流程图的算法流程图的算法流程图（2 2）求解例）求解例）求解例）求解例4.54.5的算法流程图的算法流程图的算法流程图的算法流程图 （3 3）求解例）求解例）求解例）求解例4.64.6的算法流程图的算法流程图的算法流程图的算法流程图 3 3伪代码伪代码伪代码伪代码（1 1）求解例）求解例）求解例）求解例4.44.4的伪代码算法描述：的伪代码算法描述：的伪代码算法描述：的伪代码算法描述：BEGIN(BEGIN(算法开始算法开始算法开始算法开始) )1 1 X X 2 2YYwhilewhile（Y=100Y=n)while(I=n)ENDEND（算法结束）算法结束）算法结束）算
26、法结束）（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计算机程序设计语言计算机程序设计语言计算机程序设计语言计算机程序设计语言 oo计计算算机机程程序序设设计计语语言言描描述述的的算算法法（程程序序）是是清晰的、简明的，最终也能由计算机处理的
27、。清晰的、简明的，最终也能由计算机处理的。oo缺点：缺点：n n算算算算法法法法的的的的基基基基本本本本逻逻逻逻辑辑辑辑流流流流程程程程难难难难于于于于遵遵遵遵循循循循。与与与与自自自自然然然然语语语语言言言言一一一一样样样样，程序设计语言也是基于串行的程序设计语言也是基于串行的程序设计语言也是基于串行的程序设计语言也是基于串行的n n用用用用特特特特定定定定程程程程序序序序设设设设计计计计语语语语言言言言编编编编写写写写的的的的算算算算法法法法限限限限制制制制了了了了与与与与他他他他人人人人的的的的交流，不利于问题的解决；交流，不利于问题的解决；交流，不利于问题的解决；交流，不利于问题的解决
28、；n n要要要要花花花花费费费费大大大大量量量量的的的的时时时时间间间间去去去去熟熟熟熟悉悉悉悉和和和和掌掌掌掌握握握握某某某某种种种种特特特特定定定定的的的的程程程程序序序序设计语言；设计语言；设计语言；设计语言；n n要求描述计算步骤的细节，而忽视算法的本质。要求描述计算步骤的细节，而忽视算法的本质。要求描述计算步骤的细节，而忽视算法的本质。要求描述计算步骤的细节，而忽视算法的本质。例例例例4.44.4的计算机程序设计语言（的计算机程序设计语言（的计算机程序设计语言（的计算机程序设计语言（C C语言）的算法描述：语言）的算法描述：语言）的算法描述：语言）的算法描述： main()main(
29、) 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语言）的算法描述语言）的算法描述语言）的算法描述语言）的算法描述 main()main() intn;intn;floatX,I;floatX,I;printf(Pleaseinputn:);printf(Pleaseinputn:);scanf(%d,&n);scanf
30、(%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);算法算法算法分析算法分析（1 1）算法的时间复杂度；）算法的时间复杂度；）算法的时间复杂度；）算法的时间复杂度； oo用用T(n)表示，表示，n表示问题规模的大小。表示问题规模的大小。oo使用一个记号使用一个记号 n nOrderOrder（数量级）的第一个字母，数量级）的第一个字母，数量级）的第一个字母，数量级）的第一个字母，n n允许使用允许使用允许使用允许使用“=”“=”代替代替
31、代替代替“”“”。如。如。如。如n n2 2+ +n n+1=+1= ( (n n2 2) )oo设设f(n)是是一一个个关关于于正正整整数数n的的函函数数，若若存存在在一一个个正正整整数数n0和和一一个个常常数数C，当当nn0时时， T(n) Cf(n) 均均成成立立，则则称称f(n)为为T(n)的的同同数数量量级级的的函函数。数。n n算法时间复杂度算法时间复杂度算法时间复杂度算法时间复杂度T T( (n n) )可表示为：可表示为：可表示为：可表示为：T(n)= (f(n)常见的大常见的大常见的大常见的大 表示形式有：表示形式有：表示形式有：表示形式有： (1)：称为常数级；：称为常数级
32、； (logn)：称为对数级；称为对数级； (n)：称为线性级；：称为线性级； (nc)：称为多项式级；：称为多项式级； (cn)：称为指数级；：称为指数级； (n!)：称为阶乘级。：称为阶乘级。算法的空间复杂度算法的空间复杂度算法的空间复杂度算法的空间复杂度oo指算法在执行过程中所占存储空间的大小，指算法在执行过程中所占存储空间的大小，oo用用S(n)表示，表示，S为英文单词为英文单词Space的第一个字的第一个字母。与算法的时间复杂度相同母。与算法的时间复杂度相同oo算法的空间复杂度算法的空间复杂度S(n)也可表示为：也可表示为： S(n)= (g(n)。算法算法算法的研究算法的研究算法算
33、法oo算法：定义一向工作如何完成的步骤的集合算法：定义一向工作如何完成的步骤的集合n n在一台机器可以完成一个任务之前，必须找到完在一台机器可以完成一个任务之前，必须找到完在一台机器可以完成一个任务之前，必须找到完在一台机器可以完成一个任务之前，必须找到完成这个任务的算法并且用与机器兼容的方式来描成这个任务的算法并且用与机器兼容的方式来描成这个任务的算法并且用与机器兼容的方式来描成这个任务的算法并且用与机器兼容的方式来描述述述述n n一个与机器兼容的算法的描述一个与机器兼容的算法的描述一个与机器兼容的算法的描述一个与机器兼容的算法的描述程序程序程序程序oo算法的研究开始是作为数学的一个学科算法
34、的研究开始是作为数学的一个学科n n目标：找到描述特定类型问题是如何被解决的指目标：找到描述特定类型问题是如何被解决的指目标：找到描述特定类型问题是如何被解决的指目标：找到描述特定类型问题是如何被解决的指令的集合，如令的集合，如令的集合，如令的集合，如EuclideanEuclidean算法算法算法算法n n一旦一个完成任务的算法被找到，任务的实现就一旦一个完成任务的算法被找到，任务的实现就一旦一个完成任务的算法被找到，任务的实现就一旦一个完成任务的算法被找到，任务的实现就不再需要对算法原理的理解，任务的实现仅仅是不再需要对算法原理的理解，任务的实现仅仅是不再需要对算法原理的理解，任务的实现仅
35、仅是不再需要对算法原理的理解，任务的实现仅仅是遵循算法的只是过程遵循算法的只是过程遵循算法的只是过程遵循算法的只是过程n n现有的解决问题需要的智慧被编码进了算法现有的解决问题需要的智慧被编码进了算法现有的解决问题需要的智慧被编码进了算法现有的解决问题需要的智慧被编码进了算法算法转化为智慧算法转化为智慧算法转化为智慧算法转化为智慧oo通过使用算法来得到并转化智慧，我们才可以通过使用算法来得到并转化智慧，我们才可以构建起可以表现构建起可以表现智慧行为的机器智慧行为的机器。n n机器表现的智能等级受到通过算法转化的智慧所限机器表现的智能等级受到通过算法转化的智慧所限机器表现的智能等级受到通过算法转
36、化的智慧所限机器表现的智能等级受到通过算法转化的智慧所限制制制制n n如果没有解决问题的算法，意味着问题的解决方案如果没有解决问题的算法，意味着问题的解决方案如果没有解决问题的算法，意味着问题的解决方案如果没有解决问题的算法，意味着问题的解决方案超出了机器的能力范围超出了机器的能力范围超出了机器的能力范围超出了机器的能力范围oo算法的开发就成了计算机领域的一个主要目标算法的开发就成了计算机领域的一个主要目标n n如何找到算法如何找到算法如何找到算法如何找到算法一个十分接近于寻找通用问题解一个十分接近于寻找通用问题解一个十分接近于寻找通用问题解一个十分接近于寻找通用问题解决方案决方案决方案决方案
37、n n描述这个算法描述这个算法描述这个算法描述这个算法转变为一个清晰的指令的集合转变为一个清晰的指令的集合转变为一个清晰的指令的集合转变为一个清晰的指令的集合（程序设计语言描述）（程序设计语言描述）（程序设计语言描述）（程序设计语言描述）计算机技术别用于复杂问题（大型软件系统）计算机技术别用于复杂问题（大型软件系统）计算机技术别用于复杂问题（大型软件系统）计算机技术别用于复杂问题（大型软件系统）oo不仅仅包括实现任务的单个算法的开发不仅仅包括实现任务的单个算法的开发n n还要求对组件之间的交互进行设计还要求对组件之间的交互进行设计还要求对组件之间的交互进行设计还要求对组件之间的交互进行设计n
38、n软件工程：借鉴了工程领域、项目管理领域、人软件工程：借鉴了工程领域、项目管理领域、人软件工程：借鉴了工程领域、项目管理领域、人软件工程：借鉴了工程领域、项目管理领域、人力资源管理以及程序语言设计领域的经验力资源管理以及程序语言设计领域的经验力资源管理以及程序语言设计领域的经验力资源管理以及程序语言设计领域的经验执行算法的机器的设计和实现执行算法的机器的设计和实现执行算法的机器的设计和实现执行算法的机器的设计和实现oo数据的存储数据的存储oo数据的操作数据的操作oo体系结构中涵盖了对现今技术的讨论体系结构中涵盖了对现今技术的讨论n n我们的目标不是去熟知类似当今体系结构是我们的目标不是去熟知类
39、似当今体系结构是如何用电路来实现这样的细节问题，那将会如何用电路来实现这样的细节问题，那将会导致过分陷入电子工程学科导致过分陷入电子工程学科n n正如昨天的齿轮驱动的计算机让位于电子设正如昨天的齿轮驱动的计算机让位于电子设备一样，今天的电子技术也许很快也被其它备一样，今天的电子技术也许很快也被其它的技术所取代的技术所取代理想情况下理想情况下oo希望计算机的体系结构是我们的有关算法过程希望计算机的体系结构是我们的有关算法过程知识的延续，并且不应该被技术能力酸限制知识的延续，并且不应该被技术能力酸限制n n使我们的算法知识在当代机器体系结构的发使我们的算法知识在当代机器体系结构的发展背后起推动作用
40、，而不仅仅是从技术的要展背后起推动作用，而不仅仅是从技术的要求触发来解顶机器的设计求触发来解顶机器的设计oo构建允许使用多个指令序列来代替算法的机器构建允许使用多个指令序列来代替算法的机器是可能的是可能的n n这些指令被同时执行或者作为这些指令被同时执行或者作为机器于外部世界的接口的设计于计算机的设计紧密相连机器于外部世界的接口的设计于计算机的设计紧密相连机器于外部世界的接口的设计于计算机的设计紧密相连机器于外部世界的接口的设计于计算机的设计紧密相连oo算法是如何机器中的？算法是如何机器中的？oo机器是如何被告知执行的是哪一个算法？机器是如何被告知执行的是哪一个算法？计算理论计算理论oo对解决
41、越来越复杂问题的算法的研究对解决越来越复杂问题的算法的研究n n导致了算法过程的最终限制问题导致了算法过程的最终限制问题导致了算法过程的最终限制问题导致了算法过程的最终限制问题n n如果没有算法可以解决这个问题，那么算法是不如果没有算法可以解决这个问题，那么算法是不如果没有算法可以解决这个问题，那么算法是不如果没有算法可以解决这个问题，那么算法是不能被机器所解决的，机器仅仅可以解决在算法上能被机器所解决的，机器仅仅可以解决在算法上能被机器所解决的，机器仅仅可以解决在算法上能被机器所解决的，机器仅仅可以解决在算法上可解的问题可解的问题可解的问题可解的问题ooGodel的不完全定理阐述了的不完全定
42、理阐述了n n在任何传统算术领域的数学理论中，有些是既不在任何传统算术领域的数学理论中，有些是既不在任何传统算术领域的数学理论中，有些是既不在任何传统算术领域的数学理论中，有些是既不能证明有不能被推翻的能证明有不能被推翻的能证明有不能被推翻的能证明有不能被推翻的n n任何对算术系统的彻底研究都超出了算法的能力任何对算术系统的彻底研究都超出了算法的能力任何对算术系统的彻底研究都超出了算法的能力任何对算术系统的彻底研究都超出了算法的能力n n对算法的限制的研究欲望似的数学家们设计抽象对算法的限制的研究欲望似的数学家们设计抽象对算法的限制的研究欲望似的数学家们设计抽象对算法的限制的研究欲望似的数学家
43、们设计抽象的机器来执行算法，并在理论上研究这些假想机的机器来执行算法，并在理论上研究这些假想机的机器来执行算法，并在理论上研究这些假想机的机器来执行算法，并在理论上研究这些假想机器的能力。器的能力。器的能力。器的能力。4.2 数据结构数据结构：一类定性数学模型一类定性数学模型 4.2.1数据结构的基本概念数据结构的基本概念数据结构的基本概念数据结构的基本概念 oo组成：数据结构是一类定性的数学模型，它组成：数据结构是一类定性的数学模型，它由以下由以下3部分组成部分组成n n逻辑结构逻辑结构逻辑结构逻辑结构n n存储结构（或称物理结构）存储结构（或称物理结构）存储结构（或称物理结构）存储结构（或
44、称物理结构）n n运算运算运算运算oo数据逻辑结构的形式化定义数据逻辑结构的形式化定义 DS=其中：其中： D表示数据的集合；表示数据的集合； R表示数据表示数据D上关系的集合上关系的集合。数据的存储结构数据的存储结构 oo数据的存储结构是指在反映数据逻辑关系的原数据的存储结构是指在反映数据逻辑关系的原则下，数据在存储器中的存储方式。则下，数据在存储器中的存储方式。n n顺序存储结构：借助元素在存储器中的相对位置来顺序存储结构：借助元素在存储器中的相对位置来顺序存储结构：借助元素在存储器中的相对位置来顺序存储结构：借助元素在存储器中的相对位置来表示数据元素的逻辑关系。表示数据元素的逻辑关系。表
45、示数据元素的逻辑关系。表示数据元素的逻辑关系。 n n链式存储结构：借助指针来表示数据元素之间的逻链式存储结构：借助指针来表示数据元素之间的逻链式存储结构：借助指针来表示数据元素之间的逻链式存储结构：借助指针来表示数据元素之间的逻辑关系，通常在数据元素上增加一个或多个指针类辑关系，通常在数据元素上增加一个或多个指针类辑关系，通常在数据元素上增加一个或多个指针类辑关系，通常在数据元素上增加一个或多个指针类型的属性来实现这种表示方式。型的属性来实现这种表示方式。型的属性来实现这种表示方式。型的属性来实现这种表示方式。 数据结构的基本运算内容数据结构的基本运算内容 oo建立数据结构；建立数据结构；o
46、o清除数据结构；清除数据结构；oo插入数据元素；插入数据元素；oo删除数据元素；删除数据元素；oo更新数据元素；更新数据元素；oo查找数据元素；查找数据元素；oo按序重新排列；按序重新排列；oo判判定定某某个个数数据据结结构构是是否否为为空空，或或是是否否已已达达到到最大允许的容量；最大允许的容量；oo统计数据元素的个数。统计数据元素的个数。数据结构数据结构：一类定性数学模型一类定性数学模型 4.2.2 常用的几种数据结构常用的几种数据结构 线性表线性表线性表线性表oo线性表是线性表是n个数据元素的有限序列，即（个数据元素的有限序列，即（X1，X2，X3，Xi，Xn）oo基本操作基本操作插入、
47、删除和存取数据元素插入、删除和存取数据元素oo几种特殊的线性表几种特殊的线性表n n后进先出（后进先出（LastInFirstOut，简称简称LIFO）的线性表。的线性表。n n先进先出（先进先出（FirstInFirstOut，简称简称FIFO）的线性表。的线性表。n n限定所有插入、删除和存取都在表的两端进限定所有插入、删除和存取都在表的两端进行的线性表。行的线性表。 数组数组数组数组oo线性表的推广形式之一。线性表的推广形式之一。oo如在一个如在一个m n的二维数组中，每个元素的二维数组中，每个元素Ai,j都分别属于两个线性表，即都分别属于两个线性表，即（Ai,1，Ai,2，Ai,n）和
48、（和（A1,j，A2,j，Am,j）。）。树（树（树（树（TreeTree）oo由由n（n0）个结点组成的有限集合。若个结点组成的有限集合。若n=0，则称为空树，任何一个非空树均满足以下则称为空树，任何一个非空树均满足以下两个条件：两个条件：n n仅有一个称为根的结点；仅有一个称为根的结点；n n当当n0时，其余结点可分为时，其余结点可分为m（m0）个互个互不相交的有限集合，其中每个集合又是一不相交的有限集合，其中每个集合又是一棵树，并称为根的子树。棵树，并称为根的子树。 oo上图的树有上图的树有1212个结点，个结点，A A是根结点，该树又可再分为是根结点，该树又可再分为若干不相交的子树，如
49、若干不相交的子树，如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）个个结结点点组组成成的的有有限限集集合合，它它或或者者是是空空集集（n 0），或或者者由由一一个个结结点点及及两两棵棵互互不不相相交交的的子子树树
50、组组成成，且且这这两两个个子子树树有有左左、右右之之分，其次序不能任意颠倒。分，其次序不能任意颠倒。图图图图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.3 4.3 程序程序4.3.1 算法+数据结构=程序 概念概念概念概念oo从广义上讲，程序可以认为是一种行动方案或从广义上讲，程序可以认为是一种行动方案或工作步骤。例如：工作步骤。例如：n n某个会议的日程安排某个会议的日程安排n n一条旅游路
51、线的设计一条旅游路线的设计n n手工小制作的说明书等手工小制作的说明书等oo计算机程序：一种处理事务的时间顺序和处理计算机程序：一种处理事务的时间顺序和处理步骤。步骤。n n组成计算机程序的基本单位是组成计算机程序的基本单位是指令指令n n计算机程序就是按照工作步骤事先编排好的、计算机程序就是按照工作步骤事先编排好的、具有特殊功能的具有特殊功能的指令序列指令序列。 一个程序具有一个单一的、不可分的结构，它规定了某个数据结构上的一个算法。瑞士著名计算机科学家尼可莱沃思（Nikiklaus Wirth）在1976年曾提出这样一个公式： 算法算法+数据结构数据结构=程序程序 由此看来，我们前面提到的
52、算法和数据结构是计算机程序的两个最基本的概念。算法是程序的核心，它在程序编制、软件开发，乃至在整个计算机科学中都占据重要地位。数据结构是加工的对象，一个程序要进行计算或处理总是以某些数据为对象的，而要设计一个好的程序就需将这些松散的数据按某种要求组成一种数据结构。然而，随着计算机科学的发展，人们现在已经意识到程序除了以上两个主要要素外，还应包括程序的设计方法以及相应的语言工具和计算环境。 软件软件软件软件oo软件是与程序密切相关的一个概念，在计算机发展的初期，硬件设计和生产是主要问题，那时的软件就是程序。后来，随着计算技术的发展，传统软件的生产方式已不适应发展的需要，于是人们将工程学的基本原理
53、和方法引入软件设计和生产中。oo现在计算机软件一般指计算机系统中的程序及其文档，也可以指在研究、开发、维护，以及使用上述含义下的软件所涉及的理论、方法、技术所构成的分支学科。软件软件软件软件oo软件一般分为软件一般分为3类类n n系统软件：是计算机系统中最靠近硬件层次的软件。系统软件：是计算机系统中最靠近硬件层次的软件。系统软件：是计算机系统中最靠近硬件层次的软件。系统软件：是计算机系统中最靠近硬件层次的软件。如操作系统、编译程序等。如操作系统、编译程序等。如操作系统、编译程序等。如操作系统、编译程序等。n n支撑软件：是支撑其他软件的开发与维护的软件。支撑软件：是支撑其他软件的开发与维护的软
54、件。支撑软件：是支撑其他软件的开发与维护的软件。支撑软件：是支撑其他软件的开发与维护的软件。如数据库管理系统、网络软件、各种接口软件和开如数据库管理系统、网络软件、各种接口软件和开如数据库管理系统、网络软件、各种接口软件和开如数据库管理系统、网络软件、各种接口软件和开发工具等。发工具等。发工具等。发工具等。n n应用软件：是特定应用领域的专用软件。如商业会应用软件：是特定应用领域的专用软件。如商业会应用软件：是特定应用领域的专用软件。如商业会应用软件：是特定应用领域的专用软件。如商业会计软件、教学软件等。计软件、教学软件等。计软件、教学软件等。计软件、教学软件等。硬件硬件oo计算机硬件是构成计
55、算机系统的所有物理器件、计算机硬件是构成计算机系统的所有物理器件、部件、设备，以及相应的工作原理与设计、制部件、设备，以及相应的工作原理与设计、制造、检测等技术的总称。造、检测等技术的总称。oo广义的硬件包含硬件本身及其工程技术两部分。广义的硬件包含硬件本身及其工程技术两部分。其中：其中：n n计算机系统的物理元器件包括：集成电路、印制电计算机系统的物理元器件包括：集成电路、印制电计算机系统的物理元器件包括：集成电路、印制电计算机系统的物理元器件包括：集成电路、印制电路板，以及其他磁性元件、电子元件等。路板，以及其他磁性元件、电子元件等。路板，以及其他磁性元件、电子元件等。路板，以及其他磁性元
56、件、电子元件等。n n计算机系统的部件和设备包括：控制器、运算器、计算机系统的部件和设备包括：控制器、运算器、计算机系统的部件和设备包括：控制器、运算器、计算机系统的部件和设备包括：控制器、运算器、存储器、输入输出设备、电源等。存储器、输入输出设备、电源等。存储器、输入输出设备、电源等。存储器、输入输出设备、电源等。 硬件硬件oo硬件工程技术包括：印制电路板制造、高密度硬件工程技术包括：印制电路板制造、高密度组装、抗环境干扰、抗恶劣环境破坏等技术，组装、抗环境干扰、抗恶劣环境破坏等技术，以及在设计和制造过程中为提高计算机性能所以及在设计和制造过程中为提高计算机性能所采取的措施等。采取的措施等。
57、oo计算机就是由计算机硬件和计算机软件组成的。计算机就是由计算机硬件和计算机软件组成的。硬件是计算机的硬件是计算机的“躯体躯体”，软件是计算机的，软件是计算机的“灵魂灵魂”。4.4.4 4 CC1991报告提取的报告提取的核心概念核心概念 oo核心概念是核心概念是CC1991报告首次提出的，是具有报告首次提出的，是具有普遍性、持久性的重要思想、原则和方法。它普遍性、持久性的重要思想、原则和方法。它的基本特征有：的基本特征有：n n在学科中多处出现；在学科中多处出现；n n在在各各分分支支领领域域及及抽抽象象、理理论论和和设设计计的的各各个个层层面上都有很多示例；面上都有很多示例；n n在技术上
58、有高度的独立性；在技术上有高度的独立性；n n一般都在数学、科学和工程中出现。一般都在数学、科学和工程中出现。1.1.绑定绑定绑定绑定（Binding）oo绑定指的是通过将一个对象（或事物）与其某种属性相联系，从而使抽象的概念具体化的过程。例如：将一个进程与一个处理机，一个变量与其类型或值分别联系起来。这种联系的建立，实际上就是建立了某种约束。2.2.大问题的复杂性大问题的复杂性大问题的复杂性大问题的复杂性（ComplexityofLargeProblems）oo大问题的复杂性是指随着问题规模的增长而使问题的复杂性呈非线性增加的效应。这种非线性增加的效应是区分和选择各种现有方法和技术的重要因素
59、。 3. 3. 概念和形式模型概念和形式模型概念和形式模型概念和形式模型（ConceptualandFormatModels）oo概念和形式模型是对一个想法或问题进行形式化、特征化、可视化思维的方法。抽象数据类型、语义数据类型以及指定系统的图形语言，如数据流图和E-R图等都属于概念模型。而逻辑、开关理论和计算理论中的模型大都属于形式模型。概念模型和形式模型以及形式证明是将计算学科各分支统一起来的重要的核心概念。4. 4.一致性和完备性一致性和完备性一致性和完备性一致性和完备性（ConsistencyandCompleteness）oo一一致致性性包包括括用用于于形形式式说说明明的的一一组组公公
60、理理的的一一致致性性、事事实实和和理理论论的的一一致致性性，以以及及一一种种语语言言或或接接口口设设计的内部一致性。计的内部一致性。oo完完备备性性包包括括给给出出的的一一组组公公理理，使使其其能能获获得得预预期期行行为为的的充充分分性性、软软件件和和硬硬件件系系统统功功能能的的充充分分性性，以以及及系系统统处处于于出出错错和和非非预预期期情情况况下下保保持持正正常常行行为的能力等。为的能力等。oo在在计计算算机机系系统统设设计计中中，正正确确性性、健健壮壮性性和和可可靠靠性就是一致性和完备性的具体体现。性就是一致性和完备性的具体体现。5.5.效率效率效率效率（Efficiency）oo效率是
61、关于空间、时间、人力、财力等资源消耗的度量。在计算机软硬件的设计中，要充分考虑某种预期结果所达到的效率，以及一个给定的实现过程较之替代的实现过程的效率。 6 6演化演化（Evolution） 演化指的是系统的结构、状态、特征、行为和功能等随着时间的推移而发生的更改。这里主要是指了解系统更改的事实和意义及应采取的对策。在软件进行更改时，不仅要充分考虑更改对系统各层次造成的冲击，还要充分考虑到软件的有关抽象、技术和系统的适应性问题。7.7.抽象层次抽象层次抽象层次抽象层次（Levels of Abstraction）oo抽象层次指的是通过对不同层次的细节和指标的抽象对一个系统或实体进行表述。在复杂
62、系统的设计中，隐藏细节，对系统各层次进行描述（抽象），从而控制系统的复杂程度。例如，在软件工程中，从规则说明到编码各个阶段（层次）的详细说明，计算机系统的分层思想，计算机网络的分层思想等。 8. 8.按空间排序按空间排序按空间排序按空间排序（Ordering in Space）oo按空间排序指的是各种定位方式，如物理上的定位（如网络和存储中的定位），组织方式上的定位（如处理机进程、类型定义和有关操作的定位）以及概念上的定位（如软件的辖域、耦合、内聚等）。按空间排序是计算技术中一个局部性和相邻性的概念。 9.9.按时间排序按时间排序按时间排序按时间排序（Ordering in Time）oo按时
63、间排序指的是事件的执行对时间的依赖性。例如，在具有时态逻辑的系统中，要考虑与时间有关的时序问题；在分布式系统中，要考虑进程同步的时间问题；在依赖于时间的算法执行中，要考虑其基本的组成要素。 10.10.重用重用重用重用（Reuse）oo重用指的是在新的环境下，系统中各类实体、技术、概念等可被再次使用的能力。如软件库和硬件部件的重用等。 11.11.安全性安全性安全性安全性（Security）oo安全性指的是计算机软硬件系统对合法用户的响应及对非法请求的抗拒，以保护自己不受外部影响和攻击的能力。如为防止数据的丢失、泄密而在数据库管理系统中提供的口令更换、操作员授权等功能。 12.12.折衷与结论折衷与结论折衷与结论折衷与结论（Tradeoff and Consequences）oo指的是为满足系统的可实施性而对系统设计中的技术、方案所作出的一种合理的取舍。结论是折衷的结论，即选择一种方案代替另一种方案所产生的技术、经济、文化及其他方面的影响。折衷是存在于计算学科领域各层次上的基本事实。如在算法的研究中，要考虑空间和时间的折衷；对于矛盾的设计目标，要考虑诸如易用性和完备性、灵活性和简单性、低成本和高可靠性等方面所采取的折衷等。
