计算机算法
- 格式：doc
- 大小：315.50 KB
- 文档页数：36
1 第一章 绪论
算法（Algorithm）理论处于计算机科学的核心地位，它与计算机应用的许多实际问题有着直接的联系。
§1 算法的基本概念
1 算法的地位
① 算法（Algorithm）理论处于计算机科学的核心地位。想要使用计算机解决问题，就要设计该问题的算法，要给出解决该问题所需的一系列解题步骤。
② 算法与程序
计算机软件的重要内容之一是程序，程序是计算机指令的序列，计算机一步一步地执行这个指令序列，就完成了希望它所做的事情。程序设计就是按照一定的要求编排一个合理的指令序列。程序设计主要包含两个方面，行为特性设计和结构特性设计。结构特性设计是指确定合适的数据结构，将程序处理的数据在计算机内部表示和存放。行为特性设计是确定要解决的实际问题的具体步骤，把全部解题过程完整地描述出来，这一过程就是算法设计。
算法设计是程序设计的基础。美国《计算机科学基础》一书指出，“算法代表了对问题的解”，“程序是算法在计算机上的特定实现”。N．Wirth指出“程序就是在数据的某些特定的表示方法和结构的基础上对抽象算法的具体表述。”通俗地讲，程序是用计算机语言表述的算法。
数据结构是程序设计的另一基础。程序的目的是加工数据，具体的数据加工步骤为算法，程序是算法和数据结构的统一。著名计算机科学家N．Wirth于1976年提出了“程序=算法+数据结构”的概念。这个公式表明，算法与数据结构是密切相关的，算法的设计要与数据结构相适应。
算法不等于程序，它不需考虑具体的机器，算法也不等于计算方法，它比计算方法更具体。
算法知识位于程序设计的高层（算法，方法学，语言和工具），具有相对稳定性。很多经典算法产生于20世纪50、60年代，如hash算法，快速排序算法，至今仍在使用。
2 算法的定义
下面我们先看两个例子：
例1 求一个数a的平方根。
利用迭代公式：xn+1=(xn+a/xn)/2 ， 算法如下：
① 对x赋初值x0
② 如果 | x2-a| < ε 则转④
③ x=(x+a/x)/2, 转② 2 ④ 输出x
例2 求m,n的最大公约数
利用辗转除法可得求自然数m，n的最大公约数的算法如下：
① r=m mod n
② 循环直到r=0
m=n
n=r
r= m mod n
③ 输出 n
可以看出 ，算法是解题方案的准确而完整的描述，它是由一些步骤组成的一个过程，这些步骤连在一起给出一类问题的解。
著名的Webster词典在 Algorithm 词条下指出：算法是在有限步骤内解决一个数学问题的过程，步骤中常常包括某一个操作的重复。更广义的说，一个算法就是为了解决一个问题或实现某一目标的逐步过程。
著名计算机科学家D.E.Knuth对算法给出了另一种说明：一个算法是一个有穷规则的集合，其中之规则规定了一个解决某一类特定问题的运算序列。
3 算法的特征
著名计算机科学家Knuth把算法的特征归纳以下5点：
1) 有穷性（finiteness）
一个算法必须在有限个步骤之后结束。换句话说，一个算法必须在有限时间内完成，否则，该算法就失去了实际价值。因此，在算法中不能出现无限循环。数学中的无穷级数在计算时只能取有限项。
2) 确定性（definiteness）
算法中的每一个步骤都必须有明确的定义，不允许存在多义性和摸棱两可的解释。如“将X，Y两个数进行加减运算”，是做加法运算还是做减法运算,没有说清；再如“给变量X增加一个值”，增加一个值，具体是多少，没有说清。在算法中，这样含糊不清的步骤不允许出现。
3) 能行性（effectiveness）
算法中的每一个步骤都是可以实现的，或可以分解为可执行的基本操作。例如在算法中不能出现零做除数、在实数范围内对一个负数求平方根等情况。
4) 输入（input）
算法允许有零个或多个输入量。
5) 输出（output）
算法必须有一个或多个输出。 3
根据以上讨论，我们对算法有了进一步的认识：算法是精确定义的一系列规则，这些规则指定了一系列的操作，经过有限步骤产生所求问题的解。
4 算法解决问题的类型
计算机科学领域的问题大致可分为以下三种类型：
1) 判定性问题：这类问题给出的是与否的判别。例如连通性问题，回路问题，查找与排序问题，字符匹配问题等。
2) 最优化问题：这类问题是在所有可能的解中求出最优解。例如求函数的极值，最短路径问题，最小生成树问题等。
3) 函数计算问题：这类问题是在一定约束条件下求数值解，例如方程求根，矩阵运算，函数求值等。
5 算法学科研究内容
算法学科研究内容研究内容大致分为以下三个方面：
1）算法设计：算法设计是要设计出能够正确解决问题的算法。由于计算机资源有限，算法设计还要使算法能够占用较少的存储空间，运行速度较快。另外，从软件开发的角度，还要设计出容易理解、容易编程和容易调试的算法。
2）算法分析：算法分析的任务是估计算法的运行时间和占用的空间，分析和比较各种算法的优劣。
3）可计算理论：在早期的算法研究中，人们的研究重点集中在可计算理论上。我们说一个问题在算法上是可解的是说可以编写一个计算机程序，在运行时间足够长和存储空间足够大的条件下它对任何允许的输入都可得出正确的答案。
§2算法设计
1算法设计方法
算法设计是针对某一问题，设计出解决该问题的一系列解题步骤。由于问题的多样性，设计方法也是各种各样。研究算法的中心任务就是获得有效的算法。有许多问题，只要对数据对象进行仔细分析，建立了数学模型，处理的方法就有了。有些问题则不然，还必须花费力量进行算法设计。进行算法设计时，要针对计算工具的特点，要考虑所用计算工具的操作功能、精度范围和计算工具具有的优势。对同样一个问题，所用工具不同，其算法一般也不相同，计算机算法和人工处理算法往往就不相同。
解决一个问题的算法也不是唯一的，同一个问题可能有许多算法，这些算法各有特点。人们在算法设计的实践中，研究和总结了多种算法设计方法。算法设计一般常用方法有：蛮力法(brute force method)、分治法（divide and conquer）、贪心法(greedy method)、动态规划法(dynamic programming)、回溯法(back 4 tracking)、分枝限界法(branch and bound method)、概率算法(probabilistic
algorithm)、近似算法(approximate algorithm)、线性规划法等.
2算法设计的一般过程
1）理解问题
准确而完整的描述问题是解决问题的第一步。人们需要对问题做深入的了解，如，提供了哪些信息，要得到什么结果，输入输出各是什么。此外还要仔细检查对问题的描述是否有遗漏，是否有二义性。
例如，货郎担问题，设货郎在一天内要到n个村庄去推销货物，已知从一个村庄到其他各村庄的费用，求总费用最小的路线。
为了求最小费用路线，有一些问题尚须进一步了解。如，一天之内是否可以多次经过某个村庄；其他村庄中是否有必须优先访问的村庄等。
2） 建立模型
用计算机解决问题必须有合适的数学模型。首先有两个基本问题：⑴最适合于问题的数学结构是什么？⑵是否有已解决了的类似问题可借鉴？建立模型后，还要考察模型是否表达了问题的重要信息，能否正确反映输入、输出关系，用计算机处理模型是否有困难。并在多个模型选择最有效的一个。例如货郎担问题，可用图论的知识建立模型如图1示，可建立图的邻接矩阵和费用矩阵。
图1货郎担问题村庄连接图
3） 设计算法
算法设计是针对某一问题，设计出解决该问题的一系列解题步骤。例如货郎担问题，可以设计一种列举法，即将所有可能的方案都罗列出来，计算出每一种方案的费用，从中选择出费用最小的方案。算法设计应考虑以下问题：
① 预测所有可能的输入
② 在精确解和近似解中做出选择
③ 确定适当的数据结构
④ 选择适当的设计技术 5 4） 分析算法
对于一个问题，可有多种解法，因此也就有多种不同的算法。对算法的效率进行分析。对算法所需的内存空间和运行时间做出估计，以衡量算法的优劣。
5） 实现算法
根据算法编制计算机程序。涉及到变量、数组、数据结构、选用语言等一系列问题。
6） 验证算法正确性
必须要设计出能够得到正确结果的算法。算法的正确性依赖于所用理论的正确性，但是，理论正确的算法未必能得到正确结果。我们看两个例子。
例1 已知：A=1012，B=-1012，C=1，计算A+B+C的值。
假设所用计算工具具有7位有效数字，下面两种算法会得出不同的结果。
1) A+B+C=1012+（-1012）+1=1
2) A+C+B=1012+1+（-1012）=0
显然，第二个方法没有得到正确的结果。
例2 求方程X2-（1015+1）X+1015=0的两个实根。
1) 直接使用求根公式
A=1
B=-（1015+1）
C=1015
D=SQRT（B*B-4*A*C）
X1=（-B+D）/（2*A）
X2=（-B-D）/（2*A）
结果为：X1=1015 ，X2=0
2) 使用韦达定理
A=1
B=-（1015+1）
C=1015
D=SQRT（B*B-4*A*C）
X1=（-B+D）/（2*A）
X2=C/（A*X1）
结果为：X1=1015 ，X2=1
显然，第一个方法没有得到正确的结果。
这是因为计算机计算精度是有限的，设计算法时必须要考虑计算机精度的影响，避免误差的影响过大。 6 关于算法的正确性，目前是通过验证表达该算法的程序的正确性来实现。虽然这两者不完全一致，但因目前要证明算法的正确性仍然有困难，所以上述方法仍然是主要方法。验证程序的正确性采用程序测试的方法。经测试验证是正确的程序，在很大程度上可以相信它的正确性。
1979年，美国的Boyer（博耶）和Moore（默尔）提出用新的数学归纳法证明程序的正确性。这种方法将数学归纳法与递归函数论和定理机器证明结合起来，研制了程序证明系统。但用该系统证明程序的正确性并非一个简单的问题。
§3算法复杂性分析
设计算法还要考虑复杂性（时间复杂性和空间复杂性），执行算法所需的时间要短，占用计算机的内存要少。如果一个算法的执行时间很长，比如几百年甚至上千万年，该算法也就失去了实用价值。例如，克莱姆（Cramer）规则是求解线性代数方程组的一个数学方法，但是，根据此规则设计的求解线性代数方程组的算法，在执行过程中所需的时间实际上是不能接受的。因此，在考虑算法的有穷性时，还应考虑其合理的执行时间。
算法分析对算法的效率进行分析。对算法所需的内存空间和运行时间做出估计，以衡量算法的优劣。
1算法的复杂度
算法的复杂度主要是指时间复杂度（Time complexity）和空间复杂度（Space
complexity）。算法的时间复杂度是指算法的计算工作量，即算法的时间代价。算法的时间复杂度是指算法需要占用的存储空间的大小。下面主要讨论算法的时间复杂度。
为了能比较客观地反映一个算法的效率，在度量一个算法工作量时，不仅应该与使用的计算机程序设计语言无关，而且还应与算法实现过程中的许多细节无关。为此，可以用算法在执行过程中所需基本运算的执行次数来度量算法的计算工作量。
通常一个算法包括多种运算，选择基本运算应遵循两个原则：算法执行运算的总次数与基本运算的次数大体上应成比例；基本运算以外的其他运算量可以忽略。例如，在一维数组中查找值为x的元素，可以选择“x与数组的比较”作为基本运算，总的比较次数作为查找算法的计算工作量。再如，在两个实矩阵相乘的算法中，可以选择“两个实数的乘法”作为基本运算。
