课程的主要研究问题.DOC

1、课程的主要研究问题 程序设计的基本特征结构化 模块化对象化 （OOP，Object Oriented Programming ）智能化 （AOP， Agent Oriented Programming） 程序设计标准化问题形式语义 代数规范程序正确性的代数证明 程序的形式推导 程序变换技术 程序设计标准实施问题设计风格 设计方法 设计工具 设计技巧研究内容程序设计方法学的基本研究目标是通过对程序本质属性的研究来提高程序的效率，保证程序的正确性 。通俗地说，程序设计方法学的最基本目标是通过对程序本质属性的研究，说明什么是“优秀”的程序，怎样才能设计出“优秀”的程序。 程序设计方法学是讲述程序性质

2、以及程序设计理论和方法的一门学科。程序设计方法学1基本内容结构化程序设计方法模块化程序设计方法面向对象程序设计方法函数型程序设计方法逻辑程序设计方法程序设计方法发展趋势程序正确性证明技术 程序形式推导技术程序变换技术 程序调试技术抽象数据类型 代数规范理论类型系统理论 复杂性分析技术基本方法基本理论“优秀”和“不优秀 ”程序的要素 正确性；结构化；模块化；可重用 可维护；可变化；可管理；可测试 性能均衡 错误的；非结构化； 难以维护；不能适应变化；不可管理 性能与条件失衡第一章 程序设计方法概论学习重点：了解程序设计语言、程序设计方法之间的关系了解程序设计方法形成和发展的过程掌握常见程序设计方

3、法的概况1.1 程序设计语言和程序设计方法1.1.1 程序设计语言概述一、定义：程序设计语言是一种用于书写计算机程序的语言。语言的基础是一组记号和一组规则。程序设计语言是人机交互的一种表达方法，是使用计算机的一种工具。程序设计语言是建立计算机精确处理模型与人类智能处理模型之间的某种形式化的桥梁。二、怎样理解和使用程序设计语言？（1）语法：规定程序的结构或形式，记号串的组成规则；（2）语义：程序的含义，记号的特定意义；（3）语用：程序和使用者之间的关系，人机交互的表达方式；（4）语境：理解、执行和实现程序的环境，预定义成分、与系统实现有关的成分，输入输出。三、程序设计语言的发展1、第一代语言：机

4、器语言。 机器语言是最早的计算机语言； 运行效率高。它用二进制代码表示数据和指令，这些代码不用翻译即可在计算机上直接执行； 指令难记，程序难读。编写机器语言程序是一件枯燥而繁杂的工作，存储空间的安排、寄存器变址的使用都由程序员自己计划，且所有的地址分配都是以绝对地址的形式处理； 要把为一种机器编制的程序搬到另一种机器上去运行根本行不通。因为不同的机器有不同的指令系统。2、第二代语言：汇编语言。 汇编语言是一种比机器语言更接近于自然语言和数学语言的低级程序设计语言。 指令采用助记符表示容易记忆，程序也更容易阅读。由于汇编语言一般都是为特定计算机或计算机系统设计的，因此它虽然比机器语言好学，好记，

5、程序也好写些，但仍然没有解决机器语言存在的问题，其生产效率也很低。 汇编语言也是面向机器的。它能直接操作计算机的寄存器、内存单元和输入/输出端口，能够设计出执行效率很高的程序，因而汇编语言在某些领域仍有应用。 用汇编语言编写的程序需经汇编程序翻译成机器语言程序后才能在计算机上运行。 汇编语言指令与机器指令基本上是一对一的关系，但有的汇编语言中可以有宏指令，它对应于一串机器指令。机器语言和汇编语言 原始的冯.诺依曼机器（1946 年）代码000000101011110010100000001011111100100000000011001110101000机器语言是晦涩难懂的，因此需要设计另外一

6、种语言来写程序，它应该是符号式的或者说助记性的。高级语言的优越性：可扩展性；可读性；可移植性3、第三代语言：高级语言。是指人容易理解和有利于人对解题过程进行描述的程序语言，通常所讲的程序设计语言往往指的是高级语言。一、命令式语言 科学计算的语言Backus1957为 Fortran 的成功预备了两个成分：记法和效率APL 是唯一使用带有专用符号的交互式键盘来编写程序的语言。 商用语言第一个商用语言是 COBOL(面向商业的公用语言的缩写 )。它是一种功能很强而又极为冗长的语言BASIC 设计者的最意图体现在该语言的名字上-初学者通用的符号指令码 多用途语言Alogol60 主导 20 世纪 6

