【教学课件】第4章计算学科中的核心概念.ppt

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

1、第第4 4章计算学科中的核章计算学科中的核心概念心概念李陶深李陶深 第第4章计算学科中的核章计算学科中的核 心概念心概念4.1 算法算法的历史简介算法的历史简介算法的历史简介算法的历史简介 oo公元公元825年，阿拉伯数学家阿科瓦里茨米年，阿拉伯数学家阿科瓦里茨米（AlKhowarizmi）写了著名的波斯教科书写了著名的波斯教科书（Persian Textbook），），书中概括了进行四则算书中概括了进行四则算术运算的法则。术运算的法则。n n“算法算法算法算法”（AlgorithmAlgorithm）一词就来源于这位数学家一词就来源于这位数学家一词就来源于这位数学家一词就来源于这位数学家的名

2、字。的名字。的名字。的名字。oo后来，韦氏新世界词典将其定义为后来，韦氏新世界词典将其定义为“解某解某种问题的任何专门的方法种问题的任何专门的方法”。oo而据考古学家发现，古巴比伦人在而据考古学家发现，古巴比伦人在求解代数方求解代数方程程时，就已经采用了时，就已经采用了“算法算法”的思想。的思想。丢番图方程的可解性问题丢番图方程的可解性问题丢番图方程的可解性问题丢番图方程的可解性问题 oo古希腊数学家丢番图（古希腊数学家丢番图（Diophantus）：代数学：代数学之父之父n n在算术（在算术（在算术（在算术（ArithmeticaArithmetica）一书中提出了有关一书中提出了有关一书中

3、提出了有关一书中提出了有关两两两两个或多个变量整数系数方程个或多个变量整数系数方程个或多个变量整数系数方程个或多个变量整数系数方程的有理数解问题。的有理数解问题。的有理数解问题。的有理数解问题。n n对于具有对于具有对于具有对于具有整数系数的不定方程整数系数的不定方程整数系数的不定方程整数系数的不定方程，如果只考虑其，如果只考虑其，如果只考虑其，如果只考虑其整数整数整数整数解解解解，这类方程就叫做丢番图方程。，这类方程就叫做丢番图方程。，这类方程就叫做丢番图方程。，这类方程就叫做丢番图方程。oo“丢番图方程可解性问题丢番图方程可解性问题”的实质为：能否写的实质为：能否写出一个可以判定出一个可以

4、判定任意丢番图方程是否可解任意丢番图方程是否可解的算的算法？法？一个未知数的线性丢番图方程的解一个未知数的线性丢番图方程的解一个未知数的线性丢番图方程的解一个未知数的线性丢番图方程的解ooaxax=b b，只只要要a a能能整整除除b b，就就可可判判定定其其有有整整数数解，该整数解即解，该整数解即b b/a a。两个未知数的线性丢番图方程两个未知数的线性丢番图方程两个未知数的线性丢番图方程两个未知数的线性丢番图方程 的解的解的解的解ooaxax+byby=c c，先求出先求出a a和和b b的最大公因子的最大公因子d d，若若d d能能整除整除c c，则该方程有解（整数解）。则该方程有解（整

5、数解）。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即方程的解）。即方程的解）。即方程的解）。即方程的解）。oo例例4.2 4.2 问：方程问：方程2 2x x+4+4y y=15=15有无整数解？有无整数

6、解？n n答：答：答：答：2 2 2 2和和和和4 4 4 4的最大公因子是的最大公因子是的最大公因子是的最大公因子是2 2 2 2，2 2 2 2不能整除不能整除不能整除不能整除15151515，故该方，故该方，故该方，故该方程无整数解。程无整数解。程无整数解。程无整数解。两个未知数的线性丢番图方程两个未知数的线性丢番图方程两个未知数的线性丢番图方程两个未知数的线性丢番图方程 的解：的解：的解：的解：欧几里德算法欧几里德算法欧几里德算法欧几里德算法 oo给给定定两两个个正正整整数数m和和n，求求它它们们的的最最大大公公因因子子，即能同时整除即能同时整除m和和n的最大正整数。的最大正整数。oo

