分析是数学中技巧最成功、构造最精细的部分。

约翰·冯·诺伊曼（1951）

一个简单而基本的事实是：在未来的几十年以至几个世纪内，电子计算机与其说将影响数学的全部，不如说将影响其中被认为是重要的部分。这就是有限数学部分。

华莱士·吉文斯（1966）

微积分是人类智力的伟大成就之一。仅以此为理由，任何受过教育的人就不应该没有一些微积分的知识。如果你再考察一下以微积分为基础的经典分析在理论上和实践上的全部辉煌战果，你对长期以来微积分成为所有大学数学课程的基础也就毫不奇怪了。但是，读者可能会感到意外，因为本文的目的是要辩明：微积分在大学数学课程中的地位该改变了，而且在一定程度上该衰落了。

如果你相信——就像我相信那样——数学研究同任何其他形式的智力活动一样需要高度的创造力和想象力，那么就该相信数学家——无论如何他们是优秀的人才——在努力从事本专业研究工作的时候一定是最不保守的人。这里我用的“保守”一词是指在思想方法上因循守旧。确实，在研究上获得成功的数学家必定是激进派，他们随时准备接受——或者至少考虑——最不正统的新思想。但是数学家不仅在他们的专业研究活动中是激进派，而且有许多还是教育上的激进派，至少在他们对中小学教育的看法上是如此。这里我并不想讨论所谓“新数学”，但无论你是什么看法，“新数学”的思想还是激进的。（有些人会说是“反动的”，但这不过又一次证明了政治上的事情实在是些循环论证。）然而，搞研究工作的数学家在他们自己的地盘上，即在讲授大专学校的数学课程时，竟成了最保守的人，无论怎么说，这是多么奇怪的事。

如果不怕说得过分简单的话，可以说本世纪中大学数学基本课程的唯一重要变化是：第二次世界大战结束前一向是标准的大学一年级数学课程主要内容的大学代数和三角已下放为高中课程，而代之以两学年的微积分和解析几何；后来又代之以微积分和线性代数。第二次世界大战前，大学里学数学的学生通常要到±年级才接触到微积分。六十年代曾经有过一些短命的试验，其中著名的是在达特茅斯进行的。试验的内容是在大学头两个学年内开设一学期的“有限数学”课，但是几乎在所有的试验中，这门课程现在已被线性代数所代替。近来，大学代数和三角正在大学数学课程中恢复，因为大学一年级新生的数学预备知识水平似乎在下降。但是这些变化并不影响一个基本的结论：本世纪以来大学头两年的数学课程几乎没有什么变化。

我并不是要辩明事情本来完全不应该是这样。在小学、中学或大学低年级水平上，任何学科的教材的讲述是很不应该发生突然的改变或间断的。科学知识上的根本性变化是罕见的，而这种变化导致在基本教育水平上发生相应变化的情况则更加罕见。再者，我们还几乎不了解区别教育方法好坏的标准，也几乎没有能来有效地衡量我们的教育工作，因此我们总是抱着极大的怀疑态度去看待突然的改变，而且只是在最不得已的情况下才去实现这种改变，而且只是在最不得已的情况下才去实现这种改变。

然而，我还是提出有必要进行这样一次变革。它的原因呢？过去三十年中数字电子计算机的发明和发展，这大概是自从印刷术发明以来科学技术上最重要的发展了。无论如何，电子计算机的发展不仅将给人类生活和社会结构带来深刻的影响，而且也将——这是问题的关键——给科学家所研究的问题，特别是他们所用到的数学，带来极其重要的影响。（我要在这里强调一下，以上所说的并不表示微积分和经典分析不会继续取得很多成果了；而只是表示，它们在数学及其应用上的统治地位即将受到挑战。）

什么是——或什么应该是——这次变革的内容呢？这就是离散分析和经典的连续分析在课程设置上的某种（至少）平等。这里所谓离散分析，是指那些主要地或完全地着重研究离散对象的数学分支，包括组合数学、图论、抽象代数、线性代数、数论和离散概率。这种平等至少应该体现在：提供一套以离散数学为基础的大学一二年级课程，作为除了一套标准的微积分课程外另一可供选择的教学方案。（不管怎样，对数学专业的学生来说，这样的两年课程学完后，标准的三年级课程将是微积分。）

