高德纳(Donald E. Knuth)在其名作《The Art Of Computer Programming》的第一卷《Fundamental Algorithms》中,用集合论对算法进行了严格的数学定义,仅仅用了一页,言简意赅,但是就这一页足 以体现出他深厚的数学功底,驾驭数学的高超能力,把数学语言的简洁与精确体现得淋漓尽致。我在读 这一页时想到了很多,受到的启发远不止纸上的这些,现在把这些理解写在这里,希望对大家有所帮助。

在介绍算法的数学定义之前,我们要明确算法的五个基本特征:

  • 有限性:描述了一个算法在执行有限步之后必须会终止。
  • 确定性:描述了一个算法的每个步骤都必须精确地定义,可以严格地无歧义地被执行。
  • 输入:描述了一个算法在运行之前赋给它的量或在运行过程中动态地赋给它的量。
  • 输出:描述了一个算法运行结束时的结果。
  • 有效性:描述了一个算法在运行过程中的所有运算必须是充分基本的,是可行的,原则上人们可 以用笔和纸在有限的时间内精确地完成这些运算。

高教授在用集合论定义算法时是严格按照这五个基本特征来的,下面我就用常用的集合论术语隆重地介绍 算法的定义,如下:


我们定义一个计算方法为一个四元组(Q, I, Ω, f),每个字母的意义为:
Q: 表示计算状态的集合
I: 表示输入的集合
Ω: 表示输出的集合
f: 表示计算规则的集合
满足如下约束:
enter image description here
对集合I中的每一个输入x定义一个序列:enter image description here,满足如下规则:
enter image description here
如果k是使enter image description hereΩ中为最小的整数,那么就说这个计算序列在k步 中终止,而且在此种情况下说x产生了输出enter image description here。可能有些序列永远不会终止,这只能称为一个计算方法,而不能称之为算法算法是一种对I中所有的x在有限步中终止的计算方法


到目前为止,该定义虽然是用集合论描述的,但是丝毫没有难以理解的地方,就相当于一个有限状态机, 每一节点既是上一个节点的输出节点,又是下一个节点的输入节点,最后f在输出集合Ω中保持逐点 不动,很通俗易懂。然而,这个定义还不是很全面,还只包含了算法五个基本特征的前四个,并没有包含 第五个有效性特征。在为该定义补充第五个基本特征之前,让我们先来用上述定义描述一个具体的算法, 用一个大家都很熟悉的欧几里得算法。

欧几里得算法E:m和n是两个正整数,求它们最大的公因子。
E1[求余数]:m除以n并且令r为所得的余数。(0≤r<n)
E2[判断余数是否为零]:如果r=0,算法结束,n就是输出答案。
E3[减少]:置m←n,n←r,并返回步骤E1

这个算法可以说是众人皆知,最平民化的算法。如何用上述算法定义中的术语来描述这个算法呢?首先在 欧几里得算法中,我们涉及到单点(n):表示输出;有序数对(m,n):表示输入。除此之外,还涉及 到三个不同的步骤,每一步基本都与m,n,r这三个数有关,为了方便区别这三个不同的步骤,我们还要 引入一个步骤的序列号,这样我们可以用三个有序四元组分别表示每一个步骤了。所以欧几里得算法 严格的数学描述如下:


欧几里得算法是一个四元组(Q, I, Ω, f),每个字母的意义为:
Q: 所有单点(n),所有有序数对(m,n)和所有有序四元组(m,n,r,1),(m,n,r,2) 以及(m,n,p,3)的集合,其中m,n,p是正整数,r是一个非负整数。
I: 所有有序数对(m,n)的子集。
Ω: 所有单点(n)的子集。
f的定义如下:
1. f((m,n))=(m,n,0, 1)
2. f((m,n,r,1))=(m,n,m%n,2)
3. 如果r=0,f((m,n,r,2))=(n);否则f((m,n,r,2))=(m,n,r,3)
4. f((m,n,p,3))=(n,p,p,1)
5. f((n))=(n)