7、步骤如下：步骤如下：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置置置置换换换换为为为为n n，并并并并返返返返回回回回步步步步骤骤骤骤（1 1）继续进行。继续进行。继续进行。继续进行。例例例例4.34.3设设设设mm

8、=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又又又又表表表表述述述述了了了了一一一一个个个个判判判判定定定定过过过过程程程程，该该该该过过过过程程程程可可可可以以以以判判判判定定定定“mm和和和和n n是是是是互互互互质质质质的的的的”（即即即即除

9、除除除1 1以以以以外外外外，mm和和和和n n没没没没有有有有公公公公因因因因子子子子）这这这这个个个个命题的真假。命题的真假。命题的真假。命题的真假。算法算法算法的定义和特征算法的定义和特征 1算法的非形式化定义算法的非形式化定义 oo一个算法，就是一个有穷规则的集合，其中之一个算法，就是一个有穷规则的集合，其中之规则规定了一个解决某一特定类型问题的运算规则规定了一个解决某一特定类型问题的运算序列。序列。算法的定义和特征算法的定义和特征2 2算法的重要特性算法的重要特性算法的重要特性算法的重要特性oo有穷性：一个算法在执行有穷步之后必须结束。有穷性：一个算法在执行有穷步之后必须结束。oo确

10、确定定性性：算算法法的的每每一一个个步步骤骤必必须须要要确确切切地地定定义义。即即算算法法中中所所有有有有待待执执行行的的动动作作必必须须严严格格而而不不含含混地进行规定，不能有歧义性。混地进行规定，不能有歧义性。oo输输入入：算算法法有有零零个个或或多多个个的的输输入入，即即在在算算法法开开始之前，对算法最初给出的量。始之前，对算法最初给出的量。oo输输出出：算算法法有有一一个个或或多多个个的的输输出出，即即与与输输入入有有某某个个特特定定关关系系的的量量，简简单单地地说说就就是是算算法法的的最最终终结果。结果。oo能能行行性性：算算法法中中有有待待执执行行的的运运算算和和操操作作必必须须是

11、是相当基本的，相当基本的，3算法的形式化定义算法的形式化定义 算法是一个四元组，即（算法是一个四元组，即（Q，I，F）。）。其中：其中：（1）Q是是一一个个包包含含子子集集I和和的的集集合合，它它表表示示计计算算的状态；的状态；（2）I表示计算的输入集合；表示计算的输入集合；（3）表示计算的输出集合；表示计算的输出集合；（4）F表表示示计计算算的的规规则则，它它是是一一个个由由Q到到它它自自身身的的函函数数，且且具具有有自自反反性性，即即对对于于任任何何一一个个元元素素qQ，有有F(q)=q。算法算法算法实例算法实例 例例4.4求求1+2+3+100 设设变变量量X表表示示加加数数，Y表表示示

12、被被加加数数，用用自自然然语语言言将将算法描述如下：算法描述如下：（1）将）将1赋值给赋值给X；（2）将将2赋值给赋值给Y；（3）将将X与与Y相加，结果存放在相加，结果存放在X中；中；（4）将）将Y加加1，结果存放在，结果存放在Y中；中；（5）若若Y小小于于或或等等于于100，转转到到步步骤骤（3）继继续续执执行；否则，算法结束，结果为行；否则，算法结束，结果为X。例例4.5求解调和级数求解调和级数设变量设变量X表示累加和，变量表示累加和，变量I表示循环的次数，自表示循环的次数，自然语言描述算法如下：然语言描述算法如下：（1）将）将0赋值给赋值给X；（2）将将1赋值给赋值给I；（3）将将X与与

13、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年年 意意 大大 利利 数数 学学 家家 斐斐 波波 那那 契契（L.P.FibonacciL.P.Fibonacci）在在其其珠珠算算之之书书（Liber Liber AbaciAbaci）中

