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

《计算机软件34算法和计算机软件理论基础.ppt》由会员分享，可在线阅读，更多相关《计算机软件34算法和计算机软件理论基础.ppt（51页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第三章第三章 计算机软件计算机软件3.4 3.4 算法和计算机软件理论基础算法和计算机软件理论基础3.1 3.1 计算机软件及计算机软件技术计算机软件及计算机软件技术3.2 3.2 操作系统操作系统3.3 3.3 程序设计语言及语言处理程序程序设计语言及语言处理程序3.4 算法和数据结构算法和数据结构3.4.1 3.4.1 算法算法3.4.2 3.4.2 数据结构数据结构算法算法与程序与程序软件的主体是程序，程序的核心是算法软件的主体是程序，程序的核心是算法要要使使计计算算机机解解决决某某个个问问题题，首首先先针针对对问问题题设设计计一一个个解解题题步步骤骤，然然后后在在根根据据解解题题步步骤

2、骤编编写写程程序序并并交交给给计计算算机执行。机执行。这个这个“解题步骤解题步骤”就是算法。就是算法。算法算法与程序与程序算法（算法（AlgorithmAlgorithm）：）：问题求解规则的一种过程描述。问题求解规则的一种过程描述。在在算算法法中中要要精精确确定定义义一一系系列列规规则则，这这些些规规则则指指定定了了相相应应的的操操作作顺顺序序，目标是在有限的步骤内得到所求问题的解答。目标是在有限的步骤内得到所求问题的解答。算法设计方法：由粗到细，由抽象到具体的逐步求精方法算法设计方法：由粗到细，由抽象到具体的逐步求精方法程序：对解题对象和解题步骤用程序语言进行的一种描述。程序：对解题对象和

3、解题步骤用程序语言进行的一种描述。程序中用具有一定结构的变量来表示程序中用具有一定结构的变量来表示问题的对象问题的对象用函数和语句来实现用函数和语句来实现解题的操作解题的操作“算算法法”和和“数数据据结结构构”是是编编写写程程序序所所要要首首先先考考虑虑的的两两个个重要方面。重要方面。3.4.1 算法算法算法就是解决问题的方法与步骤算法就是解决问题的方法与步骤计算机计算机求解问题的步骤求解问题的步骤(1)确定并理解问题；确定并理解问题；(2)寻找解决问题的方法与步骤，并将其表示成寻找解决问题的方法与步骤，并将其表示成算法算法(Algorithm)；(3)使用某种程序设计语言描述该算法使用某种程

4、序设计语言描述该算法(编程编程),并进行调并进行调试；试；(4)运行程序，获得问题的解答；运行程序，获得问题的解答；(5)进行评估，改进算法和程序进行评估，改进算法和程序算法是解决问题的方法与步骤算法是解决问题的方法与步骤例：有三个硬币，其中一个是伪造的，另例：有三个硬币，其中一个是伪造的，另两个是真的，伪币与真币重量略有不两个是真的，伪币与真币重量略有不同。现在提供一座天平，同。现在提供一座天平，如何如何找出伪找出伪币呢？币呢？分析：分析：方法明确而有序方法明确而有序按提供的条件进行操作按提供的条件进行操作任何人均可仿照进行任何人均可仿照进行(共享智能共享智能)开始开始C是伪币是伪币B是伪币

5、是伪币A是伪币是伪币AB？AC？是是否否否否是是关于算法的三方面问题关于算法的三方面问题如何确定算法（算法设计）？如何确定算法（算法设计）？如何表示算法（算法表示）？如何表示算法（算法表示）？如何使算法更有效（算法分析）？如何使算法更有效（算法分析）？2.算法设计举例算法设计举例例如，要对包含例如，要对包含n个整数元素的数组个整数元素的数组A按元素值由小到大排序。按元素值由小到大排序。第第1遍，给出粗略的思路：遍，给出粗略的思路：从所有整数中选一个最小的，作为已排好序的第一个数；从所有整数中选一个最小的，作为已排好序的第一个数；在在剩剩下下的的未未排排序序整整数数中中选选出出最最小小的的，放放