促使我提出这个建议的根本原因是：对于许多直接同电子计算机打交道的人——至少包括几乎所有的计算机科学家以及社会科学家、行为科学家和管理科学家——来说，最重要的数学往往不是微积分，而是离散数学的领域。然而除此之外，我还相信数学研究本身朝着离散数学方向发展的趋势正在猛烈地增长。如果考察一下数学论著的出版方面的动向，就可以使上述看法得到支持，尽管显然不能说使它得到证明，但是，除了任何经验上的根据外，这个观点还得到下述事实的支持：在相当程度上，数学的源泉总是在于数学的应用。今天，比起科学技术的任何其他领域来，更大量地引起对于数学应用的需要——而且这种需要正以快得多的速率增长着——的，一般地是电子计算机这一领域，特别是计算机科学家们 · 既然计算机和计算机科学家提出的数学问题绝大多数需要离散数学工具而不是连续数学工具，那么离散数学的研究正在迅速兴起也就不足为奇了。在下文中我将试图对离散数学在与计算机有关的数学中地位如此重要的原因提出一些见解。

首先，让我指出一个应该注重离散数学的理由，但这个理由至少在目前还不太重要。尽管用经典分析来做模型的物理对象事实上是离散系统，经典分析还是取得了惊人的成功。例如，一个物体的运动实际上是它的单个离散分子的运动的总体。然而这些分子的数目是如此之大，以致我们只有把它们当作一个总体来考虑才有可能获得有意义的结果。当然，这样所作的近似是很接近现实的，因此所得结果一般地确实非常精确。说来有点可笑的是，要在电子计算机上用经典分析的公式进行实际计算，只有先把这些公式离散化。例如，用差分代替导数，用和式代替积分。（然而，这样离散化的结果所得到的模型比真的一个一个地考虑分子时所得模型不详细得多。）因此，我们处于这样一种境地：本质上是离散的现象用连续函数来做模型，然后为了计算的目的，又必须把这些连续函数离散化。

如果一开始就直接用离散方法来处理离散问题，不是更有意义吗？目前仅在理论上是如此。这'样做所需的巨大计算量仍大大超过现有的最大电子计算机的能力。但是事情可能不会总是这样，因为微处理机的出现刺激了大型的电子计算机网络的发展。一旦这种计算成为可能，它们可以提供物理现实与计算实践之间的联系，而这种联系将对有关的物理原理的解释和运用极有帮助。但这个时代尚未到来，因为物理现实的分析目前还不能使人把它作为非接受不可的理由去强调离散分析的重要性。

算法

在离散分析的应用中，我希望特别注意的是用它来分析算法，即有明确定义的计算一些数量或符号的过程。因为几乎所有的计算机程序都是算法的执行，所以能够回答下面两个基本问题是极重要的：

1. 一个过程是不是一个算法？就是说，它能否成功地计算出所期望的结果，或者在最坏的情况下，能否给出一个说明它不能解决这个问题的表示？

2. 一个特定的算法的有效性（即效率）如何？（或者是绝对的有效性，或者是相对于解决同一问题的其他可能算法的有效性。）

算法分析的主要内容就是寻求这两个问题的解答。

为了说明算法分析中包含哪些问题和哪些数学内容，让我们考虑一个特殊的问题（这个问题本身并没有多大本质上的重要性）。巴尔的摩· 希尔顿客栈的各个房间没有配置普通的锁，而是配置了拨入一个四位数字组合的拨号盘。只要在拨入的任何数字序列中出现预定的四位数字组合，锁就被打开。假定有一个窃贼想进入某个特定的房间，但是他一点儿也不知道这个组合，他自然希望尽可能少拨一些数字。虽然可能需要拨多达40000个数字（因为有10⁴个可能的组合，而每个组合有4个数字），但是适当的策划可以允许少拨一些数字。这是因为：举例来说，拨了abed后接着拨e就有效地试验了bcde这个组合。巴尔的摩 · 希尔顿问题就是要决定为了检验所有可能的组合而必须拨入的数字的最少个数，并且要寻求一个有效的算法来产生一个具有这最少个数的数字序列。（熟悉图论的读者将会知道这个问题正是德布鲁因（de Bruijn）圈问题的另一种陈述。）

