演算法

在数学和计算机科学方面，算法（）是严格指令的有限顺序，通常用于解决一类特定问题或执行计算。算法用作执行计算和数据处理的规格。更高级的算法可以使用条件来通过各种路线（称为自动决策）将代码执行转移，并推断出有效的推论（称为自动推理），最终实现自动化。 Alan Turing用“记忆”，“搜索”和“刺激”等术语来实践人类特征作为机器的描述符。

相反，启发式方法是解决问题的方法，可能无法完全指定或可能无法保证正确或最佳的结果，尤其是在没有明确定义的正确或最佳结果的问题域中。例如，社交媒体推荐系统依靠启发式方法，以至于在21世纪流行媒体中被广泛特征为“算法”，但由于问题的性质而无法取得正确的结果。

作为一种有效的方法，可以在有限的空间和时间和定义明确的正式语言中表达算法，以计算功能。从初始状态和初始输入（也许是空）开始，指令描述了一个计算，该计算在执行时，通过有限数量的连续数量有限的连续状态进行，最终产生“输出”并在最终结束状态下终止。从一个国家到下一个状态的过渡不一定是确定性的。某些算法（称为随机算法）包含随机输入。

历史

古代算法

由于上古以来，已经证明了解决数学问题的分步程序。其中包括巴比伦数学（公元前2500年），埃及数学（公元前1550年），印度数学（大约公元前800年左右；以后；例如Shulba Sutras ， Kerala School和Brāhmasphuṭasiddhnnta ）公元前240年左右，例如eRatosthenes和Euclidean算法的筛分）和阿拉伯数学（9世纪，例如基于频率分析的代码破坏代码的加密算法）。

al-khwārizmī和术语算法

825年左右， MuḥammadIbnMūsāal-Khwārizmī写道Kitābal-ḥisābal-hindī （“印度计算书”）和Kitab al-Jam'wa'l-wa'l-tafriq al-ḥisābal-hindī （印度的添加和额外交易中” ）。目前，这两个文本在原始阿拉伯语中都丢失了。（但是，他关于代数的另一本书仍然是。）

在12世纪初期，涉及印度教 - 阿拉伯数字系统和算术的上述al-khwarizmi文本的拉丁翻译出现了：自由alghoarismi de actripica arismetrice （归因于塞维利亚的约翰）和自由主义者Indorum （归因于浴室的Adelard odelard of Bath ）。因此， Alghoarismi或Algorismi是Al-Khwarizmi名称的拉丁化；文本始于短语dixit algorismi （“因此spoke al-khwarizmi”）。

在1240年， Villedieu的亚历山大（Alexander of Villedieu ）撰写了拉丁文字，名为Carmen de Algorismo 。它以：

Haec Algorismus ars praesens diTurur，在Qua / Talibus Indorum fruimur bis quinque figuris中。

转化为：

算法是目前我们使用这些印度人物的艺术，这是两次五次。

这首诗长几行，总结了新型印度骰子（ Tali Indorum ）或印度教数字进行计算的艺术。

单词的英语演变

在1230年左右，英语单词算法得到了证明，然后由乔uc在1391年得到证明。英语通过了法语术语。

在15世纪，在希腊语单词ἀριθμός（ arithmos ，“数字”;参见“算术”）的影响下，拉丁单词被更改为algorithmus 。

1656年，在英语词典术语中，它说：

算法（[拉丁]算法）的艺术或使用密码或通过密码编号；会计技能。

Augrime （[ Latin ]算法）会计或数字中的冰鞋。

1658年，在新的英语单词的第一版中，它说：

算法（一个复杂的阿拉伯和西班牙语的单词），是由Cyphers估算的艺术。

1706年，在新的英语单词的第六版中，它说：

算法是计算或按数字进行计算的艺术，其中包含Arithmetick的五个主要规则，即。数字，加法，减法，乘法和除法；可能会添加根的提取：也称为logistica numeralis 。

算法，在算术或代数的几个部分中的实际操作；有时，这是十个数字数字的常见算术实践。

在1751年，在年轻的代数伴侣中，丹尼尔·芬宁（Daniel Fenning）将术语与算法和算法对比如下：

算法表示第一原则，算法是实用部分，或者知道如何将算法放入实践中。

自从至少1811年以来，术语算法被证明是在英语中表示“逐步程序”。

1842年，在科学，文学和艺术词典中，它说：

算法，以某种特定的方式或某种方式表示计算艺术；作为数字的算法；差分计算的算法。

机器用法

1928年，现代算法概念的部分形式化始于尝试解决戴维·希尔伯特（David Hilbert ）提出的Entscheidungsproblem （决策问题）。后来的形式化被构架，试图定义“有效的可计算性”或“有效方法”。这些形式化包括1930年，1934年和1935年的Gödel -Herbrand - Kleene 递归功能，1936年的Alonzo Church的Lambda Colculus ， Emil Post的1936年的配方，以及Alan Turing的1936 - 37年和1939年的Turing Machine of Alan Turing的Turing Machines 。

非正式定义

一个非正式的定义是“一组精确定义操作顺序的规则”，其中包括所有计算机程序（包括不执行数字计算的程序），以及（例如）任何规定的官僚程序或库克书籍食谱。

通常，只有在最终停止的情况下，该程序才是一种算法，即使无限循环有时可能是可取的。

算法的原型示例是欧几里得算法，该算法用于确定两个整数的最大常见分裂。上面的流程图描述了一个示例（还有其他），在后面的一节中描述了一个示例。

Boolos，Jeffrey＆1974，1999在以下引号中提供了“算法”一词的非正式含义：

没有人能写得足够快，或者足够长，或者很小†（†“越来越小的没有限制的……您将尝试在分子上，原子，电子上写入”），以列出通过在某些符号中互相写出自己的名字，列举了无限的命名。但是，对于某些列举的无限集，人类可以做同样有用的事情：他们可以为任意有限n提供明确的指示来确定集合的第n个成员。这样的说明应非常明确，以一种可以跟随计算机的形式，或者由能够仅在符号上进行非常基本操作的人。

“枚举无限的集合”是可以将元素与整数一对一的对应的元素。因此，Boolos和Jeffrey说，算法意味着从任意“输入”整数或整数“创建”输出整数的过程的说明，理论上可以任意大。例如，算法可以是代数方程，例如y = m + n （即，两个任意的“输入变量” m和n产生输出y ），但是各种作者的尝试定义了概念，表示单词暗示不仅仅是这样的东西（对于加法示例）：

精确的说明（用“计算机”理解的语言），用于快速，高效，“良好”过程，指定“计算机”的“移动”（机器或人类，配备了必要的内部包含的信息和功能）查找，解码，然后处理任意输入整数/符号m和n ，符号+ and = ...以及“有效地”在“合理”的时间内产生，在指定的位置和指定格式的“合理”时间，输出 - 构成y 。

