第4章计算学科中的核心概念.ppt

《第4章计算学科中的核心概念.ppt》由会员分享，可在线阅读，更多相关《第4章计算学科中的核心概念.ppt（79页珍藏版）》请在三一文库上搜索。

1、第4章 计算学科中的核 心概念,李陶深 ,第4章 计算学科中的核 心概念,4.1 算法,算法的历史简介,公元825年，阿拉伯数学家阿科瓦里茨米（AlKhowarizmi）写了著名的波斯教科书（Persian Textbook），书中概括了进行四则算术运算的法则。 “算法”（Algorithm）一词就来源于这位数学家的名字。 后来，韦氏新世界词典将其定义为“解某种问题的任何专门的方法”。 而据考古学家发现，古巴比伦人在求解代数方程时，就已经采用了“算法”的思想。,丢番图方程的可解性问题,古希腊数学家丢番图（Diophantus）：代数学之父 在算术（Arithmetica）一书中提出了有关两个或

2、多个变量整数系数方程的有理数解问题。 对于具有整数系数的不定方程，如果只考虑其整数解，这类方程就叫做丢番图方程。 “丢番图方程可解性问题”的实质为：能否写出一个可以判定任意丢番图方程是否可解的算法？,一个未知数的线性丢番图方程的解,ax=b，只要a能整除b，就可判定其有整数解，该整数解即b/a。,两个未知数的线性丢番图方程 的解,ax+by=c，先求出a和b的最大公因子d，若d能整除c，则该方程有解（整数解）。 问：方程13x+26y=52有无整数解？ 答：13和26的最大公因子是13，13又可整除52，故该方程有整数解（如x=2，y=1即方程的解）。 例4.2 问：方程2x+4y=15有无整

3、数解？ 答：2和4的最大公因子是2，2不能整除15，故该方程无整数解。,两个未知数的线性丢番图方程 的解：欧几里德算法,给定两个正整数m和n，求它们的最大公因子，即能同时整除m和n的最大正整数。 步骤如下： （1）以n除m，并令所得余数为r（r必小于n）； （2）若r=0，算法结束，输出结果n；否则，继续步骤（3）； （3）将n置换为m，r置换为n，并返回步骤（1）继续进行。,例4.3 设m=56，n=32，求m、n的最大公因子,算法如下: （1）32除56余数为24； （2）24除32余数为8； （3）8除24余数为0，算法结束，输出结果8。 答：m、n的最大公因子为8。 欧几里德算法既表述

4、了一个数的求解过程， 又表述了一个判定过程，该过程可以判定“m和n是互质的”（即除1以外，m和n没有公因子）这个命题的真假。,算法,算法的定义和特征,1算法的非形式化定义,一个算法，就是一个有穷规则的集合，其中之规则规定了一个解决某一特定类型问题的运算序列。,算法的定义和特征,2算法的重要特性,有穷性：一个算法在执行有穷步之后必须结束。 确定性：算法的每一个步骤必须要确切地定义。即算法中所有有待执行的动作必须严格而不含混地进行规定，不能有歧义性。 输入：算法有零个或多个的输入，即在算法开始之前，对算法最初给出的量。 输出：算法有一个或多个的输出，即与输入有某个特定关系的量，简单地说就是算法的最

5、终结果。 能行性：算法中有待执行的运算和操作必须是相当基本的，,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表示被加数，用自然语言将算法描述如下： （1）将1赋值给X； （2）将2赋值给Y； （3）将X与Y相加，结果存放在X中； （4）将Y加1，结果存放在Y中； （5）若Y小于或等于100

6、，转到步骤（3）继续执行；否则，算法结束，结果为X。,例4.5 求解调和级数,设变量X表示累加和，变量I表示循环的次数，自然语言描述算法如下： （1）将0赋值给X； （2）将1赋值给I； （3）将X与1/I相加，然后把结果存入X； （4）将I加1； （5）若I大于等于N，算法结束，结果为X；否则转到步骤（3）继续执行。,例4.6 求解斐波那契数,0，1，1，2，3，5，8，13，21，34， （1） 来源于1202年意大利数学家斐波那契（L.P.Fibonacci）在其珠算之书（Liber Abaci）中提出的一个“兔子问题”： 假设一对刚出生的兔子一个月后就能长大，再过一个月就能生下一对兔子

