算法:修订间差异
小 →求最大公約數演算法: 调整格式、排版 |
内容扩充 增加“基本要素”一节 |
||
第46行: | 第46行: | ||
# 有限性:依據圖靈的定義,一個演算法是能夠被任何[[圖靈完全|圖靈完備]]系統模擬的一串運算,而[[圖靈機]]-{只}-有有限個狀態、有限個輸入符號和有限個轉移函數(指令)。而一些定義更規定演算法必须在有限個步骤内完成任務。 |
# 有限性:依據圖靈的定義,一個演算法是能夠被任何[[圖靈完全|圖靈完備]]系統模擬的一串運算,而[[圖靈機]]-{只}-有有限個狀態、有限個輸入符號和有限個轉移函數(指令)。而一些定義更規定演算法必须在有限個步骤内完成任務。 |
||
# 有效性:又称可行性。能够实现,算法中描述的操作都是可以通过已经实现的基本运算执行有限次来实现。 |
# 有效性:又称可行性。能够实现,算法中描述的操作都是可以通过已经实现的基本运算执行有限次来实现。 |
||
== 基本要素 == |
|||
算法的核心是建立问题抽象的模型和明确求解目标,之后可以根据具体的问题选择不同的模式和方法完成算法的设计。 |
|||
=== 常用设计模式 === |
|||
完全遍历法 和 不完全遍历法: 在问题的解是有限离散解空间,且可以验证正确性和最优性时,最简单的算法就是把解空间的所有元素完全遍历一遍,逐个检测元素是否是我们要的解。这是最直接的算法,实现往往最简单。但是当解空间特别庞大时,这种算法很可能导致工程上无法承受的计算量。这时候可以利用不完全遍历方法——例如各种搜索法和规划法——来减少计算量。 |
|||
分治法: 把一个问题分割成互相独立的多个部分分别求解的思路。这种求解思路带来的好处之一是便于进行并行计算。 |
|||
[[动态规划]]法: 当问题的整体最优解就是由局部最优解组成的时候,经常采用的一种方法。详见词条。 |
|||
贪婪算法: 常见的近似求解思路。当问题的整体最优解不是(或无法证明是)由局部最优解组成,且对解的最优性没有要求的时候,可以采用的一种方法。 |
|||
线性规划法: |
|||
简并法: 把一个问题通过逻辑或数学推理,简化成与之等价或者近似的、相对简单的模型,进而求解的方法。 |
|||
=== 常用实现方法 === |
|||
[[递归|递归方法]] 与 [[迭代|迭代方法]]: 见词条 |
|||
顺序计算、[[并行计算]] 和 [[分布式计算]]: 顺序计算就是把形式化算法用编程语言进行单线程序列化后执行。其余见词条。 |
|||
确定性算法 和 非确定性算法: |
|||
精确求解 和 近似求解: |
|||
== 形式化算法 == |
== 形式化算法 == |
2013年3月13日 (三) 03:02的版本
在数学和计算机科学之中,算法(Algorithm)为一个计算的具体步骤,常用于计算、数据处理和自动推理。精确而言,算法是一个表示为有限长[1]列表的有效方法。算法应包含清晰定义的指令[2]用于计算函数[3] 。
算法中的指令描述的是一个计算,当其执行时能从一个初始状态和(可能为空的)初始输入开始, [4] 经过一系列有限 [5] 而清晰定义的状态最终产生输出 [6] 并停止于一个终态。一个状态到另一个状态的转移不一定是确定的。随机化算法在内的一些算法,包含了一些随机输入。 [7] [8]
形式化算法的概念部分源自尝试解决希尔伯特提出的判定问题,并在其后尝试定义有效计算性[9]或者有效方法[10]中成形。这些尝试包括库尔特·哥德尔、Jacques Herbrand和斯蒂芬·科尔·克莱尼分别于 1930年、1934年和1935年提出的递归函数,阿隆佐·邱奇于1936年提出的λ演算,1936年Emil Leon Post的Formulation 1 和艾伦·图灵1937年提出的图灵机。即使在当前,依然常有直觉想法难以定义为形式化算法的情况。[11]
历史
算法在中国古代文献中称为“术”,最早出现在《周髀算经》、《九章算术》。特别是《九章算术》,给出四则运算、最大公约数、最小公倍数、开平方根、开立方根、求素数的埃拉托斯特尼筛法,线性方程组求解的算法。三国代的刘徽给出求圆周率的算法:刘徽割圆术。
自唐代以来,历代更有许多专门论述“算法”的专著:
- 唐代:《一位算法》 一卷,《算法》 一卷;
- 宋代:《算法绪论》 一卷、《算法秘诀》 一卷;最著名的是杨辉的《杨辉算法》;
- 元代:《丁巨算法》;
- 明代:程大位 《算法统宗》
- 清代:《开平算法》、《算法一得》、《算法全书》。
而英文名称“Algorithm”来自于9世纪波斯数学家花拉子米(比阿勒·霍瓦里松,波斯语:خوارزمی ,拉丁转写:al-Khwarizmi),因为比阿勒·霍瓦里松在数学上提出了算法这个概念。“算法”原为“algorism”,即“al-Khwarizmi”的音转,意思是“花拉子米”的运算法则,在18世纪演变为“algorithm”。
欧几里得算法被人们认为是史上第一个算法。
第一次编写程序是Ada Byron于1842年为巴贝奇分析机编写求解解伯努利微分方程的程序,因此Ada Byron被大多数人认为是世界上第一位程序员。因为查尔斯·巴贝奇(Charles Babbage)未能完成他的巴贝奇分析机,这个算法未能在巴贝奇分析机上执行。
因为“well-defined procedure”缺少数学上精确的定义,19世纪和20世纪早期的数学家、逻辑学家在定义算法上出现了困难。20世纪的英国数学家图灵提出了著名的图灵论题,并提出一种假想的计算机的抽象模型,这个模型被称为图灵机。图灵机的出现解决了算法定义的难题,图灵的思想对算法的发展起到了重要的作用。
特征
以下是Donald Knuth在他的著作The Art of Computer Programming里对算法下的定义:
- 输入:一个算法必须有零个或以上输入量。
- 输出:一个算法应有一个或以上输出量,输出量是算法计算的结果。
- 明确性:算法的描述必须无歧义,以保证算法的实际执行结果是精确地符合要求或期望,通常要求实际执行结果是确定的。
- 有限性:依据图灵的定义,一个算法是能够被任何图灵完备系统模拟的一串运算,而图灵机只有有限个状态、有限个输入符号和有限个转移函数(指令)。而一些定义更规定算法必须在有限个步骤内完成任务。
- 有效性:又称可行性。能够实现,算法中描述的操作都是可以通过已经实现的基本运算执行有限次来实现。
基本要素
算法的核心是建立问题抽象的模型和明确求解目标,之后可以根据具体的问题选择不同的模式和方法完成算法的设计。
常用设计模式
完全遍历法 和 不完全遍历法: 在问题的解是有限离散解空间,且可以验证正确性和最优性时,最简单的算法就是把解空间的所有元素完全遍历一遍,逐个检测元素是否是我们要的解。这是最直接的算法,实现往往最简单。但是当解空间特别庞大时,这种算法很可能导致工程上无法承受的计算量。这时候可以利用不完全遍历方法——例如各种搜索法和规划法——来减少计算量。
分治法: 把一个问题分割成互相独立的多个部分分别求解的思路。这种求解思路带来的好处之一是便于进行并行计算。
动态规划法: 当问题的整体最优解就是由局部最优解组成的时候,经常采用的一种方法。详见词条。
贪心算法: 常见的近似求解思路。当问题的整体最优解不是(或无法证明是)由局部最优解组成,且对解的最优性没有要求的时候,可以采用的一种方法。
线性规划法:
简并法: 把一个问题通过逻辑或数学推理,简化成与之等价或者近似的、相对简单的模型,进而求解的方法。
常用实现方法
顺序计算、并行计算 和 分布式计算: 顺序计算就是把形式化算法用编程语言进行单线程序列化后执行。其余见词条。
确定性算法 和 非确定性算法:
精确求解 和 近似求解:
形式化算法
算法是计算机处理信息的本质,因为计算机程序本质上是一个算法来告诉计算机确切的步骤来执行一个指定的任务,如计算职工的薪水或打印学生的成绩单。 一般地,当算法在处理信息时,会从输入设备或数据的存储地址读取数据,把结果写入输出设备或某个存储地址供以后再调用。
复杂度
时间复杂度
算法的时间复杂度是指算法需要消耗的时间资源。一般来说,计算机算法是问题规模n 的函数f(n),算法的时间复杂度也因此记做
算法执行时间的增长率与f(n) 的增长率正相关,称作渐近时间复杂度(Asymptotic Time Complexity),简称时间复杂度。
常见的时间复杂度有:常数阶O(1),对数阶O(log2n),线性阶O(n), 线性对数阶O(nlog2n),平方阶O(n2),立方阶O(n3),..., k次方阶O(nk),指数阶O(2n)。随着问题规模n的不断增大,上述时间复杂度不断增大,算法的执行效率越低。
空间复杂度
算法的空间复杂度是指算法需要消耗的空间资源。其计算和表示方法与时间复杂度类似,一般都用复杂度的渐近性来表示。同时间复杂度相比,空间复杂度的分析要简单得多。
非确定性多项式时间(NP)
实现
算法不单单可以用计算机程序来实现,也可以在人工神经网络、电路或者机械设备上实现。
示例
求最大值算法
这是算法的一个简单的例子。
我们有一串随机数列。我们的目的是找到这个数列中最大的数。如果将数列中的每一个数字看成是一颗豆子的大小,可以将下面的算法形象地称为“捡豆子”:
- 首先将第一颗豆子放入口袋中。
- 从第二颗豆子开始检查,如果正在检查的豆子比口袋中的还大,则将它捡起放入口袋中,同时丢掉原先口袋中的豆子。直到最后一颗豆子。
- 最后口袋中的豆子就是所有的豆子中最大的一颗。
下面是一个形式算法,用ANSI C代码表示
int max(int *array, int size)
{
int mval = *array;
int i;
for (i = 1; i < size; i++)
if (array[i] > mval)
mval = array[i];
return mval;
}
求最大公约数算法
求两个自然数的最大公约数 设两个变量M和N
- 如果M < N,则交换M和N
- M被N除,得到余数R
- 判断R=0,正确则N即为“最大公约数”,否则下一步
- 将N赋值给M,将R赋值给N,重做第一步。
用“ANSI C代码”表示——
void swapi(int *x, int *y)
{
int tmp = *x;
*x = *y;
*y = tmp;
}
int gcd(int m, int n)
{
int r;
if (m < n)
swapi(&m, &n);
r = m % n;
while (r)
{
m = n;
n = r;
if (m < n)
swapi(&m, &n);
r = m % n;
}
return n;
}
利用if函数以及递归则能做出更为精简的代码,更可省去交换的麻烦。
int gcd(int a,int b)
{
if(a%b)
return gcd(b,a%b);
return b;
}
设计和分析的基本方法
分类
参考
- ^ "Any classical mathematical algorithm, for example, can be described in a finite number of English words" (Rogers 1987:2).
- ^ Well defined with respect to the agent that executes the algorithm: "There is a computing agent, usually human, which can react to the instructions and carry out the computations" (Rogers 1987:2).
- ^ "an algorithm is a procedure for computing a function (with respect to some chosen notation for integers) . . . this limitation (to numerical functions) results in no loss of generality", (Rogers 1987:1).
- ^ "An algorithm has zero or more inputs, i.e., quantities which are given to it initially before the algorithm begins" (Knuth 1973:5).
- ^ "A procedure which has all the characteristics of an algorithm except that it possibly lacks finiteness may be called a 'computational method'" (Knuth 1973:5).
- ^ "An algorithm has one or more outputs, i.e. quantities which have a specified relation to the inputs" (Knuth 1973:5).
- ^ Whether or not a process with random interior processes (not including the input) is an algorithm is debatable. Rogers opines that: "a computation is carried out in a discrete stepwise fashion, without use of continuous methods or analogue devices . . . carried forward deterministically, without resort to random methods or devices, e.g., dice" Rogers 1987:2).
- ^ Whether or not a process with random interior processes (not including the input) is an algorithm is debatable. Rogers opines that: "a computation is carried out in a discrete stepwise fashion, without use of continuous methods or analogue devices . . . carried forward deterministically, without resort to random methods or devices, e.g., dice" Rogers 1987:2).
- ^ Kleene 1943 in Davis 1965:274
- ^ Rosser 1939 in Davis 1965:225
- ^ Moschovakis, Yiannis N. What is an algorithm?. Engquist, B.; Schmid, W. (编). Mathematics Unlimited — 2001 and beyond. Springer. 2001: 919–936 (Part II).
外部链接
参见
|