课程的主要研究问题Word文档格式.docx
《课程的主要研究问题Word文档格式.docx》由会员分享，可在线阅读，更多相关《课程的主要研究问题Word文档格式.docx（47页珍藏版）》请在冰点文库上搜索。
（）语法：
规定程序的结构或形式，记号串的组成规则；
（）语义：
程序的含义，记号的特定意义；
（）语用：
程序和使用者之间的关系，人机交互的表达方式；
（）语境：
理解、执行和实现程序的环境，预定义成分、与系统实现有关的成分，输入输出。
三、程序设计语言的发展
、第一代语言：
机器语言。
●机器语言是最早的计算机语言；
●运行效率高。
它用二进制代码表示数据和指令，这些代码不用翻译即可在计算机上直接执行；
●指令难记，程序难读。
编写机器语言程序是一件枯燥而繁杂的工作，存储空间的安排、寄存器变址的使用都由程序员自己计划，且所有的地址分配都是以绝对地址的形式处理；
●要把为一种机器编制的程序搬到另一种机器上去运行根本行不通。
因为不同的机器有不同的指令系统。
、第二代语言：
汇编语言。
●汇编语言是一种比机器语言更接近于自然语言和数学语言的低级程序设计语言。
●指令采用助记符表示容易记忆，程序也更容易阅读。
由于汇编语言一般都是为特定计算机或计算机系统设计的，因此它虽然比机器语言好学，好记，程序也好写些，但仍然没有解决机器语言存在的问题，其生产效率也很低。
●汇编语言也是面向机器的。
它能直接操作计算机的寄存器、内存单元和输入输出端口，能够设计出执行效率很高的程序，因而汇编语言在某些领域仍有应用。
●用汇编语言编写的程序需经汇编程序翻译成机器语言程序后才能在计算机上运行。
●汇编语言指令与机器指令基本上是一对一的关系，但有的汇编语言中可以有宏指令，它对应于一串机器指令。
机器语言和汇编语言
▪原始的冯.诺依曼机器（年）代码
机器语言是晦涩难懂的，因此需要设计另外一种语言来写程序，它应该是符号式的或者说助记性的。
高级语言的优越性：
可扩展性；
可读性；
可移植性
、第三代语言：
高级语言。
是指人容易理解和有利于人对解题过程进行描述的程序语言，通常所讲的程序设计语言往往指的是高级语言。
一、命令式语言
▪科学计算的语言
[]为的成功预备了两个成分：
记法和效率
是唯一使用带有专用符号的交互式键盘来编写程序的语言。
▪商用语言
第一个商用语言是（面向商业的公用语言的缩写）。
它是一种功能很强而又极为冗长的语言
设计者的最意图体现在该语言的名字上初学者通用的符号指令码
▪多用途语言
主导世纪年代程序设计语言的发展。
作为教学语言扩展了
年创建语言
二、函数式语言
▪年设计了用作符号演算，具有严格的理论基础
▪、、对语言发展的推动作用
▪年是的面向对象扩展，全名是
三、面向对象语言
▪和在年设计了这个语言，目的是想同时作为一种描述语言和程序设计语言
▪是第一个严格意义的全面向对象的程序设计语言，它的设计受到了的影响
▪设计的是为了把面向对象的优点带进的命令式程序设计中
▪是面向对象程序设计语言的成熟标志
▪你需要知道的一些面向对象程序设计语言和相关语言
Ada
、第四代语言：
●第四代语言是抽象层次更高的程序设计语言，它把程序员从繁杂的过程性设计中解放出来，用自己的语法形式表示控制和数据结构，不再涉及太多的算法细节。
●使用最广的第四代语言是数据库语言，它支持用户以复杂的方式操作数据库，用户只需关心做什么，而不用关心怎么做，可以用类自然语言的形式提问。
●程序生成器是更为复杂的一类，它输入由甚高级语言书写的语句，自动产生完整的第三代语言程序。
四、程序设计语言的实现
实现系统:
任何一个程序设计语言都有一个实现系统（如编译系统或解释系统）与之匹配。
用户使用程序语言编制出的源程序必须通过实现系统的加工处理。
转换机制:
源语言→目标语言
、纵向转换：
源语言→机器语言（汇编语言）
翻译程序:
它是这样一个计算机程序,能把用高级语言书写的程序翻译为等价的机器语言或汇编语言.
翻译程序主要有编译程序和解释程序。
编译程序：
是一种把用高级语言编写的源程序作为输入，经过翻译变换产生出面向目标计算机的目标代码程序作为输出的翻译程序。
编译程序比较重视目标代码的效率。
语言采用这种方式。
解释程序：
是一种一边解释用高级语言编写的源程序的语句，一边根据解释的结果直接执行。
解释程序花费的机器时间要多些，但所占的内存要少些。
编译程序设计概述
、词法分析：
区别、分离出源程序行文中一个一个的单词，如标识符、保留字、常量、运算符、定界符等。
、语法分析：
识别出源程序的基本结构，如模块、子程序、分程序、程序包、数据说明、语句等，并生成有关表格（含语义分析的有关工作）。
、中间代码生成：
根据语法分析阶段识别出的语法范畴产生相应的中间代码。
中间代码有多种形式，如逆波兰表示法，三元式、四元式等。
、优化处理：
主要任务是对前一阶段所产生的代码进行时间与空间的优化。
、目标代码生成：
根据中间代码及有关表格生成可在裸机上执行的目标代码，其中包括内存与寄存器的分配等工作。
、横向转换：
以描述语言表示的源程序→以描述语言表示的源程序
中间语言
在语言的实现过程中产生的非目标语言。
中间语言的作用：
（）如中间语言是汇编语言，可实现混合编程。
可方便地调用库过程、库函数、外部过程和函数，实现链接功能的扩充和统一。
（）作为两种语言的翻译语言，实现翻译功能。
（）
（）形成中间语言是编译过程中必不可少的过程。
在编译过程中的每一趟均存在着不同形式的中间语言。
（）中间语言提供了不依赖于机器的语言实现机制；
的编译器把的源程序转换成字节码，它不依赖机器，可以看作中间语言，字节码由的运行系统解释执行。
（）在函数式语言中，中间语言（计算模型）是描述对象和控制策略的工具。
语言的等价性理解:
重在功能等价。
、源程序级的功能等价：
编译过程中产生的中间语言程序和目标程序，它们的功能是相同的。
相同的输入产生相同的输出。
、不同语言之间的功能等价：
定义：
对于算法，采用两个程序设计语言和，所编出源程序（）和（），如果则对于算法，和是等价的。
如果对于任何算法，定义都满足，则称和是语言功能等价的。
、不同语言的语法单位的功能等价（横向软件工程中经常用到）：
例：
数据类型定义：
语言：
;
:
循环语句：
；
{
}
（）；
注意：
语言是条件为假时退出循环。
、同一种语言中，相同功能的不同实现。
与语句的等价：
：
:
循环语句之间的等价：
等价为：
（）
语句与语句之间的等价：
语句与语句之间的等价：
四、程序设计语言的设计原则
、什么样的语言可以成功？
满足市场需要（解决实际问题，较高的性价比）；
满足用户需要（适用、高效、可靠）
满足理论价值需要（语言设施完备、严密、科学）
、程序设计语言的设计原则
（）定义严密性：
对语言的语法、语义、语用和语境有严密的定义，语法正确、语义合理、语用清楚、语境明确。
（）可靠性：
信息隐藏、数据抽象、类属机制、模块独立。
（）可读性：
表示，结构化语法
（）可维护性：
模块独立、数据抽象、分别编译
（）效率：
以该语言编写的程序能以最小的资源（时间和空间）消耗实现其预定的功能的程度。
从执行过程考察，递归和回溯，解释执行和编译执行
（）可移植性：
语言成分与实现环境之间的最小依赖程度。
依赖于机器的成分：
实数精度、整数位数。
（）可扩充性：
数据类型的扩充，字符集的扩充，预定义成分的扩充
（）风格合理性（简明性、一致性）
简明性，能以较少的符号写出程序；
一致性：
版本之间一致性，与通用语言表达习惯的一致性。
v随着计算机技术发展，程序设计从技巧上升为科学；
v语言和程序设计方法之间关系密切；
Ø
新型方法导至新语言的产生；
语言是方法的体现，是程序设计的工具；
v程序设计的关键是算法设计，即方法是第一位的；
v学习程序设计方法就是设计与规划的能力；
v程序的正确性是追求的首要目标，而科学的程序设计方法是程序质量的保证。
程序设计方法的作用
首先，从哲学的角度来看，任何实践活动都需要理论指导。
程序设计作为人类在计算机领域的实践活动同样需要科学的理论和方法作为指导。
其次，通过对程序设计方法的学习，不仅可以提高对相应语言的运用能力，而且可以从全局的角度对整个软件系统进行规划。
最后，科学的程序设计方法是程序质量的可靠保证。
程序设计方法的形成软件危机的产生
年月日美国一个计划飞往金星的飞船水手号在升空秒之后坠毁。
经调查发现，地面控制计算机中一段运行程序执行了类似这样的代码：
雷达发现火箭不调整火箭的飞行路线。
然而程序员一个不小心漏掉了，导致了这些事故的发生
美国公司在年至年开发的机的操作系统。
这一项目花了人一年的工作量，最多时有人投入开发工作，写出了近万行源程序。
据统计，这个操作系统每次发行的新版本都是从前一版本中找出个程序错误而修正的结果。
年统计，美国共取消了亿美元的商业软件项目，其中％的项目未做完就被取消，％的软件项目进度通常要延长的时间，只有％的软件项目能够及时交付并且费用也控制在预算之内。
年
公司发表了有关项目的调查结果。
该调查是以北美的个专家为对象实施问卷调查进行的。
根据此调查，项目中有失败，这些项目的平均成本每年花费万美元。
▪软件危机的内涵
▪软件开发成本和进度的估计常常很不准确
▪用户对“已完成的”软件系统不满意的现象经常发生
▪软件常常是不可维护的
▪软件常常是不可管理的
▪软件在计算机系统总成本中所占的比例逐年上升
▪软件开发生产率提高的速度远远跟不上计算机应用迅速及深入普及的速度
程序设计方法的形成
软件危机如何解决
▪管理学和工程学角度——软件工程划分阶段；
加强审计；
质量控制；
过程改进；
▪方法学和语言学角度——程序设计方法标准的程序设计；
设计模式；
设计风格；
设计技巧
程序设计方法的形成和发展
、程序设计技巧阶段
v面向机器编程
数字计算机之所以能进行程序设计，是因为它有一有穷指令集。
年代编程是使用机器指令代码进行的。
随后的汇编语言程序虽然用符号代替代码，但在程序设计本质上没有改变。
这个时代的编程者要对机器代码和符号代码非常熟悉。
面向机器所编程，程序运行效率一般较高，但维护性、可读性、移植性、通用性都很差。
v高级语言编程
高级语言的出现，大大简化程序设计。
高级语言编程基本上与机器无关，而主要集中解决算法、数据结构问题。
程序设计算法数据结构程序设计语言
各种领域的计算机程序的开发促进程序设计的发展。
出现多种高级程序设计语言。
但新出现的复杂的操作系统、数据库等软件对程序设计在可靠性、维护、修改、和移植性等方面提出更高要求。
此时，传统的程序设计方法出现“软件危机”。
、程序设计从技巧上升为科学
v结构化程序设计方法
年，提出结构化程序设计思想：
从程序结构上改变传统的程序设计方法。
经实践，结构化程序设计方法解决“软件危机”，使程序设计走向系统化、工程化。
另外，递归程序设计、自上而下逐步求精设计进一步完善了结构化程序设计方法。
一个好的按结构化要求设计程序，一般要求：
结构清晰，易读易改易验证，可靠性好，运行效率也高。
当运行效率与结构化发化矛盾时，我们宁可牺牲效率，确保好的结构。
v面向过程的程序设计方法
程序由若干个过程（函数）组成，采用自顶向下逐步求精的手段，实现模块分解和功能抽象。
程序按功能被划分成若干个模块，各模块在功能上相对独立。
每个模块可以用过程（函数）来实现。
模块之间要求高内聚、低耦合。
过程式程序设计也称为模块化程序设计。
数据和过程是相互独立的两个实体。
主要设计语言有、、、
v面向对象的程序设计方法
结构化程序设计解决了“软件危机”。
但庞大、复杂的程序维护成为整个软件开发过程中非常繁杂的工作，也面临新的考验。
面向对象程序设计方法直接将“解”映射到人们对问题的认识上，努力取得对象和操作之间的协调。
面向对象方法有目的地把系统分解为模块策略，并将设计决策与客观世界的认识相匹配。
在人工智能、数据库领域的研究表明，面向对象不只是有效的程序设计技术，还应成为软件开发的基本方法，成为开发技术是今后软件发展的主流之一。
现在的“、、、”等编程语言都使用了该技术。
v其它程序设计方法
函数式程序设计方法
程序被看作是描述输入与输出之间关系的一个数学函数主要语言有。
也常被称为函数式程序设计语言。
逻辑程序设计语言
逻辑被看作是知识推理的工具。
程序被看作描述输入与输出之间各种关系的一组方程。
程序设计可归结为事实列举、定义逻辑关系、逻辑公式演绎，以提问方式求解。
代表语言是。
程序设计的一般途径
程序设计中最为关心的是程序的效率与程序的正确性。
程序的效率常由算法的效率来决定；
程序的正确性要保证程序的易读性、可靠
性、可维护性等。
在程序设计中十全十美的方法是不存在的。
所谓好的程序设计方法只能是针对某些特定的情况而言，所以我们平时应注重在程序设计方法本质的理解和灵活的运用。
程序设计的基本步骤
对一个实际问题进行程序设计时通常按照以下步骤进行：
✓问题分析即弄清待解决问题的功能需求
✓建立数学模型
✓算法设计即确定面向计算机的解决问题的方法和步骤
✓选用合适的算法描述工具进行算法描述
✓选用合适的计算机语言进行编码
✓在给定的计算机环境中编辑、测试、调试、运行程序，以得到预期的结果
第二章程序设计的基本理论
、了解算法的基本概念和计算机算法的特性
、掌握常用算法描述工具
、了解数据结构的基本概念
、掌握常用数据结构类型
一般地说，程序设计通常要涉及下面几方面算法
算法的概念
【例】交换两个变量，中的值。
交换的步骤如下：
：
输入变量和的值；
将的值赋给（用⇐表示）；
输出变量和的值;
结束。
的内容：
◆为待解决的问题确定正确的解题方法和步骤
◆为问题所涉及的数据特性进行分析并选择合适的数据结构
◆选用适当的程序设计方法，提高程序设计质量
◆选用优质的软件工具，实现程序编码和测试
2.1.1算法的概念
广义地说，所谓“算法”就是解决问题时所采用的方法和步骤，也就是说算法是对问题处理过程的一种描述。
解决同一个问题算法不止一个，但总存在着一个最佳算法，人们在解决问题时实际上就是在为问题寻找一个最佳算法。
算法的特性
算法是由若干指令组成的有限序列，一个算法应具有下列个重要特性。
．有穷性
一个算法必须是（对任何合法的输入值）在执行有穷步骤之后结束，且每一步都可在有穷时间内完成。
．确定性
算法中每一条指令必须有确切的含义，无二义性，即对于相同的输入只能得出相同的输出
．可行性
算法中描述的操作都可以通过已经实现的基本运算执行有限次来实现。
．输入
一个算法有个或多个的输入，这些输入取自于某个特定的对象的集合。
．输出
一个算法有一个或多个的输出。
算法的分析
．算法评价
一个好的算法应达到以下目标：
（）正确性。
（）可读性。
（）健壮性。
（）效率。
其中算法的效率包括时间效率和空间效率。
．算法分析
一个程序在计算机上运行时所耗费的时间取决于下列因素。
（）问题的规模。
（）依据算法选用的策略。
（）书写程序的语言。
（）机器执行指令的速度。
（）对源程序编译的时间。
一般用算法中所有语句的频度之和来表示一个算法所需要的时间。
语句的频度（）是指该语句重复执行的次数。
【例】下面是两个×
矩阵相乘的算法。
（[][][][][][]）
（）（<
）
（）[][];
（）[][][][][][]*[][];
表矩阵相乘算法的语句频度
语句
语句频度
（）
该算法中耗费的时间为：
（）（）（）
算法中的执行时间是问题规模的某个函数（），算法的时间度量记作：
（）（（））
它表示随问题规模的增大，算法执行时间的增长率和（）的增长率相同，称作算
法的渐近时间复杂度，简称时间复杂度。
两个矩阵相乘算法的时间量级是（）（）
算法描述工具
常用算法的描述工具：
自然语言、、程序流程图和图
自然语言
所谓“自然语言”就是日常生活中使用的语言，如汉语、英语或数学表达式等。
用自然语言描述下列算法。
【例】某商店为了促销，采用购物打折的优惠办法：
每位顾客一次购物元以下，没有折扣；
元到元之间，按九五折优惠；
元以上，按九折优惠。
假设每位顾客的购物花费用表示，计算折扣后用表示实收的费用，算法的自然语言描述如下所示：
▪（）输入顾客的消费金额
▪（）如果<
，则
▪（）如果≤<
，则*
▪（）如果≤，则*
2.2.2过程设计语言（伪代码）
也称为伪码，是用正文形式表示数据和处理过程的工具。
具有严格的关键字外部语法，用于定义控制结构和数据结构；
另一方面，表示实际操作和条件的内部语法通常又是灵活自由的，以便可以适应各种工程项目的需要。
【例】用语言描述“数组中求最大数”的问题
<
2.2.3程序流程图
程序流程图也称程序框图，是用一种标准的图形助记符表示编程思路的辅助手段，是一个描述程序的控制流程和指令执行情况的有向图.一个流程图通常由种图形符号组成。
流程图的符号组成
1.处理单元（），也称函数结点，只有一个入口和一个出口线，是函数结点的名称，函数结点一般和赋值语句对应。
判断单元（），也称谓词结点，有一个入口和两个出口线，且谓词结点不改变变量的值（只作判断，不做计算），一般对应条件语句。
连接单元（），也称汇点。
有两个入口和一个出口线，或者有一个入口和多个出口，控制路径在此聚会或者在此发散，汇点不执行任何运算，只是一个简单的的结点。
流线（），也称连接线，从一个处理单元到另外一个处理单元，表示程序的运行方向。
.开始单元（）
表示为长圆形的符号及其引出线，表示一个算法流程图的逻辑起始点。
一般而言，一个程序的流程图主要由函数结点、谓词结点、汇点组成，如下图：
用程序流程图描述下例算法
流程图
图，也称盒图。
它的主要特点是：
完全去掉流程图中的流程线，所有算法的描述只通过种基本控制结构来描述。
（）顺序结构
（）分支结构
（）当型循环结构
（）直到型循环结构
（）多分支选择
（）调用子程序（函数）
【例】判断自然数（>
）是否为素数
数据结构的基本概念
什么是数据结构
数据结构指的是数据之间的相互关系，即数据的组织形式，它一般包括以下个方面的内容：
（）数据元素之间的逻辑关系，也称为数据的逻辑结构。
（）数据元素及其关系在计算机存储器内的表示，称为数据的存储结构。
（）数据的运算，即对数据施加的操作。
数据结构的常用术语
数据：
是描述客观事件的数据、字符以及所有能输入到计算机中并被计算机程序处理的符号的集合。
数据元素：
是数据的基本单位。
有时一个数据元素可以由若干个数据项组成，在这种情况下，常把数据元素称为记录。
数据项是具有独立含义的最小单位。
数据的逻辑结构用来描述数据元素之间存在的某种特定关系，通常分为线性结构和非线性结构。
（）线性结构
线性结构的逻辑特征是：
在数据元素的非空有限集合中，有且仅有一个开始结点，它没有前驱结点，只有一个后继结点；
有且仅有一个终端结点，它没有后继结点，只有一个前驱结点；
除开始结点和终端结点外，集合中的每个结点有且只有一个前驱结点，有且只有一个后继结点。
线性表、栈、队列和字符串均属于线性结构。
线性结构的基本关系图如下图所示
（）非线性结构
非线性结构的逻辑特征是一个结点可能
有多个直接前驱和直接后继。
树和图属于非
线性结构。
非线性结构的基本关系图如下所示：
树形结构的基本关系图
图状结构的基本关系图
▪数据的存储结构又称数据的物理结构，它是数据逻辑结构在计算机存储器中的实现，即数据及其关系在计算机中的物理表示，是依赖于计算机的。
▪数据的存储结构一般由下面种基本的存储方式体现。
（）顺序存储方法
顺序存储方法是把逻辑上相邻的结点存储在物理位置上相邻的存储单元里。
顺序存储结构通常借用程序语言的数组来描述。
（）链式存储结构
链式存储方法不要求逻辑上相邻的结点在物理位置上亦相邻。
链式存储结构通常借助于程序语言的指针类型来实现。
（）索引存储方法
索引存储方法通常是在存储结点信息的同时，还建立附加的索引
升级会员 