关于算法介绍

[拼音]：suanfa

[外文]：algorithm

在古代，算法指一种运算或计算，最初是指对自然数的计算如加减乘除（所谓四则运算）等。后来数的概念推广了，运算的概念也推广成函数，算法也相应地推广为对任何一种函数的计算，广义地说，是指为解决任意一个问题时所作的一种处理过程。自古以来，对算法赋予了一种要求──能行性。因此现在所谓算法是指对任何一个问题所作的能行性的处理。由于能行性要求，算法必须具有离散性与机械性。

离散性是指算法的出发点所给的原始数据（所谓输入，例如自变元的值），以及算法的终点所求的结果数据（所谓输出，例如函数的值），必须可用一些符号表示，而这些符号又可以明确地分解为有限多个不可再分解的符号。后面这些不能再分解的符号叫做字母，由字母所组成的符号叫做该字母表上的字。算法的第一个要求是其输入与输出必须可以表成某个固定的字母表上的字。因此，例如，不能以某条曲线作为输入或输出。第二，算法的处理过程必须可以明确地分解成有限多个不能再分解的步骤，算法过程便由这些有限多个步骤组成。例如，不能用画曲线作为算法的处理过程，因为画曲线不能分解成有限多个步骤。为此，算法必须有一组变换规则或产生式来规定这些步骤。第三，算法是否继续进行或算法结束必须用明确的结束条件来确定。如果算法不给出结束条件，或给出结束条件尚未实现，则算法应继续进行不能停止。

所谓机械性主要是指算法的变换规则必须是非常简单而机械的，不必须依靠人的聪明才智，甚至无须人们去领会理解，连最笨的人甚至于机器都能执行的，而且执行的结果都是一样的。

人们还可以从反面来理解算法的能行性。第一，对于输入与输出的大小是没有限制的，由于能行性，每次输入输出的字固然必须是有限长的，但输出入字的长度是没有上界的。这是指空间方面。第二，由于能行性，每次计算当然只进行有限多步，但步数也是没有上界的。这是指时间方面。第三，每次计算所得的中间结果（亦即所需利用的中间结果）当然是有限多的，但也是无界的，因此存储中间结果的存储单元（所谓“草稿纸”）应该无界多地供给。这也是指空间方面。

总结起来，一个算法U必须具有下列两个内容：

（1）一张字母表A(以便用A中字表示输入输出以及中间结果)，②一组变换规则（又名产生式），也可叫做指令，用以规定各步改造动作。

给出算法U后，如果一个字p经过执行一条变换规则而变成字Q，则说U把p一次改造成Q，记为U:p喩Q；如果p经过实施多次（包括0次，即未改造时）变换规则而变成Q，则说U把p 改造成Q，记为U:p喺Q。如果算法规定有结束条件，当p改造成Q时结束条件实现，则说U把p改造最终得Q，记为U:p 喺·Q。

各种算法的区别在于字母表与变换规则表的不同，此外，还可对算法作各种的分类。

附有结束条件的算法特别关心的是对一字改造的最终结果，而不是未结束时所得的中间结果，这种算法仍叫做算法。对于不附有结束条件因而对每步改造结果都同样重视的算法则特名曰演算。

一般的算法是关心改造的结果，但是有一种算法却只关心是否结束以及结束的方式。当因实施结束规则而结束时，它便接受该输入字，而当因无法改造而结束或者永不结束时，它便不接受该输入字。这种算法叫做识别算法。

对任何输入字都必然结束的算法叫做完全算法，对某些输入字结束而对另一些输入字不结束的算法，叫做部分算法。部分算法用以计算部分函数，即函数在某处的值有定义时，算法应该结束而给出其值，函数在某处的值没有定义时算法可以不结束或结束而用特殊符号表明该函数没有值。使用完全算法可以使人们完全解决问题（有值与否必可知道），但完全算法很难作出，一般容易作出的是部分算法，因此在实用上部分算法更为重要。