7、，并且此后每个月都能生一对兔子，且新生的兔子在第二个月后也是每个月生一对兔子。 问：一对兔子一年内可繁殖成多少对兔子？,在序列（1）中，每个数都是它的前两个数之和，Fn表示这个序列的第n个数，该序列可以形式化的定义为： F0=0，F1=1，Fn+2=Fn+1+Fn，n0 斐波那契数列还是一个关于加法算法的典型实例。,设变量X表示前一个数的值，即定义中的Fn，变量Y表示当前数的值，即定义中的Fn+1，变量Z表示后一个数的值，即定义中的Fn+2。那么求解问题的自然语言描述如下：,算法设计,（1）如果=0，那么将0赋值给Y，并输出Y，转步骤（11）继续执行； （2）将0赋给X，将1赋值给Y； （3）

8、输出X、Y； （4）将1赋值给I； （5）如果I大于-1，则转到步骤（11），否则继续执行； （6）将X和Y的和赋值给Z； （7）将Y赋值给X； （8）将Z赋值给Y； （9）将Y输出； （10）将I加1，转步骤（5）继续执行； （11）算法结束。,算法,算法的表示方法,原语,一个算法的表达需要使用一些语言形式 自然语言“Visiting grandchildren can be nerve-racking”,可能即意味着孙子孙女导致了很多问题，也表示去看他们可能会有问题 图形语言：很少人能够根据折纸图给出的步骤成功地叠出一只鸟来，但一个专门学习过折纸的学生可以轻松完成 当用来描述算法的语言并没

9、有被准确定义或者没有给予足够信息的时候，交流就会产生问题,原语,通过建立一个可以描述算法的意义明确的基本块（原语）集合，计算机科学即就可以解决上述的勾通问题 原语描述算法需要建立一个统一的细节描述级别，原语连同一组表达了原语如何表达复杂的想法的规定组成了一种程序设计语言 组成 语法：原语的符号表示 语义：表达了原语的意义,1自然语言,缺点 由于自然语言的歧义性，容易导致算法执行的不确定性； 自然语言的语句一般太长，从而导致了用自然语言描述的算法太长； 由于自然语言表示的串行性，因此，当一个算法中循环和分支较多时就很难清晰地表示出来； 自然语言表示的算法不便翻译成计算机程序设计语言理解的语言。,

10、2流程图,它采用美国国家标准化协会ANSI（American National Standard Institute）规定的一组图形符号来表示算法。 流程图可以很方便地表示顺序、选择和循环结构，而任何程序的逻辑结构都可以用顺序、选择和循环结构来表示， 流程图可以表示任何程序的逻辑结构。 用流程图表示的算法不依赖于任何具体的计算机和计算机程序设计语言，,（1）求解例4.4的算法流程图,（2）求解例4.5的算法流程图,（3）求解例4.6的算法流程图,3伪代码（1）求解例4.4的伪代码算法描述：,BEGIN(算法开始) 1 X 2 Y while（Y=100） X+Y X Y+1 Y Print X

11、 END（算法结束）,（2）求解例4.5的伪代码算法描述：,BEGIN（算法开始） 0 X 1 I do X+1/I X I+1 I while(I=n) END（算法结束）,（3）例4.6的伪代码算法描述：,BEGIN if n = =0 0 Y Print Y else ,0 X 1 Y Print X，Y for(i=1;i=n-1;i+) X+YZ YX ZY Print Y END,4计算机程序设计语言,计算机程序设计语言描述的算法（程序）是清晰的、简明的，最终也能由计算机处理的。 缺点： 算法的基本逻辑流程难于遵循。与自然语言一样，程序设计语言也是基于串行的 用特定程序设计语言编写