7、0 年代程序设计语言的发展。Pascal 作为教学语言扩展了 AlgolDennis Ritchie1972 年创建 C 语言二、 函数式语言 1958 年 MCarthy 设计了 LISP 用作符号演算，具有严格的理论基础 Standard ML、Miranda 、Haskell 对语言发展的推动作用 1984 年 CLOS 是 LISP 的面向对象扩展，全名是 Common Lisp Object System三、 面向对象语言 Simula :Kristen Nygaard 和 Ole-Jodan Dahl 在 1961 年设计了这个语言，目的是想同时作为一种描述语言和程序设计语言 Sm

8、alltalk 是第一个严格意义的全面向对象的程序设计语言，它的设计受到了 LISP的影响 C+设计的是为了把面向对象的优点带进 C 的命令式程序设计中 JAVA 是面向对象程序设计语言的成熟标志 你需要知道的一些面向对象程序设计语言和相关语言Algol Ada Smalltalk C C+ JAVA4、第四代语言：第四代语言是抽象层次更高的程序设计语言，它把程序员从繁杂的过程性设计中解放出来，用自己的语法形式表示控制和数据结构，不再涉及太多的算法细节。使用最广的第四代语言是数据库语言，它支持用户以复杂的方式操作数据库，用户只需关心做什么，而不用关心怎么做，可以用类自然语言的形式提问。程序生成

9、器是更为复杂的一类 4GL，它输入由甚高级语言书写的语句，自动产生完整的第三代语言程序。四、 程序设计语言的实现实现系统:任何一个程序设计语言都有一个实现系统 (如编译系统或解释系统)与之匹配。用户使用程序语言编制出的源程序必须通过实现系统的加工处理。1 转换机制:源语言目标语言a、纵向转换：源语言机器语言（汇编语言）翻译程序:它是这样一个计算机程序 ,能把用高级语言书写的程序翻译为等价的机器语言或汇编语言.翻译程序主要有编译程序和解释程序。编译程序：是一种把用高级语言编写的源程序作为输入，经过翻译变换产生出面向目标计算机的目标代码程序作为输出的翻译程序。编译程序比较重视目标代码的效率。FOR

10、TRAN 语言采用这种方式。解释程序：是一种一边解释用高级语言编写的源程序的语句，一边根据解释的结果直接执行。解释程序花费的机器时间要多些，但所占的内存要少些。解释程序源程序 结果数据编译程序设计概述1、词法分析：区别、分离出源程序行文中一个一个的单词，如标识符、保留字、常量、运算符、定界符等。2、语法分析：识别出源程序的基本结构，如模块、子程序、分程序、程序包、数据说明、语句等，并生成有关表格（含语义分析的有关工作） 。3、中间代码生成：根据语法分析阶段识别出的语法范畴产生相应的中间代码。中间代码有多种形式，如逆波兰表示法，三元式、四元式等。4、优化处理：主要任务是对前一阶段所产生的代码进行

11、时间与空间的优化。5、目标代码生成：根据中间代码及有关表格生成可在裸机上执行的目标代码，其中包括内存与寄存器的分配等工作。词法分析语法分析语义分析与中 间代码生成优化处理目标代码生成表格管理输 入输 出处 理源程序目标 程序其它 编译信息中间 代码程序语义错误信息语法 错误信息b、横向转换：以描述语言 Li 表示的源程序 SLi以描述语言 Lj 表示的源程序 SLjLi LjFi GjLijPSLjSLi实现系统2 中间语言在语言的实现过程中产生的非目标语言。中间语言的作用：（1）如中间语言是汇编语言，可实现混合编程。可方便地调用库过程、库函数、外部过程和函数，实现链接功能的扩充和统一。（2）

12、作为两种语言的翻译语言，实现翻译功能。Fi（Li）=MGj（M ）=LjLi Lj中间语言MFi Gj（3）形成中间语言是编译过程中必不可少的过程。在编译过程中的每一趟均存在着不同形式的中间语言。（4）中间语言提供了不依赖于机器的语言实现机制；Java 的编译器把 Java 的源程序转换成字节码，它不依赖机器，可以看作中间语言，字节码由 Java 的运行系统解释执行。（5）在函数式语言中，中间语言（计算模型）是描述对象和控制策略的工具。4 语言的等价性理解:重在功能等价。a、源程序级的功能等价：编译过程中产生的中间语言程序和目标程序，它们的功能是相同的。相同的输入产生相同的输出。从操作语义上理