我在这里有必要说明一下,上面的f定义了5条规则,第1条规则是得到输入数对之后初始化为四元组,才 能参与后面的步骤;第2条对应于E1;第3条对应于E2;第4条对应于E3;第5条是算法结束的 终止条件。显而易见,欧几里得算法这样的数学定义与先前的步骤是一一对应的,但是更加严格准确了。

现在,大家应该对算法的集合论定义有了比较清晰的了解。前面已经说过,该集合论的数学定义还不尽如 人意,还不包括前面的有效性基本特征。例如,当Q是仅用纸和笔而无法计算的无穷序列,或者f是紧 靠人脑也无法实现的计算,那么这时就不满足有效性的特征,也就不能称之为算法。所以为了使算法的数 学定义更加完善,我们应该给Q和f加一些约束,使运算的每一步都是可行的有效的,或更加具体一点说,就是使每一运算都只涉及初等运算。在计算机中,什么样的初等运算最具有代表性呢?当然是字符串 的删除,添加,替换等操作啊,这些操作是绝对可行的,而且表示的含义也很广泛,当然你也可以使用其 他的初等运算。接下来我们就在Q和f上加一些约束了:


首先令A是字母的有限集合,并且令A上所有串的集合,我们用的串来对计 算的状态进行编码,即不同的串代表不同的计算状态。于是我们有:
Q:是所有(σ,j)的集合,其中σ∈,0≤j≤N,N为非负整数
I:是所有j=0时Q的子集,即是所有(σ,0)的集合
Ω:是所有j=N时Q的子集,即是所有(σ,N)的集合

为了方便描述,我们还要给出一个定义:对于θ,σ,α,ω∈,如果σ=αθω,那么则称θ 出现在σ中

现在我们可以给出f的约束了,如下:
enter image description here
——F1式:如果enter image description here不出现在enter image description here中,那么: enter image description here

——F2式:如果enter image description here是满足enter image description here的最短的字符串,那么:enter image description here

——F3式enter image description here

[注]
1. F1式通俗地说就是:如果在一个字符串enter image description here中如果找不到另一个字符串enter image description here,就跳转第enter image description here步。
2. F2式通俗地说就是:如果在一个字符串enter image description here中找到了另一个字符串enter image description here,就用字符串enter image description here替换字符串enter image description here,然后跳转到第enter image description here步。
3. F3式是终止条件。


上面对于f的约束显然能确保算法的有效性基本特征,因为上述定义的每一步都是对字符串进行了简单的 操作。事实上,F1式F2式F3式这三个式子足够可以描述我们手头的所有事情,更具 体一点就是,足够可以描述所有的计算机程序。我为什么这样说呢?我们知道所有的计算机算法程序都是 用某种编程语言写的,而所有的编程语言无外乎三种结构:顺序选择循环。上面的三 个式子正好可以描述这三种结构。我将一一进行解释:

  • 顺序结构
    这个最简单,这三个式子任意执行就可以了,而且只要指定j,下一步就会进行你指定的第j个运算,所以不再赘述了。
  • 选择结构
    F1式F2式结合起来使用便是选择结构:如果enter image description here不出现在enter image description here中,就执行F1式,如果enter image description here出现在enter image description here中,就执行F2式。这里字符串中的出现与不出现就分别表示的是相反的两种计算状态。
  • 循环结构
    F2式中,令enter image description here,便会进行循环运算,然后用F1式判断是否跳出循环,非常容易。

F3式是描述算法执行结束的状态。所以用上面的F1式F2式F3式三个式子可以 描述所有的算法,而且每一步都是有效的,到这里算法的集合论数学定义才算完备,囊括了算法所有的五 个基本特征。



