信息时代的组合数学

《信息时代的组合数学》由会员分享，可在线阅读，更多相关《信息时代的组合数学（23页珍藏版）》请在金锄头文库上搜索。

1、信息时代的组合数学信息时代的组合数学南开大学组合数学研究中心 陈永川1. 组合数学概述组合数学，又称为离散数学，但有时人们也把组合数学和图论加在一起算成是离散数学。组合数学是计算机出现以后迅速发展起来的一门数学分支。计算机科学就是算法的科学，而计算机所处理的对象是离散的数据，所以离散对象的处理就成了计算机科学的核心，而研究离散对象的科学恰恰就是组合数学。组合数学的发展改变了传统数学中分析和代数占统治地位的局面。现代数学可以分为两大类：一类是研究连续对象的，如分析、方程等，另一类就是研究离散对象的组合数学。组合数学不仅在基础数学研究中具有极其重要的地位，在其它的学科中也有重要的应用，如计算机科学

2、、编码和密码学、物理、化学、生物等学科中均有重要应用。微积分和近代数学的发展为近代的工业革命奠定了基础。而组合数学的发展则是奠定了本世纪的计算机革命的基础。计算机之所以可以被称为电脑，就是因为计算机被人编写了程序，而程序就是算法，在绝大多数情况下，计算机的算法是针对离散的对象，而不是在作数值计算。正是因为有了组合算法才使人感到，计算机好象是有思维的。组合数学不仅在软件技术中有重要的应用价值，在企业管理，交通规划，战争指挥，金融分析等领域都有重要的应用。在美国有一家用组合数学命名的公司，他们用组合数学的方法来提高企业管理的效益，这家公司办得非常成功。此外，试验设计也是具有很大应用价值的学科，它的

3、数学原理就是组合设计。用组合设计的方法解决工业界中的试验设计问题，在美国已有专门的公司开发这方面的软件。最近，德国一位著名组合数学家利用组合数学方法研究药物结构，为制药公司节省了大量的费用，引起了制药业的关注。在 1997 年 11 月的南开大学组合数学研究中心成立大会上，吴文俊院士指出，每个时代都有它特殊的要求，使得数学出现一个新的面貌，产生一些新的数学分支，组合数学这个新的分支也是在时代的要求下产生的。最近，吴文俊院士又指出，信息技术很可能会给数学本身带来一场根本性的变革，而组合数学则将显示出它的重要作用。杨乐院士也指出组合数学无论在应用上和理论上都具有越来越重要的位置，它今后的发展是很有

4、生命力，很有前途的，中国应该倡导这个方面的研究工作。万哲先院士甚至举例说明了华罗庚，许宝禄，吴文俊等中国老一辈的数学家不仅重视组合数学，同时还对组合数学中的一些基本问题作了重大贡献。迫于中国组合数学发展自身的需要，以及中国信息产业发展的需要，在中国发展组合数学已经迫在眉睫，刻不容缓。2. 组合数学与计算机软件随着计算机网络的发展，计算机的使用已经影响到了人们的工作，生活，学习，社会活动以及商业活动，而计算机的应用根本上是通过软件来实现的。我在美国听到过一种说法，将来一个国家的经济实力可以直接从软件产业反映出来。我国在软件上的落后，要说出根本的原因可能并不是很简单的事，除了技术和科学上的原因外，

5、可能还跟我们的文化，管理水平，教育水平，思想素质等诸多因素有关。除去这些人文因素以外，一个最根本的原因就是我国的信息技术的数学基础十分薄弱，这个问题不解决，我们就难成为软件强国。然而问题决不是这么简单，信息技术的发展已经涉及到了很深的数学知识，而数学本身也已经发展到了很深、很广的程度并不是单凭几个聪明的头脑去想想就行了，而更重要的是需要集体的合作和力量，就象软件的开发需要多方面的人员的合作。美国的软件之所以能领先，其关键就在于在数学基础上他们有很强的实力，有很多杰出的人才。一般人可能会认为数学是一门纯粹的基础科学，1+1 的解决可能不会有任何实际的意义。如果真是这样，一门纯粹学科的发展落后几年