[我们顺便指出关于锁的不适当的名称。用数学术语来说，我们所寻求的是一个产生所有排列而不是所有组合的方法。通常称为组合锁（即号码锁——译者注）的那种锁事擎上应该称为排列锁。]

就像数学家惯于做的那样，我们首先把这个问题一般化。让我们假定有m个不同的符号（在巴尔的摩· 希尔顿问题中，m=10），同时假定我们想要做出一个最短符号串，其中包含所有n（在上例中n=4）个符号的组合——即排列。这个符号串的长度的一个下界是mⁿ＋n－1因为共有mⁿ个可能的组合，第一个组合可以由一个长度为n的符号串形成、以后每加一个符号至多只能形成其余mⁿ－1个组合中的一个。

这个下界是能够达到的呢，还是具有最短长度的序列一定会包含一些长度为n的序列的重复呢？作为离散数学主要分支的图论中的一个著名定理对此给出了回答。这个定理表明，所有的重复都可避免，因此我们所寻求的最短长度正是这个下界。

为了说明这点，我们来考察一个有m^n-1个结点的图，每个结点用我们那m个符号的m^n-1个长度为n－1的组合（即排列）之一作标记。图1是这样一个图的一部分，图中我们已假设我们那m个符号就是数字0，1，…，m－1，从标记为m₁m₂…m_n－1的结点有m条边出发，分别到达标记为m₂m₃…m_n－1i（i=0，1，…，m－1）的结点；每条边都标上相应的i。另外，又有m条标记为m_n－1的边分别从标记为im₁m₂…m_n－2（i=0，1，…，n－1）的结点出发到达这个结点。

我们的分析所需要的定理说：如果在一个如图1所示的图（用专业术语来说，一个连通的有向图）的每个结点上，出发的边的数目与到达的边的数目相同，那么从这个图的任何结点出发，有一条经过每条边一次且仅经过一次的道路（用专业术语来说，有一条欧拉道路）。（这只不过是一种流行的儿童游戏的形式解答，这种游戏要求描出一个几何图形，但不许铅笔离纸，也不许经过同一线段两次。）在图1所示的图中，每个结点都有m条边进入、m条边离去，而且这个图是连通的，所以从它的任何结点出发，必有一条欧拉道路。

现在假定我们从数串m₁m₂…m_n－1开始，即从具有这个标记的结点出发，沿着一条欧拉道路走遍整个图。每经过一条边，我们就把这条边的标记加入我们的数串。（例如，当从结点m₁m₂…m_n－1走到结点m₂m₃…m_n－1i时，我们就把i加在数串后面。）随着每条边被经过，数串的最后n个符号就构成我们的组合之一，而且，由于结点与边的标记方式，没有一个组合能出现一次以上。因为有mⁿ条边（共有m^n-1个结点，从每个结点有m条边出发），所以当我们走完我们的欧拉道路时，我们的数串将正好有mⁿ＋n－1个符号，同时这个数串无重复地包含mⁿ个长度为n的排列（即锁组合）。

利用这个关于长度为mⁿ＋n－1的数串的存在性的证明，我们能提出一个算法来产生这个数串：

1. 从n个0组成的数串开始。（这相当于从标记为n－1个零的结点出发，经过标记为0的边，这条边是一个环，它把你立即带回你出发的那个结点。）

2. 每经过一步，给数串加上一个非零的数，如果这样不会给出一个已经产生的排列的话；否则，就加上一个0。

这个过程一直要到你第m＋1次返回起点时才能终止，而这只有当所有的边都被经过后才会发生。这一结论的证明，虽然不是十分平凡，但也不是太困难。（一条欧拉道路知果在它的起点处终止，则称为欧拉圈。）

这就是这个问题的结束吗？或许是的，数学家就是这样认为的。我们已经证明了解的存在性，并且给出了一种构造这个解的方法。但是计算机科学家还不满足，他想要知道这个算法能否在电子计算机上有效地执行。最大的问题是在步骤2上。在这一步骤中，每一个待选的符号必须经受一种范围很大的“重复检验”，以保证加上它不会重复产生一个前已产生的组合、对于m=10、n=4的巴尔的摩 ·希尔顿问题来说，就需要能存储10，000个字的存储器来存储这10，000个可能的组合，以便每当一个组合出现在序列之中时就能以某种方式把它记下。而且，每当我们想加上一个符号时，我们对能需要在这张有10，000个值的表中查询达九次，直至我们找到一个尚未出现过的序列为止。一般说来，这张表将会有mⁿ个字长，而每次查表数将达m－1次。

