组合数学在计算机科学中的应用
陈 家*, 杨光崇(成都信息工程学院计算科学系,四川成都610225)
摘要:介绍了组合数学的概念、起源与研究的主要内容,分析了组合数学的特点,阐述了组合数学与计算机软件的联系,并着重通过两个例子说明了Ramsey数在计算机科学的信息检索、分组交换网设计分支中的重要应用。
关 键 词:组合数学;组合算法; Ramsey数;
信息检索;分组交换网中图分类号: O157
文献标识码: A*
组合数学是近年来随着计算机科学的发展而新兴起来的一门综合性、边缘性学科。
组合数学是什么,有很多不同的看法。Richard A. BrualDi所著5Introductory Combinatorics6中认为组合数学研究的是事物按照某种规则的安排,主要有:存在性问题,计数性问题和对已知安排的研究。Daniel I. A. Cohen所著5Basic Techniques ofCombinatorial T heory6中这样描述:组合数学就是对给定描述的事物有多少种或者某种事物发生的途径有多少种的研究。综合以上观点,组合数学就是主要研究/事物的安排0中涉及的数学问题。
2 组合数学研究的主要内容与传统的数学课程相比,组合数学研究的是一些离散的事物之间存在的数学关系,包括存在性问题、计数性问题、构造性问题以及最优化问题等,其主要内容是计数和枚举。计数问题是组合学中研究得最多的内容,它出现在所有的数学分支中。计算机科学需要研究算法,必须对算法所需的运算量和存储单元作出估计,即算法的时间复杂性和空间复杂性分析,其中组合数学的研究主要包括以下内容[ 1- 3]:排列组合;生成函数和递推关系;容斥原理和鸽巢原理; Burnside定理与PŽlya定理;线性规划等等。3 组合数学与计算机软件311 信息时代的组合数学 现代数学可以分为两大类:一类是研究连续对象,如分析、方程等,另一类就是研究离散对象的组合数学。计算机科学就是算法的科学,而计算机所处理的对象是离散的数据,研究离散对象的科学恰恰就是组合数学。因此,在信息时代的今天,组合数学就是信息时代的数学。312 组合数学在计算机软件的应用随着计算机科学的发展,组合数学也在迅猛发展,而组合数学在理论方面的推进也促进计算机科学的发展。计算机软件空前发展的今天要求有相应的数学基础,组合数学作为大多数计算机软件设计的理论基础,它的重要性也就不言而喻。组合数学在计算机方面的应用极其广泛。计算机软件与各种算法的研究分不开,为了衡量一个算法的效率,必须估计用此算法解答具有给定长的输入(问题)时需要多少步(例如算术运算、二进制比较、程序调用等的次数)。这要求对算法所需的计算量及存储单元数进行估算,这就是计数问题的内容,而组合数学分析主要研究内容就是计数
和枚举的方法和理论
组合数学在国外软件业的发展状况纵观全世界软件产业,美国处于绝对的垄断地位。造成这种现象的一个根本原因就是计算机科学在美国的飞速发展。当今计算机科学界的最权威人士很多都是研究组合数学出身的。美国最重要的计算机科学系( MIT,Princeton, Stanford,Harvard, Yale,,,)都有第一流的组合数学家。组合数学在国外早已成为十分重要的学科,甚至可以说是计算机科学的基础。一些大公司,如IBM, AT & T都有全世界最强的组合研究中心。美国政府也成立了离散数学及理论计算机科学中心DIMACS(与Princeton大学, Rutgers大学, AT& T联合创办的,设在Rutgers大学) ,该中心已是组合数学理论计算机科学的重要研究阵地。4 Ramsey数在计算机科学中的应用411 Ramsey定理和Ramsey数 众所周知,若有n+ 1只鸽子同时飞进n个鸽巢中,则一定有某个鸽巢中至少飞进两只鸽,这就是有名的鸽巢原理(也叫抽屉原理)。它非常简单,其正确性也显而易见,但却有很广泛的应用。鸽巢原理有如下重要的推广:Ramsey定理 设q1, q2,,, qn; t是正整数,且qiEt( i= 1,2,,, n ) ,则存在最小的正整数r (记作r ( q1,q2,,q n; t)使得:对任意m元集合s,若mEr ,当把S的所有t元子集放到n个盒子里时,那么存在某个i (1FiFn )和某q i个元素,它的所有t元子集都在第i个盒子里。这是称r ( q1, q2,,q n; t)为Ramsey数。上述定理是Ramsey 1930年提出并给出证明。当t= 1时, Ramsey定理就是加强形式的鸽巢原理,且容易求出r ( q1, q2,,qn;1)=Eni= 1qi-n+ 1Ramsey定理是组合论中一个重要的存在性定理,它的发表推动了组合论等数理科学的发展,而且关于Ram-sey定理和Ramsey数自身的研究目前已成为组合学中一个重要的分支)))n+ 1)))Ramsey理论。但是, Ram-sey定理只保证了Ramsey数的存在性,并没有给出计算Ramsey数的有效方法。目前,确定Ramsey数的问题仍是一个尚未解决的大难题,要找到一个很小的Ramsey数是很困难的。虽然如此,由于其重要的理论价值和广泛的应用价值,确定Ramsey数是很有意义的。下面用两个例子说明Ramsey数在信息检索、分组交换网设计等计算机科学领域中的重要应用。412 信息检索信息检索是计算机科学中一个基本而又重要的问题。如何组织数据,使用什么样的查找方法,对检索的效率有很大的影响。所熟知的在有序表结构上的二分搜索算法是一种很有效的方法,那么二分搜索是最好的算法吗?Yao[ 4]利用Ramsey数对这一问题作了肯定的回答。具体地讲,假设一个表有n个不同的项,其元素取自键空间M={1,2,,, m } ,希望找到在表中存储M的任意n元子集S的方法,使得容易回答下述询问: X在S中吗?如何存储M的n元子集的规则称为一个表结构或( m , n)-表结构。最简单的表结构是有序表结构,它是按上升序列出S中的元素。更一般的是按置换排序的表结构,其方法是固定{1,2,,, n}的一个置换,根据比置换的次序列出S中的元素。信息检索的计算复杂性依赖于表结构和搜索策略。复杂性的度量是最坏情形下确定x是否在S中所需要的询问次数。例如,对有序表结构,如果用二分搜索,所需要的询问次数是[log2( n+ 1) ]。复杂性f ( m , n )定义为所有的( m , n)-表结构和搜索策略下的复杂性的最小值。关于f ( m , n ), Yao[4]证明了:定理1 对每个n,存在数N ( n)使得f ( m , n)=[log2( n+ 1) ]对所有mEN ( n )成立。据此定理,对充分大的m,就信息检索来说,用有序表结构是最有效的方法。
参考资料：http://wenku.baidu.com/view/d93958d576eeaeaad1f330cf.html