狠狠撸

狠狠撸Share a Scribd company logo

信息时代的组合数学

?Download as DOC, PDF?
?
wensheng wei
wensheng wei
1 of 4
Download to read offline
信息时代的组合数学 1. 组合数学概述 组 合数学，又称为离散数学，但有时人们也把组合数学和图论加在一起算成是离散数学。组合数学是计算机出现 以后迅速发展起来的一门数学分支。计算机科学就是算 法的科学，而计算机所处理的对象是离散的数据，所以离 散对象的处理就成了计算机科学的核心，而研究离散对象的科学恰恰就是组合数学。组合数学的发展改变了 传统 数学中分析和代数占统治地位的局面。现代数学可以分为两大类：一类是研究连续对象的，如分析、方程等，另 一类就是研究离散对象的组合数学。组合数学不 仅在基础数学研究中具有极其重要的地位，在其它的学科中也有 重要的应用，如计算机科学、编码和密码学、物理、化学、生物等学科中均有重要应用。微积分和近 代数学的发 展为近代的工业革命奠定了基础。而组合数学的发展则是奠定了本世纪的计算机革命的基础。计算机之所以可以 被称为电脑，就是因为计算机被人编写了 程序，而程序就是算法，在绝大多数情况下，计算机的算法是针对离散 的对象，而不是在作数值计算。正是因为有了组合算法才使人感到，计算机好象是有思维的。 组 合数学不仅在软件技术中有重要的应用价值，在公司管理，交通规划，战争指挥，金融分析等领域都有重要的 应用。在美国有一家用组合数学命名的公司，他们用组 合数学的方法来提高公司管理的效益，这家公司办得非常 成功。此外，试验设计也是具有很大应用价值的学科，它的数学原理就是组合设计。用组合设计的方法解决 工业 界中的试验设计问题，在美国已有专门的公司开发这方面的软件。最近，德国一位著名组合数学家利用组合数学 方法研究药物结构，为制药公司节省了大量的费 用，引起了制药业的关注。 在 1997 年 11 月的南开大学组合数学研究中心成立大会上，吴文俊院士指出，每个时代都有它特殊的要求，使得 数学出现一个新的面貌，产生一些新的数学分支，组合数学 这个新的分支也是在时代的要求下产生的。最近，吴 文俊院士又指出，信息技术很可能会给数学本身带来一场根本性的变革，而组合数学则将显示出它的重要作用。 杨乐院士也指出组合数学无论在应用上和理论上都具有越来越重要的位置，它今后的发展是很有生命力，很有前 途的，中国应该倡导这个方面的研究工作。万哲先院 士甚至举例说明了华罗庚，许宝禄，吴文俊等中国老一辈的 数学家不仅重视组合数学，同时还对组合数学中的一些基本问题作了重大贡献。迫于中国组合数学发展自 身的需 要，以及中国信息产业发展的需要，在中国发展组合数学已经迫在眉睫，刻不容缓。 2. 组合数学与计算机软件 随 着计算机网络的发展，计算机的使用已经影响到了人们的工作，生活，学习，社会活动以及商业活动，而计算 机的应用根本上是通过软件来实现的。我在美国听到过 一种说法，将来一个国家的经济实力可以直接从软件产业 反映出来。我国在软件上的落后，要说出根本的原因可能并不是很简单的事，除了技术和科学上的原因外， 可能 还跟我们的文化，管理水平，教育水平，思想素质等诸多因素有关。除去这些人文因素以外，一个最根本的原因 就是我国的信息技术的数学基础十分薄弱，这个 问题不解决，我们就难成为软件强国。然而问题决不是这么简 单，信息技术的发展已经涉及到了很深的数学知识，而数学本身也已经发展到了很深、很广的程度并不 是单凭几 个聪明的头脑去想想就行了，而更重要的是需要集体的合作和力量，就象软件的开发需要多方面的人员的合作。 美国的软件之所以能领先，其关键就在于在 数学基础上他们有很强的实力，有很多杰出的人才。一般人可能会认 为数学是一门纯粹的基础科学，1+1 的解决可能不会有任何实际的意义。如果真 是这样，一门纯粹学科的发展落 后几年，甚至十年，关系也不大。然而中国的软件产业的发展已向数学基础提出了急切的需求：网络算法和分 析，信息压缩，网络安 全，编码技术，系统软件，并行算法，数学机械化和计算机推理，等等。此外，与实际应 用有关的还有许多许多需要数学基础的算法，如运筹规划，金融工程，计算 机辅助设计等。如果我们的软件产业 还是把眼光一直盯在应用软件和第二次开发，那么我们在应用软件这个领域也会让国外的公司抢去很大的市场。 如果我们现在在 信息技术的数学基础上，大力支持和投入，那将是亡羊补牢，犹未为晚；只要我们能抢回信息技 术的数学基地，那么我们还有可能在软件产业的竞争中，扭转局面， 甚至反败为胜。吴文俊院士开创和领导的数 学机械化研究，为中国在信息技术领域占领了一个重要的阵地，有了雄厚的数学基础，自然就有了软件开发的竞 争力。这 样的阵地多几个，我们的软件产业就会产生新的局面。值得注意的是，印度有很好的统计和组合数学基 础，这可能也是印度的软件产业近几年有很大发展的原因。 3. 组合数学在国外的状况 纵观全世界软件产业的情况，易见一个奇特的现象：美国处于绝对的垄断地位。造成这种现象的一个根本的原因 就是计算机科学在美国的飞速发展。当今计算机科学界的最权威人士很多都是研究组合数学出身的。美国最重要 的计算机科学系（MIT，Princeton，Stanford，Harvard，Yale，….） 都有第一流的组合数学家。计算机科学通
过对软件产业的促进，带来了巨大的效益，这已是不争之事实。组合数学在国外早已成为十分重要的学科，甚至 可以说是计 算机科学的基础。一些大公司，如 IBM，AT&T 都有全世界最强的组合研究中心。Microsoft 的 Bill Gates 近来也在提倡和支持计算机科学的基础研究。例如，Bell 实验室的有关线性规划算法的实现，以及有关计 算机网络的算法，由于有明显的商业价值， 显然是没有对外公开的。美国已经有一种趋势，就是与新的算法有关 的软件是可以申请专利的。如果照这种趋势发展，世界各国对组合数学和计算机算法的投入和竞 争必然日趋激 烈。美国政府也成立了离散数学及理论计算机科学中心 DIMACS（与 Princeton 大学，Rutgers 大学，AT&T 联合创 办的，设在 Rutgers 大学），该中心已是组合数学理论计算机科学的重要研究阵地。美国国家数学科学研究所 （Mathematical Sciences Research Institute，由陈省身先生创立）在 1997 年选择了组合数学作为研究专题， 组织了为期一年的研究活动。日本的 NEC 公司还在美国的设立了研究中 心，理论计算机科学和组合数学已是他们 重要的研究课题，该中心主任 R. Tarjan 即是组合数学的权威。我所熟悉的美国重要的国家实际室（Los Alamos 国家实验室，以造出第一颗原子弹著称于世），从曼哈顿计划以来一直重视应用数学的研究，包括组合数学的研 究。我所接触到的有关组合数学的计算 机模拟项目经费达三千万美元。不仅如此，该实验室最近还在积极充实组 合数学方面的研究实力。美国另外一个重要的国家实验室 Sandia 国家实验室有一个专 门研究组合数学和计算机 科学的机构，主要从事组合编码理论和密码学的研究，在美国政府以及国际学术界都具有很高的地位。由于生物 学中的 DNA 的结构和生物 现象与组合数学有密切的联系，各国对生物信息学的研究都很重视，这也是组合数学可 以发挥作用的一个重要领域。前不久召开的北京香山会议就体现了国家对生物 信息学的高度重视。据说 IBM 也将 成立一个生物信息学研究中心。由于 DNA 就是组合数学中的一个序列结构，美国科学院院士，近代组合数学的奠 基人 Rota 教授预言，生物学中的组合问题将成为组合数学的一个前沿领域。 美 国的大学，国家研究机构，工业界，军方和情报部门都有许多组合数学的研究中心，在研究上投入了大量的经 费。但他们得到的收益远远超过了他们的投入，更主要 的是他们还聚集了组合数学领域全世界最优秀的人才。高 层次的软件产物处处用到组合数学，更确切地说就是组合算法。传统的计算机算法可以分为两大类，一类是 组合 算法，一类是数值算法（包括计算数学和与处理各种信息数据有关的信息学）。依我个人的浅见，近年来计算机 算法又多了一类：那就是符号计算算法。吴文俊 院士开创的机器证明方法就属于符号计算，引起了国际上的高度 评价，被称为吴方法。而国际上还有专门的符号计算杂志。符号算法和吴方法跟代数组合学也有十分 密切的联 系。组合数学，数值计算（包括计算数学，科学计算，非线性科学，和与处理各种信息数据有关的信息学）和统 计学可能是应用最广的数学分支，而组合数 学的价值甚至不亚于统计学和数值计算。由于数学机械化近年来的发 展和在计算机科学中的重要性，把数学机械化，科学计算和组合数学组合起来，就可以说是中国 信息产业的基 础。组合数学家 H. Wilf 和 D. Zeilberger1998 因为在组合恒等式的机械化证明方面的成果，获得 1998 年美国数 学会的 Steele 奖。 Gian-Carlo Rota 教授在他去年不幸逝世之前，还专门向我提出，希望我向中国有关部门和领导人呼吁，组合数学 是计算机软件产业的基础，中国最终一定能成为一个软件大 国，但是要实现这个目标的一个突破点就是发展组合 数学。中国在软件技术上远远落后于美国，而在组合数学上则更是落后于美国和欧洲。如果中国只是想在软件技 术上跟着西方走，而不在组合数学上下功夫，那么中国的软件将一直处于落后的状态。他特别强调组合数学在计 算机科学中的作用，以及在大学计算机系加强组合数 学教学和人才培养。 最近 Thomson Science 公司创刊的一份电子刊物《离散数学和理论计算机科学》即是一个很好的说明。它的内容 涉及离散数学和计算机科学的众多方面。由于计算机软件的 促进和需求，组合数学已成为一门既广博又深奥的学 科，需要很深的数学基础，逐渐成为了数学的主流分支。本世纪公认的伟大数学家盖尔芳德预言组合数学和几何 学将是下一世纪数学研究的前沿阵地。这一观点不仅得到国际数学界的赞同，也得到了中国数学界的赞同和响 应。 加拿大在 Montreal 成立了试验数学研究中心，他们的思路可能和吴文俊院士的数学机械化研究中心的发展思路类 似，使数学机械化，算法化，不仅使数学为计算机科学服务，同时也使计算机为数学研究服务。吴文俊院士指 出，中国传统数学中本身就有浓厚的算法思想。 今 后的计算机要向更加智能化的方向发展，其出路仍然是数学的算法，和数学的机械化。另外的一个有说服力的 现象是，组合数学家总是可以在大学的计算机系或者在 计算机公司找到很好的工作，一个优秀的组合数学家自然 就是一个优秀的计算机科学家。相反，美国所有大学计算机系都有组合数学的课程。 除 上述以外，欧洲也在积极发展组合数学，英国、法国、德国、荷兰、丹麦、奥地利、瑞典、意大利、西班牙等 国家都建立了各种形式的组合数学研究中心。近几年， 南美国家也在积极推动组合数学的研究。澳大利亚，新西 兰也组建了很强的组合数学研究机构。值得一提的是亚洲的发达国家也十分重视组合数学的研究。日本有组 合数
学研究中心，并且从美国引进人才，不仅支持日本国内的研究，还出资支持美国的有关课题的研究，这样使日本 的组合数学这几年的发展极为迅速。台湾、香港 两地也从美国引进人才，大力发展组合数学。新加坡，韩国，马 来西亚也在积极推动组合数学的研究和人才培养。台湾的数学研究中心也正在考虑把组合数学作为重 点方向来发 展。世界各地对组合数学的如此钟爱显然是有原因的，那就是没有组合数学就没有计算机科学，没有计算机软 件。 4. 组合数学花絮 ** 在日常生活中我们常常遇到组合数学的问题。如果你仔细留心一张世界地图，你会发现用一种颜色对一个国家 着色，那么一共只需要四种颜色就能保证每两个相邻的 国家的颜色不同。这样的着色效果能使每一个国家都能清 楚地显示出来。但要证明这个结论确是一个著名的世界难题，最终借助计算机才得以解决，最近人们才发现 了一 个更简单的证明。 ** 我国古代的河洛图上记载了三阶幻方，即把从一到九这九个数按三行三列的队行排列，使得每行，每列，以及 两条对角线上的三个数之和都是一十五。组合数学中有许多象幻方这样精巧的结构。1977 年美国旅行者 1 号、2 号 宇宙飞船就带上了幻方以作为人类智慧的信号。 ** 当你装一个箱子时，你会发现要使箱子尽可能装满不是一件很容易的事，你往往需要做些调整。从理论上讲， 装箱问题是一个很难的组合数学问题，即使用计算机也是不容易解决的。 ** 在中小学的数学游戏中，有这样一个问题，一个船夫要把一只狼，一只羊和一棵白菜运过河。问题是当人不在 场时，狼要吃羊，羊要吃白菜，而他的船每趟只能运其中的一个。他怎样才能把三者都运过河呢？这就是一个很 典型、很简单的组合数学问题。 ** 我们还会遇到更复杂的调度和安排问题。例如，在生产原子弹的曼哈顿计划中，涉及到很多工序，许多人员的 安排，很多元件的生产，怎样安排各种人员的工作，以及各种工序间的衔接，从而使整个工期的时间尽可能短？ 这些都是组合数学典型例子。 ** 航空调度和航班的设定也是组合数学的问题。怎样确定各个航班以满足不同旅客转机的需要，同时也使得每个 机场的航班起落分布合理。此外，在一些航班有延误等特殊情况下，怎样作最合理的调整，这些都是 组合数学的 问题。 ** 对于城市的交通管理，交通规划，哪些地方可能是阻塞要地，哪些地方应该设单行道，立交桥建在哪里最合 适，红绿灯怎样设定最合理， 如此等等，全是组合数学的问题。 ** 一个邮递员从邮局出发，要走完他所管辖的街道，他应该怎样选择什么样的路径，这就是著名的"中国邮递员 问题"，由中国组合数学家管梅谷教授提出，著名组合数学家，J. Edmonds 和他的合作者给出了一个解答。 ** 一个通讯网络怎样布局最节省？美国的贝尔实验室和 IBM 公司都有世界一流的组合数学家在研究这个问题，这 个问题直接关系到巨大的经济利益。 ** 据说，假日饭店的管理中，也严格规定了有关的工序，如清洁工的第一步是换什么，清洗什么，第二步又做什 么，总之，他进出房间的次数应该最少。既然，这样一个简单的工作都需要讲究工序，那么一个复杂的工程就更 不用说了。 ** 库房和运输的管理也是典型的组合数学问题。怎样安排运输使得库房充分发挥作用，进一步来说，货物放在什 么地方最便于存取（如存储时间短的应该放在容易存取的地方）。 ** 我们知道，用形状相同的方型砖块可以把一个地面铺满（不考虑边缘的情况），但是如果用不同形状，而又非 方型的砖块来铺一个地面，能否铺满呢？这不仅是一个与实际相关的问题，也涉及到很深的组合数学问题。 ** 组合数学中有一个著名问题：是否存在稳定婚姻的问题。假如能找到两对夫妇（如张（男）--李（女）和赵 （男）--王（女）），如果张（男）更喜欢王 （女），而王（女）也更喜欢张（男），那么这样就可能有潜在的 不稳定性。组合数学的方法可以找到一种婚姻的安排方法，使得没有上述的不稳定情况出现（当然 这只是理论上 的结论）。这种组合数学的方法却有一个实际的用途：美国的医院在确定录取住院医生时，他们将考虑申请者的 志愿的先后次序，同时也给申请排序。 按这样的 次序考虑出的总的方案将没有医院和申请者两者同时后悔的情 况。实际上，高考学生的最后录取方案也可以用这种方法。
** 组合数学还可用于金融分析，投资方案的确定，怎样找出好的投资组合以降低投资风险。南开大学组合数学研 究中心开发出了"金沙股市风险分析系统"现已投放市场，为短线投资者提供了有效的风险防范工具。 总之，组合数学无处不在，它的主要应用就是在各种复杂关系中找出最优的方案。所以组合数学完全可以看成是 一门量化的关系学，一门量化了的运筹学，一门量化了的管理学。 胡锦涛同志在 1998 年接见"五四"青年奖章时发表的讲话中指出，组合数学不同于传统的纯数学的一个分支，它还 是一门应用学科，一门交叉学科。他希望中国的组合数学研究能够为国家的经济建设服务。 如果 21 世纪是信息社会的世纪，那么 21 世纪也必将是组合数学大有可为的世纪。