改进这种空间效率（或者用更常见的名称空间复杂性）的一种可能的方法是：存储一个包含10，000个二进制数位的序列来代替字。如果相应的序列尚未出现，就记为0；如果出现过了，就记为1。但是这将以时间复杂性为代价，因为在一张二进制数位表中查找一些东西的效率典型地比在一张字表中搜寻信息的效率低得多。

我们所要的是一种构造性的算法，这种算法使我们能够直接把一个符号加在序列之后，而不需要在一张表上搜寻。这样的算法确实存在，但它们都很复杂，所以我们在这里只概述其中一种。

1. 从单个的数字m－1开始。

2. 然后，接上m－1个长度为n的数串。第一个是(m－1)(m－1)…(m－1)(m－2)，以后每一个数串除最后一个符号每次减少1外，其余符号都相同。（在巴尔的摩－希尔顿问题中，步骤2结束后，我们将有9 9998 9997 9996…9990。）

3. 接着，接上(m－1)²个长度为n的数串。第—个是(m－1)…(m－1) (m－2) (m－2)，以后每一个数串都有n－2个(m－1)，而末尾两个符号选自0，1，…，m－2，它们组成的二位数恰好小于前一个数串中相应的二位数。（在巴尔的摩－希尔顿问题中，这就产生9988 9987…9980 9978...9970…9900。）

4. 现在，由于随之而来的复杂性，我们不得不说得含糊些。我们继续接上一些长度为n的数串。在每一步，我们有规则地引入逐步减少的并放在不同位置上的m－1。但是，每个长度为n的数串确实都以明确定义的方式决定于它的前一个数串。

5. 最后，我们接上在m－1和n的情况下的相应数串，这个数串是我们以m－1代替了m来运用步骤1至4而形成；然后我们以m－2代替了m－1来运用这一步骤，如此一直下去。由于在m=1而n为任何正整数的情况下形成的数串只是n个零，所以在步骤1至4运用了m－1次以后，这个过程就结束。

关于这个算法有几件事情值得提出。首先，既然每个长度为n的数串都以明确定义的方式决定于它的前一个数串，这个算法就不需要一个存储器来判别哪些数串是先前已经产生的。而且因为一个数串由同它相邻的数串产生的规则十分简单，所以这个算法无论从时间复杂性还是从空间复杂性的观点来看都是同样有效的。

步骤2至4：包含一个迭代过程（即一个接一个地产生数串），这是离散数学和算法学中许多问题的特征。步骤5包含一个递归，这是关于一个特殊参数（m）的问题的一种求解方法，这个参数依赖于它的顺次减小的值（m－1，m－2，…，1）。递归对离散数学家和计算机科学家都是最有力的工具之一。

最后，尽管在我们关于这个算法的讨论中没有显示出来，但是事实证明，这个算法的细节在n为素数时比n不为素数时简单得多，这或许是十分令人惊奇的。

总而言之，这个问题连同与它相联系的算法，典型地说明了算法分析所包含的内容，以及离散数学各领域（图论、组合数学甚至数论）与算法分析和设计之间的相互作用。然而，一个例子并不说明一种情况。但我相信：与算法设计和分析有关的问题的范围是如此之广，重要性正在增长得如此之快，而且这种重要性将持续如此之久，以致离散数学的研究将飞速发展以提供为算法学所需要的结果和技巧。因此，我还是回到本文开始时提出的观点：让离散数学在大学数学课程中至少与经典分析平分秋色，这在今天即使不是为时过晚，也应该是当务之急了。

[Mathematics Tomorrow，1981年213~220页]

_______________________

*安东运·罗尔斯顿是美国布法罗纽约卅立大学计算机科学系教授，并于1967~1980年任该系主任。他在马萨诸塞理工学院受到了成为数学家所必需的教育，并分别于1952年和1956年获理学士和哲学博士学位。他曾指导布法罗纽约卅立大学（1972~1970）和史蒂文斯理工学院（I960~1965）的主要计算中心。1972~1974年任计算机械协会主席，1975~1976年任美国信息处理学会联合会主席。他撰写和主编了八本关于数学和计算机科学各方面专题的著作。——原注。