14、提出的一个中提出的一个“兔子问题兔子问题”：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+F Fn n，n n00oo斐斐波波那那契契数数列列还还是是一一个个关关于于加加法法算算法法的的典典型型实例。实例。oo设变量设变量X表示前一个数的值，即定义中的表示

16、前一个数的值，即定义中的Fn，变量变量Y表示当前数的值，即定义中的表示当前数的值，即定义中的Fn+1，变量变量Z表示后一个数的值，即定义中的表示后一个数的值，即定义中的Fn+2。那么求那么求解问题的自然语言描述如下：解问题的自然语言描述如下：算法设计算法设计算法设计算法设计（1 1）如如如如果果果果=0=0，那那那那么么么么将将将将0 0赋赋赋赋值值值值给给给给Y Y，并并并并输输输输出出出出Y Y，转转转转步步步步骤骤骤骤（1111）继续执行；）继续执行；）继续执行；）继续执行；（2 2）将）将）将）将0 0赋给赋给赋给赋给X X，将将将将1 1赋值给赋值给赋值给赋值给Y Y；（3 3）输出

17、输出输出输出X X、Y Y；（4 4）将将将将1 1赋值给赋值给赋值给赋值给I I；（5 5）如果如果如果如果I I大于大于大于大于-1-1，则转到步骤（，则转到步骤（，则转到步骤（，则转到步骤（1111），否则继续执行；），否则继续执行；），否则继续执行；），否则继续执行；（6 6）将）将）将）将X X和和和和Y Y的和赋值给的和赋值给的和赋值给的和赋值给Z Z；（7 7）将将将将Y Y赋值给赋值给赋值给赋值给X X；（8 8）将将将将Z Z赋值给赋值给赋值给赋值给Y Y；（9 9）将将将将Y Y输出；输出；输出；输出；（1010）将）将）将）将I I加加加加1 1，转步骤（，转步骤（，转步

18、骤（，转步骤（5 5）继续执行；）继续执行；）继续执行；）继续执行；（1111）算法结束。）算法结束。）算法结束。）算法结束。算法算法算法的表示方法算法的表示方法原语原语原语原语oo一个算法的表达需要使用一些语言形式一个算法的表达需要使用一些语言形式n n自然语言自然语言自然语言自然语言“VisitinggrandchildrencanbeVisitinggrandchildrencanbenerve-racking”,nerve-racking”,可能即意味着孙子孙女导致了很可能即意味着孙子孙女导致了很可能即意味着孙子孙女导致了很可能即意味着孙子孙女导致了很多问题，也表示去看他们可能会有问题

19、多问题，也表示去看他们可能会有问题多问题，也表示去看他们可能会有问题多问题，也表示去看他们可能会有问题n n图形语言：很少人能够根据折纸图给出的步骤成图形语言：很少人能够根据折纸图给出的步骤成图形语言：很少人能够根据折纸图给出的步骤成图形语言：很少人能够根据折纸图给出的步骤成功地叠出一只鸟来，但一个专门学习过折纸的学功地叠出一只鸟来，但一个专门学习过折纸的学功地叠出一只鸟来，但一个专门学习过折纸的学功地叠出一只鸟来，但一个专门学习过折纸的学生可以轻松完成生可以轻松完成生可以轻松完成生可以轻松完成oo当用来描述算法的语言并没有被准确定义或当用来描述算法的语言并没有被准确定义或者没有给予足够信息的

20、时候，交流就会产生者没有给予足够信息的时候，交流就会产生问题问题原语原语原语原语oo通过建立一个可以描述算法的意义明确的基本通过建立一个可以描述算法的意义明确的基本块（块（原语原语）集合，计算机科学即就可以解决上）集合，计算机科学即就可以解决上述的勾通问题述的勾通问题oo原语描述算法需要建立一个统一的细节描述级原语描述算法需要建立一个统一的细节描述级别，原语连同一组表达了原语如何表达复杂的别，原语连同一组表达了原语如何表达复杂的想法的规定组成了一种程序设计语言想法的规定组成了一种程序设计语言oo组成组成n n语法：原语的符号表示语法：原语的符号表示语法：原语的符号表示语法：原语的符号表示n n