6、，甚至十年，关系也不大。然而中国的软件产业的发展已向数学基础提出了急切的需求：网络算法和分析，信息压缩，网络安全，编码技术，系统软件，并行算法，数学机械化和计算机推理，等等。此外，与实际应用有关的还有许多许多需要数学基础的算法，如运筹规划，金融工程，计算机辅助设计等。如果我们的软件产业还是把眼光一直盯在应用软件和第二次开发，那么我们在应用软件这个领域也会让国外的企业抢去很大的市场。如果我们现在在信息技术的数学基础上，大力支持和投入，那将是亡羊补牢，犹未为晚；只要我们能抢回信息技术的数学基地，那么我们还有可能在软件产业的竞争中，扭转局面，甚至反败为胜。吴文俊院士开创和领导的数学机械化研究，为中国

7、在信息技术领域占领了一个重要的阵地，有了雄厚的数学基础，自然就有了软件开发的竞争力。这样的阵地多几个，我们的软件产业就会产生新的局面。值得注意的是，印度有很好的统计和组合数学基础，这可能也是印度的软件产业近几年有很大发展的原因。3. 组合数学在国外的状况纵观全世界软件产业的情况，易见一个奇特的现象：美国处于绝对的垄断地位。造成这种现象的一个根本的原因就是计算机科学在美国的飞速发展。当今计算机科学界的最权威人士很多都是研究组合数学出身的。美国最重要的计算机科学系（MIT，Princeton，Stanford，Harvard，Yale，.）都有第一流的组合数学家。计算机科学通过对软件产业的促进，带

8、来了巨大的效益，这已是不争之事实。组合数学在国外早已成为十分重要的学科，甚至可以说是计算机科学的基础。一些大公司，如 IBM，ATT 都有全世界最强的组合研究中心。Microsoft 的 Bill Gates 近来也在提倡和支持计算机科学的基础研究。例如，Bell 实验室的有关线性规划算法的实现，以及有关计算机网络的算法，由于有明显的商业价值，显然是没有对外公开的。美国已经有一种趋势，就是与新的算法有关的软件是可以申请专利的。如果照这种趋势发展，世界各国对组合数学和计算机算法的投入和竞争必然日趋激烈。美国政府也成立了离散数学及理论计算机科学中心 DIMACS（与 Princeton 大学，Ru

9、tgers 大学，ATT 联合创办的，设在 Rutgers 大学） ，该中心已是组合数学理论计算机科学的重要研究阵地。美国国家数学科学研究所（Mathematical Sciences Research Institute，由陈省身先生创立）在 1997 年选择了组合数学作为研究专题，组织了为期一年的研究活动。日本的 NEC 公司还在美国的设立了研究中心，理论计算机科学和组合数学已是他们重要的研究课题，该中心主任 R. Tarjan即是组合数学的权威。我所熟悉的美国重要的国家实际室（Los Alamos 国家实验室，以造出第一颗原子弹著称于世） ，从曼哈顿计划以来一直重视应用数学的研究，包括组

10、合数学的研究。我所接触到的有关组合数学的计算机模拟项目经费达三千万美元。不仅如此，该实验室最近还在积极充实组合数学方面的研究实力。美国另外一个重要的国家实验室 Sandia 国家实验室有一个专门研究组合数学和计算机科学的机构，主要从事组合编码理论和密码学的研究，在美国政府以及国际学术界都具有很高的地位。由于生物学中的 DNA 的结构和生物现象与组合数学有密切的联系，各国对生物信息学的研究都很重视，这也是组合数学可以发挥作用的一个重要领域。前不久召开的北京香山会议就体现了国家对生物信息学的高度重视。据说 IBM 也将成立一个生物信息学研究中心。由于 DNA 就是组合数学中的一个序列结构，美国科学

11、院院士，近代组合数学的奠基人 Rota 教授预言，生物学中的组合问题将成为组合数学的一个前沿领域。美国的大学，国家研究机构，工业界，军方和情报部门都有许多组合数学的研究中心，在研究上投入了大量的经费。但他们得到的收益远远超过了他们的投入，更主要的是他们还聚集了组合数学领域全世界最优秀的人才。高层次的软件产品处处用到组合数学，更确切地说就是组合算法。传统的计算机算法可以分为两大类，一类是组合算法，一类是数值算法（包括计算数学和与处理各种信息数据有关的信息学） 。依我个人的浅见，近年来计算机算法又多了一类：那就是符号计算算法。吴文俊院士开创的机器证明方法就属于符号计算，引起了国际上的高度评价，被称