12、的算法限制了与他人的交流，不利于问题的解决； 要花费大量的时间去熟悉和掌握某种特定的程序设计语言； 要求描述计算步骤的细节，而忽视算法的本质。,例4.4的计算机程序设计语言（C语言）的算法描述：,main() int X,Y; X=1; Y=2; while(Y=100) X=X+Y; Y=Y+1; ; printf(“%d“,X); ,例4.5的计算机程序设计语言（C语言）的算法描述,main() int n; float X,I; printf(“Please input n:“); scanf(“%d“,do X=X+1/I; I=I+1; while(I=n); printf(“n%f

13、“,X); ,算法,算法分析,（1）算法的时间复杂度；,用T(n)表示，n表示问题规模的大小。 使用一个记号 Order（数量级）的第一个字母， 允许使用“=”代替“”。如n2+n+1=(n2) 设f(n)是一个关于正整数n的函数，若存在一个正整数n0和一个常数C，当nn0时，T(n)C f(n)均成立，则称f(n)为T(n)的同数量级的函数。 算法时间复杂度T(n)可表示为： T(n)= (f(n),常见的大表示形式有：,(1) ：称为常数级； (logn)： 称为对数级； (n) ：称为线性级； (nc) ：称为多项式级； (cn) ：称为指数级； (n!) ：称为阶乘级。,算法的空间复杂

14、度,指算法在执行过程中所占存储空间的大小， 用S(n)表示，S为英文单词Space的第一个字母。与算法的时间复杂度相同 算法的空间复杂度S(n)也可表示为： S(n)= (g(n)。,算法,算法的研究,算法,算法：定义一向工作如何完成的步骤的集合 在一台机器可以完成一个任务之前，必须找到完成这个任务的算法并且用与机器兼容的方式来描述 一个与机器兼容的算法的描述程序 算法的研究开始是作为数学的一个学科 目标：找到描述特定类型问题是如何被解决的指令的集合，如Euclidean算法 一旦一个完成任务的算法被找到，任务的实现就不再需要对算法原理的理解，任务的实现仅仅是遵循算法的只是过程 现有的解决问题

15、需要的智慧被编码进了算法,算法转化为智慧,通过使用算法来得到并转化智慧，我们才可以构建起可以表现智慧行为的机器。 机器表现的智能等级受到通过算法转化的智慧所限制 如果没有解决问题的算法，意味着问题的解决方案超出了机器的能力范围 算法的开发就成了计算机领域的一个主要目标 如何找到算法一个十分接近于寻找通用问题解决方案 描述这个算法转变为一个清晰的指令的集合（程序设计语言描述）,计算机技术别用于复杂问题（大型软件系统）,不仅仅包括实现任务的单个算法的开发 还要求对组件之间的交互进行设计 软件工程：借鉴了工程领域、项目管理领域、人力资源管理以及程序语言设计领域的经验,执行算法的机器的设计和实现,数据

16、的存储 数据的操作 体系结构中涵盖了对现今技术的讨论 我们的目标不是去熟知类似当今体系结构是如何用电路来实现这样的细节问题，那将会导致过分陷入电子工程学科 正如昨天的齿轮驱动的计算机让位于电子设备一样，今天的电子技术也许很快也被其它的技术所取代,理想情况下,希望计算机的体系结构是我们的有关算法过程知识的延续，并且不应该被技术能力酸限制 使我们的算法知识在当代机器体系结构的发展背后起推动作用，而不仅仅是从技术的要求触发来解顶机器的设计 构建允许使用多个指令序列来代替算法的机器是可能的 这些指令被同时执行或者作为,机器于外部世界的接口的设计于计算机的设计紧密相连,算法是如何机器中的？ 机器是如何被

17、告知执行的是哪一个算法？,计算理论,对解决越来越复杂问题的算法的研究 导致了算法过程的最终限制问题 如果没有算法可以解决这个问题，那么算法是不能被机器所解决的，机器仅仅可以解决在算法上可解的问题 Godel的不完全定理阐述了 在任何传统算术领域的数学理论中，有些是既不能证明有不能被推翻的 任何对算术系统的彻底研究都超出了算法的能力 对算法的限制的研究欲望似的数学家们设计抽象的机器来执行算法，并在理论上研究这些假想机器的能力。,4.2 数据结构：一类定性数学模型,4.2.1 数据结构的基本概念,数据结构的基本概念,组成：数据结构是一类定性的数学模型，它由以下3部分组成 逻辑结构 存储结构（或称物

18、理结构） 运算 数据逻辑结构的形式化定义 DS= 其中： D表示数据的集合； R表示数据D上关系的集合。,数据的存储结构,数据的存储结构是指在反映数据逻辑关系的原则下，数据在存储器中的存储方式。 顺序存储结构：借助元素在存储器中的相对位置来表示数据元素的逻辑关系。 链式存储结构：借助指针来表示数据元素之间的逻辑关系，通常在数据元素上增加一个或多个指针类型的属性来实现这种表示方式。,数据结构的基本运算内容,建立数据结构； 清除数据结构； 插入数据元素； 删除数据元素； 更新数据元素； 查找数据元素； 按序重新排列； 判定某个数据结构是否为空，或是否已达到最大允许的容量； 统计数据元素的个数。,数

19、据结构：一类定性数学模型,4.2.2 常用的几种数据结构,线性表,线性表是n个数据元素的有限序列，即（X1，X2，X3，Xi，Xn） 基本操作插入、删除和存取数据元素 几种特殊的线性表 后进先出（Last In First Out，简称LIFO）的线性表。 先进先出（First In First Out，简称FIFO）的线性表。 限定所有插入、删除和存取都在表的两端进行的线性表。,数组,线性表的推广形式之一。 如在一个mn的二维数组中，每个元素Ai,j都分别属于两个线性表，即 （Ai,1，Ai,2，Ai,n） 和（A1,j，A2,j，Am,j）。,树（Tree）,由n（n0）个结点组成的有限集

20、合。若n=0，则称为空树，任何一个非空树均满足以下两个条件： 仅有一个称为根的结点； 当n0时，其余结点可分为m（m0）个互不相交的有限集合，其中每个集合又是一棵树，并称为根的子树。,上图的树有12个结点，A是根结点，该树又可再分为若干不相交的子树，如T1=B，E，F，K，T2=C，G，T3=D，H，I，J，L等。图4.4所示的树中有12个结点，A是根结点，该树又可再分为若干不相交的子树，如T1=B，E，F，K，T2=C，G，T3=D，H，I，J，L等。,二叉树,n（n0）个结点组成的有限集合，它或者是空集（n0），或者由一个结点及两棵互不相交的子树组成，且这两个子树有左、右之分，其次序不能任

21、意颠倒。,图,由结点和连接这些结点的边所组成的集合。 图的形式化定义为： 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.1 算法+数据结构=程序,概念,从广义上讲，程序可以认为是一种行动方案或工作步骤。例如： 某个会议的日程安排 一条旅游路线的设计 手工小制作的说明书等 计算机程序：一种处理事务的时间顺序和处理步骤。 组成计算机程序的基本单位是指令 计算机程序就是按照工作步骤事先编排好的、具有特殊功能的指令序列。,一个程序具有一个单一的、不

22、可分的结构，它规定了某个数据结构上的一个算法。瑞士著名计算机科学家尼可莱沃思（Nikiklaus Wirth）在1976年曾提出这样一个公式： 算法+数据结构=程序,由此看来，我们前面提到的算法和数据结构是计算机程序的两个最基本的概念。算法是程序的核心，它在程序编制、软件开发，乃至在整个计算机科学中都占据重要地位。数据结构是加工的对象，一个程序要进行计算或处理总是以某些数据为对象的，而要设计一个好的程序就需将这些松散的数据按某种要求组成一种数据结构。然而，随着计算机科学的发展，人们现在已经意识到程序除了以上两个主要要素外，还应包括程序的设计方法以及相应的语言工具和计算环境。,软件,软件是与程序

23、密切相关的一个概念，在计算机发展的初期，硬件设计和生产是主要问题，那时的软件就是程序。后来，随着计算技术的发展，传统软件的生产方式已不适应发展的需要，于是人们将工程学的基本原理和方法引入软件设计和生产中。 现在计算机软件一般指计算机系统中的程序及其文档，也可以指在研究、开发、维护，以及使用上述含义下的软件所涉及的理论、方法、技术所构成的分支学科。,软件,软件一般分为3类 系统软件：是计算机系统中最靠近硬件层次的软件。如操作系统、编译程序等。 支撑软件：是支撑其他软件的开发与维护的软件。如数据库管理系统、网络软件、各种接口软件和开发工具等。 应用软件：是特定应用领域的专用软件。如商业会计软件、教

24、学软件等。,硬件,计算机硬件是构成计算机系统的所有物理器件、部件、设备，以及相应的工作原理与设计、制造、检测等技术的总称。 广义的硬件包含硬件本身及其工程技术两部分。其中： 计算机系统的物理元器件包括：集成电路、印制电路板，以及其他磁性元件、电子元件等。 计算机系统的部件和设备包括：控制器、运算器、存储器、输入输出设备、电源等。,硬件,硬件工程技术包括：印制电路板制造、高密度组装、抗环境干扰、抗恶劣环境破坏等技术，以及在设计和制造过程中为提高计算机性能所采取的措施等。 计算机就是由计算机硬件和计算机软件组成的。硬件是计算机的“躯体”，软件是计算机的“灵魂”。,4.4 CC1991报告提取的核心

25、概念,核心概念是CC1991报告首次提出的，是具有普遍性、持久性的重要思想、原则和方法。它的基本特征有： 在学科中多处出现； 在各分支领域及抽象、理论和设计的各个层面上都有很多示例； 在技术上有高度的独立性； 一般都在数学、科学和工程中出现。,1. 绑定（Binding）,绑定指的是通过将一个对象（或事物）与其某种属性相联系，从而使抽象的概念具体化的过程。例如：将一个进程与一个处理机，一个变量与其类型或值分别联系起来。这种联系的建立，实际上就是建立了某种约束。,2. 大问题的复杂性（Complexity of Large Problems）,大问题的复杂性是指随着问题规模的增长而使问题的复杂性

26、呈非线性增加的效应。这种非线性增加的效应是区分和选择各种现有方法和技术的重要因素。,3. 概念和形式模型（Conceptual and Format Models）,概念和形式模型是对一个想法或问题进行形式化、特征化、可视化思维的方法。抽象数据类型、语义数据类型以及指定系统的图形语言，如数据流图和E-R图等都属于概念模型。而逻辑、开关理论和计算理论中的模型大都属于形式模型。概念模型和形式模型以及形式证明是将计算学科各分支统一起来的重要的核心概念。,4.一致性和完备性（Consistency and Completeness）,一致性包括用于形式说明的一组公理的一致性、事实和理论的一致性，以及一

27、种语言或接口设计的内部一致性。 完备性包括给出的一组公理，使其能获得预期行为的充分性、软件和硬件系统功能的充分性，以及系统处于出错和非预期情况下保持正常行为的能力等。 在计算机系统设计中，正确性、健壮性和可靠性就是一致性和完备性的具体体现。,5. 效率（Efficiency）,效率是关于空间、时间、人力、财力等资源消耗的度量。在计算机软硬件的设计中，要充分考虑某种预期结果所达到的效率，以及一个给定的实现过程较之替代的实现过程的效率。,6演化（Evolution）,演化指的是系统的结构、状态、特征、行为和功能等随着时间的推移而发生的更改。这里主要是指了解系统更改的事实和意义及应采取的对策。在软件

28、进行更改时，不仅要充分考虑更改对系统各层次造成的冲击，还要充分考虑到软件的有关抽象、技术和系统的适应性问题。,7. 抽象层次（Levels of Abstraction）,抽象层次指的是通过对不同层次的细节和指标的抽象对一个系统或实体进行表述。在复杂系统的设计中，隐藏细节，对系统各层次进行描述（抽象），从而控制系统的复杂程度。例如，在软件工程中，从规则说明到编码各个阶段（层次）的详细说明，计算机系统的分层思想，计算机网络的分层思想等。,8.按空间排序（Ordering in Space）,按空间排序指的是各种定位方式，如物理上的定位（如网络和存储中的定位），组织方式上的定位（如处理机进程、类型

29、定义和有关操作的定位）以及概念上的定位（如软件的辖域、耦合、内聚等）。按空间排序是计算技术中一个局部性和相邻性的概念。,9. 按时间排序（Ordering in Time）,按时间排序指的是事件的执行对时间的依赖性。例如，在具有时态逻辑的系统中，要考虑与时间有关的时序问题；在分布式系统中，要考虑进程同步的时间问题；在依赖于时间的算法执行中，要考虑其基本的组成要素。,10. 重用（Reuse）,重用指的是在新的环境下，系统中各类实体、技术、概念等可被再次使用的能力。如软件库和硬件部件的重用等。,11. 安全性（Security）,安全性指的是计算机软硬件系统对合法用户的响应及对非法请求的抗拒，以保护自己不受外部影响和攻击的能力。如为防止数据的丢失、泄密而在数据库管理系统中提供的口令更换、操作员授权等功能。,12.折衷与结论（Tradeoff and Consequences）,指的是为满足系统的可实施性而对系统设计中的技术、方案所作出的一种合理的取舍。结论是折衷的结论，即选择一种方案代替另一种方案所产生的技术、经济、文化及其他方面的影响。折衷是存在于计算学科领域各层次上的基本事实。如在算法的研究中，要考虑空间和时间的折衷；对于矛盾的设计目标，要考虑诸如易用性和完备性、灵活性和简单性、低成本和高可靠性等方面所采取的折衷等。,