如果在每一步骤只能使用一条变换规则，执行这条规则后又只有一个结果，因此从开始到结束，都是同样进行，得到同样结果。这种算法叫做一意算法。如果在各步骤中，可以使用若干条（有限多条）规则之一，而执行该规则后，又可能有有限多个不同结果，从而改造结果不是惟一的，这种算法叫做多意算法。一般是使用一意算法的，但因和演算相比较，近年来渐渐使用多意算法了。演算对各中间结果是同样重视的，因此一般是多意的，它考虑在改造过程中是否曾经出现过某种形状的中间结果。

最有名的算法有图灵机、正规算法以及首尾算法，最有名的演算是各种公理系统与形式语言文法。

图灵机是一条两端（或一端）无限延长的纸带，上面划成方格，每个方格可以印上某字母表中的一个字母(亦可为空格，这时说印有字母S0)。又有一个读头，它具有有限个内部状态(每个状态可以看作一条指令)。任何时候读头都注视着一个方格，并根据注视方格的内容以及读头当时的内部状态而执行变换规则所规定的动作。每个图灵机都有一组变换规则，它们具有下列三种形状之一：

qjαRqj， qjαLqj， qjαbqj。

其意是:当读头处在状态qj时如果注视格的内容为字母α则读头右移一格、左移一格、印下字母b(亦即把注视格内容由α改为b，然后转到状态qj。易见图灵机带上的各格相当于计算机的存储单元，而读头的状态qj则相当于第i条指令。

另一个有名的算法是马尔可夫的正规算法。正规算法中每条变换规则都有下列形状（换中规则）：

Aj→Bj。

其意是：把被改造的字中第一个(最左)出现的Aj换为Bj（两边其余的字母不变）。正规算法也叫做换中算法。

还有一个是E.L.波斯特的首尾算法。其中每条变换规则都是首尾规则：

Ajp喩pBj，

即当被改造的字以Aj起头时，把头Aj删掉，再在最右边添上Bj，这是最简单的算法。

已经证明，图灵机、换中算法、首尾算法的力量是一样的，凡可以用其中一种算法计算的函数，都可以用另外两种算法计算。根据丘吉-图灵论题，凡直觉上认为可以计算的函数，恰巧就是可以用这三种算法之一计算的函数。这三种算法既简单，又威力大，其重要性由此可见。

各种各样的公理系统便是一个大演算。公理系统中的常元与变元便相当于字母表中的字母，而项以及公式相当于字母表上的字。公理系统中的推理规则相当于变换规则（一般是多元的规则，即把多个字变成一个字的规则）。具有公理的公理系统相当于具有固定开始字的演算，没有公理的公理系统相当于没有固定开始字的演算。

形式语言中的文法便是简化了的演算。它的变换规则都是换中规则，它把字母表分成两个，一个是变元字母表，一个是终极字母表（相当于常元），并指定一个变元字母（一般记为S）作为开始字母，凡将这个字母改造而得的不含变元字母（纯含终极字母）的字便叫做该语言的语句。全体语句的集合叫做该文法所产生的语言。上述的文法（对其变换规则不再加任何限制）叫做零型文法，如果逐步增加限制，便得出一型、二型、三型文法。其中以二型文法最为重要，因为现在计算机所使用的算法语言，大多数是二型文法所产生的语言。

如果把图灵机的内部状态解释为指令，用字母表的字来表示，和输出字输入字同样存储在机器里，那便是一部电子计算机。可以说，电子计算机正是图灵机与电子技术结合之后的产物，电子计算机的发展，又促进了形式语言的研究，算法理论现在已经日趋重要。

参考文章

• 母猪产期推算法猪
• 猪粮比不足据 养殖利润应有新算法猪
• KDJ指标的算法是什么股票基金
• 现货黄金阻力位的几种算法股票基金
• 低瓦斯矿井如何采用总体核算法对矿井通风能力进行核定？采矿冶炼
• 如何采用由里向外核算法核算矿井通风能力？采矿冶炼
• 阿隆指标的算法股票基金
• EXPMA指标基础算法以及计算公式股票基金
• CR能量指标的算法,用途及使用方法股票基金
• 双边匹配理论的匹配算法经济百科