组合数学在计算机中的应用.docx

Revised as of 23 November 2020 目录 TOC \o 1-5 \h \z 要 -.1 .组合数学概 述 .组合数学在生活中的应 用 .组合数学与计算机软 件 信息时代的组合数 学 组合数学在计算机软件的应 用 组合数学与计算机软件的关系 组合数学在国外软件业的发展状 况 Ramsey数在计算机科学中的应 用 Ramsey定理和Ramsey数 信息检 索 参考文 组合数学在计算机中的应用 摘要:介绍了组合数学的概念、起源与研究的主要内容，分析了组合数学的特点以及其 在生活中的应用、阐述了组合数学与计算机软件的联系、并着重通过两个例子说明了 Ramsey数在计算机科学的信息检索中的重要应用。 关键词：组合数学:组合算法:Ramsey数:信息检索； 1 :组合数学概述 组合数学，又称为离散数学，但有时人们也把组合数学和图论加在一起算成是离 散数学。组合数学是计算机岀现以后迅速发展起来的一门数学分支。计算机科学就是 算法的科学，而计算机所处理的对象是离散的数据，所以离散对象的处理就成了计算 机科学的核心，而研究离散对象的科学恰恰就是组合数学。组合数学的发展改变了传 统数学中分析和代数占统治地位的局面。现代数学可以分为两大类：一类是研究连续 对象的，如分析、方程等，另一类就是研究离散对象的组合数学。组合数学不仅在基 础数学研究中具有极其重要的地位，在其它的学科中也有重要的应用，如计算机科 学、编码和密码学、物理、化学、生物等学科中均有重要应用。微积分和近代数学的 发展为近代的工业革命奠定了基础。而组合数学的发展则是奠定了本世纪的计算机革 命的基础。计算机之所以可以被称为电脑，就是因为计算机被人编写了程序，而程序 就是算法，在绝大多数情况下，计算机的算法是针对离散的对象，而不是在作数值计 算 正是因为有了组合算法才使人感到，计算机好象是有思维的。 2：组合数学在生活中的应用 在曰常生活中我们常常遇到组合数学的问题。如果你仔细留心一张世界地图.你 会发现用一种颜色对一个国家着色，那么一共只需要四种颜色就能保证每两个相邻的 国家的颜色不同。这样的着色效果能使每一个国家都能清楚地显示出来。但要证明这 个结论确是一个着名的世界难题’最终借助计算机才得以解决，最近人们才发现了一 个更简单的证明。 当你装一个箱子时，你会发现要使箱子尽可能装满不是一件很容易的事，你往往 需要做些调整。从理论上讲，装箱问题是一个很难的组合数学问题.即使用计算机也 是不容易解决的。航空调度和航班的设定也是组合数学的问题。怎样确定各个航班以 满足不同旅客转机的需要,同时也使得每个机场的航班起落分布合理.此外，在一些 航班有延误等特殊情况下，怎样作最合理的调整，这些都是组合数学的问题。 组合数学在企业管理,交通规划’战争指挥，金融分析等领域都有重要的应用’ 在美国有一家用组合数学命名的公司，他们用组合数学的方法来提高企业管理的效 益，这家公司办得非常成功。此外，试验设计也是具有很大应用价值的学科，它的数 学原理就是组合设计。用组合设计的方法解决工业界中的试验设计问题，在美国已有 专门的公司开发这方面的软件。最近，德国一位着名组合数学家利用组合数学方法研 究药物结构，为制药公司节省了大量的费用，引起了制药业的关注。 总之，组合数学无处不在，它的主要应用就是在各种复杂关系中找出最优的方 案 所以组合数学完全可以看成是一门量化的关系学，一门量化了的运筹学，一门量 化了的管理学。 3:组合数学与计算机软件 随着计算机网络的发展’计算机的使用已经影响到了人们的工作，生活，学习， 社会活动以及商业活动，而计算机的应用根本上是通过软件来实现的。 信息时代的组合数学 现代数学可以分为两大类:一类是研究连续对象，如分析、方程等，另一类就是研究 离散对象的组合数学。计算机科学就是算法的科学，而计算机所处理的对象是离散的数 据,研究离散对象的科学恰恰就是组合数学。因此?在信息时代的今天，组合数学就是信 息时代的数学。 组合数学在计算机软件的应用 随着计算机科学的发展,组合数学也在迅猛发展,而组合数学在理论方面的推进也促 进计算机科学的发展。计算机软件空前发展的今天要求有相应的数学基础，组合数学作 为大多数计算机软件设计的理论基础,它的重要性也就不言而喻。 组合数学在计算机方面的应用极其广泛。计算机软件与各种算法的研究分不开，为 了衡量一个算法的效率,必须佔计用此算法解答具有给定於的输入（问题）时需要多少步 （例如算术运算、二进制比较、程序调用等的次数）。这要求对算法所需的计算量及存 储单元数进行估算，这就是计数问题的内容,而组合数学分析主要研究内容就是计数和 枚举的方法和理论。 组合数学与计算机软件的关系 我国在软件上