More Related Content

信息时代的组合数学

  • 1. 信息时代的组合数学 1. 组合数学概述 组 合数学，又称为离散数学，但有时人们也把组合数学和图论加在一起算成是离散数学。组合数学是计算机出现 以后迅速发展起来的一门数学分支。计算机科学就是算 法的科学，而计算机所处理的对象是离散的数据，所以离 散对象的处理就成了计算机科学的核心，而研究离散对象的科学恰恰就是组合数学。组合数学的发展改变了 传统 数学中分析和代数占统治地位的局面。现代数学可以分为两大类：一类是研究连续对象的，如分析、方程等，另 一类就是研究离散对象的组合数学。组合数学不 仅在基础数学研究中具有极其重要的地位，在其它的学科中也有 重要的应用，如计算机科学、编码和密码学、物理、化学、生物等学科中均有重要应用。微积分和近 代数学的发 展为近代的工业革命奠定了基础。而组合数学的发展则是奠定了本世纪的计算机革命的基础。计算机之所以可以 被称为电脑，就是因为计算机被人编写了 程序，而程序就是算法，在绝大多数情况下，计算机的算法是针对离散 的对象，而不是在作数值计算。正是因为有了组合算法才使人感到，计算机好象是有思维的。 组 合数学不仅在软件技术中有重要的应用价值，在公司管理，交通规划，战争指挥，金融分析等领域都有重要的 应用。在美国有一家用组合数学命名的公司，他们用组 合数学的方法来提高公司管理的效益，这家公司办得非常 成功。此外，试验设计也是具有很大应用价值的学科，它的数学原理就是组合设计。用组合设计的方法解决 工业 界中的试验设计问题，在美国已有专门的公司开发这方面的软件。最近，德国一位著名组合数学家利用组合数学 方法研究药物结构，为制药公司节省了大量的费 用，引起了制药业的关注。 在 1997 年 11 月的南开大学组合数学研究中心成立大会上，吴文俊院士指出，每个时代都有它特殊的要求，使得 数学出现一个新的面貌，产生一些新的数学分支，组合数学 这个新的分支也是在时代的要求下产生的。最近，吴 文俊院士又指出，信息技术很可能会给数学本身带来一场根本性的变革，而组合数学则将显示出它的重要作用。 杨乐院士也指出组合数学无论在应用上和理论上都具有越来越重要的位置，它今后的发展是很有生命力，很有前 途的，中国应该倡导这个方面的研究工作。万哲先院 士甚至举例说明了华罗庚，许宝禄，吴文俊等中国老一辈的 数学家不仅重视组合数学，同时还对组合数学中的一些基本问题作了重大贡献。迫于中国组合数学发展自 身的需 要，以及中国信息产业发展的需要，在中国发展组合数学已经迫在眉睫，刻不容缓。 2. 组合数学与计算机软件 随 着计算机网络的发展，计算机的使用已经影响到了人们的工作，生活，学习，社会活动以及商业活动，而计算 机的应用根本上是通过软件来实现的。我在美国听到过 一种说法，将来一个国家的经济实力可以直接从软件产业 反映出来。我国在软件上的落后，要说出根本的原因可能并不是很简单的事，除了技术和科学上的原因外， 可能 还跟我们的文化，管理水平，教育水平，思想素质等诸多因素有关。除去这些人文因素以外，一个最根本的原因 就是我国的信息技术的数学基础十分薄弱，这个 问题不解决，我们就难成为软件强国。然而问题决不是这么简 单，信息技术的发展已经涉及到了很深的数学知识，而数学本身也已经发展到了很深、很广的程度并不 是单凭几 个聪明的头脑去想想就行了，而更重要的是需要集体的合作和力量，就象软件的开发需要多方面的人员的合作。 美国的软件之所以能领先，其关键就在于在 数学基础上他们有很强的实力，有很多杰出的人才。一般人可能会认 为数学是一门纯粹的基础科学，1+1 的解决可能不会有任何实际的意义。如果真 是这样，一门纯粹学科的发展落 后几年，甚至十年，关系也不大。然而中国的软件产业的发展已向数学基础提出了急切的需求：网络算法和分 析，信息压缩，网络安 全，编码技术，系统软件，并行算法，数学机械化和计算机推理，等等。此外，与实际应 用有关的还有许多许多需要数学基础的算法，如运筹规划，金融工程，计算 机辅助设计等。如果我们的软件产业 还是把眼光一直盯在应用软件和第二次开发，那么我们在应用软件这个领域也会让国外的公司抢去很大的市场。 如果我们现在在 信息技术的数学基础上，大力支持和投入，那将是亡羊补牢，犹未为晚；只要我们能抢回信息技 术的数学基地，那么我们还有可能在软件产业的竞争中，扭转局面， 甚至反败为胜。吴文俊院士开创和领导的数 学机械化研究，为中国在信息技术领域占领了一个重要的阵地，有了雄厚的数学基础，自然就有了软件开发的竞 争力。这 样的阵地多几个，我们的软件产业就会产生新的局面。值得注意的是，印度有很好的统计和组合数学基 础，这可能也是印度的软件产业近几年有很大发展的原因。 3. 组合数学在国外的状况 纵观全世界软件产业的情况，易见一个奇特的现象：美国处于绝对的垄断地位。造成这种现象的一个根本的原因 就是计算机科学在美国的飞速发展。当今计算机科学界的最权威人士很多都是研究组合数学出身的。美国最重要 的计算机科学系（MIT，Princeton，Stanford，Harvard，Yale，….） 都有第一流的组合数学家。计算机科学通
  • 2. 过对软件产业的促进，带来了巨大的效益，这已是不争之事实。组合数学在国外早已成为十分重要的学科，甚至 可以说是计 算机科学的基础。一些大公司，如 IBM，AT&T 都有全世界最强的组合研究中心。Microsoft 的 Bill Gates 近来也在提倡和支持计算机科学的基础研究。例如，Bell 实验室的有关线性规划算法的实现，以及有关计 算机网络的算法，由于有明显的商业价值， 显然是没有对外公开的。美国已经有一种趋势，就是与新的算法有关 的软件是可以申请专利的。如果照这种趋势发展，世界各国对组合数学和计算机算法的投入和竞 争必然日趋激 烈。美国政府也成立了离散数学及理论计算机科学中心 DIMACS（与 Princeton 大学，Rutgers 大学，AT&T 联合创 办的，设在 Rutgers 大学），该中心已是组合数学理论计算机科学的重要研究阵地。美国国家数学科学研究所 （Mathematical Sciences Research Institute，由陈省身先生创立）在 1997 年选择了组合数学作为研究专题， 组织了为期一年的研究活动。日本的 NEC 公司还在美国的设立了研究中 心，理论计算机科学和组合数学已是他们 重要的研究课题，该中心主任 R. Tarjan 即是组合数学的权威。我所熟悉的美国重要的国家实际室（Los Alamos 国家实验室，以造出第一颗原子弹著称于世），从曼哈顿计划以来一直重视应用数学的研究，包括组合数学的研 究。我所接触到的有关组合数学的计算 机模拟项目经费达三千万美元。不仅如此，该实验室最近还在积极充实组 合数学方面的研究实力。美国另外一个重要的国家实验室 Sandia 国家实验室有一个专 门研究组合数学和计算机 科学的机构，主要从事组合编码理论和密码学的研究，在美国政府以及国际学术界都具有很高的地位。由于生物 学中的 DNA 的结构和生物 现象与组合数学有密切的联系，各国对生物信息学的研究都很重视，这也是组合数学可 以发挥作用的一个重要领域。前不久召开的北京香山会议就体现了国家对生物 信息学的高度重视。据说 IBM 也将 成立一个生物信息学研究中心。由于 DNA 就是组合数学中的一个序列结构，美国科学院院士，近代组合数学的奠 基人 Rota 教授预言，生物学中的组合问题将成为组合数学的一个前沿领域。 美 国的大学，国家研究机构，工业界，军方和情报部门都有许多组合数学的研究中心，在研究上投入了大量的经 费。但他们得到的收益远远超过了他们的投入，更主要 的是他们还聚集了组合数学领域全世界最优秀的人才。高 层次的软件产物处处用到组合数学，更确切地说就是组合算法。传统的计算机算法可以分为两大类，一类是 组合 算法，一类是数值算法（包括计算数学和与处理各种信息数据有关的信息学）。依我个人的浅见，近年来计算机 算法又多了一类：那就是符号计算算法。吴文俊 院士开创的机器证明方法就属于符号计算，引起了国际上的高度 评价，被称为吴方法。而国际上还有专门的符号计算杂志。符号算法和吴方法跟代数组合学也有十分 密切的联 系。组合数学，数值计算（包括计算数学，科学计算，非线性科学，和与处理各种信息数据有关的信息学）和统 计学可能是应用最广的数学分支，而组合数 学的价值甚至不亚于统计学和数值计算。由于数学机械化近年来的发 展和在计算机科学中的重要性，把数学机械化，科学计算和组合数学组合起来，就可以说是中国 信息产业的基 础。组合数学家 H. Wilf 和 D. Zeilberger1998 因为在组合恒等式的机械化证明方面的成果，获得 1998 年美国数 学会的 Steele 奖。 Gian-Carlo Rota 教授在他去年不幸逝世之前，还专门向我提出，希望我向中国有关部门和领导人呼吁，组合数学 是计算机软件产业的基础，中国最终一定能成为一个软件大 国，但是要实现这个目标的一个突破点就是发展组合 数学。中国在软件技术上远远落后于美国，而在组合数学上则更是落后于美国和欧洲。如果中国只是想在软件技 术上跟着西方走，而不在组合数学上下功夫，那么中国的软件将一直处于落后的状态。他特别强调组合数学在计 算机科学中的作用，以及在大学计算机系加强组合数 学教学和人才培养。 最近 Thomson Science 公司创刊的一份电子刊物《离散数学和理论计算机科学》即是一个很好的说明。它的内容 涉及离散数学和计算机科学的众多方面。由于计算机软件的 促进和需求，组合数学已成为一门既广博又深奥的学 科，需要很深的数学基础，逐渐成为了数学的主流分支。本世纪公认的伟大数学家盖尔芳德预言组合数学和几何 学将是下一世纪数学研究的前沿阵地。这一观点不仅得到国际数学界的赞同，也得到了中国数学界的赞同和响 应。 加拿大在 Montreal 成立了试验数学研究中心，他们的思路可能和吴文俊院士的数学机械化研究中心的发展思路类 似，使数学机械化，算法化，不仅使数学为计算机科学服务，同时也使计算机为数学研究服务。吴文俊院士指 出，中国传统数学中本身就有浓厚的算法思想。 今 后的计算机要向更加智能化的方向发展，其出路仍然是数学的算法，和数学的机械化。另外的一个有说服力的 现象是，组合数学家总是可以在大学的计算机系或者在 计算机公司找到很好的工作，一个优秀的组合数学家自然 就是一个优秀的计算机科学家。相反，美国所有大学计算机系都有组合数学的课程。 除 上述以外，欧洲也在积极发展组合数学，英国、法国、德国、荷兰、丹麦、奥地利、瑞典、意大利、西班牙等 国家都建立了各种形式的组合数学研究中心。近几年， 南美国家也在积极推动组合数学的研究。澳大利亚，新西 兰也组建了很强的组合数学研究机构。值得一提的是亚洲的发达国家也十分重视组合数学的研究。日本有组 合数
  • 3. 学研究中心，并且从美国引进人才，不仅支持日本国内的研究，还出资支持美国的有关课题的研究，这样使日本 的组合数学这几年的发展极为迅速。台湾、香港 两地也从美国引进人才，大力发展组合数学。新加坡，韩国，马 来西亚也在积极推动组合数学的研究和人才培养。台湾的数学研究中心也正在考虑把组合数学作为重 点方向来发 展。世界各地对组合数学的如此钟爱显然是有原因的，那就是没有组合数学就没有计算机科学，没有计算机软 件。 4. 组合数学花絮 ** 在日常生活中我们常常遇到组合数学的问题。如果你仔细留心一张世界地图，你会发现用一种颜色对一个国家 着色，那么一共只需要四种颜色就能保证每两个相邻的 国家的颜色不同。这样的着色效果能使每一个国家都能清 楚地显示出来。但要证明这个结论确是一个著名的世界难题，最终借助计算机才得以解决，最近人们才发现 了一 个更简单的证明。 ** 我国古代的河洛图上记载了三阶幻方，即把从一到九这九个数按三行三列的队行排列，使得每行，每列，以及 两条对角线上的三个数之和都是一十五。组合数学中有许多象幻方这样精巧的结构。1977 年美国旅行者 1 号、2 号 宇宙飞船就带上了幻方以作为人类智慧的信号。 ** 当你装一个箱子时，你会发现要使箱子尽可能装满不是一件很容易的事，你往往需要做些调整。从理论上讲， 装箱问题是一个很难的组合数学问题，即使用计算机也是不容易解决的。 ** 在中小学的数学游戏中，有这样一个问题，一个船夫要把一只狼，一只羊和一棵白菜运过河。问题是当人不在 场时，狼要吃羊，羊要吃白菜，而他的船每趟只能运其中的一个。他怎样才能把三者都运过河呢？这就是一个很 典型、很简单的组合数学问题。 ** 我们还会遇到更复杂的调度和安排问题。例如，在生产原子弹的曼哈顿计划中，涉及到很多工序，许多人员的 安排，很多元件的生产，怎样安排各种人员的工作，以及各种工序间的衔接，从而使整个工期的时间尽可能短？ 这些都是组合数学典型例子。 ** 航空调度和航班的设定也是组合数学的问题。怎样确定各个航班以满足不同旅客转机的需要，同时也使得每个 机场的航班起落分布合理。此外，在一些航班有延误等特殊情况下，怎样作最合理的调整，这些都是 组合数学的 问题。 ** 对于城市的交通管理，交通规划，哪些地方可能是阻塞要地，哪些地方应该设单行道，立交桥建在哪里最合 适，红绿灯怎样设定最合理， 如此等等，全是组合数学的问题。 ** 一个邮递员从邮局出发，要走完他所管辖的街道，他应该怎样选择什么样的路径，这就是著名的"中国邮递员 问题"，由中国组合数学家管梅谷教授提出，著名组合数学家，J. Edmonds 和他的合作者给出了一个解答。 ** 一个通讯网络怎样布局最节省？美国的贝尔实验室和 IBM 公司都有世界一流的组合数学家在研究这个问题，这 个问题直接关系到巨大的经济利益。 ** 据说，假日饭店的管理中，也严格规定了有关的工序，如清洁工的第一步是换什么，清洗什么，第二步又做什 么，总之，他进出房间的次数应该最少。既然，这样一个简单的工作都需要讲究工序，那么一个复杂的工程就更 不用说了。 ** 库房和运输的管理也是典型的组合数学问题。怎样安排运输使得库房充分发挥作用，进一步来说，货物放在什 么地方最便于存取（如存储时间短的应该放在容易存取的地方）。 ** 我们知道，用形状相同的方型砖块可以把一个地面铺满（不考虑边缘的情况），但是如果用不同形状，而又非 方型的砖块来铺一个地面，能否铺满呢？这不仅是一个与实际相关的问题，也涉及到很深的组合数学问题。 ** 组合数学中有一个著名问题：是否存在稳定婚姻的问题。假如能找到两对夫妇（如张（男）--李（女）和赵 （男）--王（女）），如果张（男）更喜欢王 （女），而王（女）也更喜欢张（男），那么这样就可能有潜在的 不稳定性。组合数学的方法可以找到一种婚姻的安排方法，使得没有上述的不稳定情况出现（当然 这只是理论上 的结论）。这种组合数学的方法却有一个实际的用途：美国的医院在确定录取住院医生时，他们将考虑申请者的 志愿的先后次序，同时也给申请排序。 按这样的 次序考虑出的总的方案将没有医院和申请者两者同时后悔的情 况。实际上，高考学生的最后录取方案也可以用这种方法。
  • 4. ** 组合数学还可用于金融分析，投资方案的确定，怎样找出好的投资组合以降低投资风险。南开大学组合数学研 究中心开发出了"金沙股市风险分析系统"现已投放市场，为短线投资者提供了有效的风险防范工具。 总之，组合数学无处不在，它的主要应用就是在各种复杂关系中找出最优的方案。所以组合数学完全可以看成是 一门量化的关系学，一门量化了的运筹学，一门量化了的管理学。 胡锦涛同志在 1998 年接见"五四"青年奖章时发表的讲话中指出，组合数学不同于传统的纯数学的一个分支，它还 是一门应用学科，一门交叉学科。他希望中国的组合数学研究能够为国家的经济建设服务。 如果 21 世纪是信息社会的世纪，那么 21 世纪也必将是组合数学大有可为的世纪。