文档介绍：第4章算法
当我们试图用计算机解决一个问题时,大体都要经历如下几个步骤:
1. 把问题抽象为一个带有一般性的数学问题,即数学化。这一步要引入一些数学概念,给出所求问题的已知条件、所要求的结果、以及在已知条件和所要求的结果之间存在着的隐式或显式的联系。
2. 建立相应的求解方法。这一步要给出问题的求解模型,即确定问题的数据模型并在此模型上定义一组运算,然后借助于对这组运算的调用和控制,根据已知数据导出所要求的结果。
3. 用一种程序设计语言描述算法。即将非形式自然语言表达的算法转变为一种程序设计语言表达的算法。也可称做程序设计或程序编制。
4. 编辑、调试和测试程序代码,直到输出所要求的结果。
获得了计算方法和算法,并不等于问题可解,是否可解取决于算法的存在性和计算的复杂性。即是否存在求解算法,算法所需要的时间和空间在数量级上能否被接受。
1900年,数学家希尔伯特在巴黎举行的世界数学家大会上发表了至今仍著名的演说。在演说中,他提出了23个数学问题,这就是著名的“希尔伯特23个问题”,并认为它们是对下一个世纪的挑战。其中的第10个问题是“丢番图方程的可解性问题”。其具体涵义是设计一个算法来测试多项式是否有整数根。将该问题做相应简化可以设:
D={p|p是有整数根的 x的多项式},则集合D是否可判定?答案是否定的。
我们可以把多项式输入到计算机中进行处理,当x赋值为0,-1,1,-2,2,-3,3,……时,分别求出多项式的值,一旦求得0值,就接受,如果p没有整数根,则程序将永远运行下去。
本章内容
算法的概念
算法的表示
常用算法介绍
并行算法
算法的评价
算法的设计要求
算法的定义
算法是程序设计的精髓,程序设计的实质就是构造解决问题的算法,将其解释为计算机语言。
有关算法(algorithm)的定义不只一种,其中一种叙述为:算法是对特定问题求解步骤的一种描述,它是指令的有限序列,其中每一条指令表示一个或多个操作。
曾获图灵奖的著名科学家克努斯()对算法这一概念给出了进一步的描述。
一个算法,就是一个有穷规则的集合,其中之规则确定了一个解决某一特定类型问题的运算序列。此外,算法的规则序列必须满足下列五个重要条件:
(1) 有穷性。算法必须总是在执行有穷步之后结束;
(2) 确定性。算法的每一步骤必须被确切地定义;
(3) 输入。算法有零个或多个输入;
(4) 输出。算法有一个或多个输出;
(5)能行性。算法中有待执行的运算和操作必须是相当基本的,即它们原则上都是能够精确地进行的,而且用笔和纸做有穷次就可以完成。
除了算法的非形式化定义外,还有算法的形式化定义:
算法是一个四元组,即(Q, I,O, F)。
其中:
1 Q 是一个包含子集I 和的集合它表示计算的状态。
2 I 表示计算的输入集合;
3 O 表示计算的输出集合;
4 F 表示计算的规则,它是一个由Q 到它自身的函数,且具有自反性,即对于任何一个元素q∈ Q, 有F(q)=q 。