算法的概念还用于定义可定义性的概念，这是一个概念，这是解释形式系统如何从一小部分公理和规则开始的核心。在逻辑上，无法测量算法需要完成的时间，因为它显然与习惯物理维度无关。从这样的不确定性来看，持续工作的特征是构成了适合具体（从某种意义上说）和该术语抽像用法的算法定义的不可用。

大多数算法旨在作为计算机程序实现。但是，在电路或机械装置中，在生物神经网络中（例如，实施算术或寻找食物的昆虫的人脑）在生物神经网络中（例如，实施算术或寻找食物的昆虫的人脑）也实现了演算法.

形式化

算法对于计算机处理数据的方式至关重要。许多计算机程序都包含算法，详细说明计算机应通过特定订单执行指定任务的特定说明，例如计算员工的薪水或打印学生的成绩单。因此，可以将算法视为可以通过Turing-Complete系统模拟的任何操作序列。断言这一论文的作者包括Minsky（1967），Savage（1987）和Gurevich（2000）：

明斯基：“但是我们还将通过图灵（Turing）保持……任何可以自然地称为有效的程序，实际上都可以通过（简单的）机器实现。尽管这似乎是极端的，但论证是。。 Gurevich：“……图灵的非正式论点赞成他的论文是有道理的，这是一个更强有力的论文：每种算法都可以由图灵机器模拟……根据Savage [1987]，算法是图灵机定义的计算过程。”

图灵机可以定义未终止的计算过程。算法的非正式定义通常要求该算法始终终止。这项要求将决定形式程序是否是一般情况下不可能的算法的任务，这是一种被称为停止问题的计算性理论的主要定理。

通常，当算法与处理信息相关联时，可以从输入源读取数据，并写入输出设备并存储以进行进一步处理。存储的数据被视为执行该算法的实体内部状态的一部分。实际上，状态存储在一个或多个数据结构中。

对于这些计算过程中的某些，必须以在所有可能出现的情况下使用的方式对算法进行严格定义和指定。这意味着任何有条件的步骤都必须系统地处理。每种情况的标准必须清晰（可计算）。

由于算法是精确步骤的精确列表，因此计算顺序对于算法的功能始终至关重要。通常假定说明是明确列出的，被描述为“从顶部”开始，然后“向下到底部”，这是通过控制流更正式描述的想法。

到目前为止，关于算法形式化的讨论已经采用了命令编程的前提。这是最常见的概念，它试图用离散的“机械”术语描述任务。与这种形式化算法的概念相关的是分配操作，该操作设置了变量的值。它源自“记忆”作为刮刀的直觉。可以在下面找到这样的分配的示例。

有关构成算法的替代概念，请参见功能编程和逻辑编程。

表达算法

算法可以用多种符号表示，包括自然语言，伪代码，流程图， Drakon-charts ，编程语言或控制表（由口译员处理）。算法的自然语言表达往往是冗长而模棱两可的，很少用于复杂或技术算法。伪代码，流程图，Drakon-Charts和控制表是表达算法的结构化方法，这些算法避免了许多基于自然语言的陈述中常见的歧义。编程语言主要用于以可以由计算机执行的形式表达算法，但它们通常也被用作定义或文档算法的一种方式。

有各种各样的表示形式，并且可以作为一系列机器表表达给定的Turing Machine程序（有关更多信息，请参见有限状态机器，状态转换表和控制表），如Flowcharts和Drakon-Charts（请参阅状态图表的图），或称为“四边形集合”的基本机器代码或装配代码的形式（有关更多信息，请参见Turing Machine ）。

算法的表示可以分为三个公认的图灵机器描述，如下：

1个高级描述: “ ...散文描述算法，忽略实现细节。在此级别上，我们不需要提及机器如何管理磁带或头部。”
2实施描述: “ ...散文用来定义图灵机使用其头部以及将数据存储在磁带上的方式。在此级别上，我们不提供状态或过渡功能的详细信息。”
3正式描述: 最详细的“最低级别”给出了图灵机的“状态表”。

有关所有三个级别中描述的简单算法“添加M+N”的示例，请参见示例。

设计

算法设计是指解决问题和工程算法的方法或数学过程。算法的设计是许多解决方案理论的一部分，例如在操作研究中的划分和混合或动态编程。设计和实施算法设计的技术也称为算法设计模式，其中包括模板方法模式和装饰器模式在内。

算法设计最重要的方面之一是资源（运行时，内存使用）效率；大o符号用于描述EG，例如，随着其输入的大小的增加，算法的运行时间增长。

算法开发的典型步骤：

问题定义
开发模型
算法的规范
设计算法
检查算法的正确性
算法分析
实施算法
程序测试
文档准备

计算机算法

“优雅”（紧凑）程序，“良好”（快速）程序：“简单和优雅”的概念在Knuth中非正式地出现在Chaitin中：

诺斯：“ ...我们想要一些宽松定义的美学意义上的好算法。一个标准...是执行算法所花费的时间。...其他标准是算法对计算机的适应性，其简单性和其简单性和优雅等等。”

Chaitin：“ ...一个程序是'优雅'，我的意思是它是产生其输出的最小程序”

Chaitin的定义为：“我会表明您不能证明程序是'优雅' ” - 这样的证明可以解决停止问题（同上）。

算法与函数可通过算法计算：对于给定函数，可能存在多个算法。即使不扩展程序员可用的可用说明集，也是如此。罗杰斯观察到：“很重要的是，要区分算法的概念，即过程和可通过算法计算的函数概念，即通过过程产生的映射。相同的函数可能具有多种不同的算法”。

不幸的是，优雅的程序可能会采取更多步骤来完成计算，而不是优雅的计算，善良（速度）和优雅（紧凑）之间可能会有一个权衡。使用Euclid算法的一个示例出现在下面。

计算机（和计算机），计算模型：计算机（或人类“计算机”）是一种受限制的机器类型，是一种盲目遵循其说明的“离散确定性机械设备”。梅尔扎克（Melzak's）和兰贝克（Lambek）的原始模型将此概念降低为四个要素：（i）离散的，可区分的位置，（ii）离散的，难以区分的计数器（iii）代理，以及（iv）（iv）相对于相对于相对于能力的有效指令列表代理人。

明斯基描述了兰贝克（Lambek）在其“非常简单的可计算性基础”中的“算盘”模型的更加差异。 Minsky的机器依次通过其五个（或六个，取决于一个指令）的指令进行进行，除非有条件的IF-then Goto或无条件的GOTO更改程序以序列为单位。除了停顿之外，明斯基的机器还包括三个分配（替换，替换）操作：零（例如，位置的内容替换为0：l←0），后继（例如L←L+1）和降低（例如，L - l-- l-- 1）。很少有程序员用如此有限的说明集编写“代码”。但是明斯基（Minsky）表明（梅尔扎克（Melzak）和兰贝克（Lambek）也是如此），他的机器仅包含四种通用类型的说明：有条件的goto，无条件的goto，任务/替换/替换和停止。但是，对于图灵完整性，也需要一些不同的分配指令（例如，降低，增量和零/清除/空）；他们的确切规范在某种程度上取决于设计师。无条件的goto很方便；可以通过将专用位置初始化为零来构建，例如“ z←0”指令；此后，如果z = 0，则指令xxx是无条件的。