12、为吴方法。而国际上还有专门的符号计算杂志。符号算法和吴方法跟代数组合学也有十分密切的联系。组合数学，数值计算（包括计算数学，科学计算，非线性科学，和与处理各种信息数据有关的信息学）和统计学可能是应用最广的数学分支，而组合数学的价值甚至不亚于统计学和数值计算。由于数学机械化近年来的发展和在计算机科学中的重要性，把数学机械化，科学计算和组合数学组合起来，就可以说是中国信息产业的基础。组合数学家 H. Wilf 和 D. Zeilberger1998因为在组合恒等式的机械化证明方面的成果，获得1998 年美国数学会的 Steele 奖。南开大学组合数学研究中心 陈永川1. 组合数学概述组合数学，又称

13、为离散数学，但有时人们也把组合数学和图论加在一起算成是离散数学。组合数学是计算机出现以后迅速发展起来的一门数学分支。计算机科学就是算法的科学，而计算机所处理的对象是离散的数据，所以离散对象的处理就成了计算机科学的核心，而研究离散对象的科学恰恰就是组合数学。组合数学的发展改变了传统数学中分析和代数占统治地位的局面。现代数学可以分为两大类：一类是研究连续对象的，如分析、方程等，另一类就是研究离散对象的组合数学。组合数学不仅在基础数学研究中具有极其重要的地位，在其它的学科中也有重要的应用，如计算机科学、编码和密码学、物理、化学、生物等学科中均有重要应用。微积分和近代数学的发展为近代的工业革命奠定了基

14、础。而组合数学的发展则是奠定了本世纪的计算机革命的基础。计算机之所以可以被称为电脑，就是因为计算机被人编写了程序，而程序就是算法，在绝大多数情况下，计算机的算法是针对离散的对象，而不是在作数值计算。正是因为有了组合算法才使人感到，计算机好象是有思维的。组合数学不仅在软件技术中有重要的应用价值，在企业管理，交通规划，战争指挥，金融分析等领域都有重要的应用。在美国有一家用组合数学命名的公司，他们用组合数学的方法来提高企业管理的效益，这家公司办得非常成功。此外，试验设计也是具有很大应用价值的学科，它的数学原理就是组合设计。用组合设计的方法解决工业界中的试验设计问题，在美国已有专门的公司开发这方面的软

15、件。最近，德国一位著名组合数学家利用组合数学方法研究药物结构，为制药公司节省了大量的费用，引起了制药业的关注。在 1997 年 11 月的南开大学组合数学研究中心成立大会上，吴文俊院士指出，每个时代都有它特殊的要求，使得数学出现一个新的面貌，产生一些新的数学分支，组合数学这个新的分支也是在时代的要求下产生的。最近，吴文俊院士又指出，信息技术很可能会给数学本身带来一场根本性的变革，而组合数学则将显示出它的重要作用。杨乐院士也指出组合数学无论在应用上和理论上都具有越来越重要的位置，它今后的发展是很有生命力，很有前途的，中国应该倡导这个方面的研究工作。万哲先院士甚至举例说明了华罗庚，许宝禄，吴文俊等

16、中国老一辈的数学家不仅重视组合数学，同时还对组合数学中的一些基本问题作了重大贡献。迫于中国组合数学发展自身的需要，以及中国信息产业发展的需要，在中国发展组合数学已经迫在眉睫，刻不容缓。2. 组合数学与计算机软件随着计算机网络的发展，计算机的使用已经影响到了人们的工作，生活，学习，社会活动以及商业活动，而计算机的应用根本上是通过软件来实现的。我在美国听到过一种说法，将来一个国家的经济实力可以直接从软件产业反映出来。我国在软件上的落后，要说出根本的原因可能并不是很简单的事，除了技术和科学上的原因外，可能还跟我们的文化，管理水平，教育水平，思想素质等诸多因素有关。除去这些人文因素以外，一个最根本的原因就是我国的信息技术的数学基础十分薄弱，这个问题不解决，我们就难成为软件强国。然而问题决不是这么简单，信息技术的发展已经涉及到了很深的数学知识，而数学本身也已经发展到了很深、很广的程度并不是单凭几个聪明的头脑去想想就行了，而更重要的是需要集体的合作和力量，就象软件的开发需要多方面的人员的合作。美国的软件之所以能领先，其关键就在于在数学基础上他们有很强的实力，有很多杰出的人才。一般人可能会认为数学