21、语义：表达了原语的意义语义：表达了原语的意义语义：表达了原语的意义语义：表达了原语的意义1 1自然语言自然语言自然语言自然语言oo缺点缺点n n由由由由于于于于自自自自然然然然语语语语言言言言的的的的歧歧歧歧义义义义性性性性，容容容容易易易易导导导导致致致致算算算算法法法法执执执执行行行行的的的的不确定性；不确定性；不确定性；不确定性；n n自自自自然然然然语语语语言言言言的的的的语语语语句句句句一一一一般般般般太太太太长长长长，从从从从而而而而导导导导致致致致了了了了用用用用自自自自然然然然语言描述的算法太长；语言描述的算法太长；语言描述的算法太长；语言描述的算法太长；n n由由由由于于于于

22、自自自自然然然然语语语语言言言言表表表表示示示示的的的的串串串串行行行行性性性性，因因因因此此此此，当当当当一一一一个个个个算算算算法中循环和分支较多时就很难清晰地表示出来；法中循环和分支较多时就很难清晰地表示出来；法中循环和分支较多时就很难清晰地表示出来；法中循环和分支较多时就很难清晰地表示出来；n n自自自自然然然然语语语语言言言言表表表表示示示示的的的的算算算算法法法法不不不不便便便便翻翻翻翻译译译译成成成成计计计计算算算算机机机机程程程程序序序序设设设设计语言理解的语言。计语言理解的语言。计语言理解的语言。计语言理解的语言。2 2流程图流程图流程图流程图 oo它它 采采 用用 美美 国

23、国 国国 家家 标标 准准 化化 协协 会会ANSI（AmericanNationalStandardInstitute）规定的一组图形符号来表示算法。规定的一组图形符号来表示算法。n n流流流流程程程程图图图图可可可可以以以以很很很很方方方方便便便便地地地地表表表表示示示示顺顺顺顺序序序序、选选选选择择择择和和和和循循循循环环环环结结结结构构构构，而而而而任任任任何何何何程程程程序序序序的的的的逻逻逻逻辑辑辑辑结结结结构构构构都都都都可可可可以以以以用用用用顺顺顺顺序序序序、选选选选择择择择和和和和循循循循环结构来表示，环结构来表示，环结构来表示，环结构来表示，n n流程图可以表示任何程序的

24、逻辑结构。流程图可以表示任何程序的逻辑结构。流程图可以表示任何程序的逻辑结构。流程图可以表示任何程序的逻辑结构。n n用用用用流流流流程程程程图图图图表表表表示示示示的的的的算算算算法法法法不不不不依依依依赖赖赖赖于于于于任任任任何何何何具具具具体体体体的的的的计计计计算算算算机机机机和计算机程序设计语言，和计算机程序设计语言，和计算机程序设计语言，和计算机程序设计语言，（1 1）求解例）求解例）求解例）求解例4.44.4的算法流程图的算法流程图的算法流程图的算法流程图（2 2）求解例）求解例）求解例）求解例4.54.5的算法流程图的算法流程图的算法流程图的算法流程图（3 3）求解例）求解例）

25、求解例）求解例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（算法结束）算法结束）算法结束）算法结束）（3 3）例）例）例）例4.64.6的伪代码算法描述：的伪代码算法描述：的伪代码算法描述：的伪代码算法描述：BEGINBEGINifn=0ifn=0 0 0YYPrintY

26、PrintY 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计计算算机机程程序序设设计计语语言言描描述述的的算算法法（程程序序）是是清晰的、简明的，最终也能由计算机处理的。清晰的、简明的，最终也能由计算机处理的。oo缺点：缺点：n n算算算算法法法法的的的的基基基基本本本本逻逻逻逻辑辑辑辑流流流流程程程程难难难难于于于于遵遵遵遵循循循循。与与与与自自自