除此之外,编程语言中最基本的数据类型——整型,可以用某个字符的个数来表示,而编程语言中最基本的初等运算——加减法,可以用字符串的替换来表示,所以现在,我可以说基于字符串集合F1式F2式F3式三个式子就构成了一门编程语言,通过它们可以编写任何你想要的合法程序,和那些高级语言(如C语言等)效果一样。但是这是一门有严格数学定义的编程语言,为了以后叙述的方便,我将其命名为M语言(是Math语言的简称,后面均用此简称)。M语言中仅仅涉及enter image description here这四个变量(变量的定义和前面一致),所以这四个变量的取值就决定了M语言中语句的每一步执行,换句话说,在M语言中每一条语句就是这四个变量的取值,因此每一条语句就可以用这个四元组表示。以后,我们如果说用M语言来编写程序,就是说用这四元组来编写程序,程序的每一条语句都是四元组,整个程序就是由这些四元组构成的。



为了熟练使用这种由集合论进行了严格数学定义的算法语言——M语言,最后,我将M语言应用于 一个具体的例子,用来说明其强大的描述能力。当然,我们还是以欧几里得算法为例,考虑到用字符串来 描述初等运算,我们使用欧几里得辗转相减法,而不是原先的辗转相除法。

题目表述如下:
通过描述上面的F1式F2式F3式三个式子中的enter image description here,给出计算正整数m和n的最大公因子的一个“有效性”算法,令输入为字符串enter image description here,输出结果是enter image description here,当然你完全可以输出除b 以外的其他字母,这里只是为了方便而已。希望你尽可能给出简单的解。

我用自己的话重述一下这个题目:就是用M语言编写求最大公因子的欧氏辗转相减法。根据我前面 所述,就是求一系列四元组。首先我还是按照前面介绍欧氏辗转相除法的方式来介绍辗转相减法,如下:

欧氏辗转相减法ERM:m和n是两个正整数,求它们最大的公因子。 ERM1[求差]:m减n并且令r为所得的差的绝对值。(0≤r<n)
ERM2[判断差是否为零]:如果r=0,算法结束,n就是输出答案。
ERM3[减少]:置m←min(m,n),n←r,并返回步骤ERM1

这个算法ERM和前面的算法E的正确性很容易证明,限于篇幅,这里就略去了。下面我就主要讲 解一下我解决这道题目的思路:


题中两个正整数m和n分别是用a和b的个数表示的,所以要求m和n的差,只要每次分别去掉一个“a”和一 个“b”,为了便于字符串的操作,每次直接去掉“ab”,一直到只剩下“a┄”序列或“b┄”序列为止,这时剩下的“a”或“b”的个数就是m和n差的绝对值r,这就完成了步骤ERM1。为了方便步骤ERM3的赋值操作,我们需要知道min(m,n)到底是哪一个,显然min(m,n)就是去掉的“ab”的个数,因 此我们需要换一种简单的方式保留“ab”的个数,就用另外一个字母“c”替换“ab”,这就是F2式中 的操作。但是“c”会把字符串中的“a”序列和“b”序列分开,无法进行继续去掉“ab”的操作,因此我们要把“c”移到字符串的最左边或最右边(这就导致了两种解法,下文我都会给出。)这种移到最左边或最右边的操作一般会是连续重复的,这就会使用到上文所说的F2式中的循环操作。然后继续替换“ab” 也会使用该循环操作。等替换完所有的“ab”后,这时可以执行步骤ERM3,“c”的个数就是min(m,n),余下的“a”或“b”的个数就是r,接下来要分两种情况,如果把“c”移到了最左端,由于跳到步 骤ERM1后要继续替换“ab”,所以这时要将所有的“c”变成“a”,将所有的“b”或“a”都变成“b”;如果把“c”移到了最右端,这时要将所有的“c”变成“b”,将所有的“b”或“a”都变成“a”,这些就是执行步骤ERM3,当然这些过程都会用到F1式中的跳转操作和F2式中的循 环操作。执行完步骤ERM3后就会重复执行步骤ERM1,以此循环直到执行步骤ERM2,即r=0, 也就是说字符串中只剩下“c”的序列,这时“c”的个数就是m和n的最大公因子(gcd(m,n))。当然不一 定最后以“c”的表示输出,可以输出任意其他字符,那么就可以用F2式中的循环替换操作。


