计算机软件34算法和计算机软件理论基础.ppt

第三章 计算机软件,3.4 算法和数据结构,算法与程序,软件的主体是程序，程序的核心是算法要使计算机解决某个问题，首先针对问题设计一个解题步骤，然后在根据解题步骤编写程序并交给计算机执行。这个“解题步骤”就是算法。,算法与程序,算法（Algorithm）：问题求解规则的一种过程描述。在算法中要精确定义一系列规则，这些规则指定了相应的操作顺序，目标是在有限的步骤内得到所求问题的解答。算法设计方法：由粗到细，由抽象到具体的逐步求精方法程序：对解题对象和解题步骤用程序语言进行的一种描述。程序中用具有一定结构的变量来表示问题的对象用函数和语句来实现解题的操作“算法”和“数据结构”是编写程序所要首先考虑的两个重要方面。,3.4.1 算法,算法就是解决问题的方法与步骤,计算机求解问题的步骤,(1)确定并理解问题；(2)寻找解决问题的方法与步骤，并将其表示成算法(Algorithm)；(3)使用某种程序设计语言描述该算法(编程),并进行调试；(4)运行程序，获得问题的解答；(5)进行评估，改进算法和程序,算法是解决问题的方法与步骤,例：有三个硬币，其中一个是伪造的，另两个是真的，伪币与真币重量略有不同。现在提供一座天平，如何找出伪币呢？分析：方法明确而有序按提供的条件进行操作任何人均可仿照进行(共享智能),关于算法的三方面问题,如何确定算法（算法设计）？如何表示算法（算法表示）？如何使算法更有效（算法分析）？,2.算法设计举例,例如，要对包含n个整数元素的数组A按元素值由小到大排序。第1遍，给出粗略的思路：从所有整数中选一个最小的，作为已排好序的第一个数；在剩下的未排序整数中选出最小的，放在已排好序列的最后一个数后面；反复执行，直到所有整数都放到已排好的序列中。第2遍，细化，考虑“序列存放在何处”，如何“反复执行”等。用“伪代码”描述为：for i=1 to n选出Ai到An中最小的元素，设为Aj；交换Ai和j;,筛选法排序,第一轮比较,第二轮比较,第三轮比较,第四轮比较,筛选法排序,例：筛选法排序。（设从大到小排序）分析：将N个无序数据存放在 数组中，对数组进行N-1轮扫视。第一轮扫视：将A（1）与A（2）比较，若A（1）A（2），则交换A（1）和A（2）的值；再将A（1）与A（3）、A（4）A（N）依次按以上规则比较和交换，第一轮扫视完毕，N个数中最大数存放到A（1）中。第二轮扫视：将A（2）与A（3）、A（4）A（N）依次按以上规则比较；第三轮扫视：将A（3）与A（4）、A（5）A（N）依次按以上规则比较；这样N-1轮扫视下来排序完成。,筛选法排序,假定待排序的N个数已存放在数组 A 中,1.确定排序需要几轮的比较,For I=1 To N 1Next I,1.确定排序需要几轮的比较2.进行每一轮的比较,For J=To Next J,1.确定排序需要几轮的比较2.进行每一轮的比较3.在每一轮比较中，比较两 个数的大小，根据比较结 果决定是否交换两个数,If A(I)A(J)then T=A(I)A(I)=A(J)A(J)=TEnd If,I+1,N,Text1=Text1&Str(A(I),Text1=Text1&Str(A(N),筛选法排序,假定数据已放入A数组中，I，J，T变量均为整型变量Option ExplicitOption Base 1Dim A(10)As IntegerPrivate Sub Cmd数据准备_Click()Dim I As Integer Randomize For I=1 To 10 A(I)=Int(100-9)*Rnd)+1 Text1=Text1&Str(A(I)Next IEnd Sub,返回,算法设计举例,第3遍，具体给出如何选最小的元素，交换元素等，整合算法。第4遍，选择程序语言编程，如用C语言编写的函数模块sort如下：,void sort(int A,int n)int i,min,t;for(i=0;in-1;i+)min=i;for(k=i+1;kn;k+)if(AkAmin)min=k;t=Ai;Ai=Amin;Amin=t;,算法,什么是算法,在计算机学科中,算法指的是用于完成某个信 息处理任务的一组有序而明确的、可以由计算机执行的操作(或指令),它能在有限时间内执行结束并产生结果。这里所说的操作(指令)，必须是计算机可以执行的而且是十分明确的(什么样的输入一定得到什么样的输出）。计算机算法是一个有终结的过程,它必须在有限步瑕内得到所 求问题的解答。,算法体现了解决问题所需的智能。是一种将智能与他人共享的途径,算法的基本性质,确定性：算法中的每一步运算必须有确切的定义，无二义性。有穷性:(可终结性)一个算法总是在执行了有穷步运算后终止能行性：算法中有待实现的运算都是基本的、能精确进行的，且能在有限的时间内完成。输入：具有0个或多个输入量。输出：至少产生一个输出（包括参量状态的变化）,算法的一个显著的特点：它是解决的是一类问题而不是解决一个特定的问题。,算法与程序的区别,终止性区别：一个程序不一定满足有穷性。例如一个操作系统程序。能行性区别：程序中的指令必须是具体机器可执行的，所有细节必须精确描述；对算法中的运算语句无此限制。可略过可实现的细节，采用“伪代码”、流程图等方式来描述算法。,虽然算法与计算机程序密切相关，但二者也存在区别：计算机程序是算法的一个实例，是将算法通过某种计算机语言表达出来的具体形式；同一个算法可以用任何一种计算机语言来表达。,3.算法的表示,算法的表示方法,文字说明流程图表示用N-S盒图表示算法用PAD图描述算法伪代码（一种介于自然语言和程序设计语言之间的文字和符号表达工具）,自然语言描述,“比较与的重量，若，则是伪造的；否则再比较与的重量，若，则是伪造的；否则是伪造的。”缺点：容易产生歧义，很难“精确”地进行表达叙述冗长，很难清楚地表达算法的逻辑流程,算法的流程图表示,流程图由结点和有向边构成，它描述了算法所执行操作的顺序及执行操作的条件流程图符号：,比文字描述简明，但当算法比较复杂时，理解困难，容易产生错误,求最大公约数的伪代码表示,算法3：辗转相除法求最大公约数BEGIN input m,n;/*输入正整数m和n*/do rm mod n;m n;n r;while r0;print m；/*输出最大公约数*/END,4.算法的分析,算法分析的基本内容,正确性：给定有效输入后，经过有限时间的计算，产生正确的输出结果简单性 算法是否容易理解，是否容易验证其正确性，程序是否容易调试简单的算法效率不一定高，要在保证一定效率的前提下力求算法简两个度量特性执行算法所要占用的计算机资源的多少，主要有时间复杂度和空间复杂度两个方面。时间复杂性(Time Complexity)：当问题的规模n充分大时，运行该算法所需要的时间的数量级表示 T(n)空间复杂性(Space Complexity)：除原始数据之外，额外占用的存储空间的大小g(n),算法分析,对一个正确的算法，分析其好坏时，应考虑以下因素：算法是否易理解，是否易调试和易测试等执行算法所要占用的计算机资源的多少，主要有时间复杂度和空间复杂度两个方面。两个度量特性 当问题的规模以某种单位由1增至n时时间代价：解决该问题的算法运行所耗费的时间，以某种单位由T(1)增至T(n)，则称该算法的时间代价为T(n)。T(n)表示的是，当问题的规模n充分大时，运行该算法程序所需时间的数量级表示空间代价：解决该问题的算法实现时所占用存储空间也以某种单位由g(1)增至g(n)，则称该算法的空间代价为g(n)。,选择排序算法的时间复杂性,假设参加排序的整数有n个（1）比较操作的次数：在第i趟排序中选出最小整数时，需做n-i次比较操作，因此，总的比较操作次数为：n(n-1)/2=(n2-n)/2（2）移动操作的次数：最好情况(原始数据已经排序)时，移动次数为0最坏情况(原始数据逆序排列)时，每趟均要执行交换操作(3次传送)，总的移动次数取最大值为：3(n-1)所以，直接选择排序的时间复杂性 为 O(n2),设置i的初值为1，循环执行下列操作，直到I=n：确定Ai 到An中最小的整数元素的位置，设为j；交换Ai和j；i=i+1,算法分析,时间复杂度只是对执行算法所需占用的计算机时间资源的预测，类似地，空间复杂度是对算法所需空间资源的预测。算法分析时，通常把整个程序中重复执行基本运算的次数之和作为该程序的运行时间特性，记为T(n)实际时间代价是依据算法编制为程序后在计算机中运行时所耗费的时间大小来确定的。,算法分析,算法分析结果的上界比具体的表达式更有意义。因此，常用“O函数”来近似地表示算法分析的（数量级）结果。称某算法的时间代价（或时间复杂性）T(n)=O(f(n)，则意味着存在常数C和N，当问题规模nN时，有T(n)Cf(n)。空间复杂度：若存在常数C和N，当问题规模nN时，有S(n)Cg(n)，则称该算法的空间代价（空间复杂度）为O(g(n)。,算法分析,从数学上看，若按数量级递增对算法分析中常见的时间代价排列，则它们依次为常数阶O（1），对数阶O（log2n），线性阶O(n)，线性对数阶O（nlog2n），平方阶O(n2)，立方阶（n3）K次方阶O(nK)，指数阶O(2n)等。时间代价为指数阶O(2n)的算法，其效率极低，当n值稍大时，这样的算法就无法应用了。算法的选择使用次数较少的程序，应力求算法简明易读反复运行多次的程序，应尽可能选用快速的算法待解决问题的数据量较大，算法设计时应主要考虑如何节省存储空间,算法设计方法,设计算法是有方法可循的。常用的算法设计方法：迭代法、穷举搜索法、递推法、递归技术、分治法、回溯法、贪婪法和动态规划法等。递归：算法实施过程中直接或间接地使用了算法本身。例如，阶乘函数f的递归定义为：f(int n)if(n=1)return 1;else return n*f(n-1);定义阶乘f的迭代算法为：f=1;i=1;while(i n)f=f*i;i=i+1;return f;递归本质上是一种循环结构，它把“较复杂”的计算逐次归结为“较简单”的计算，一直归结到“最简单”的计算，并得到计算结果为止。,算法设计方法,Private Sub Form_Click()Dim Fact As Long,I As Integer,N As Integer N=InputBox(输入N)Fact=1 For I=1 To N Fact=Fact*I Next I Print N;!=;FactEnd Sub,算法设计方法,Private Sub Command1_Click()Dim N As Integer N=InputBox(输入N)Print Fact(N)End SubPrivate Function Fact(N As Integer)As Long Dim I As Integer If N=1 Then Fact=1 Else Fact=N*Fact(N-1)End IfEnd Function,3.4.2 数据结构,数据结构（Data Structures）：确定算法所处理的对象以及对象之间的相互关系，并将它们以计算机的数据的形式进行表示，这就是“数据结构”。研究如何在计算机中表示被处理的对象及对象之间的关系和运算，即如何组织数据。主要研究内容：数据的逻辑结构数据的存储结构在数据结构上定义的运算的集合,数据的逻辑结构,数据的逻辑结构是数据间关系的描述；即数据结构中包括哪些元素，相互之间有什么关系等。数据的逻辑结构它只抽象地反映数据元素间的逻辑关系，而不管其在计算机中的存储方式。例如：,数据的逻辑结构,例如：字符串的逻辑结构是一组字符型的字符元素，该字符串中字符元素间有明显的前后顺序关系。在以“学生属性”为数据元素的“学生属性表”数据结构中，若不同数据元素的前后关系能完全确定，则确定了称为“线性表结构”的逻辑结构。在以“家庭成员”为数据元素的“家族树”中，各元素之间的逻辑关系具有层次性，只有一个家庭成员是“家族树”中所有其他家庭成员的祖先（称为根），其他每一个家庭成员都可能有 0 个或多个子女，除根以外的每个家庭成员都有惟一的“双亲”数据元素。这种数据结构称为“树形结构”还有二叉树、森林、多重表、图等逻辑结构,2.线性数据结构,举例：线性表(Liner-List),定义：若干个相同类型的数据元素组成的一个有限序列，其中每个数据元素可由多个数据项组成。表中有且仅有一个开始元素和一个结束元素，且所有元素都最多只有一个直接前趋和一个直接后继例：考生成绩登记表(table),数据元素已经排了序的线性表称为有序线性表，简称有序表,每个数据元素包含3个数据项：准考证号、姓名、总分,线性表的运算(操作),增加1个新的数据元素删除1个指定数据元素查找指定的数据元素最高分考生最低分考生将表中的数据元素排序对表中的数据进行计算计算平均分,例：有序表的实现方法之1,使用数组实现，在内存中顺序存放元素：,如果要在表中加一个姓名:马 明，结果为：,分析：寻找指定的数据元素很容易插入元素或删除元素很不方便,内存地址,有序表的实现方法之2,使用链接表(linked list)实现：数据元素在内存中可不按顺序存放，它们之间的顺序用“指针”来表示指针实际上就是后继数据元素的地址,演示,2种实现方法的对比：数组实现的空间开销少；存取指定元素的速度比较块链表实现时插入/删除指定元素的速度快，表的长度不受限制,数据的存储结构,数据的存储结构：数据的逻辑结构在计算机存储器上的实现映相。为全面地反映数据的逻辑结构，它在存储器中的映象应包括：数据元素自身的值数据元素之间的关系同一个数据的逻辑结构可以有不同的存储结构实例,数据结构的实现存储结构,顺序存储结构：借助数据元素在存储器中的相对位置来表示数据元素之间的逻辑关系链接表存储结构：利用地址指针来表示元素之间的逻辑关系,数据的存储结构,表示“线性表结构”方法1：顺序存储结构。元素逻辑关系的前后用顺序存储位置值的大小表达。很多高级语言中用数组实现顺序存储结构，数据元素自身的值放在数组元素单元中方法2：链接结构。如用链接表以指针方式表示。设计一个节点有两部分，第一部分存放数据元素自身的值（学号、姓名、专业，年龄等），第二部分表示该元素与其他元素的关系，存放的值是它的后继元素存储的指针，称为链接信息域，最后一个元素链接信息域的值为（空指针）。,数据的运算,每种逻辑结构都有一个可施行运算的集合，常用的运算有：检索、插入、删除、更新、排序等数据的运算定义在数据逻辑结构上，而其运算的具体实现要在存储结构上进行数据结构、数据运算及实现算法是相互关联的在程序设计语言中，主要用数据类型反映数据结构。简单的数据结构可用单一的标准数据类型（如整型、实型和字符型等）来定义复杂的数据结构则需用简单类型的复合构造（如数组、记录、指针等）来实现还可将数据的逻辑结构与运算一并定义为对象来实现。,小 结 1,数据结构研究如何在计算机中描述操作对象和操作对象之间的关系：所有操作对象在计算机中均表示为某种类型的数据(或数据结构)操作对象之间的关系可以刻画为：每一种数据结构均有3个方面的内容：设计其概念结构（逻辑结构）设计其存储结构（物理结构）设计并实现其运算（操作）,小 结 2,数据结构与高级程序设计语言的关系：初级(基本)数据类型 语言本身定义(扩充)的数据类型程序员定制的新的数据类型瑞士计算机科学家尼沃思（N.Wirth）在20世纪70年代曾经提出过一个著名公式：“数据结构+算法=程序”之后他又提出：“计算机科学就是研究算法的学问”,计算机软件理论基础,数学与电子学等学科一起奠定了计算机科学的基础，而数学特别是计算机软件的理论基础。计算机科学也推动了数学的发展。数学的地位程序设计就是数理逻辑，或者是用计算机语言书写的数理逻辑，或者是数理逻辑在计算机上的应用。主要数学分支 数值计算 离散数学 计算理论 程序理论,数值计算（numerical computation）,研究使用计算机求解各种数学问题的数值方法，包括离散型方程和连续系统离散化的数值求解。需要考虑误差、收敛性和稳定性等因素。包括数值逼近、数值微分与数值积分、数值代数、最优化方法、常（偏）微分方程数值解法、积分方程数值解法、计算几何，计算概率统计等。,离散数学（discrete mathematics）,特点：涉及的许多数学学科大多具有“离散性”和“能行性”的特点“离散数学”：是以离散结构为主要研究对象且与计算机科学技术密切相关的一些现代数学分支的总称。主要包括：集合论，逻辑学、抽象代数、范畴论、图论、计算数论、组合学等。,计算理论（theory of computation）,计算理论是关于计算和计算机械的数学理论。1936年，对于每个问题是否都有求解算法的讨论，导致创造了递归函数论，提出了理想计算机和通用图灵机的概念近代研究的焦点从理论可计算性转移到现实可计算性，产生了算法学和计算复杂性理论、自动机理论和形式语言理论等。,程序理论（Theory of Programs）,是研究程序的语义性质、程序设计及开发方法的理论。基本问题：如何建立一个相对完善的理论框架，为软件的设计和开发方法提供理论依据。这个框架应能提供有效地描述程序规约的语言；应能定义可操作的变换方法以便能规约构造可执行的程序；应能给出验证程序与其规约之间一致性的机制包括：程序语义理论、程序逻辑理论、类型理论、程序验证理论、并发程序理论等。进入1980年代后，并行程序理论和网格计算理论已发展，成为新的重要分支。,