算法的仿真：计算机（计算机）语言：Knuth建议读者“学习算法的最佳方法是尝试一下……立即取笔和纸并通过示例进行工作”。但是，真实事物的模拟或执行呢？程序员必须将算法转换为模拟器/计算机/计算机可以有效执行的语言。斯通给出了一个例子：计算二次方程的根时，计算机必须知道如何取平方根。如果他们没有，那么要有效的算法必须提供一组提取平方根的规则。

这意味着程序员必须知道与目标计算代理（计算机/计算机）有效的“语言”。

但是，应该使用哪种模型进行仿真呢？ Van Emde Boas观察到“即使我们将复杂性理论基于抽象而不是具体机器基础，但选择模型的任意性仍然存在。在这一点上，模拟的概念进入了”。测量速度时，指令设置很重要。例如，如果程序员具有可用的“模量”指令，而不仅仅是减法（或更糟糕的是：Just Minsky的“减少”），则欧几里得算法中的子程序将执行其余部分。

结构化的编程，规范结构：根据教会的论文，任何算法都可以通过已知已知完整的模型来计算，并且根据Minsky的示范，Turing完整性只需要四种指令类型，即条件goto，无条件，无条件的goto，goto，tossment，sistmentment，halt。 Kemeny和Kurtz观察到，尽管“无条件”使用无条件的gotos和有条件的话，如果gotos可以导致“意大利面代码”，但程序员可以仅使用这些指令编写结构化的程序；另一方面，“以结构化语言编写结构性良好的程序也是可能的，而且不太难”。 Tausworthe增强了三个Böhm-Jacopini典型结构：序列，如果是else，则又有两个：还有两个：do-while and case和case。结构化程序的另一个好处是，它可以使用数学诱导来证明正确性的证明。

规范流程图符号：称为流程图的图形辅助工具提供了一种描述和记录算法（以及与之相对应的计算机程序）的方法。就像Minsky机器的程序流一样，流程图总是从页面顶部开始，然后继续进行。它的主要符号只有四个：有向箭头显示程序流，矩形（序列，goto），钻石（如果是else）和点（or-tie）。 Böhm -Jacopini规范结构是由这些原始形状制成的。子结构可以在矩形中“嵌套”，但前提是从上层建筑发生单个出口。符号及其用于构建规范结构的用途显示在图中。

例子

算法示例

最简单的算法之一是在随机顺序列表列表中找到最大数量。查找解决方案需要查看列表中的每个数字。从此开始，简单的算法可以在英语散文中的高级描述中说明，为：

高级描述：

如果集合中没有数字，则没有最高数字。
假设集合中的第一个数字是集合中的最大数字。
对于集合中的每个剩余数字：如果此数字大于当前最大数字，则将此数字视为集合中的最大数字。
当该集合中没有数字以迭代遍历时，将当前最大数字视为该集合的最大数字。

（Quasi-）正式描述：用散文书写，但更接近计算机程序的高级语言，以下是伪代码或pidgin代码中算法更正式的编码：

Algorithm LargestNumber
Input: A list of numbers L.
Output: The largest number in the list L.

if L.size = 0 return null
largest ← L[0]
for each item in L, do
    if item > largest, then
        largest ← item
return largest

“←”表示作业。例如，“最大←项目”是指对项目值的最大变化值。
“返回”终止算法并输出以下值。

欧几里得的算法

在数学中，欧几里得算法或欧几里得的算法是计算两个整数（数字）的最大共同分裂（GCD）的有效方法，这是将它们划分的最大数字，而它们均不剩余。它以古希腊数学家欧几里得的名字命名，后者首先在他的元素中描述了这一点（约公元前300年）。它是常用中最古老的算法之一。它可用于将分数减少到最简单的形式，并且是许多其他数字理论和加密计算的一部分。

欧几里得提出了一个问题：“给定两个数字不是彼此的，找到他们最大的共同度量”。他定义了“一个由单位组成的数字”：一个数字，一个正整数不包括零。 “测量”是沿较长的长度L连续地放置较短的测量长度S （ Q时间），直到其余部分r小于较短的长度s 。用现代词，剩余的r = l - q × s ， q是商，或剩余的r是“模量”，这是划分后留下的整数裂缝部分。

为了使欧几里得成功的方法必须满足两个要求：（i）长度不能为零，并且（ii）减法必须是“正确的”；即，测试必须保证从较大的两个数字中较小的两个数字中的较小（或两个数字可以相等，因此它们的减法得出零）。

Euclid的原始证明增加了第三个要求：两个长度不得彼此之间。 Euclid规定了这一点，因此他可以构建一个荒谬的荒谬证据，证明这两个数字的共同度量实际上是最大的。虽然尼科马斯的算法与欧几里得相同，但是当数字彼此吻合时，它会产生数字“ 1”的常见度量。因此，确切地说，以下实际上是Nicomachus的算法。

欧几里得算法的图形表达，以找到1599和650的最大共同除数
1599 = 650×2 + 299 650 = 299×2 + 52 299 = 52×5 + 39 52 = 39×1 + 13 39 = 13×3 + 0

欧几里得算法的计算机语言

执行Euclid的算法 - 某些逻辑测试（有条件的GOTO），无条件goto，分配（替换）和减法只需要几种指令类型。

位置由上案字母，例如S，A等象征。
位置中的不同数量（数字）用与位置名称相关的低案例字母和（通常）写成。例如，开始时的位置l可能包含数字L = 3009。

欧几里得算法的不高度程序

以下算法被构架为Knuth的四步版本的Euclid's and Nicomachus'，但是，它并没有使用除法来查找其余部分，而是使用剩余长度r的较短长度s的连续减法，直到r小于s 。大胆显示的高级描述是根据Knuth 1973：2-4：改编的。

输入：

1 [Into two locations L and S put the numbers l and s that represent the two lengths]:
INPUT L, S
2 [Initialize R: make the remaining length r equal to the starting/initial/input length l]:
R ← L

E0：[确保r≥s 。 ]

3 [Ensure the smaller of the two numbers is in S and the larger in R]:
IF R > S THEN
the contents of L is the larger number so skip over the exchange-steps 4, 5 and 6:
GOTO step 7
ELSE
swap the contents of R and S.
4 L ← R (this first step is redundant, but is useful for later discussion).
5 R ← S
6 S ← L