27、自然然然然语语语语言言言言一一一一样样样样，程序设计语言也是基于串行的程序设计语言也是基于串行的程序设计语言也是基于串行的程序设计语言也是基于串行的n n用用用用特特特特定定定定程程程程序序序序设设设设计计计计语语语语言言言言编编编编写写写写的的的的算算算算法法法法限限限限制制制制了了了了与与与与他他他他人人人人的的的的交流，不利于问题的解决；交流，不利于问题的解决；交流，不利于问题的解决；交流，不利于问题的解决；n n要要要要花花花花费费费费大大大大量量量量的的的的时时时时间间间间去去去去熟熟熟熟悉悉悉悉和和和和掌掌掌掌握握握握某某某某种种种种特特特特定定定定的的的的程程程程序序序序设计语言

28、；设计语言；设计语言；设计语言；n n要求描述计算步骤的细节，而忽视算法的本质。要求描述计算步骤的细节，而忽视算法的本质。要求描述计算步骤的细节，而忽视算法的本质。要求描述计算步骤的细节，而忽视算法的本质。例例例例4.44.4的计算机程序设计语言（的计算机程序设计语言（的计算机程序设计语言（的计算机程序设计语言（C C语言）的算法描述：语言）的算法描述：语言）的算法描述：语言）的算法描述：main()main()intX,Y;intX,Y;X=1;X=1;Y=2;Y=2;while(Y=100)while(Y=100)X=X+Y;X=X+Y;Y=Y+1;Y=Y+1;printf(%d,X);p

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

30、tf(n%f,X);算法算法算法分析算法分析（1 1）算法的时间复杂度；）算法的时间复杂度；）算法的时间复杂度；）算法的时间复杂度；oo用用T(n)表示，表示，n表示问题规模的大小。表示问题规模的大小。oo使用一个记号使用一个记号 n nOrderOrder（数量级）的第一个字母，数量级）的第一个字母，数量级）的第一个字母，数量级）的第一个字母，n n允许使用允许使用允许使用允许使用“=”“=”代替代替代替代替“”“”。如。如。如。如n n2 2+n n+1=+1=(n n2 2)oo设设f(n)是是一一个个关关于于正正整整数数n的的函函数数，若若存存在在一一个个正正整整数数n0和和一一个个常

