




版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
1、专业导论第5讲 计算机学科核心概念吴伟民,计算学科中的核心概念,掌握和应用学科的核心概念是成熟的计算机科学家和工程师的标志之一 算法计算学科中最具方法论性质的核心概念 算法的历史、定义、表示方法 算法的分析等 数据结构、程序、软件、硬件。 CC1991提取的12个核心概念: (1)绑定 (2)大问题的复杂性 (3)概念模型和形式模型 (4)一致性和完备性 (5)效率 (6)演化 (7)抽象层次 (8)按空间排序 (9)按时间排序 (10)重用 (11)安全性 (12)折衷与结论,5.1 引 言,学科中的核心概念是学科中最关键、最重要的概念,它涉及学科研究的内涵、对象、本质、核心要素等内容,其基
2、本特征有以下4点: (1)在学科中多处出现; (2)在各分支领域及抽象、理论和设计的各个层面上都有很多示例; (3)在技术上有高度的独立性; (4)一般都在数学、科学和工程中出现。 在计算学科的一般文献中,学科中的核心概念指的是CC1991报告提取的学科中反复出现的12个核心概念。为便于教学,本书将学科中最具方法论性质的概念算法,以及数据结构、程序、软件、硬件、计算机中的数据等与CC1991报告提取的12个核心概念一起统称为学科中的核心概念。,5.2 算法,算法是计算学科中最具方法论性质的核心概念,也被誉为计算学科的灵魂。算法设计的优劣决定着软件系统的性能,对算法进行研究能使我们深刻地理解问题
3、的本质以及可能的求解技术。,5.2.1 算法的历史简介,公元825年,阿拉伯数学家阿科瓦里茨米(AlKhowarizmi)撰写了著名的波斯教科书(Persian Textbook),书中概括了进行四则算术运算的法则。“算法(Algorithm)”一词就来源于这位数学家的名字。后来,韦氏新世界词典(Websters New World Dictionary)将其定义为“解某种问题的任何专门的方法”。而据考古学家发现,古巴比伦人在求解代数方程时,就已经采用了“算法”的思想。 在算法的研究中,人们不可避免的要提到丢番图方程,希尔伯特著名的23个数学问题中的第十个问题就是关于“丢番图方程的可解性问题”
4、。 古希腊数学家丢番图(Diophantus)对代数学的发展有极其重要的贡献,并被后人称之为“代数学之父”。,他在算术(Arithmetica)一书中提出了有关两个或多个变量整数系数方程的有理数解问题。对于具有整数系数的不定方程,若只考虑其整数解,这类方程就叫丢番图方程。“丢番图方程可解性问题”的实质为:能否写出一个可以判定任意丢番图方程是否可解的算法? 对于只有一个未知数的线性丢番图方程而言,求解很简单,如ax=b,只要a能整除b,就可判定其有整数解,该整数解即b/a。 对于有两个未知数的线性丢番图方程判定其是否有解的方法也很简单,如ax+by=c,先求出a和b的最大公因子d,若d能整除c,
5、则该方程有整数解。,例5.1 问:方程13x+26y=52有无整数解? 答:13和26的最大公因子是13,13又可整除52,故该方程有整数解(如x=2,y=1即方程的解)。 例5.2 问:方程2x+4y=15有无整数解? 答:2和4的最大公因子是2,2不能整除15,故该方程无整数解。 因此可以看出,对于两个未知数的线性丢番图方程来说,求解的关键就是求最大公因子。公元前300年左右,欧几里德在其著作几何原本(Elements)第七卷中阐述了关于求解两个数最大公因子的过程,这就是著名的欧几里德算法:给定两个正整数m和n,求它们的最大公因子,即能同时整除m和n的最大正整数。,算法如下: (1)以n除
6、m,并令所得余数为r(r必小于n); (2)若r=0,算法结束,输出结果n;否则,继续步骤(3); (3)将n置换为m,r置换为n,并返回步骤(1)继续进行。 例5.3 设m=56,n=32,求m、n的最大公因子。 算法的执行过程如下: (1)32除56余数为24; (2)24除32余数为8; (3)8除24余数为0,算法结束,输出结果8。 答:m、n的最大公因子为8。 欧几里德算法既表述了一个数的求解过程,同时,它又表述了一个判定过程,该过程可以判定“m和n是互质的”(即除1以外,m和n没有公因子)这个命题的真假。,5.2.2 算法的定义和特征,有关算法的定义不少,其内涵基本上是一致的,其中
7、最为著名的是计算机科学家克努特在其经典巨著计算机程序设计的艺术(The Art of Computer Programming)第一卷中对算法的定义和特性所作的有关描述。 1算法的非形式化定义 一个算法,就是一个有穷规则的集合,其中之规则规定了一个解决某一特定类型问题的运算序列。 2算法的重要特性 (1)有穷性:一个算法在执行有穷步之后必须结束。也就是说,一个算法,它所包含的计算步骤是有限的。如在欧几里德算法中,由于m和n均为正整数,在步骤(1)之后,r必小于n,若r0,下一次进行步骤(1)时,n的值已经减小,而正整数的递降序列最后必然要终止。因此,无论给定m和n的原始值有多大,步骤(1)的执
8、行都是有穷次。,(2)确定性:算法的每一个步骤必须要确切地定义。即算法中所有有待执行的动作必须严格而不含混地进行规定,不能有歧义性。如欧几里德算法中,步骤(1)中明确规定“以n除m”,而不能有类似“以n除m或以m除n”这类有两种可能做法的规定。 (3)输入:算法有零个或多个的输入,即在算法开始之前,对算法最初给出的量。如欧几里德算法中,有两个输入,即m和n。 (4)输出:算法有一个或多个的输出,即与输入有某个特定关系的量,简单地说就是算法的最终结果。如在欧几里德算法中只有一个输出,即步骤(2)中的n。 (5)能行性:算法中有待执行的运算和操作必须是相当基本的,换言之,它们都是能够精确地进行的,
9、算法执行者甚至不需要掌握算法的含义即可根据该算法的每一步骤要求进行操作,并最终得出正确的结果。,3算法的形式化定义 算法的形式化定义:算法是一个四元组,即(Q,I,F)。 其中: (1)Q是一个包含子集I和的集合,它表示计算的状态; (2)I表示计算的输入集合; (3)表示计算的输出集合; (4)F表示计算的规则,它是一个由Q到它自身的函数,且具有自反性,即对于任何一个元素qQ,有F(q)=q。 一个算法是对于所有的输入元素x,都在有穷步骤内终止的一个计算方法。在算法的形式化定义中,对于任何一个元素xI,x均满足以下性质:x0=x,xk+1=F(xk),(k0) 该性质表示任何一个输入元素x均
10、为一个计算序列,即x0,x1,x2,xk。对任何输入元素x,该序列表示算法在第k步结束。,5.2.3 算法实例,下面,再介绍几个简单的算法实例,以加深读者对算法思想的理解。 例5.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。 例5.5 求解调和级数Hn。 Hn=1/1+1/2+1/3+1/n,调和级数在算法分析中有重要作用。直觉上,当n很大时,Hn也未必会得到很
11、大的值。其实不然,只要n充分大,则Hn就能得到我们所需要的不论多大的数。这个例子与梵天塔问题一样清晰地表明:在算法的研究中,不能依靠人的直觉,而只能依靠严密的数学方法。 下面,给出求解调和级数的算法。 设变量X表示累加和,变量I表示循环的次数,自然语言描述算法如下: (1)将0赋值给X; (2)将1赋值给I; (3)将X与1/I相加,然后把结果存入X; (4)将I加1; (5)若I大于等于N,算法结束,结果为X;否则转到步骤 (3)继续执行。,例5.6 求解斐波那契数。 0,1,1,2,3,5,8,13,21,34, (1) 数列(1)即著名的斐波那契数列,它来源于1202年意大利数学家斐波那
12、契(L.P.Fibonacci)在其珠算之书(Liber Abaci)中提出的一个“兔子问题”: 假设一对刚出生的兔子一个月后就能长大,再过一个月就能生下一对兔子,并且此后每个月都能生一对兔子,且新生的兔子在第二个月后也是每个月生一对兔子。问:一对兔子一年内可繁殖成多少对兔子? 在序列(1)中,每个数都是它的前两个数之和,Fn表示这个序列的第个数,该序列可以形式化的定义为: F0=0,F1=1,Fn+2=Fn+1+Fn,n0,斐波那契数列不仅包含着一个有趣的“兔子问题”,而且还是一个关于加法算法的典型实例。 求解前个斐波那契数的算法: 设变量X表示前一个数的值,即定义中的Fn,变量Y表示当前数
13、的值,即定义中的Fn+1,变量Z表示后一个数的值,即定义中的Fn+2。那么求解问题的自然语言描述如下: (1)如果n=0,那么将0赋值给Y,并输出Y,转步骤(11)继续执行; (2)将0赋给X,将1赋值给Y; (3)输出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)算法结束。,5.2.4 算法的表示方法,算法是对解题过程的精确描述,这种描述是建立在语言基础之上的,表示算法的语言主要有自然语言、流程图、伪代码、计
14、算机程序设计语言等。 1自然语言 前面关于欧几里德算法以及算法实例的描述使用的都是自然语言,自然语言是人们日常所用的语言,如汉语、英语、德语等。使用这些语言不用专门训练,所描述的算法也通俗易懂。然而,其缺点也是明显的: (1)由于自然语言的歧义性,容易导致算法执行的不确定性; (2)自然语言的语句一般太长,从而导致了用自然语言描述的算法太长; (3)由于自然语言表示的串行性,因此,当一个算法中循环和分支较多时就很难 清晰地表示出来; (4)自然语言表示的算法不便翻译成计算机程序设计语言理解的语言。,2流程图 流程图是描述算法的常用工具,它采用美国国家标准化协会ANSI(American Nat
15、ional Standard Institute)规定的一组图形符号来表示算法。流程图可以很方便地表示顺序、选择和循环结构,而任何程序的逻辑结构都可以用顺序、选择和循环结构来表示,因此,流程图可以表示任何程序的逻辑结构。另外,用流程图表示的算法不依赖于任何具体的计算机和计算机程序设计语言,从而有利于不同环境的程序设计。就算法的描述而言,流程图优于其他描述算法的语言。下面,分别给出求解例5.4、例5.5和例5.6的流程图算法描述。,图5.1 例5.4算法流程图,(1)求解例5.4的算法流程图,如图5.1所示。,(2)求解例5.5的算法流程图,如图5.2所示。,图5.2 例5.5算法流程图,(3)
16、求解例5.6的算法流程图,如图5.3所示。,图5.3 例5.6算法流程图,3伪代码 伪代码是用介于自然语言和计算机语言之间的文字和符号来描述算法的工具。它不用图形符号,因此,写方便,格式紧凑,易于理解,便于向计算机程序设计语言算法(程序)过渡。下面,分别给出求解例5.4、例5.5和例5.6的伪代码算法描述。 (1)求解例5.4的伪代码算法描述: BEGIN(算法开始) 1=X 2=Y while(YX Y+1=Y do X+1/I= X I+1=I while(I=n) END(算法结束),(3)例5.6的伪代码算法描述: BEGIN(算法开始) if n = =0 0=Y Print Y e
17、lse 0=X 1=Y Print X,Y for(i=1;iZ Y=X Z=Y Print Y END(算法结束),4计算机程序设计语言 计算机不能识别自然语言、流程图和伪代码等算法描述的语言。因此,用自然语言、流程图和伪代码等语言描述的算法最终还必须转换为具体的计算机程序设计语言描述的算法,即转换为具体的程序。 一般而言,计算机程序设计语言描述的算法(程序)是清晰的、简明的,最终也能由计算机处理的。然而,就使用计算机程序设计语言描述算法而言,它还存在以下几个缺点: (1)算法的基本逻辑流程难于遵循。与自然语言一样,程序设计语言也是基于串行的,当算法的逻辑流程较为复杂时,这个问题就变得更加严
18、重; (2)用特定程序设计语言编写的算法限制了与他人的交流,不利于问题的解决;,(3)要花费大量的时间去熟悉和掌握某种特定的程序设计语言; (4)要求描述计算步骤的细节,而忽视算法的本质。 下面,分别给出求解例5.4、例5.5和例5.6的计算机程序设计语言(C语言)的算法描述。 (1)求解例5.4的计算机程序设计语言(C语言)的算法描述: main() int X,Y; X=1; Y=2; while=100) X=X+Y; Y=Y+1; ; printf(%d,X); ,(2)求解例5.5的计算机程序设计语言(C语言)的算法描述: main() int n; float X,I; print
19、f(Please input n:); scanf(%d, ,(3)求解例4.6的计算机程序设计语言(C语言)的算法描述: main() int X,Y,Z,I,j,n; printf(please input n:); scanf(%d, ,else X=0; Y=1; printf(%d %d , X ,Y); for(I=1;I=n-1;I+) Z=X+Y; X=Y; Y=Z; printf(%d , Y); ,5.2.5 算法分析,解一个问题,往往有若干不同的算法,这些算法决定着根据该算法编写的程序性能的好坏。那么,在保证算法正确性的前提下,如何确定算法的优劣就是一个值得研究的课题。
20、在算法的分析中,一般应考虑以下3个问题: (1)算法的时间复杂度; (2)算法的空间复杂度; (3)算法是否便于阅读、修改和测试。 算法时间复杂度是指算法中有关操作次数的多少,它用T(n)表示,T为英文单词Time的第一个字母,T(n)中的n表示问题规模的大小。如在累加求和中,n表示待加数的个数;在矩阵相加问题中,n表示矩阵的阶数;在图中,n表示顶点数等。,在算法的复杂度分析中,经常使用一个记号(读作“大”),该记号是保罗巴克曼(P.Bachmann)于1892年在解析数论(Analytische Zahlentheorie)一书引进的,它为Order(数量级)的第一个字母,它允许使用“=”代
21、替“”。如n2+n+1=(n2),该表达式表示,当n足够大时表达式左边约等于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!)称为阶乘级。 一般而言,对于较复杂的算法,应将它分成容易估算的几个部分,然后用的求解原则计算整个算法的时间复杂度,最好不要采用指数级和阶乘级的算法,而应尽可能选
22、用多项式级或线性级等时间复杂度较小的算法。另外,还要在算法最好、平均和最坏的情况下区别执行效率的不同。,对于上一讲的梵天塔问题,需要移动的盘子次数为h(n)=2n-1,该问题的算法时间复杂度表示为(2n);例5.4的算法时间复杂度表示为(1);例5.5的算法时间复杂度表示为(n);例5.6的算法时间复杂度表示为(n)等等。,在阶乘级的算法中,如果问题规模n为10,则算法时间复杂度为10!(3 628 800)。若要检验10!种情况,设每种情况需要1毫秒的计算时间,则整个计算将需1小时左右。一般来说,如果选用了阶乘级的算法,则当问题规模等于或者大于10时,就要认真考虑算法的适用性问题。 算法的空
23、间复杂度是指算法在执行过程中所占存储空间的大小,它用S(n)表示,S为英文单词Space的第一个字母。与算法的时间复杂度相同,算法的空间复杂度S(n)也可表示为:S(n)= (g(n)。,5.3 数据结构,数学模型有定量模型和定性模型两类之分。定量模型指的是可以用数值方程表示的一类模型,而定性模型则是指非数值性的数据结构(如表、树和图等)及其运算。 在计算领域中,数据结构(Data Structure)指的是一类定性数学模型,它是计算机算法设计的基础,它在计算科学中占有十分重要的地位。本节将介绍数据结构的基本概念和常用的几种数据结构,如线性表、数组、树和二叉树以及图等。,5.3.1 数据结构的
24、基本概念,1数据结构的组成 数据结构是一类定性的数学模型,它由数据的逻辑结构、数据的存储结构(或称物理结构)及其运算3部分组成。 2数据逻辑结构的形式化定义 DS = 其中: D表示数据的集合; R表示数据D上关系的集合。,3数据的存储结构 数据的存储结构是指在反映数据逻辑关系的原则下,数据在存储器中的存储方式。数据存储结构的基本组织方式有顺序存储结构和链式存储结构。 (1)顺序存储结构:借助元素在存储器中的相对位置来表示数据元素的逻辑关系。 (2)链式存储结构:借助指针来表示数据元素之间的逻辑关系,通常在数据元素上增加一个或多个指针类型的属性来实现这种表示方式。,4数据结构的基本运算内容 (
25、1)建立数据结构; (2)清除数据结构; (3)插入数据元素; (4)删除数据元素; (5)更新数据元素; (6)查找数据元素; (7)按序重新排列; (8)判定某个数据结构是否为空,或是否已达到最大允许的容量; (9)统计数据元素的个数。,5.3.2 常用的几种数据结构,1线性表 线性表是n个数据元素的有限序列,即(X1,X2,X3,Xi,Xn)。插入、删除和存取数据元素是所有数据结构的基本操作,若对线性表的这些基本操作加一定的限制,则形成下面几种特殊的线性表: (1)后进先出(Last In First Out,简称LIFO)的线性表。它的所有插入、删除和存取都是在线性表的表尾进行的; (
26、2)先进先出(First In First Out,简称FIFO)的线性表。它的所有插入都是在线性表的一端进行的,而所有的删除和存取又都在线性表的另一端进行; (3)限定所有插入、删除和存取都在表的两端进行的线性表。 2数组 数组是线性表的推广形式之一。如在一个mn的二维数组中,每个元素Ai,j都分别属于两个线性表,即(Ai,1,Ai,2,Ai,n)和(A1,j,A2,j,Am,j)。,3树和二叉树 树和二叉树是一种具有层次关系的非线性结构,在计算机领域中有广泛的应用,尤其以二叉树最为常用。 (1)树 树(Tree)是由n(n0)个结点组成的有限集合。若n=0,则称为空树,任何一个非空树均满足
27、以下两个条件: 仅有一个称为根的结点; 当n0时,其余结点可分为m(m0)个互不相交的有限集合,其中每个集合又是一棵树,并称为根的子树。 例如,图4.4所示的树中有12个结点,A是根结点,该树又可再分为若干不相交的子树,如T1=B,E,F,K,T2=C,G,T3=D,H,I,J,L等。,图5.4 树,(2)二叉树 二叉树是n(n0)个结点组成的有限集合,它或者是空集(n0),或者由一个结点及两棵互不相交的子树组成,且这两个子树有左、右之分,其次序不能任意颠倒。,4图 图是由结点和连接这些结点的边所组成的集合。在图形结构中,结点之间的关系可以是任意的,图中任意两个数据元素之间都可能相关。 图的形
28、式化定义为:G= 其中: V是一个非空结点的集合; E是连结结点的边的集合。 例 G= 其中V=A,B,C,D, E=(A,B),(A,C),(B,D),(B,C),(D,C),(A,D)。 该图也可以用图5.5来表示。,图5.5 图的表示,5.4 程序,“程序”一词,从广义上讲可以认为是一种行动方案或工作步骤。在日常生活中,经常碰到这样的程序:某个会议的日程安排、一条旅游路线的设计、手工小制作的说明书等,这些程序表示的都是在做一件事务时按时间的顺序应先做什么后做什么。 这里所指的程序特指计算机的程序,也是一种处理事务的时间顺序和处理步骤。由于组成计算机程序的基本单位是指令,因此,计算机程序就
29、是按照工作步骤事先编排好的、具有特殊功能的指令序列。 一个程序具有一个单一的、不可分的结构,它规定了某个数据结构上的一个算法。瑞士著名计算机科学家尼可莱沃思(Nikiklaus Wirth)在1976年曾提出这样一个公式: 算法 + 数据结构 = 程序,前面提到的算法和数据结构是计算机程序的两个最基本的概念。 算法是程序的核心,它在程序编制、软件开发,乃至在整个计算机科学中都占据重要地位。 数据结构是加工的对象,一个程序要进行计算或处理总是以某些数据为对象的,而要设计一个好的程序就需将这些松散的数据按某种要求组成一种数据结构。 然而,随着计算机科学的发展,人们现在已经意识到程序除了以上两个主要
30、要素外,还应包括程序的设计方法以及相应的语言工具和计算环境等内容。,5.5 软 件,软件是与程序密切相关的一个概念,在计算机发展的初期,硬件设计和生产是主要问题,那时的软件就是程序。后来,随着计算技术的发展,传统软件的生产方式已不适应发展的需要,于是人们将工程学的基本原理和方法引入软件设计和生产中。现在计算机软件一般指计算机系统中的程序及其文档,也可以指在研究、开发、维护,以及使用上述含义下的软件所涉及的理论、方法、技术所构成的分支学科。软件一般分为系统软件、支撑软件、应用软件3类。 (1)系统软件是计算机系统中最靠近硬件层次的软件。如操作系统、编译程序等。 (2)支撑软件是支撑其他软件的开发
31、与维护的软件。如数据库管理系统、网络软件、各种接口软件和开发工具等。 (3)应用软件是特定应用领域的专用软件。如商业会计软件、教学软件等。,5.6 硬件,计算机硬件是构成计算机系统的所有物理器件、部件、设备,以及相应的工作原理与设计、制造、检测等技术的总称。广义的硬件包含硬件本身及其工程技术两部分。其中: 计算机系统的物理元器件包括:集成电路、印制电路板,以及其他磁性元件、电子元件等。 计算机系统的部件和设备包括:控制器、运算器、存储器、输入输出设备、电源等。 硬件工程技术包括:印制电路板制造、高密度组装、抗环境干扰、抗恶劣环境破坏等技术,以及在设计和制造过程中为提高计算机性能所采取的措施等。
32、 计算机就是由计算机硬件和计算机软件组成的。硬件是计算机的“躯体”,软件是计算机的“灵魂”。,5.7 CC1991报告提取的核心概念,学科中的核心概念是CC1991报告首次提出的,具有普遍性、持久性的重要思想、原则和方法。报告认为,熟练掌握和应用这些核心概念是一个成熟的计算机科学家和工程师的标志之一。 1绑定(Binding) 绑定指的是通过将一个对象(或事物)与其某种属性相联系,从而使抽象的概念具体化的过程。例如,将一个程序的执行过程与一个处理机联系起来;一个变量与其类型或值联系起来。 2大问题的复杂性(Complexity of Large Problems) 大问题的复杂性是指随着问题规
33、模的增长而使问题的复杂性呈非线性增加的效应。这种非线性增加的效应是区分和选择各种现有方法和技术的重要因素。例如,在软件工程中,随着问题规模的增大,系统的复杂性也在增大。每个新的信息项、功能或限制都可能影响整个系统的其他元素。因此,随着问题复杂性的增加,系统分析的任务将呈几何级数增长。在研制一个大系统时,显然,控制和降低系统的复杂性便成为区分和选择现有方法和技术的重要因素。,3概念模型和形式模型(Conceptual and Format Models) 概念模型和形式模型是对一个想法或问题进行形式化、特征化、可视化思维的方法。抽象数据类型、语义数据类型以及指定系统的图形语言,如数据流图和E-R
34、图等都属于概念模型。而逻辑、开关理论和计算理论中的模型大都属于形式模型。概念模型和形式模型以及 形式证明是将计算学科各分支统一起来的重要核心概念。 4一致性和完备性(Consistency and Completeness) 一致性包括用于形式说明的一组公理的一致性、事实和理论的一致性,以及一种语言或接口设计的内部一致性。完备性包括给出的一组公理,使其能获得预期行为的充分性、软件和硬件系统功能的充分性,以及系统处于出错和非预期情况下保持正常行为的能力等,在计算机系统设计中,正确性、健壮性和可靠性就是一致性和完备性的具体体现。 5效率(Efficiency) 效率是关于空间、时间、人力、财力等资
35、源消耗的度量。在计算机软硬件的设计中,要充分考虑某种预期结果所达到的效率,以及一个给定的实现过程较之替代的实现过程的效率。 6演化(Evolution) 演化指的是系统的结构、状态、特征、行为和功能等随着时间的推移而发生的更改。这里主要是指了解系统更改的事实和意义及应采取的对策。在软件进行更改时,不仅要充分考虑更改对系统各层次造成的冲击,还要充分考虑到软件的有关抽象、技术和系统的适应性问题。,7抽象层次(Levels of Abstraction) 抽象层次指的是通过对不同层次的细节和指标的抽象对一个系统或实体进行表述。在复杂系统的设计中,隐藏细节,对系统各层次进行描述(抽象),从而控制系统的
36、复杂程度。例如,在软件工程中,从规格说明到编码各个阶段(层次)的详细说明,计算机系统的分层思想,计算机网络的分层思想等。 8按空间排序(Ordering in Space) 按空间排序指的是各种定位方式,如物理上的定位(如网络和存储中的定位),组织方式上的定位(如处理机进程、类型定义和有关操作的定位)以及概念上的定位(如软件的辖域、耦合、内聚等)。按空间排序是计算技术中一个局部性和相邻性的概念。 9按时间排序(Ordering in Time) 按时间排序指的是事件的执行对时间的依赖性。例如,在具有时态逻辑的系统中,要考虑与时间有关的时序问题;在分布式系统中,要考虑进程同步的时间问题;在依赖于
37、时间的算法执行中,要考虑其基本的组成要素。,10重用(Reuse) 重用指的是在新的环境下,系统中各类实体、技术、概念等可被再次使用的能力。如软件库和硬件部件的重用等。 11安全性(Security) 安全性指的是计算机软硬件系统对合法用户的响应及对非法请求的抗拒,以保护自己不受外部影响和攻击的能力。如为防止数据的丢失、泄密而在数据库管理系统中提供的口令更换、操作员授权等功能。 12折衷和结论(Tradeoff and Consequences) 折衷指的是为满足系统的可实施性而对系统设计中的技术、方案所作出的一种合理的取舍。结论是折衷的结论,即选择一种方案代替另一种方案所产生的技术、经济、文化及其他方面的影响。折衷是存在于计算学科领域各层次上的基本事实。如在算法的研究中,要考虑空间和时间的折衷;对于矛盾的设计目标,要考虑诸如易用性和完备性、灵活性和简单性、低成本和高可靠性等方面所采取的折衷等。,5.8 本讲小结,算法是计算学科中最具方法论性质的核心概念,也被誉为计算学科的灵魂。一个算法,就是一个有穷规则的集合,其中之规则规定了一个解决某一特定类型问题的运算序列。 算法的重要特性有:有穷性、确定性、输入、输出、能行性。 算法是对解题过程的精确描述,这种描述是建立在语言基础之上的,表示算法的语言主要有自然语言、流程图、伪代码、计算机程序设计语言
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 蔬菜种子培育技术推广合同
- 2025至2030建材行业发展趋势分析与未来投资战略咨询研究报告
- 林业生态保护与利用合同
- 城市轨道交通智慧运维系统在2025年智慧交通网络中的数据驱动决策研究
- 采购合同质量保证协议条款附加合同
- 观后感作文天堂的孩子的观后感550字9篇范文
- 2025年金融科技企业估值模型构建与投资决策报告:金融科技产业链上下游分析
- 二零二五年度特色餐饮品牌独家加盟合作协议
- 2025年智能医疗健康服务平台商业模式创新报告
- 二零二五年环保设备制造参股协议书模板
- 2025春季学期国开电大专科《行政组织学》一平台在线形考(形考任务1至5)试题及答案
- 某矿业股份有限公司高管人员绩效考核与薪酬激励制度
- 动火作业施工方案
- 施工现场防汛安全教育
- 2025年ibm英语客服面试题及答案
- JJF1070-2023定量包装商品净含量计量检验规则
- 科技革命与产业变革-深度研究
- 部编初中历史八下第14课海峡两岸的交往教案
- 17J008挡土墙(重力式、衡重式、悬臂式)图示图集
- T管造影及胆道解剖培训课件
- 人工智能技术发展现状及未来趋势分析
评论
0/150
提交评论