E1：[查找余数] ：直到r中的剩余长度r小于s中的较短长度，从R中的其余长度r反复减去s中的测量数s 。

7 IF S > R THEN
done measuring so
GOTO 10
ELSE
measure again,
8 R ← R − S
9 [Remainder-loop]:
GOTO 7.

E2：[剩余的零吗？小于S中的测量数。

10 IF R = 0 THEN
done so
GOTO step 15
ELSE
CONTINUE TO step 11,

E3：[Interchange s和r ] ：欧几里得算法的螺母。使用剩余r来测量以前较小的s ；我是临时位置。

11 L ← R
12 R ← S
13 S ← L
14 [Repeat the measuring process]:
GOTO 7

输出：

15 [Done. S contains the greatest common divisor]:
PRINT S

完毕：

16 HALT, END, STOP.

欧几里得算法的优雅程序

以下版本的Euclid算法只需要六个核心说明即可完成13个“ Inelegant”需要做的事情；更糟糕的是，“不高”需要更多类型的说明。 “优雅”的流程图可以在本文的顶部找到。在（非结构化的）基本语言中，这些步骤是编号的，并且指令LET [] = []是←象征的作业指令。

5 REM Euclid's algorithm for greatest common divisor
6 PRINT "Type two integers greater than 0"
10 INPUT A,B
20 IF B=0 THEN GOTO 80
30 IF A > B THEN GOTO 60
40 LET B=B-A
50 GOTO 20
60 LET A=A-B
70 GOTO 20
80 PRINT A
90 END

“优雅”的工作方式：“优雅”而不是外部“ Euclid Loop”，而是使用Modulo来计算分区的其余部分，并在每次迭代中移动变量A和B。以下算法可以与C家族的编程语言一起使用：

标准函数ABS将负整数变为正整数
当输入A或B具有值0时，算法停止，结果为0
如果输入A大于输入B，则该算法将在第一次迭代中通过Modulo自动交换变量A和B
迭代（a时循环）启动，并且仅在变量B设置为0时停止。
- ％计算A和B的模量，该模量减少了数字（例如：23 = 3×6 +剩余5）
- A等同于B
- b等同于模量星期
- 只要B大于0，迭代就会继续
当迭代停止时，变量a总是包含最大的共同除数

// Euclid's algorithm for greatest common divisor
int euclidAlgorithm (int A, int B) {
    A = abs(A);
    B = abs(B);
    if (A == 0 || B == 0) {
       return 0;
    }
    do { 
       int res = A % B; 
       A = B;
       B = res;
    } while (B > 0);
  return A;

测试欧几里得算法

算法是否会做作者想要它做的事情？一些测试用例通常会对核心功能充满信心。但是测试还不够。对于测试用例，一个来源使用3009和884。Knuth建议40902，24140。另一个有趣的案例是两个相对质数14157和5950。

但是必须识别和测试“例外情况”。当r> s，s> r，r = s时，“不高”会正确执行吗？同上“优雅”：b> a，a> b，a = b？（全部同意）。当一个数字为零，两个数字为零时会发生什么？（在所有情况下，“ Inelegant”均永远计算；“优雅”在a = 0时永远计算。）如果输入负数，会发生什么？分数数字？如果输入号，即由算法/程序计算的函数的域，则仅包括包括零在内的正整数，则零的故障表示算法（以及实例化的程序）是部分函数，而不是部分函数，而不是部分函数总功能。异常引起的显著故障是Ariane 5 Flight 501火箭故障（1996年6月4日）。

通过使用数学诱导的程序正确性证明：Knuth演示了数学诱导在Euclid算法的“扩展”版本中的应用，他提出了“适用于证明任何算法有效性的一般方法”。 Tausworthe提出，对程序的复杂性的度量是其正确性证明的长度。

测量和改进欧几里得算法

优雅（紧凑）与优点（速度） ：只有六个核心说明，“优雅”是清晰的赢家，与13个说明中的“不高”相比。但是，“不高”速度更快（它以更少的步骤停止）。算法分析表明为什么会有这种情况：“ Elegant”在每个减法循环中进行两个条件测试，而“不高级”只能进行。由于算法（通常）需要许多循环直通，因此平均浪费了很多时间“ B = 0？”。仅在计算其余部分之后才需要的测试。

可以改进算法吗？ ：一旦程序员判断程序“拟合”和“有效”（即它计算其作者意图的功能），那么问题就会得到改进吗？

消除五个步骤可以改善“不高级”的紧凑性。但是Chaitin证明，压实算法不能由广义算法自动化。相反，它只能启发。即，通过详尽的搜索（在忙碌的海狸中找到示例），反复试验，聪明，洞察力，归纳推理的应用等。观察步骤4、5和6在步骤11、12和13中重复。 “ Elegant”提供了一个暗示，即可以消除这些步骤以及步骤2和第3步。这将核心说明的数量从十三幅减少到8个，这使其比“优雅”在九个步骤中“优雅”。

通过移动“ B = 0？”可以提高“优雅”的速度？在两个减法回路之外进行测试。此更改要求添加三个说明（b = 0？，a = 0？，goto）。现在，“优雅”计算示例数更快；对于任何给定的A，B和R，S始终是这种情况，都需要进行详细的分析。

算法分析

在理论上，特定资源（例如时间或存储）在理论上需要多少特定资源（例如时间或存储），这通常很重要。已经开发了用于分析算法以获得此类定量答案的方法（估计）；例如，使用大o符号将n数字列表元素的算法累加，将有时间要求。在任何时候，算法只需要记住两个值：到目前为止所有元素的总和以及其当前位置在输入列表中。因此，据说有一个空间要求，如果未计算存储输入编号的空间或计数。

不同的算法可以在更少或更多或更多的时间，空间或努力下完成相同的任务，而不是其他指令。例如，当用于排序列表或数组上的表查找时，二进制搜索算法（带有成本）优于顺序搜索（成本）。

正式与经验

算法的分析和研究是计算机科学的一项学科，通常在不使用特定的编程语言或实施的情况下抽象实践。从这个意义上讲，算法分析类似于其他数学学科，因为它的重点是算法的基本属性，而不是任何特定实现的细节。通常，伪代码用于分析，因为它是最简单，最通用的表示。但是，最终，大多数算法通常是在特定的硬件/软件平台上实现的，最终使用真实代码将其算法效率进行测试。为了解决“一个偏离”问题，特定算法的效率可能不会产生重大后果（除非n非常大），但是对于专为快速互动，商业或长寿科学用法而设计的算法可能至关重要。从小n到大N的缩放通常会暴露出良性良性的效率低下的算法。

经验测试很有用，因为它可能会发现影响性能的意外相互作用。基准可用于比较程序优化后的潜在改进之前/之后的算法。但是，经验测试不能替代正式的分析，并且并不能够以公平的方式进行。

执行效率

为了说明即使在建立良好的算法中也可能取得的潜在改进，最近与FFT算法有关的一项重大创新（在图像处理领域中大量使用），可以将处理时间降低高达1000倍的医学成像应用。通常，速度提高取决于问题的特殊特性，这在实际应用中非常普遍。如此庞大的加速能够实现大量使用图像处理（例如数码相机和医疗设备）的计算设备，从而消耗了更少的功率。

分类

有多种方法可以对算法进行分类，每种算法都有自己的优点。

通过实施

对算法进行分类的一种方法是通过实现手段。

int gcd(int A, int B) {
    if (B == 0)
        return A;
    else if (A > B)
        return gcd(A-B,B);
    else
        return gcd(A,B-A);
}

从上述流程图中递归C实施Euclid算法

递回: 递归算法是一种反复调用（引用）本身的算法，直到某种条件（也称为终止条件）匹配为止，这是功能编程共有的方法。迭代算法使用循环等重复构造，有时甚至是其他数据结构（例如堆栈）来解决给定的问题。一些问题自然适合一种或另一个实施。例如，使用递归实现对河内的塔楼有很好的了解。每个递归版本都具有等效的（但可能或多或少复杂）的迭代版本，反之亦然。
串行，平行或分布: 通常会以这样的假设讨论算法，即计算机一次执行一项算法的指令。这些计算机有时称为串行计算机。专为这种环境设计的算法称为串行算法，而不是平行算法或分布式算法。并行算法是利用计算机架构的算法，在该算法中，多个处理器可以同时解决问题。分布式算法是使用与计算机网络连接的多个机器的算法。并行和分布式算法将问题分为更对称或不对称的子问题，并将结果重新收集在一起。例如，CPU将是并行算法的一个示例。这种算法中的资源消耗不仅是每个处理器上的处理器周期，而且是处理器之间的通信开销。某些分类算法可以有效地并行化，但是它们的沟通开销很昂贵。迭代算法通常是可行的，但是有些问题没有平行算法，被称为固有的序列问题。
确定性或非确定性: 确定性算法在算法的每个步骤中都通过确切的决定解决了问题，而非确定性算法通过猜测解决了问题，尽管通过使用启发式方法使典型的猜测更加准确。
精确或近似: 尽管许多算法达到了精确的解，但近似算法寻求近似值，该近似值接近真实解。可以通过使用确定性或随机策略来达到近似值。这种算法对于许多严重问题具有实际价值。近似算法的示例之一是背包问题，其中有一组给定的项目。它的目标是打包背包以获得最大总价值。每个项目都有一定的重量和一定的价值。可以携带的总重量不超过一些固定数字X。因此，解决方案必须考虑项目的权重及其价值。
量子算法: 它们以量子计算的现实模型运行。该术语通常用于那些看起来固有量子的算法，或使用量子计算的某些基本特征，例如量子叠加或量子纠缠。

通过设计范式

对算法进行分类的另一种方法是通过其设计方法或范式。有一定数量的范式，每个范式都与彼此不同。此外，这些类别中的每一个都包括许多不同类型的算法。一些常见的范例是：

蛮力或详尽的搜索: 蛮力是一种解决问题的方法，涉及系统地尝试所有可能的选项，直到找到最佳解决方案。这种方法可能非常耗时，因为它需要贯穿所有可能的变量组合。但是，当其他方法不可用或太复杂时，通常会使用它。蛮力可用于解决各种问题，包括找到两个点之间的最短路径和破裂的密码。
分裂和征服: 划分和诱使算法反复将问题的实例降低到一个或多个相同问题的较小实例（通常是递归），直到实例足够小以易于解决。这样的一个例子是合并分类。在将数据分为段之后，可以对数据的每个段进行排序，并且可以通过合并段来在征服阶段获得整个数据的排序。划分和征服的一种更简单的变体称为减少和争议算法，该算法解决了相同的子问题，并使用此子问题的解决方案来解决更大的问题。分裂和征服将问题分为多个子问题，因此征服阶段比减少和征服算法更为复杂。减少和征服算法的一个例子是二进制搜索算法。
搜索和枚举: 许多问题（例如下棋）可以建模为图表上的问题。图形探索算法指定了围绕图形移动的规则，对于此类问题很有用。此类别还包括搜索算法，分支和数个枚举和回溯。
随机算法: 这种算法可以随机（或伪随机）做出一些选择。对于找到确切的解决方案可能是不切实际的问题的近似解决方案，它们可能非常有用（请参见下面的启发式方法）。对于其中一些问题，众所周知，最快的近似值必须涉及一些随机性。具有多项式时间复杂性的随机算法是否可以成为某些问题的最快算法，这是一个开放的问题，称为P与NP问题。有两类此类算法：

Monte Carlo算法以高概率返回正确的答案。例如， RP是在多项式时间内运行的子类。
拉斯维加斯算法始终返回正确的答案，但是它们的运行时间仅在概率上绑定，例如ZPP 。

降低复杂性: 该技术涉及通过将其转换为我们（希望）徒劳的最佳算法的知名问题来解决困难问题。目的是找到一种减少的算法，其复杂性并非由降低的算法所主导的算法。例如，一种用于在未分类列表中查找中位数的选择算法涉及首先对列表进行排序（昂贵的部分），然后在排序列表（廉价部分）中撤出中间元素。该技术也被称为变换和征服。
后退跟踪: 在这种方法中，当确定它们不能导致有效的完整解决方案时，可以逐渐构建多个解决方案。

优化问题

为了优化问题，算法有更具体的分类。此类问题的算法可能属于上述一个或多个一般类别，以及以下一个：

线性规划: 当搜索与线性平等和不等式约束的线性函数的最佳解决方案时，问题的约束可以直接用于生成最佳解决方案。有一些算法可以解决此类别中的任何问题，例如流行的单纯算法。可以通过线性编程解决的问题包括有向图的最大流问题。如果问题还要求一个或多个未知数必须是整数，则将其分类为整数编程。如果可以证明，整数值的所有限制都是浅表的，即，解决方案都可以满足这些限制。在一般情况下，根据问题的难度，使用了近似解决方案的专业算法或算法。
动态编程: 当问题显示最佳子结构时 - 可以从最佳解决方案到子问题构建问题的最佳解决方案 - 并重叠的子问题，这意味着使用相同的子问题来解决许多不同的问题实例，一种更快的方法称为动态程序，避免了对解决方案进行避免对解决方案进行调整解决方案。已经计算出来。例如， Floyd -Warshall算法，可以通过使用所有相邻顶点的目标通往目标的最短路径来找到来自加权图中顶点的目标的最短路径。动态的编程和纪念活动在一起。动态编程与划分和征服之间的主要区别在于，子问题或多或少在分裂和征服中是独立的，而在动态编程中的子问题重叠。动态编程和直接递归之间的差异在于递归调用的缓存或记忆。当子问题是独立的，并且没有重复时，回忆无济于事。因此，动态编程并不是解决所有复杂问题的解决方案。通过使用回忆或维护已经解决的子问题表，动态编程将许多问题的指数性质降低到多项式复杂性。
贪婪的方法: 贪婪的算法类似于动态编程算法，因为它通过检查子结构而起作用，在这种情况下，不是问题，而是给定解决方案。这种算法从某些解决方案开始，这些解决方案可以以某种方式给出或构建，并通过进行小型修改来改进它。对于某些问题，他们可以找到最佳解决方案，而对于其他问题，他们在本地Optima停止，即在无法通过算法改进但不是最佳的解决方案上。贪婪算法最流行的用途是找到最小的生成树，在这种方法中可以找到最佳解决方案。 Huffman Tree ， Kruskal ， Prim ， Sollin是可以解决此优化问题的贪婪算法。
启发式方法: 在优化问题中，在找到最佳解决方案不切实际的情况下，可以使用启发式算法来找到接近最佳解决方案的解决方案。这些算法通过随着进步而越来越近的最佳解决方案来起作用。原则上，如果运行无限的时间，他们将找到最佳解决方案。他们的优点是他们可以在相对较短的时间内找到非常接近最佳解决方案的解决方案。这种算法包括本地搜索，禁忌搜索，模拟退火和遗传算法。其中一些，例如模拟退火，是非确定性算法，而其他算法（例如Tabu Search）是确定性的。当知道非最佳解的误差的结合时，该算法将进一步归类为近似算法。

通过研究领域

每个科学领域都有自己的问题，需要有效的算法。经常一起研究一个领域的相关问题。一些示例课程是搜索算法，分类算法，合并算法，数值算法，图形算法，字符串算法，计算几何算法，组合算法，组合算法，医学算法，机器学习，机器学习，密码，数据压缩算法和数据压缩算法和标准化技术。

字段倾向于相互重叠，一个字段中的算法进步可能会改善另一个字段的算法，有时是完全无关的字段。例如，发明了动态编程，以优化行业资源消耗，但现在用于解决许多领域的广泛问题。

通过复杂性

与输入大小相比，可以按需要完成的时间来对算法进行分类：

恒定时间：如果算法所需的时间相同，无论输入大小如何。例如，访问数组元素。
对数时间：如果时间是输入大小的对数函数。例如二进制搜索算法。
线性时间：如果时间与输入大小成正比。例如列表的遍历。
多项式时间：如果时间是输入大小的幂。例如，气泡排序算法具有二次时间复杂性。
指数时间：如果时间是输入大小的指数函数。例如蛮力搜索。

某些问题可能具有多种复杂性的多种算法，而其他问题可能没有算法或没有已知的有效算法。从某些问题到其他问题也有映射。因此，基于对它们的最佳算法的复杂性，它更适合于将问题本身分类而不是将算法分类为等效类。

连续算法

当应用于“算法”一词时，形容词“连续”可能意味着：

在代表连续数量的数据上运行的算法，即使该数据由离散近似表示，但在数值分析中研究了算法；或者
一种以微分方程形式的算法，该算法在模拟计算机上运行的数据连续运行。

算法=逻辑 +控制

在逻辑编程中，算法被视为具有“逻辑组件，它指定了用于解决问题的知识，又是一个控制组件，它通过使用该知识的使用方式来确定解决问题的策略。”

欧几里得算法说明了这种算法的观点。这是一个逻辑编程表示，使用： - 表示“ if”，而关系gcd（a，b，c）表示函数gcd（a，b）= c：

gcd(A, A, A).
gcd(A, B, C) :- A > B, gcd(A-B, B, C).
gcd(A, B, C) :- B > A, gcd(A, B-A, C).

在逻辑编程语言中， GCD关系可以直接用功能符号表示：

gcd(A, A) := A.
gcd(A, B) := gcd(A-B, B) :- A > B.
gcd(A, B) := gcd(A, B-A) :- B > A.

CIAO实施将功能符号转化为Prolog中的关系表示法，将嵌入式减法AB和BA提取为单独的条件：

gcd(A, A, A).
gcd(A, B, C) :- A > B, A' is A-B, gcd(A', B, C).
gcd(A, B, C) :- B > A, B' is B-A, gcd(A, B, C).

结果程序具有纯粹的逻辑（和“声明性” ）阅读，作为递归（或归纳）定义，它与逻辑如何用于解决问题的方式无关：

The gcd of A and A is A.
The gcd of A and B is C, if A > B and A' is A-B and the gcd of A' and B is C.
The gcd of A and B is C, if B > A and B' is B-A and the gcd of A and B' is C.

不同的解决问题的策略将逻辑转化为不同的算法。从理论上讲，鉴于一对整数A和B，可以使用前向（或“自下而上”）推理来生成GCD关系的所有实例，并在生成A和B的所需GCD时终止。当然，在这种情况下，远期推理完全没有用。但是在其他情况下，例如斐波那契序列和数据核的定义，远期推理可能是有效的解决问题策略。（例如，请参见逻辑程序以计算算法中的斐波那契数=逻辑 +控制）。

与此示例中远期推理的效率低下相反，使用SLD分辨率向后（或“自上而下”）推理将逻辑转化为欧几里得算法：

To find the gcd C of two given numbers A and B:
If A = B, then C = A.
If A > B, then let A' = A-B and find the gcd of A' and B, which is C.
If B > A, then let B' = B-A and find the gcd of A and B', which is C.

算法的逻辑编程表示的优点之一是，其纯粹的逻辑读数使算法相对于GCD的标准非寻求定义是正确的。这是序言中写的标准定义：

gcd(A, B, C) :- divides(C, A), divides(C, B),
    forall((divides(D, A), divides(D, B)), D =< C).
           
 divides(C, Number) :- 
   between(1, Number, C), 0 is Number mod C.

该定义是欧几里得算法的规范，在序言中也可以执行：向后推理将规范视为蛮力算法，该算法通过1和a之间的所有整数C进行迭代，以检查C是否分配A和B ，然后对于每个这样的C再次迭代通过1和A之间的所有整数D，直到找到C的C，使C大于或等于所有d也均分配A和B。尽管此算法为这表明，正式规格通常可以以逻辑编程形式编写，并且可以通过Prolog执行，以检查它们是否正确表示非正式要求。

法律问题

算法本身通常是不可申请的。在美国，仅由简单的抽象概念，数字或信号的简单操纵组成的主张并不构成“过程”（USPTO 2006），因此算法是不可申请的（如Gottschalkv。Benson中所述）。但是，算法的实际应用有时是可以专利的。例如，在Diamond诉Diehr中，使用简单的反馈算法来帮助固化合成橡胶的固化是可申请的。软件的专利是有争议的，并且有涉及算法的批评专利，尤其是数据压缩算法，例如Unisys的LZW专利。

此外，某些加密算法具有导出限制（请参阅加密的导出）。

历史：“算法”概念的发展

古老的近东

算法的最早证据是在古代美索不达米亚（现代伊拉克）的巴比伦数学中发现的。在巴格达附近的Shuruppak发现的苏美尔粘土平板电脑，可追溯至c。公元前2500年描述了最早的分区算法。在汉堡王朝期间c。 1800 - c。公元前1600年，巴比伦粘土片描述了用于计算公式的算法。算法也用于巴比伦天文学。巴比伦粘土片描述并采用算法程序来计算重大天文事件的时间和地点。

在古埃及数学中也发现了算术算法，可以追溯到Rhind数学纸莎草纸。公元前1550年。后来在古代的希腊化数学中使用了算法。两个例子是Eratosthenes的筛子，在Nicomachus的算术引言中描述了euclidean算法，该算法在Euclid的元素（ C。300BC ）中首先描述。

离散和可区分的符号

Tally-Marks：为了跟踪他们的羊群，他们的谷物袋和金钱，古人使用的是：积累石头或痕迹在棍子上刮擦或在粘土中制作离散的符号。通过巴比伦和埃及人的商标和符号的使用，最终的罗马数字和算盘发展（Dilson，第16-41页）。 Tally标记在Turing Machine和Post -Winder机器计算中使用的一元数字系统算术中显著。

将符号作为数字的“位置持有人”的操纵：代数

波斯数学家穆罕默德·伊本·穆萨米（MuhammadIbnMūsāal-Khwārizmī）在9世纪写了al-jabr 。术语“算法”和“算法”源自al-khwārizmī的名称，而术语“代数”源自本书al-jabr 。在欧洲，“算法”一词最初用于指代al-Khwarizmi使用的一组规则和技术来求解代数方程，然后再被推广以参考任何一组规则或技术。最终，这最终达到了莱布尼兹（ Leibniz ）的演算结果概念（ c。1680 ）：

莱布尼兹（Leibniz）比他的时代领先一个半世纪，提出了一个逻辑代数，该代数将以普通代数指定操纵数字规则的方式来指定操纵逻辑概念的规则。

加密算法

第一种用于解密加密代码的密码算法是由9世纪阿拉伯数学家 Al-Kindi在有关解密的加密消息的手稿中开发的。他通过频率分析（最早的代码破坏算法）对密码分析进行了第一个描述。

离散状态的机械性

时钟：Bolter将重量驱动时钟的发明称为“ [中世纪的欧洲的关键发明），尤其是为我们提供机械时钟的tick和tock的边缘逃逸。从13世纪开始，“准确的自动机”立即引导到“机械自动机”，最后到达了“计算机” - 19世纪中叶的Charles Babbage和Countess Ada Lovelace的差异引擎和分析引擎。 Lovelace的首次创建了用于在计算机上处理的算法（Babbage的分析引擎），这是第一个被视为真实的Turing-Complete计算机而不是计算器的设备- 有时被称为“历史记录”，因此被称为“历史记录”。尽管Babbage的第二个设备的全面实施要等到她一生后的几十年才实现。

逻辑机1870 - Stanley Jevons的“逻辑算盘”和“逻辑机器” ：技术问题是在以类似于现在所谓的Karnaugh Maps类似的形式显示时减少布尔方程。 Jevons（1880）首先描述了一个简单的“算盘”，这些木材的木板带有销钉，以便可以机械地挑选出任何[逻辑]组合的任何部分或类别的组合……但是，最近，我减少了该组合系统到完全机械形式，因此体现了整个间接推理过程中可能所谓的逻辑机器的推理过程“他的机器配备了“某些可移动的木制杆”和“脚下的“是21个钥匙”，就像那些的钥匙钢琴[等] ...”。借助这台机器，他可以分析“三段论或任何其他简单的逻辑论点”。

他于1870年展示的这台机器在皇家学会的研究员之前展出。然而，另一位逻辑学家约翰·维恩（John Venn）在他的1881年象征逻辑中，对这一努力感到轻浮的眼睛：“我对有时所谓的逻辑机器的兴趣或重要性没有高度估计……在我看来，我似乎并没有目前已知或可能被发现的任何自我都应该得到逻辑机器的名称”；请参阅有关算法表征的更多信息。但不要被淘汰，他也提出了“我理解的一个计划有点类似于Jevon教授的算盘... [和] [A]获得的收益，与Jevons教授的逻辑机器相对应，可以描述以下案例。仅将其称为逻辑数字机...但是我想它可以完全可以做任何逻辑机器可以理性地期望的事情”。

Jacquard Loom，Hollerith Punch卡，电报和电话 - 机电接力：Bell and Newell（1971）表明， Jacquard Loom （1801）， Hollerith Cards的前代（Punch Cards，1887）和“电话开关技术”和“电话开关技术”是导致第一台计算机开发的树。到19世纪中叶，电话是电话的先驱电报，它在世界各地都使用，其离散的和可区分的字母编码是“点和破折号”，一种常见的声音。到19世纪后期，股票录像带（ 1870年代）正在使用，在1890年美国人口普查中使用Hollerith卡也是如此。然后是Teprinter （ c。1910 ），其打孔器在磁带上使用Baudot代码。

机电继电器的电话开关网络（发明了1835年）是数字添加设备的发明者乔治·斯蒂比茨（George Stibitz ，1937年）的作品。当他在贝尔实验室工作时，他观察到“繁重的”用齿轮的机械计算器使用。”他在1937年的一个晚上回家，打算测试自己的想法...当修补林结束时，Stibitz构建了一个二进制添加设备” 。

数学家马丁·戴维斯（Martin Davis）观察了机电继电器的特殊重要性（及其两个“二元状态”开放和关闭）：

只有从1930年代开始，使用电气继电器的机电计算器的开发才能建造机器，并设想了瞄准镜。”

直到20世纪中叶的19世纪数学

符号和规则：迅速继承，乔治·布尔（George Boole）的数学（1847，1854）， Gottlob Frege （1879）和Giuseppe Peano （1888–1889）将算术降低为一系列由规则操纵的符号。 Peano的《算术原理》（通过新方法（1888）提出）是“以象征性语言进行数学的公理化尝试”。

但是Heijenoort赋予Frege（1879）这种荣誉：Frege是“也许是有史以来最重要的单一作品。...在其中我们看到了一种“ '公式语言'，那是一种通用语言特征，是一种写有特殊符号的语言，“为纯思想”，也就是说，没有修饰的点缀……由根据明确规则操纵的特定符号构建”。弗雷格的工作进一步简化和放大了阿尔弗雷德·诺斯·诺斯·怀特海和贝特兰德·罗素的原则。（1910–1913）。

悖论：与此同时，文献中出现了许多令人不安的悖论，特别是Burali-Forti Paradox （1897）， Russell Paradox （1902-03）和Richard Paradox 。由此产生的考虑导致了库尔特·戈德尔（KurtGödel ）的论文（1931年） - 他特别引用了骗子的悖论，这完全将递归规则降低到了数字。

有效的可计算性：为了解决希尔伯特精确定义的ientscheidungsproblem ，数学家首先开始定义“有效方法”或“有效计算”或“有效的计算性”或“有效的计算性”的含义（即，计算，将成功的计算）。迅速连续出现： Alonzo Church ， Stephen Kleene和JB Rosser的λ-Calculus从Gödel的作品中对“一般递归”的定义进行了精心磨练的定义，该作品是根据Jacques Herbrand的建议（参见Gödel的1934年Princeton extures of 1934）的建议。随后的Kleene进行了简化。教会证明了Entscheidungsproblem是无法解决的， Emil Post的定义有效地可计算性作为工人无意识地按照一系列房间的左右说明列表，而虽然在那里删除了纸张或删除纸张或观察纸张或制作纸张并制作并制作不是关于下一个指令的决定。艾伦·图灵（Alan Turing）证明了ientscheidungsproblem无法通过使用“ A- [自动]机器”来解决，这与Post的“配方”几乎相同， J。Barkley Rosser对“有效方法”的定义是“有效方法”的定义。机器”。克莱恩（Kleene）提出的“教会论文”的先驱提出了他所说的“论文”，几年后，克莱恩（Kleene）将他的论文命名为“教会的论文”并提出“图灵的论文” 。

Emil Post（1936）和Alan Turing（1936-37，1939）

Emil Post （1936）描述了“计算机”（人类）的行为，如下所示：

“ ...涉及两个概念：符号空间的符号空间，在该符号空间中，从问题到回答的工作是要进行的，以及一组固定的不可改变的方向。

他的象征空间将是

“一个双向无限的空间或盒子序列……解决方案或工人是在此符号空间中移动和工作即承认只有两个可能的条件，即空无一人或未标记，并在其中有一个标记，例如垂直中风。

“一个盒子要被选出并称为起点。...一个特定的问题应以有限数量的盒子（即输入）标记为符号形式。同样，答案[即，输出]将以符号形式给出，通过标记框的这种配置...

“适用于通用问题的一组指示可以在应用于每个特定问题时设置确定性过程。此过程仅在涉及类型（c）[IE，停止]方向时终止。”。在邮政机器上查看更多

艾伦·图灵（Alan Turing）的作品先于Stibitz（1937）的作品；尚不清楚斯蒂比茨是否知道图灵的工作。图灵的传记作者认为，图灵（Turing打字机“机械” 。鉴于摩尔斯密码，电报，磁带机和电视节目的流行率很有可能在他年轻时对图丁的影响很有可能。

图灵（Turing） - 他的计算模型现在称为图灵机器（Turing Machine ），就像帖子一样，对人类计算机进行了分析，他将其缩减为简单的基本动作和“心态”。但是他继续进一步，并创建一台计算机作为数字计算模型。

“计算通常是通过在纸上编写某些符号来完成的。我们可以假设本文像孩子的算术书一样分为正方形……我假设我假设计算是在一维纸上进行的，即在磁带上进行。进入正方形。我还要假设可以打印的符号数量是有限的...

“计算机的行为随时由他观察到的符号和他的“心态”决定。观察一刻。如果他想观察更多，他必须使用连续的观察。我们还将假设需要考虑的心态数量是有限的.. .

“让我们想像，计算机执行的操作将其分为'简单操作'，这是如此基本，以至于不容易想像它们会进一步分裂。”

图灵的减少产生以下内容：

“因此，简单的操作必须包括：

”（a）在一个观察到的正方形之一上改变符号

（b）观察到的一个正方形的一个正方形的变化，一个先前观察到的正方形的L正方形内的另一个正方形。

“可能是其中一些变化一定会引起思维状态的改变。因此，最一般的单一操作必须是以下内容之一：

”（a）可能的更改（a），以及可能的心态变化。

“（b）可能改变（b）观察到的正方形，以及可能改变的心态”

“我们现在可以构建一台计算机工作的机器。”

几年后，图灵用这种有力的表达扩大了他的分析（论文，定义）：

“如果可以通过某个纯机械过程找到其值，则说“一个函数可以有效地计算”。尽管很容易对此想法进行直观的掌握，但仍需要更确定的数学表达定义，但仍需.. . [他讨论了上述关于戈德尔，赫布兰德，克莱恩，教堂，图灵和职位的定义的历史] ...可以通过机器进行。可以以某种正常形式对这些机器的结构进行数学描述。这些思想的发展导致作者对可计算功能的定义，并确定可计算性†具有有效的可计算性...

“†我们将使用“可计算函数”表达式来表示一台计算机可计算的函数，并且我们让“有效计算”指的是无需特殊识别的直观思想，而没有特定的识别。

JB Rosser（1939）和SC Kleene（1943）

J. Barkley Rosser通过以下方式定义了一种“有效的[数学]方法”（添加了斜体化）：

“在这里使用'有效方法'的方法是针对每个步骤的特殊意义迄今为止。[他的脚注＃5；请参见下面的讨论]。这些最简单的说明（由于帖子和图灵）本质上说，如果可以构建一台机器，则存在一种有效解决某些问题的有效方法除了插入问题之外，没有任何人为干预的设置问题，并且（以后）阅读答案。这三个定义都是等效的，因此使用哪个定义。此外，这三个定义都是等效的事实关于任何人的正确性的非常有力的论点。” （Rosser 1939：225–226）

罗瑟（Rosser）的脚注第5号引用了（1）教堂和克莱恩（Church）和克莱恩（Kleene）的作品，尤其是他们对λ-可确度性的定义，尤其是教会在他的基本数字理论无法解决的问题中对它的使用（1936）；（2）Herbrand andGödel及其对递归的使用，尤其是Gödel在其著名的论文中使用了对Principia Mathematica及相关系统I（1931）的正式不可决定的命题的使用；（3）Post（1936）和图灵（1936–37）的计算机理模型。

斯蒂芬·克莱恩（Stephen C.但是他在以下上下文中做到了这一点（原始中的粗体）：

“ 12.算法理论...在建立完整的算法理论时，我们要做的是描述一个过程，可用于每组独立变量值的过程，哪些过程必然会终止，并且从结果中以我们可以从结果中终止阅读一个确定的答案，“是”或“否”，“否”，“谓词值是正确的？”（Kleene 1943：273）

1950年以后的历史

已经为进一步改进了“算法”的定义进行了许多努力，并且由于围绕数学基础（尤其是教会 - 论文论文）和心理哲学（尤其是论点）而进行的活动正在进行中。关于人工智能）。有关更多信息，请参见算法表征。

演算法

历史