31、常数数C，当当nn0时时，T(n)Cf(n)均均成成立立，则则称称f(n)为为T(n)的的同同数数量量级级的的函函数。数。n n算法时间复杂度算法时间复杂度算法时间复杂度算法时间复杂度T T(n n)可表示为：可表示为：可表示为：可表示为：T(n)=(f(n)常见的大常见的大常见的大常见的大 表示形式有：表示形式有：表示形式有：表示形式有：(1)：称为常数级；：称为常数级；(logn)：称为对数级；称为对数级；(n)：称为线性级；：称为线性级；(nc)：称为多项式级；：称为多项式级；(cn)：称为指数级；：称为指数级；(n!)：称为阶乘级。：称为阶乘级。算法的空间复杂度算法的空间复杂度算法的空

32、间复杂度算法的空间复杂度oo指算法在执行过程中所占存储空间的大小，指算法在执行过程中所占存储空间的大小，oo用用S(n)表示，表示，S为英文单词为英文单词Space的第一个字的第一个字母。与算法的时间复杂度相同母。与算法的时间复杂度相同oo算法的空间复杂度算法的空间复杂度S(n)也可表示为：也可表示为：S(n)=(g(n)。算法算法算法的研究算法的研究算法算法oo算法：定义一向工作如何完成的步骤的集合算法：定义一向工作如何完成的步骤的集合n n在一台机器可以完成一个任务之前，必须找到完在一台机器可以完成一个任务之前，必须找到完在一台机器可以完成一个任务之前，必须找到完在一台机器可以完成一个任务

33、之前，必须找到完成这个任务的算法并且用与机器兼容的方式来描成这个任务的算法并且用与机器兼容的方式来描成这个任务的算法并且用与机器兼容的方式来描成这个任务的算法并且用与机器兼容的方式来描述述述述n n一个与机器兼容的算法的描述一个与机器兼容的算法的描述一个与机器兼容的算法的描述一个与机器兼容的算法的描述程序程序程序程序oo算法的研究开始是作为数学的一个学科算法的研究开始是作为数学的一个学科n n目标：找到描述特定类型问题是如何被解决的指目标：找到描述特定类型问题是如何被解决的指目标：找到描述特定类型问题是如何被解决的指目标：找到描述特定类型问题是如何被解决的指令的集合，如令的集合，如令的集合，如

34、令的集合，如EuclideanEuclidean算法算法算法算法n n一旦一个完成任务的算法被找到，任务的实现就一旦一个完成任务的算法被找到，任务的实现就一旦一个完成任务的算法被找到，任务的实现就一旦一个完成任务的算法被找到，任务的实现就不再需要对算法原理的理解，任务的实现仅仅是不再需要对算法原理的理解，任务的实现仅仅是不再需要对算法原理的理解，任务的实现仅仅是不再需要对算法原理的理解，任务的实现仅仅是遵循算法的只是过程遵循算法的只是过程遵循算法的只是过程遵循算法的只是过程n n现有的解决问题需要的智慧被编码进了算法现有的解决问题需要的智慧被编码进了算法现有的解决问题需要的智慧被编码进了算法现

35、有的解决问题需要的智慧被编码进了算法算法转化为智慧算法转化为智慧算法转化为智慧算法转化为智慧oo通过使用算法来得到并转化智慧，我们才可以通过使用算法来得到并转化智慧，我们才可以构建起可以表现构建起可以表现智慧行为的机器智慧行为的机器。n n机器表现的智能等级受到通过算法转化的智慧所限机器表现的智能等级受到通过算法转化的智慧所限机器表现的智能等级受到通过算法转化的智慧所限机器表现的智能等级受到通过算法转化的智慧所限制制制制n n如果没有解决问题的算法，意味着问题的解决方案如果没有解决问题的算法，意味着问题的解决方案如果没有解决问题的算法，意味着问题的解决方案如果没有解决问题的算法，意味着问题的解

36、决方案超出了机器的能力范围超出了机器的能力范围超出了机器的能力范围超出了机器的能力范围oo算法的开发就成了计算机领域的一个主要目标算法的开发就成了计算机领域的一个主要目标n n如何找到算法如何找到算法如何找到算法如何找到算法一个十分接近于寻找通用问题解一个十分接近于寻找通用问题解一个十分接近于寻找通用问题解一个十分接近于寻找通用问题解决方案决方案决方案决方案n n描述这个算法描述这个算法描述这个算法描述这个算法转变为一个清晰的指令的集合转变为一个清晰的指令的集合转变为一个清晰的指令的集合转变为一个清晰的指令的集合（程序设计语言描述）（程序设计语言描述）（程序设计语言描述）（程序设计语言描述）计

37、算机技术别用于复杂问题（大型软件系统）计算机技术别用于复杂问题（大型软件系统）计算机技术别用于复杂问题（大型软件系统）计算机技术别用于复杂问题（大型软件系统）oo不仅仅包括实现任务的单个算法的开发不仅仅包括实现任务的单个算法的开发n n还要求对组件之间的交互进行设计还要求对组件之间的交互进行设计还要求对组件之间的交互进行设计还要求对组件之间的交互进行设计n n软件工程：借鉴了工程领域、项目管理领域、人软件工程：借鉴了工程领域、项目管理领域、人软件工程：借鉴了工程领域、项目管理领域、人软件工程：借鉴了工程领域、项目管理领域、人力资源管理以及程序语言设计领域的经验力资源管理以及程序语言设计领域的经

38、验力资源管理以及程序语言设计领域的经验力资源管理以及程序语言设计领域的经验执行算法的机器的设计和实现执行算法的机器的设计和实现执行算法的机器的设计和实现执行算法的机器的设计和实现oo数据的存储数据的存储oo数据的操作数据的操作oo体系结构中涵盖了对现今技术的讨论体系结构中涵盖了对现今技术的讨论n n我们的目标不是去熟知类似当今体系结构是我们的目标不是去熟知类似当今体系结构是如何用电路来实现这样的细节问题，那将会如何用电路来实现这样的细节问题，那将会导致过分陷入电子工程学科导致过分陷入电子工程学科n n正如昨天的齿轮驱动的计算机让位于电子设正如昨天的齿轮驱动的计算机让位于电子设备一样，今天的电子

39、技术也许很快也被其它备一样，今天的电子技术也许很快也被其它的技术所取代的技术所取代理想情况下理想情况下oo希望计算机的体系结构是我们的有关算法过程希望计算机的体系结构是我们的有关算法过程知识的延续，并且不应该被技术能力酸限制知识的延续，并且不应该被技术能力酸限制n n使我们的算法知识在当代机器体系结构的发使我们的算法知识在当代机器体系结构的发展背后起推动作用，而不仅仅是从技术的要展背后起推动作用，而不仅仅是从技术的要求触发来解顶机器的设计求触发来解顶机器的设计oo构建允许使用多个指令序列来代替算法的机器构建允许使用多个指令序列来代替算法的机器是可能的是可能的n n这些指令被同时执行或者作为这些

40、指令被同时执行或者作为机器于外部世界的接口的设计于计算机的设计紧密相连机器于外部世界的接口的设计于计算机的设计紧密相连机器于外部世界的接口的设计于计算机的设计紧密相连机器于外部世界的接口的设计于计算机的设计紧密相连oo算法是如何机器中的？算法是如何机器中的？oo机器是如何被告知执行的是哪一个算法？机器是如何被告知执行的是哪一个算法？计算理论计算理论oo对解决越来越复杂问题的算法的研究对解决越来越复杂问题的算法的研究n n导致了算法过程的最终限制问题导致了算法过程的最终限制问题导致了算法过程的最终限制问题导致了算法过程的最终限制问题n n如果没有算法可以解决这个问题，那么算法是不如果没有算法可以

41、解决这个问题，那么算法是不如果没有算法可以解决这个问题，那么算法是不如果没有算法可以解决这个问题，那么算法是不能被机器所解决的，机器仅仅可以解决在算法上能被机器所解决的，机器仅仅可以解决在算法上能被机器所解决的，机器仅仅可以解决在算法上能被机器所解决的，机器仅仅可以解决在算法上可解的问题可解的问题可解的问题可解的问题ooGodel的不完全定理阐述了的不完全定理阐述了n n在任何传统算术领域的数学理论中，有些是既不在任何传统算术领域的数学理论中，有些是既不在任何传统算术领域的数学理论中，有些是既不在任何传统算术领域的数学理论中，有些是既不能证明有不能被推翻的能证明有不能被推翻的能证明有不能被推翻

42、的能证明有不能被推翻的n n任何对算术系统的彻底研究都超出了算法的能力任何对算术系统的彻底研究都超出了算法的能力任何对算术系统的彻底研究都超出了算法的能力任何对算术系统的彻底研究都超出了算法的能力n n对算法的限制的研究欲望似的数学家们设计抽象对算法的限制的研究欲望似的数学家们设计抽象对算法的限制的研究欲望似的数学家们设计抽象对算法的限制的研究欲望似的数学家们设计抽象的机器来执行算法，并在理论上研究这些假想机的机器来执行算法，并在理论上研究这些假想机的机器来执行算法，并在理论上研究这些假想机的机器来执行算法，并在理论上研究这些假想机器的能力。器的能力。器的能力。器的能力。4.2 数据结构数据结

43、构：一类定性数学模型一类定性数学模型 4.2.1数据结构的基本概念数据结构的基本概念数据结构的基本概念数据结构的基本概念 oo组成：数据结构是一类定性的数学模型，它组成：数据结构是一类定性的数学模型，它由以下由以下3部分组成部分组成n n逻辑结构逻辑结构逻辑结构逻辑结构n n存储结构（或称物理结构）存储结构（或称物理结构）存储结构（或称物理结构）存储结构（或称物理结构）n n运算运算运算运算oo数据逻辑结构的形式化定义数据逻辑结构的形式化定义 DS=其中：其中：D表示数据的集合；表示数据的集合；R表示数据表示数据D上关系的集合上关系的集合。数据的存储结构数据的存储结构 oo数据的存储结构是指在

44、反映数据逻辑关系的原数据的存储结构是指在反映数据逻辑关系的原则下，数据在存储器中的存储方式。则下，数据在存储器中的存储方式。n n顺序存储结构：借助元素在存储器中的相对位置来顺序存储结构：借助元素在存储器中的相对位置来顺序存储结构：借助元素在存储器中的相对位置来顺序存储结构：借助元素在存储器中的相对位置来表示数据元素的逻辑关系。表示数据元素的逻辑关系。表示数据元素的逻辑关系。表示数据元素的逻辑关系。n n链式存储结构：借助指针来表示数据元素之间的逻链式存储结构：借助指针来表示数据元素之间的逻链式存储结构：借助指针来表示数据元素之间的逻链式存储结构：借助指针来表示数据元素之间的逻辑关系，通常在数

45、据元素上增加一个或多个指针类辑关系，通常在数据元素上增加一个或多个指针类辑关系，通常在数据元素上增加一个或多个指针类辑关系，通常在数据元素上增加一个或多个指针类型的属性来实现这种表示方式。型的属性来实现这种表示方式。型的属性来实现这种表示方式。型的属性来实现这种表示方式。数据结构的基本运算内容数据结构的基本运算内容 oo建立数据结构；建立数据结构；oo清除数据结构；清除数据结构；oo插入数据元素；插入数据元素；oo删除数据元素；删除数据元素；oo更新数据元素；更新数据元素；oo查找数据元素；查找数据元素；oo按序重新排列；按序重新排列；oo判判定定某某个个数数据据结结构构是是否否为为空空，或或

46、是是否否已已达达到到最大允许的容量；最大允许的容量；oo统计数据元素的个数。统计数据元素的个数。数据结构数据结构：一类定性数学模型一类定性数学模型 4.2.2 常用的几种数据结构常用的几种数据结构 线性表线性表线性表线性表oo线性表是线性表是n个数据元素的有限序列，即（个数据元素的有限序列，即（X1，X2，X3，Xi，Xn）oo基本操作基本操作插入、删除和存取数据元素插入、删除和存取数据元素oo几种特殊的线性表几种特殊的线性表n n后进先出（后进先出（LastInFirstOut，简称简称LIFO）的线性表。的线性表。n n先进先出（先进先出（FirstInFirstOut，简称简称FIFO）

47、的线性表。的线性表。n n限定所有插入、删除和存取都在表的两端进限定所有插入、删除和存取都在表的两端进行的线性表。行的线性表。数组数组数组数组oo线性表的推广形式之一。线性表的推广形式之一。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仅

48、有一个称为根的结点；仅有一个称为根的结点；n n当当n0时，其余结点可分为时，其余结点可分为m（m0）个互个互不相交的有限集合，其中每个集合又是一不相交的有限集合，其中每个集合又是一棵树，并称为根的子树。棵树，并称为根的子树。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个结点，个结点，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等。等。二叉树二叉树二叉树二叉树oon（n0）个个结结点点组组成成的的有有限限集集合合，它它或或者者是是空空集集（n 0），或或者者由由一一个个结结点点及及两两棵棵互互不不相相交交的的子子树树组组成成，且且这这两两个个子子树树有有左左、右右之之分，其次序不能任意颠倒。分，其次序不能任意颠倒。图图图图oo由结点和连接这些结点的边所组成的集合。oo图的形式化定义为：G=其中：V是一个非空结点的集合；E是连结结点的边的集合。例例G=其中其中V=A，

50、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一条旅游路线的设计一条旅游路线的设计n n手工小制作的说明书等手工小制作的说明书等oo计算机程序：一种处理事务的时间顺序和处理计算机程序：一种处理事务的时间顺序和处理步骤。步骤。n n组成计算机程序的基本单位是组成计算机程序的基本单位是指令指令n n计算机程序就是按照工作步骤