1、文章编号：1671-1742（2006）增-0094-04组合数学在计算机科学中的应用陈家!，杨光崇（成都信息工程学院计算科学系，四川 成都 610225）摘要：介绍了组合数学的概念、起源与研究的主要内容，分析了组合数学的特点，阐述了组合数学与计算机软件的联系，并着重通过两个例子说明了 Ramsey 数在计算机科学的信息检索、分组交换网设计分支中的重要应用。关键词：组合数学；组合算法；Ramsey 数；信息检索；分组交换网中图分类号：O157文献标识码：A!成都信息工程学院计算科学系信息与计算科学专业 2001 级 3 班1组合数学的概念组合数学是近年来随着计算机科学的发展而新兴起来的一门综合
2、性、边缘性学科。组合数学是什么，有很多不同的看法。Richard A.BruaIDi 所著 Introductory Combinatorics 中认为组合数学研究的是事物按照某种规则的安排，主要有：存在性问题，计数性问题和对已知安排的研究。DanieI I.A.Cohen 所著 Basic Technigues of Combi-natoriaI Theory 中这样描述：组合数学就是对给定描述的事物有多少种或者某种事物发生的途径有多少种的研究。综合以上观点，组合数学就是主要研究“事物的安排”中涉及的数学问题。2组合数学研究的主要内容与传统的数学课程相比，组合数学研究的是一些离散的事物之间存
3、在的数学关系，包括存在性问题、计数性问题、构造性问题以及最优化问题等，其主要内容是计数和枚举。计数问题是组合学中研究得最多的内容，它出现在所有的数学分支中。计算机科学需要研究算法，必须对算法所需的运算量和存储单元作出估计，即算法的时间复杂性和空间复杂性分析，其中组合数学的研究主要包括以下内容1-3：排列组合；生成函数和递推关系；容斥原理和鸽巢原理；Burnside 定理与 P Iya 定理；线性规划等等。3组合数学与计算机软件3.1信息时代的组合数学现代数学可以分为两大类：一类是研究连续对象，如分析、方程等，另一类就是研究离散对象的组合数学。计算机科学就是算法的科学，而计算机所处理的对象是离散
4、的数据，研究离散对象的科学恰恰就是组合数学。因此，在信息时代的今天，组合数学就是信息时代的数学。3.2组合数学在计算机软件的应用随着计算机科学的发展，组合数学也在迅猛发展，而组合数学在理论方面的推进也促进计算机科学的发展。计算机软件空前发展的今天要求有相应的数学基础，组合数学作为大多数计算机软件设计的理论基础，它的重要性也就不言而喻。组合数学在计算机方面的应用极其广泛。计算机软件与各种算法的研究分不开，为了衡量一个算法的效率，必须估计用此算法解答具有给定长的输入（问题）时需要多少步（例如算术运算、二进制比较、程序调用等的次数）。这要求对算法所需的计算量及存储单元数进行估算，这就是计数问题的内容
5、，而组合数学分析主要研究内容就是计数和枚举的方法和理论。第 21 卷增刊2006 年 12 月成都信息工程学院学报JOURNAL OF CHENGDU UNIVERSITY OF INFORMATION TECHNOLOGYVoI.21 SuppI.Dec.20063.3组合数学在国外软件业的发展状况纵观全世界软件产业，美国处于绝对的垄断地位。造成这种现象的一个根本原因就是计算机科学在美国的飞速发展。当今计算机科学界的最权威人士很多都是研究组合数学出身的。美国最重要的计算机科学系（MIT，Princeton，Stanford，Harvard，Yale，）都有第一流的组合数学家。组合数学在国外早
6、已成为十分重要的学科，甚至可以说是计算机科学的基础。一些大公司，如 IBM，ATST 都有全世界最强的组合研究中心。美国政府也成立了离散数学及理论计算机科学中心 DIMACS（与 Princeton 大学，Rutgers 大学，ATST 联合创办的，设在 Rutgers 大学），该中心已是组合数学理论计算机科学的重要研究阵地。4Ramsey 数在计算机科学中的应用4.lRamsey 定理和 Ramsey 数众所周知，若有 I+l 只鸽子同时飞进 I 个鸽巢中，则一定有某个鸽巢中至少飞进两只鸽，这就是有名的鸽巢原理（也叫抽屉原理）。它非常简单，其正确性也显而易见，但却有很广泛的应用。鸽巢原理有如
7、下重要的推广：Ramsey 定理设 gl，g2，gI；t 是正整数，且 gi!t（i=l，2，I），则存在最小的正整数 r（记作 r（gl，g2，gI；t）使得：对任意 m 元集合 S，若 m!r，当把 S 的所有 t 元子集放到 I 个盒子里时，那么存在某个 i（liI）和某 gi个元素，它的所有 t 元子集都在第 i 个盒子里。这是称 r（gl，g2，gI；t）为 Ramsey 数。上述定理是 Ramsey l930 年提出并给出证明。当 t=l 时，Ramsey 定理就是加强形式的鸽巢原理，且容易求出r（gl，g2，gI；l）=#Ii=lgi-I+lRamsey 定理是组合论中一个重要的
8、存在性定理，它的发表推动了组合论等数理科学的发展，而且关于 Ram-sey 定理和 Ramsey 数自身的研究目前已成为组合学中一个重要的分支 I+l Ramsey 理论。但是，Ramsey定理只保证了 Ramsey 数的存在性，并没有给出计算 Ramsey 数的有效方法。目前，确定 Ramsey 数的问题仍是一个尚未解决的大难题，要找到一个很小的 Ramsey 数是很困难的。虽然如此，由于其重要的理论价值和广泛的应用价值，确定 Ramsey 数是很有意义的。下面用两个例子说明 Ramsey 数在信息检索、分组交换网设计等计算机科学领域中的重要应用。4.2信息检索信息检索是计算机科学中一个基本
9、而又重要的问题。如何组织数据，使用什么样的查找方法，对检索的效率有很大的影响。所熟知的在有序表结构上的二分搜索算法是一种很有效的方法，那么二分搜索是最好的算法吗？Yao4利用 Ramsey 数对这一问题作了肯定的回答。具体地讲，假设一个表有 I 个不同的项，其元素取自键空间 M=l，2，m，希望找到在表中存储 M 的任意 I 元子集 S 的方法，使得容易回答下述询问：X 在 S 中吗？如何存储 M 的 I 元子集的规则称为一个表结构或（m，I）-表结构。最简单的表结构是有序表结构，它是按上升序列出 S 中的元素。更一般的是按置换排序的表结构，其方法是固定 l，2，I 的一个置换，根据比置换的次
10、序列出 S 中的元素。信息检索的计算复杂性依赖于表结构和搜索策略。复杂性的度量是最坏情形下确定 x 是否在 S 中所需要的询问次数。例如，对有序表结构，如果用二分搜索，所需要的询问次数是 log2（I+l）。复杂性 f（m，I）定义为所有的（m，I）-表结构和搜索策略下的复杂性的最小值。关于 f（m，I），Yao4证明了：定理 1对每个 I，存在数 N（I）使得 f（m，I）=log2（I+l）对所有 m!N（I）成立。据此定理，对充分大的 m，就信息检索来说，用有序表结构是最有效的方法。利用下述两个引理，立即可得此定理的证明。引理 1若 m!2I-l，I!2，对于按置换排序的表结构。无论采用
11、何种策略，在最坏情形下要确定 x 是否在 S 中至少需要 log2（I+l）次检查。59增刊陈家等：组合数学在计算机科学中的应用引理!给定 I，存在数 N（I）具有下述性质：若 m!N（I），且给定一个（m，I）-表结构，则存在有 2I-l 个键的集合 K，使得对应于 K 的 I 元子集的表形成按置换排序的表结构。略去引理 l 的证明，这里只给出引理 2 的证明。引理 2 的证明：设 I 个键的集体 S=l，2，I 以某种次序存放在表结构中，如果 l 2 I 的最小的 r 是多少？比如对图 l 有 I=6，由于r（C4，C4）=6，r（C4，C4，C4）=ll，所以 r=3，即需要 3 个中间
12、设施。Boyles 和 EXoo 指出，在他们使用的场合，利用 Erdos6的下述结果足以估计 r 的值：若一个 I 顶点图至少有l2I3.2+l4I 条边，则它总包含有 C4。若 I 顶点69成都信息工程学院学报第 2l 卷图的!（!-1）2 条边分成#个颜色类，由鸽巢原理，则必存在某个类至少有!（!-1）2#条边。要#使得不存在包含有12!3.2+14!条边的类。因此，应使#满足!（!-1）2#12!3.2+14!$由此得出#应满足的条件。参考文献：1 卢开澄，卢华明.组合数学（第 3 版）M.北京：清华大学出版社，2002.2 杨振生.组合数学及其算法 M.合肥：中国科学技术大学出版社，
13、1997.3 杨骅飞.组合数学及其应用 M.北京：北京理工大学出版社，1992.4 A.C.Yao.Shouid Tabies Be Sorted J.ACM，1981，28.5 陈树柏.网络图论及其应用 M.北京：科学出版社，1982.6 R.L.Graham，B.L.Rothschiid，J.H.spencer.Ramsey Theory（second edition）M.John Wiiey 8.Sons，New.York，1990.Application of combinatorics to computer softwareCHEN Jia，YANG Guang-chong（Dep
14、t.of Computing Science，CUIT，Chengdu 610225，China）Abstract：The concept of the combinatorics，the history，the deveiopment and the content are introduced.The characteristicsof the combinatorics and its appiications to the computer software are anaiyzed.Two exampies are used to show the importanceof the
15、Ramsey number in many areas such as information retrievai of the computer science and network design of the groupingexchange.Key words：combinatoriai mathematics；combination aigorithm；Ramsey number；information index；grouping exchange net-work79增刊陈家等：组合数学在计算机科学中的应用组合数学在计算机科学中的应用组合数学在计算机科学中的应用作者：陈家，杨光崇
16、，CHEN Jia，YANG Guang-chong作者单位：陈家,CHEN Jia(成都信息工程学院计算科学系信息与计算科学专业2001级3班,四川,成都,610225)，杨光崇,YANG Guang-chong(成都信息工程学院计算科学系,四川,成都,610225)刊名：成都信息工程学院学报英文刊名：JOURNAL OF CHENGDU UNIVERSITY OF INFORMATION TECHNOLOGY年，卷(期)：2006,21(z1)被引用次数：2次 参考文献(6条)参考文献(6条)1.卢开澄;卢华明 组合数学 20022.杨振生 组合数学及其算法 19973.杨骅飞 组合数学及
17、其应用 19924.A C Yao Should Tables Be Sorted 19815.陈树柏 网络图论及其应用 19826.R L Graham;B L Rothschild;J H spencer Ramsey Theory 1990 本文读者也读过(10条)本文读者也读过(10条)1.高洁 浅谈组合数学的应用与教学期刊论文-中国科技信息2005(15)2.陈永川 组合数学及其应用的研究进展会议论文-19993.胡勤.HU Qin 组合数学浅析期刊论文-电脑知识与技术2010,6(11)4.曾友良.刘建军.Zeng You-liang.Liu Jian-jun 组合数学的游戏起源期
18、刊论文-自然杂志2003,25(5)5.毛俊超 概率方法在组合数学中的应用学位论文20076.刘秀梅 组合数学中常用的思想与方法期刊论文-新课程学习（学术教育）2010(12)7.余平 组合数学中二项式系数恒等式证明归纳期刊论文-科技信息（学术版）2007(2)8.洪梅 鸽巢原理及其应用期刊论文-科技信息2009(28)9.郭燕莎 组合算法的研究与实现学位论文200810.戴想元 组合数学中两种常用思想方法期刊论文-湖北大学成人教育学院学报2001,19(4)引证文献(2条)引证文献(2条)1.迟庆云 组合数学在决策树生成算法中的应用期刊论文-重庆通信学院学报 2009(2)2.李恺 组合数学在软件工程领域的应用期刊论文-软件导刊 2013(2)本文链接：http:/