13、解：meaning(SL)= meaning(SML1)= meaning(SML2)= meaning(SOL)b、不同语言之间的功能等价：定义 1：对于算法 A，采用两个程序设计语言 PL1 和 PL2，所编出源程序 SPL1（A ）和SPL2（A） ，如果则对于算法 A， PL1 和 PL2 是等价的。定义 2：如果对于任何算法，定义 1 都满足，则称 PL1 和 PL2 是语言功能等价的。c、不同语言的语法单位的功能等价（横向软件工程中经常用到）：例 1：数据类型定义：PASCAL 语言：var x:real;C 语言：float x;ADA 语言：x: float;例 2：循环语句：

14、PASCAL 语言：REPEATS1；UNTIL B；C 语言：DOS1；while（!B） ；注意：C 语言是条件为假时退出循环。d、同一种语言中，相同功能的不同实现。例 1：while B do S与 if 语句的等价：L1：if B thenbeginS；goto L1；end else goto L2;L2:例 2：循环语句之间的等价：PASCAL 语言：REPEATS1；UNTIL B；等价为：S1；while（!B）do S1例 3：if 语句与 case 语句之间的等价：PASCAL 语言：if B then s1 else s2等价为：i:=BoolIntTran(B);CAS

15、E i of 1: S1;2: S2;end CASE;例 4： case 语句与 if 语句之间的等价：PASCAL 语言：CASE i of 1: S1;2: S2;3: S3;4: S4;end CASE;等价为：if i=1 then S1;else if i=2 then S2;else if i=3 then S3;else S4;四、程序设计语言的设计原则1、什么样的语言可以成功？满足市场需要（解决实际问题，较高的性价比） ；满足用户需要（适用、高效、可靠）满足理论价值需要（语言设施完备、严密、科学）2、程序设计语言的设计原则（1）定义严密性：对语言的语法、语义、语用和语境有严密

16、的定义，语法正确、语义合理、语用清楚、语境明确。（2）可靠性：信息隐藏、数据抽象、类属机制、模块独立。（3）可读性：English_like 表示，结构化语法（4）可维护性：模块独立、数据抽象、分别编译（5）效率：以该语言编写的程序能以最小的资源（时间和空间）消耗实现其预定的功能的程度。从执行过程考察，递归和回溯，解释执行和编译执行（6）可移植性：语言成分与实现环境之间的最小依赖程度。依赖于机器的成分：实数精度、整数位数。（7）可扩充性：数据类型的扩充，字符集的扩充，预定义成分的扩充（8）风格合理性（简明性、一致性）简明性，能以较少的符号写出程序；一致性：版本之间一致性，与通用语言表达习惯的一

17、致性。1.2 程序设计语言和程序设计方法 随着计算机技术发展，程序设计从技巧上升为科学； 语言和程序设计方法之间关系密切； 新型方法导至新语言的产生； 语言是方法的体现，是程序设计的工具； 程序设计的关键是算法设计，即方法是第一位的； 学习程序设计方法就是设计与规划的能力； 程序的正确性是追求的首要目标，而科学的程序设计方法是程序质量的保证。程序设计方法的作用首先，从哲学的角度来看，任何实践活动都需要理论指导。程序设计作为人类在计算机领域的实践活动同样需要科学的理论和方法作为指导。其次，通过对程序设计方法的学习，不仅可以提高对相应语言的运用能力，而且可以从全局的角度对整个软件系统进行规划。最后

18、，科学的程序设计方法是程序质量的可靠保证。程序设计方法的形成-软件危机的产生1962 年 7 月 22 日美国一个计划飞往金星的飞船水手 1 号在升空 290 秒之后坠毁。经调查发现，地面控制计算机中一段运行程序执行了类似这样的代码：If not 雷达发现火箭 then 不调整火箭的飞行路线。然而程序员一个不小心漏掉了 not，导致了这些事故的发生美国 IBM 公司在 1963 年至 1966 年开发的 IBM360 机的操作系统。这一项目花了 5000 人一年的工作量，最多时有 1000 人投入开发工作，写出了近 100 万行源程序。据统计，这个操作系统每次发行的新版本都是从前一版本中找出

19、1000 个程序错误而修正的结果。 1995 年 SEI 统计，美国共取消了 810 亿美元的商业软件项目，其中 31的项目未做完就被取消，53的软件项目进度通常要延长 50%的时间，只有 9的软件项目能够及时交付并且费用也控制在预算之内。程序设计方法的形成-软件危机的产生2000 年 Tech Republic 公司发表了有关 IT 项目的调查结果。该调查是以北美的 1375 个 IT专家为对象实施问卷调查进行的。根据此调查，IT 项目中有 40%失败，这些项目的平均成本每年花费 100 万美元。程序设计方法的形成-软件危机的产生 软件危机的内涵 软件开发成本和进度的估计常常很不准确 用户对

