2.计算机软件概述

2.1什么是计算机软件

① 计算机硬件：组成计算机各种物理设备的总称。

② 计算机软件（Computer Software）：能指示计算机完成特定任务的、以电子格式存储的程序、数据和相关的文档。

(资料图)

2.2计算机软件的分类

① 软件分类

▶ 系统软件：

▪  操作系统（DOS，Windows98/2000/NT,Windows XP/vista,UNIX\Linux) 

▪  语言处理系统（编译程序。解释程序，汇编程序） 

▪  系统服务程序（监控、检测程序，连接编辑程序，调试程序，其他服务程序  

▪  数据库管理系统（DBASE、FoxBase、VFP,Oracle、Sybass、IBM、DB2、SQL Server）

▶ 应用软件：

▪  文字处理软件  

▪  表格处理软件  

▪  辅助设计软件 

▪  实施控制软件

② 其他分类方法：

▶ 客户端软件/服务器软件

▶ 移动/非移动软件

▶ 前/后台软件

▶ 智能//非智能软件

2.3计算与算法

① 科学规律：问题的数学模型（问题：需要回答的一般性提问。通常包括若干参数，由求解问题描述、输入条件和输出要求等要素组成）

② 途径方法：问题求解的算法+软件的设计与实现+计算机计算

③ 所谓计算：就是在一定的公理体系基础上，按照规则把字符串s转换成字符串t的过程

④ 计算机数：位数有限，个数有限，大小有限

⑤数据与信息

▶ 数据的概念：客观物体内在性质的表示，具有数字、文字、图片、声音和活动图象等形式

▶ 信息的概念：是对事物运动状态和特征的描述。信息是对数据的解释，是数据含义的体现

信息既是对各种事物的变化和特征的反映，又是事物之间相互作用和联系的表征。而数据是信息的载体。信息有意义而数据没意义。

比如做问卷调查的时候，问卷收回以后，得到的只有数据，只有将数据进行整理、分析之后，得到的才能叫信息。也就是说，信息是有意义的数据。

▶ 人是如何解决问题的：

观察、分析问题→收集必要的信息→（根据已有的知识、经验）判断、推理→（（按照一定的方法和步骤）解决问题

▶ 计算机问题求解：

▪  第一步分析问题  

▪  第二步用自然语言描述计算方法  

▪  第三步将算法编写成计算机程序  

▪  第四步运行、调试程序，检验结果  

▪  第五步问题得到解决

▶ 计算机解决问题流程：

▪  分析问题  

▪  设计算法  

▪  编写程序  

▪  运行程序，验证结果 

2.4可计算性与计算复杂性

② 什么是可计算：通俗地说，停机问题就是判断任意一个程序是否在有限的时间内结束运行的问题

停机问题的关键：能否找到一个测试程序，这个测试程序能判定任何一个程序在给定的输出下能否终止

Church—Turing理论：任何能直观计算的问题都能被图灵机计算。如果证实了某个问题是用图灵机是不可解决的，那么这个问题就是不可解决的。

一般性的停机问题：对于任意的图灵机和输入，是否存在一个算法，用于判定图灵机在接收初始输入后可达停机状态。若能找到这种算法，停机问题可解；否则不可解。

1936年。Turing发表“论可计算数及其在判定问题中的应用”论文中提出一般性停机问题的不可判定性，并用形式化方法证明其为一个不可计算问题。

数学反证法证明：先假设这样的测试程序，然后再构造一个程序，该测试程序不能测试。

③ 什么是计算复杂性

计算复杂性的理论研究的资源：最常见的是时间（要通过多少步演算才能解决问题）和空间（在解决问题时需要多少内存）。其他资源亦可考虑，例如在并行计算中，需要多少并行处理器才能解决问题。

时间复杂度是指在计算机科学与工程领域完成一个算法所需要的时间，是衡量一个算法优劣的重要参数。时间复杂度越小，说明该算法效率越高，则该算法越有价值。

空间复杂度是指计算机科学领域完成一个算法所需要占用的存储空间，一般是输入参数的函数。它是算法优劣的重要度量指标，一般来说，空间复杂度越小，算法越好。