下面我就给出该题目的一种解答(将“c”移到最左边),并将详细解释该M语言编写的程序的每一 步,该程序如下:
enter image description here
【上述M语言版的辗转相减法程序注解】:j表示程序的步骤号,每个步骤的具体含义为:

  • 第0步:如果找到“ab”就用“c”替换,然后跳转到第1步;如果找不到“ab”,就直接跳转到第2 步。(这一步就是用“c”替换“ab”
  • 第1步:如果找到“ac”就用“ca”替换,然后循环执行这一步;否则直接跳转到第0步。(这一步 就是将“c”移到最左边
  • 第2步:如果找到“a”就用“b”替换,然后循环执行这一步;否则直接跳转到第3步。(这一步就 是执行ERM3中的n←r操作
  • 第3步:如果找到“c”就用“a”替换,然后循环执行这一步;否则直接跳转到第4步。(这一步就 是执行ERM3中的m←min(m,n)操作
  • 第4步:如果找到“b”就用“b”替换,然后跳转到第0步;否则直接跳转到第5步。(这一步就是相 当于执行ERM2的判断
  • 第5步:如果找到“a”就用“b”替换,然后循环执行这一步(这一步就是为了满足题目的要求最终 以“b”序列的形式输出来结果

为了使该M语言版算法的步骤更加清晰,我给出一个实例:m=6,n=4,此时的输入为σ=aaaaaabbbb,执行过程图如下:

aaaaaabbbb→aaaaacbbb→aaaacabbb→aaacaabbb→aacaaabbb →acaaaabbb→caaaaabbb→caaaacbb→caaacabb→caacaabb→cacaaabb →ccaaaabb→ccaaacb→ccaacab→ccacaab→cccaaab→cccaac→cccaca →ccccaa→ccccba→ccccbb→acccbb→aaccbb→aaacbb→aaaabb→aaacb →aacab→acaab→caaab→caac→caca→ccaa→ccba→ccbb→acbb→aabb →acb→cab→cc→ac→aa→ba→bb

执行结果输出结果σ=bb,即gcd(6,4)=2。

同理,我再给出该题目的另外一个解(将“c”移到最右边),该程序如下:
enter image description here
分析同上面的将“c”移到最左边的解。

最后为了完整性,同时考虑通用性,我将用伪代码的形式实现由F1式F2式F3式所严 格定义的算法通用程序,如下:

while(!terminate condition){
    find the first Theta_j in the input_string;
    if(No Found){
       j=a_j;    
    }else{
       input_string=the sub_string in front of Theta_j 
                    + Phi_j 
                    + the sub_string behind Theta_j;
       j=b_j;
    }
}

上面伪代码中选择语句if···else···的第一部分相当于F1式,第二部分相当于F2式,而terminate condition相当于F3式,所以具有通用性,很容易将上述伪代码用高级语言编程实现,例如依照该伪代码,可以轻松的将上面讲的辗转相减法的M语言版用高级语言实现。下面就是我用C++实现的辗转相减法的第一种解(第二种解几乎一样,只要改一下状态表中的变量值即可),如下:

#include    <iostream>
#include    <string>

using namespace std;

int main (){
    int j=0; 
    string theta[]={"ab","ac","a","c","b","a"};
    string phi[]={"c","ca","b","a","b","b"};
    int b[]={1,1,2,3,0,5};
    int a[]={2,0,3,4,5,5}; 
    string input;

    cout<<"Input:";
    cin>>input;
    cout<<"Output:"<<endl;

    while(input.find("a",0)!=-1 || input.find("c",0)!=-1){
        int location=input.find(theta[j],0);
        if (location==-1){
            j=a[j];
        }else{
            input=input.substr(0,location)
                  +phi[j]
                  +input.substr(location+theta[j].length());
            j=b[j];

        cout<<input<<"→";
        }
    }
    cout<<"Success"<<endl;
    system("pause");
    return 0;
}                

假设输入aaaaaabbbb,则运行该程序的结果为:
enter image description here

至此,就是我阅读这一页Knuth教授用集合论对算法进行严格数学定义的全部理解。