20、“已完成的”软件系统不满意的现象经常发生 软件常常是不可维护的 软件常常是不可管理的 软件在计算机系统总成本中所占的比例逐年上升 软件开发生产率提高的速度远远跟不上计算机应用迅速及深入普及的速度程序设计方法的形成-软件危机如何解决 管理学和工程学角度软件工程划分阶段；加强审计；质量控制；过程改进；结构化； 方法学和语言学角度程序设计方法标准的程序设计；设计模式；设计风格；设计技巧1.3 程序设计方法的形成和发展1、程序设计技巧阶段 面向机器编程 数字计算机之所以能进行程序设计，是因为它有一有穷指令集。 50 年代编程是使用机器指令代码进行的。 随后的汇编语言程序虽然用符号代替代码，但在程序设计

21、本质上没有改变。 这个时代的编程者要对机器代码和符号代码非常熟悉。 面向机器所编程，程序运行效率一般较高，但维护性、可读性、移植性、通用性都很差。 高级语言编程 高级语言的出现，大大简化程序设计。 高级语言编程基本上与机器无关，而主要集中解决算法、数据结构问题。 程序设计=算法+数据结构+程序设计语言 各种领域的计算机程序的开发促进程序设计的发展。出现多种高级程序设计语言。 但新出现的复杂的操作系统、数据库等软件对程序设计在可靠性、维护、修改、和移植性等方面提出更高要求。 此时，传统的程序设计方法出现“软件危机”。2、程序设计从技巧上升为科学 结构化程序设计方法 1969 年，Dijkstra

22、 提出结构化程序设计思想：从程序结构上改变传统的程序设计方法。 经实践，结构化程序设计方法解决“软件危机”，使程序设计走向系统化、工程化。 另外，递归程序设计、自上而下逐步求精设计进一步完善了结构化程序设计方法。 一个好的按结构化要求设计程序，一般要求：结构清晰，易读易改易验证，可靠性好，运行效率也高。 当运行效率与结构化发化矛盾时，我们宁可牺牲效率，确保好的结构。 面向过程的程序设计方法 程序由若干个过程（函数） 组成，采用自顶向下逐步求精的手段，实现模块分解和功能抽象。 程序按功能被划分成若干个模块，各模块在功能上相对独立。每个模块可以用过程（函数）来实现。 模块之间要求高内聚、低耦合。

23、过程式程序设计也称为模块化程序设计。 数据和过程是相互独立的两个实体。 主要设计语言有 FORTRAN、BASIC、C、Pascal 面向对象的程序设计方法 结构化程序设计解决了“软件危机”。但庞大、复杂的程序维护成为整个软件开发过程中非常繁杂的工作，也面临新的考验。 面向对象程序设计方法直接将“解”映射到人们对问题的认识上，努力取得对象和操作之间的协调。 面向对象方法有目的地把系统分解为模块策略，并将设计决策与客观世界的认识相匹配。 在人工智能、数据库领域的研究表明，面向对象不只是有效的程序设计技术，还应成为软件开发的基本方法，成为开发技术是今后软件发展的主流之一。 现在的“B、C、D、F”

24、等编程语言都使用了该技术。 其它程序设计方法 函数式程序设计方法程序被看作是描述输入与输出之间关系的一个数学函数主要语言有 LISP。C 也常被称为函数式程序设计语言。 逻辑程序设计语言逻辑被看作是知识推理的工具。程序被看作描述输入与输出之间各种关系的一组方程。程序设计可归结为事实列举、定义逻辑关系、逻辑公式演绎，以提问方式求解。代表语言是 Prolog。1.4 程序设计的一般途径程序设计中最为关心的是程序的效率与程序的正确性。 程序的效率常由算法的效率来决定； 程序的正确性要保证程序的易读性、可靠性、可维护性等。在程序设计中十全十美的方法是不存在的。所谓好的程序设计方法只能是针对某些特定的情况而言，所以我们平时应注重在程序设计方法本质的理解和灵活的运用。程序设计的基本步骤对一个实际问题进行程序设计时通常按照以下步骤进行： 问题分析 即弄清待解决问题的功能需求 建立数学模型 算法设计 即确定面向计算机的解决问题的方法和步骤 选用合适的算法描述工具进行算法描述 选用合适的计算机语言进行编码 在给定的计算机环境中编辑、测试、调试、运行程序，以得到预期的结果第二章 程序设计的基本理论学习重点：1、了解算法的基本概念和计算机算法的特性2、掌握常用算法描述工具3、了解数据结构的基本概念4、掌握常用数据结构类型