可计算性理论和计算复杂度理论不同，可计算性理论的重心在于问题能否解决，不考虑需要多少资源（假设时间无限多，存储空间无限大）。而计算复杂性理论作为计算理论的分支，某种程度上被认为和算法理论是一种“矛”与“盾”的关系，即算法理论专注于设计有效的算法，而复杂性理论专注于理解为什么对于某类问题，不存在有效的算法。

④ 计算复杂性的度量

算法复杂性→针对特定算法

计算复杂性→针对特定问题，反映问题的固有难度

计算复杂性=最佳的算法复杂性

计算复杂性：用计算机求解问题的难易程度

▶ 度量标准：

▪  时间复杂性→计算所需的步数或指令条数 

▪  空间复杂度→计算所需的存储空间大小

如果一个问题没有多项式时间复杂性的算法，则被称为难解型问题。

2.5问题求解算法设计简述

① 递归算法设计与汉诺塔问题

▶ 问题描述：将第一根柱子上的64个盘子借助第二根柱子全部移到第三根柱子上

▶ 移动规则：

▪  每次只能移动一个盘子；

▪  盘子只能在三根柱子上移动，不能放在他处；

▪  在移动过程中，三根柱子上的盘子必须始终保持大盘在下，小盘在上

▶ 递归思想：将一个较大的问题的求解归约为一个或多个子问题的求解。而这些子问题比原问题简单，且在结构上与原问题相同。

② 迭代递推算法设计

算法比较：计算速度快，计算精度高

迭代法的应用是有条件的

2.6指令、程序与软件

① 计算基础与算法

▶ 计算基础：计算理论+计算机+程序设计语言+程序+算法

▶ 程序与算法：

▪  算法是指为解决某一问题而采取的方法和步骤  

▪  算法的特点：有穷性/确定性/有效性/输入及输出  

▪  算法的表示：自然语言/流程图/伪码  

▪  算法的评价标准：正确性/时间复杂度/空间复杂度/可理解性

②

▶ 机器语言

▶ 汇编语言

▶ 高级语言：Fortran…

▶ 结构化程序设计语言

▶ 面向对象程序设计语言

▶ 可视化程序设计语言

▶ 人工智能程序设计语言

③ 算法表示技术：

▶ 自然语言描述（易理解，但书写烦、易引起歧义） ；

▶ 用流程图描述（直观、形象） ；

▶ 用伪代码或直接用计算机程序描述（能被计算机识别和执行）

④ 用流程图描述算法：流程图是一种比较直观易懂的、用图形来描述算法的方法，流程图中所使用的符号必须遵循国家颁布的标准

⑤ 算法的实现与程序

程序是程序设计人员编写的、计算机能够理解并执行的命令集合，是算法在计算机中的实现。

“程序=数据结构+算法”的著名论断是由N.Wirth（沃斯）提出来的，数据结构指的是数据与数据之间的逻辑关系，算法指的是解决特定问题的步骤和方法。

⑥ 软件的工作方式及其分类

▶ 计算机软件子系统：系统软件   应用软件

▶ 系统软件：操作系统   语言翻译系统   软件开发环境   数据库管理系统

▶ 应用软件：办公软件  辅助设计软件  图像处理软件  网页制作软件  网络通信软件  工具软件  实际应用软件

▶ 工作方式分类：

▪  单机工作模式  

▪  网络工作模式（客户机/服务器（c/s），浏览器/服务器（B/S）

▪  任务模式（单任务，批处理多任务）  

▪  其它（实时软件/可靠软件，安全/可信软件/智能软件，可移动软件/嵌入式软件）

软件：是指计算机系统中的程序和有关的文件

程序：是计算任务的处理对象和处理规则的描述

文件：是为了便于了解程序所需的资料说明

程序必须装入机器内部才能工作，文件一般是给人看的，不一定装入机器。程序作为一种具有逻辑结构的精确而完整地描述计算任务中的处理对象和处理规则。这一描述还必须通过相应的实体才能实现，记载上述信息的实体就是硬件

关键词： 计算复杂性 解决问题 停机问题