6、在在已已排排好好序序列列的的最最后一个数后面；后一个数后面；反复执行反复执行，直到所有整数都放到已排好的序列中。，直到所有整数都放到已排好的序列中。第第2遍遍，细细化化，考考虑虑“序序列列存存放放在在何何处处”，如如何何“反反复复执执行行”等。用等。用“伪代码伪代码”描述为：描述为：for i=1 to n选出选出Ai到到An中最小的元素，设为中最小的元素，设为Aj；交换交换Ai和和j;筛选法排序 2 1 3 4 6 2 1 3 4 6不不交换交换交换交换 3 1 2 4 6 4 1 2 3 6交换交换交换交换 6 1 2 3 4 6 1 2 3 4交换交换 6 2 1 3 4交换交换交换交换

7、 6 3 1 2 4 6 4 1 2 3 6 4 1 2 3交换交换 6 4 2 1 3 6 4 3 1 2交换交换 6 4 3 1 2交换交换 6 4 3 2 1第一轮比较第一轮比较第二轮比较第二轮比较第三轮比较第三轮比较第四轮比较第四轮比较筛选法排序例：筛选法排序。（设从大到小排序）例：筛选法排序。（设从大到小排序）分析分析：将：将N个无序数据存放在个无序数据存放在 数组中，对数组进行数组中，对数组进行N-1轮扫视。轮扫视。第一轮扫视第一轮扫视：将：将A（1）与与A（2）比较，若比较，若A（1）A（2），），则交则交换换A（1）和和A（2）的值；再将的值；再将A（1）与与A（3）、）、A（

8、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 1For I=1 To

9、N 1Next INext I1.确定排序需要几轮的比较确定排序需要几轮的比较2.进行每一轮的比较进行每一轮的比较 For J=For J=To To Next JNext J1.确定排序需要几轮的比较确定排序需要几轮的比较2.进行每一轮的比较进行每一轮的比较3.在每一轮比较中，比较两在每一轮比较中，比较两 个数的大小，根据比较结个数的大小，根据比较结 果决定是否交换两个数果决定是否交换两个数If A(I)A(J)thenIf A(I)A(J)then T=A(T=A(I)A(I)=A(J)A(J)=TEnd IfEnd IfI I+1 1 N NText1=Text1&Text1=Text1

10、&StrStr(A(I)(A(I)Text1=Text1&Text1=Text1&StrStr(A(N)(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

11、遍，遍，具体给出如何选最小的元素，交换元素等，整合算法。具体给出如何选最小的元素，交换元素等，整合算法。第第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(AkN时，有时，有T(n)Cf(n)。空空间间复复杂杂度度：若若存存在在常常数数C和和N，当当问问题题规规模模nN时时，有有S(n)Cg(n)，则称该算法的空间代价（空间复杂度则称该算法的空间代价（空间复杂度）为）为O(g(n)

12、。算法分析算法分析从从数数学学上上看看，若若按按数数量量级级递递增增对对算算法法分分析析中中常常见见的的时时间间代代价价排排列列，则则它它们们依依次次为为常常数数阶阶O（1），对对数数阶阶O（log2n），线线性性阶阶O(n)，线线性性对对数数阶阶O（nlog2n），平平方方阶阶O(n2)，立立方方阶阶（n3）K次次方方阶阶O(nK)，指指数数阶阶O(2n)等等。时时间间代代价价为为指指数数阶阶O(2n)的的算算法法，其其效效率率极极低低，当当n值值稍稍大大时时，这这样样的的算算法法就就无无法法应用了应用了。算法的选择算法的选择使用次数较少的程序，应力求算法简明易读使用次数较少的程序，应力求算

13、法简明易读反复运行多次的程序，应尽可能选用快速的算法反复运行多次的程序，应尽可能选用快速的算法待待解解决决问问题题的的数数据据量量较较大大，算算法法设设计计时时应应主主要要考考虑虑如如何何节节省存储空间省存储空间算法设计方法算法设计方法 设计设计算法是有方法可循算法是有方法可循的。的。常常用用的的算算法法设设计计方方法法：迭迭代代法法、穷穷举举搜搜索索法法、递递推推法法、递递归归技技术术、分分治治法法、回溯法、回溯法、贪贪婪法和婪法和动态规动态规划法等。划法等。递归递归：算法算法实施过程中直接或间接地使用了实施过程中直接或间接地使用了算法本身算法本身。例如，例如，阶阶乘乘函数函数f f的的递归

14、递归定定义为义为：f(f(intint n)if(n=1)return 1;else return n*f(n-1);n)if(n=1)return 1;else return n*f(n-1);定定义阶义阶乘乘f f的迭代算法的迭代算法为为：f=1;i=1;f=1;i=1;while(i while(i n)n)f=f*i;i=i+1;f=f*i;i=i+1;return f;return f;递递归归本本质质上上是是一一种种循循环环结结构构，它它把把“较较复复杂杂”的的计计算算逐逐次次归归结结为为“较较简简单单”的的计计算，一直算，一直归结归结到到“最最简单简单”的的计计算，并得到算，并得

15、到计计算算结结果果为为止。止。算法设计方法算法设计方法 Private Sub Form_Click()Private Sub Form_Click()Dim Fact As Long,I As Integer,N As Integer Dim Fact As Long,I As Integer,N As Integer N=N=InputBoxInputBox(输入输入N)N)Fact=1 Fact=1 For I=1 To N For I=1 To N Fact=Fact*I Fact=Fact*I Next I Next I Print N;!=;Fact Print N;!=;Fact

16、End SubEnd Sub算法设计方法算法设计方法 Private Sub Command1_Click()Private Sub Command1_Click()Dim N As Integer Dim N As Integer N=N=InputBoxInputBox(输入输入N)N)Print Fact(N)Print Fact(N)End SubEnd SubPrivate Function Fact(N As Integer)As LongPrivate Function Fact(N As Integer)As Long Dim I As Integer Dim I As Int

17、eger If N=1 Then If N=1 Then Fact=1 Fact=1 Else Else Fact=N*Fact(N-1)Fact=N*Fact(N-1)End If End IfEnd FunctionEnd Function3.4.2 数据结构数据结构数据结构数据结构（Data Structures）：）：确确定定算算法法所所处处理理的的对对象象以以及及对对象象之之间间的的相相互互关关系系，并并将将它它们们以以计计算算机机的的数数据据的的形形式式进进行行表表示示，这这就就是是“数数据据结结构构”。研研究究如如何何在在计计算算机机中中表表示示被被处处理理的的对对象象及及对对象

18、象之之间间的的关关系系和运算和运算，即如何组织数据。，即如何组织数据。主要研究内容：主要研究内容：数据的逻辑结构数据的逻辑结构数据的存储结构数据的存储结构在数据结构上定义的运算的集合在数据结构上定义的运算的集合数据的逻辑结构数据的逻辑结构 数数据据的的逻逻辑辑结结构构是是数数据据间间关关系系的的描描述述；即即数数据据结结构构中中包包括括哪些元素，相互之间有什么关系等。哪些元素，相互之间有什么关系等。数数据据的的逻逻辑辑结结构构它它只只抽抽象象地地反反映映数数据据元元素素间间的的逻逻辑辑关关系系，而不管其在计算机中的存储方式。而不管其在计算机中的存储方式。例如：例如：线性结构线性结构网状结构网状

19、结构树形结构树形结构集合结构集合结构数据的逻辑结构数据的逻辑结构例如：例如：字字符符串串的的逻逻辑辑结结构构是是一一组组字字符符型型的的字字符符元元素素，该该字字符符串串中中字字符元素间有明显的符元素间有明显的前后顺序关系前后顺序关系。在以在以“学生属性学生属性”为数据元素的为数据元素的“学生属性表学生属性表”数据结构中，数据结构中，若若不不同同数数据据元元素素的的前前后后关关系系能能完完全全确确定定，则则确确定定了了称称为为“线线性表结构性表结构”的逻辑结构。的逻辑结构。在在以以“家家庭庭成成员员”为为数数据据元元素素的的“家家族族树树”中中，各各元元素素之之间间的的逻逻辑辑关关系系具具有有

20、层层次次性性，只只有有一一个个家家庭庭成成员员是是“家家族族树树”中中所所有有其其他他家家庭庭成成员员的的祖祖先先（称称为为根根），其其他他每每一一个个家家庭庭成成员员都都可可能能有有 0 个个或或多多个个子子女女，除除根根以以外外的的每每个个家家庭庭成成员员都都有有惟惟一一的的“双双亲亲”数数据据元元素素。这这种种数数据据结结构构称称为为“树树形形结构结构”还有二叉树、森林、多重表、图等逻辑结构还有二叉树、森林、多重表、图等逻辑结构2.线性数据结构线性数据结构 举例：线性表举例：线性表(Liner-List)定义：若干个相同类型的数据元素组成的一个有限序列，其中每个数据元定义：若干个相同类型

21、的数据元素组成的一个有限序列，其中每个数据元素可由多个素可由多个数据项数据项组成。表中有且仅有一个开始元素和一个结束元素，且组成。表中有且仅有一个开始元素和一个结束元素，且所有元素都最多只有一个直接前趋和一个直接后继所有元素都最多只有一个直接前趋和一个直接后继例：考生成绩登记例：考生成绩登记表表(table)数据元素已经排了序的线性表称为数据元素已经排了序的线性表称为有序线性表，有序线性表，简称简称有序表有序表34681张张 雷雷64834682王王 宁宁68234683周光明周光明58834684李霞霞李霞霞61534685钱钱 欣欣60834700赵赵 刚刚658准考准考证证号号姓名姓名总

22、总分分表中的每一行是表中的每一行是1 1个数据元素个数据元素每个数据元素包含每个数据元素包含3 3个数据项：个数据项：准考证号、姓名、总分准考证号、姓名、总分开开始始元元素素结结束束元元素素前趋元素前趋元素后继元素后继元素线性表的运算线性表的运算(操作操作)增加增加1 1个新的数据元素个新的数据元素删除删除1 1个指定数据元素个指定数据元素查找指定的数据元素查找指定的数据元素最高分考生最高分考生最低分考生最低分考生将表中的数据元素排序将表中的数据元素排序对表中的数据进行计算对表中的数据进行计算计算平均分计算平均分 34681张张 雷雷64834682王王 宁宁68234683周光明周光明588

23、34684李霞霞李霞霞61534685钱钱 欣欣60834700赵赵 刚刚658准考准考证证号号姓名姓名总总分分假设下面的有假设下面的有序表中姓名已序表中姓名已按拼音排序按拼音排序例：有序表的实现方法之例：有序表的实现方法之1使用使用数组数组实现，在内存中顺序存放元素：实现，在内存中顺序存放元素：如果要在表中加一个姓名如果要在表中加一个姓名:马马 明，结果为：明，结果为：程程 红红李李 军军刘刘 林林刘建平刘建平王晓林王晓林张小明张小明 010 016 022 028 034 040 046 程程 红红李李 军军刘刘 林林刘建平刘建平王晓林王晓林张小明张小明 010 016 022 028 0

24、34 040 046 马马 明明 分析：分析：寻找指定的数据元素很容易寻找指定的数据元素很容易插入元素或删除元素很不方便插入元素或删除元素很不方便程程 红红李李 军军刘刘 林林刘建平刘建平王晓林王晓林张小明张小明内内存存地地址址有序表的实现方法之有序表的实现方法之2使用链接表使用链接表(linked list)实现：实现：数据元素在内存中可不按顺序存放，它们之间的顺序用数据元素在内存中可不按顺序存放，它们之间的顺序用“指针指针”来表示来表示指针实际上就是后继数据元素的地址指针实际上就是后继数据元素的地址演示演示 2种实现方法的对比：种实现方法的对比：数组实现的空间开销少；存取指定元素的速度比较

25、块数组实现的空间开销少；存取指定元素的速度比较块链表实现时插入链表实现时插入/删除指定元素的速度快，表的长度不受限制删除指定元素的速度快，表的长度不受限制第第n个考生个考生 准考证号、姓名、准考证号、姓名、第第1个考生个考生 准考证号准考证号、姓名、姓名、Link第第2个考生个考生 准考证号、姓名、准考证号、姓名、Link第第3个考生个考生 准考证号、姓名、准考证号、姓名、Link数据的存储结构数据的存储结构数数据据的的存存储储结结构构：数数据据的的逻逻辑辑结结构构在在计计算算机机存存储储器器上上的的实实现现映映相。相。为全面地反映数据的逻辑结构，它在存储器中的映象应包括：为全面地反映数据的逻

26、辑结构，它在存储器中的映象应包括：数据元素自身的值数据元素自身的值数据元素之间的关系数据元素之间的关系同一个数据的逻辑结构可以有不同的存储结构同一个数据的逻辑结构可以有不同的存储结构实例实例数据结构的实现数据结构的实现存储结构存储结构顺序存储结构：顺序存储结构：借助数据元素在存储器中的相对位置来表示数据元素之间的借助数据元素在存储器中的相对位置来表示数据元素之间的逻辑关系逻辑关系链接表存储结构：链接表存储结构：利用地址指针来表示元素之间的逻辑关系利用地址指针来表示元素之间的逻辑关系a1a2低地址低地址高地址高地址a2是是a1的后继元素的后继元素a1 p1 a2a2是是a1的后继元素的后继元素数

27、据的存储结构数据的存储结构表示表示“线性表结构线性表结构”方方法法1 1：顺顺序序存存储储结结构构。元元素素逻逻辑辑关关系系的的前前后后用用顺顺序序存存储储位位置置值值的的大大小小表表达达。很很多多高高级级语语言言中中用用数数组组实实现现顺顺序序存存储储结结构构，数数据据元元素素自自身身的的值值放放在在数数组组元素单元中元素单元中方方法法2 2：链链接接结结构构。如如用用链链接接表表以以指指针针方方式式表表示示。设设计计一一个个节节点点有有两两部部分分，第第一一部部分分存存放放数数据据元元素素自自身身的的值值（学学号号、姓姓名名、专专业业，年年龄龄等等），第第二二部部分分表表示示该该元元素素与

28、与其其他他元元素素的的关关系系，存存放放的的值值是是它它的的后后继继元元素素存存储储的的指指针，称为链接信息域，最后一个元素链接信息域的值为针，称为链接信息域，最后一个元素链接信息域的值为（空指针）。（空指针）。学号、姓名学号、姓名学号、姓名学号、姓名infoinfolinklinkinfoinfolinklink第第1 1个个学生学生第第2 2个学生个学生第第n n个学生个学生学生表的链接结构学生表的链接结构学生表的链接结构学生表的链接结构学号、姓名学号、姓名infoinfolinklink数据的运算数据的运算每每种种逻逻辑辑结结构构都都有有一一个个可可施施行行运运算算的的集集合合，常常用用

29、的的运运算算有有：检检索、插入、删除、更新、排序等索、插入、删除、更新、排序等数数据据的的运运算算定定义义在在数数据据逻逻辑辑结结构构上上，而而其其运运算算的的具具体体实实现现要要在在存储结构上进行存储结构上进行数据结构、数据运算及实现算法是相互关联的数据结构、数据运算及实现算法是相互关联的在程序设计语言中，在程序设计语言中，主要用数据类型反映数据结构。主要用数据类型反映数据结构。简简单单的的数数据据结结构构可可用用单单一一的的标标准准数数据据类类型型（如如整整型型、实实型型和字符型等）来定义和字符型等）来定义复复杂杂的的数数据据结结构构则则需需用用简简单单类类型型的的复复合合构构造造（如如数

30、数组组、记记录、指针等）来实现录、指针等）来实现还可还可将数据的逻辑结构与运算一并定义为对象来实现。将数据的逻辑结构与运算一并定义为对象来实现。小小 结结 1数据结构研究如何在计算机中描述操作对象和操作对象之间的关系：数据结构研究如何在计算机中描述操作对象和操作对象之间的关系：所有操作对象在计算机中均表示为某种类型的数据所有操作对象在计算机中均表示为某种类型的数据(或数据结构或数据结构)操作对象之间的关系可以刻画为：操作对象之间的关系可以刻画为：每一种数据结构均有每一种数据结构均有3个方面的内容：个方面的内容：设计其概念结构（逻辑结构）设计其概念结构（逻辑结构）设计其存储结构（物理结构）设计其

31、存储结构（物理结构）设计并实现其运算（操作）设计并实现其运算（操作）集合结构集合结构线性结构线性结构树形结构树形结构网状结构网状结构小小 结结 2数据结构与高级程序设计语言的关系：数据结构与高级程序设计语言的关系：初级初级(基本基本)数据类型数据类型 语言本身定义语言本身定义(扩充扩充)的数据类型的数据类型程序员定制的新的数据类型程序员定制的新的数据类型瑞士计算机科学家尼瑞士计算机科学家尼沃思（沃思（N.Wirth）在在20世纪世纪70年代曾经提出过一年代曾经提出过一个著名公式：个著名公式：“数据结构数据结构+算法算法=程序程序”之后他又提出：之后他又提出：“计算机科学就是研究算法的学问计算机

32、科学就是研究算法的学问”数据结构数据结构计算机软件理论基础计算机软件理论基础数数学学与与电电子子学学等等学学科科一一起起奠奠定定了了计计算算机机科科学学的的基基础础，而而数数学学特特别别是是计计算算机机软软件件的的理理论论基基础础。计计算算机机科科学学也也推推动动了了数数学学的的发发展。展。数学的地位数学的地位程程序序设设计计就就是是数数理理逻逻辑辑，或或者者是是用用计计算算机机语语言言书书写写的的数数理理逻辑，或者是数理逻辑在计算机上的应用。逻辑，或者是数理逻辑在计算机上的应用。主要数学分支主要数学分支 数值计算数值计算 离散数学离散数学 计算理论计算理论 程序理论程序理论数值计算数值计算（

33、numerical computation）研研究究使使用用计计算算机机求求解解各各种种数数学学问问题题的的数数值值方方法法，包包括括离离散散型型方程和连续系统离散化的数值求解。方程和连续系统离散化的数值求解。需要考虑误差、收敛性和稳定性等因素。需要考虑误差、收敛性和稳定性等因素。包包括括数数值值逼逼近近、数数值值微微分分与与数数值值积积分分、数数值值代代数数、最最优优化化方方法法、常常（偏偏）微微分分方方程程数数值值解解法法、积积分分方方程程数数值值解解法法、计计算算几何，计算概率统计等。几何，计算概率统计等。离离散散数学数学（discrete mathematicsdiscrete mat

34、hematics）特特点点：涉涉及及的的许许多多数数学学学学科科大大多多具具有有“离离散散性性”和和“能能行性行性”的特点的特点“离离散散数数学学”：是是以以离离散散结结构构为为主主要要研研究究对对象象且且与与计计算算机科学技术密切相关的一些现代数学分支的总称。机科学技术密切相关的一些现代数学分支的总称。主主要要包包括括：集集合合论论，逻逻辑辑学学、抽抽象象代代数数、范范畴畴论论、图图论论、计算数论、组合学等。、计算数论、组合学等。计算理论计算理论（theory of computationtheory of computation）计算理论是关于计算和计算机械的数学理论。计算理论是关于计算和

35、计算机械的数学理论。19361936年年，对对于于每每个个问问题题是是否否都都有有求求解解算算法法的的讨讨论论，导导致致创创造造了了递递归归函函数数论论，提提出出了了理理想想计计算算机机和和通通用用图图灵灵机的概念机的概念近近代代研研究究的的焦焦点点从从理理论论可可计计算算性性转转移移到到现现实实可可计计算算性性，产产生生了了算算法法学学和和计计算算复复杂杂性性理理论论、自自动动机机理理论论和和形形式式语言理论等。语言理论等。程序理论程序理论（Theory of ProgramsTheory of Programs）是研究程序的语义性质、程序设计及开发方法的理论。是研究程序的语义性质、程序设计

36、及开发方法的理论。基基本本问问题题：如如何何建建立立一一个个相相对对完完善善的的理理论论框框架架，为为软软件件的的设设计和开发方法提供理论依据。这个框架计和开发方法提供理论依据。这个框架应能提供有效地描述程序规约的语言；应能提供有效地描述程序规约的语言；应应能能定定义义可可操操作作的的变变换换方方法法以以便便能能规规约约构构造造可可执执行行的的程程序；序；应能给出验证程序与其规约之间一致性的机制应能给出验证程序与其规约之间一致性的机制包包括括：程程序序语语义义理理论论、程程序序逻逻辑辑理理论论、类类型型理理论论、程程序序验验证证理理论论、并并发发程程序序理理论论等等。进进入入19801980年年代代后后，并并行行程程序序理理论论和和网格计算理论已发展，成为新的重要分支。网格计算理论已发展，成为新的重要分支。