第21卷增刊
2006年12月
文章编号:1671-1742(2006)增-0094-04成都信息工程学院学报JOURNALOFCHENGDUUNIVERSITYOFINFORMATIONTECHNOLOGYVoI.21SuppI.Dec.2006
组合数学在计算机科学中的应用
陈家!,杨光崇
(成都信息工程学院计算科学系,四川成都610225)
摘要:介绍了组合数学的概念、起源与研究的主要内容,分析了组合数学的特点,阐述了组合数学与计算机软
件的联系,并着重通过两个例子说明了Ramsey数在计算机科学的信息检索、分组交换网设计分支中的重要应用。
关键词:组合数学;组合算法;信息检索;分组交换网Ramsey数;
文献标识码:A中图分类号:O1571组合数学的概念
组合数学是近年来随着计算机科学的发展而新兴起来的一门综合性、边缘性学科。组合数学是什么,有很多不同的看法。RichardA.BruaIDi所著《IntroductoryCombinatorics》中认为组合数学研究的是事物按照某种规则的安排,主要有:存在性问题,计数性问题和对已知安排的研究。DanieII.A.Cohen所著《BasicTechniguesofCombi-
中这样描述:组合数学就是对给定描述的事物有多少种或者某种事物发生的途径有多少种的研natoriaITheory》
究。综合以上观点,组合数学就是主要研究“事物的安排”中涉及的数学问题。
2组合数学研究的主要内容
与传统的数学课程相比,组合数学研究的是一些离散的事物之间存在的数学关系,包括存在性问题、计数性问题、构造性问题以及最优化问题等,其主要内容是计数和枚举。计数问题是组合学中研究得最多的内容,它出现在所有的数学分支中。计算机科学需要研究算法,必须对算法所需的运算量和存储单元作出估计,即算法的
[1-3]时间复杂性和空间复杂性分析,其中组合数学的研究主要包括以下内容:排列组合;生成函数和递推关系;
容斥原理和鸽巢原理;线性规划等等。Burnside定理与P Iya定理;
3
3.1组合数学与计算机软件信息时代的组合数学
现代数学可以分为两大类:一类是研究连续对象,如分析、方程等,另一类就是研究离散对象的组合数学。计算机科学就是算法的科学,而计算机所处理的对象是离散的数据,研究离散对象的科学恰恰就是组合数学。因此,在信息时代的今天,组合数学就是信息时代的数学。
3.2组合数学在计算机软件的应用
随着计算机科学的发展,组合数学也在迅猛发展,而组合数学在理论方面的推进也促进计算机科学的发展。计算机软件空前发展的今天要求有相应的数学基础,组合数学作为大多数计算机软件设计的理论基础,它的重要性也就不言而喻。
组合数学在计算机方面的应用极其广泛。计算机软件与各种算法的研究分不开,为了衡量一个算法的效率,必须估计用此算法解答具有给定长的输入(问题)时需要多少步(例如算术运算、二进制比较、程序调用等的次数)。这要求对算法所需的计算量及存储单元数进行估算,这就是计数问题的内容,而组合数学分析主要研究内容就是计数和枚举的方法和理论。
!成都信息工程学院计算科学系信息与计算科学专业2001级3班
2006 文章编号: 1671 21742( 2006) 增20094 204 组合数学在计算机科学中的应用陈 家* , 杨光崇 ( 成都信息工程学院计算科学系, 四川 成都 610225) 摘要: 介...
组合数学在计算机中的应用_数学_自然科学_专业资料。组合数学在计算机中的应用组合数学, 又称为离散数学, 但有时人们也把组合数学和图论加在一起算成是离散数学...
7 第二章 组合数学在计算机科学中的应用... 10 2.1 组合数学的概念 ......
离散数学在计算机科学中的应用_理学_高等教育_教育专区 暂无评价0人阅读0次下载举报文档 离散数学在计算机科学中的应用_理学_高等教育_教育专区。离散数学在...
0 0 7 年 第 10 期 百家谭 一 计算机科学中的组合数学 口王 理 口李 ...它 的应用 越来 越广泛 它的 前景无 限广 阔 : 收稿 日期 2 0 , , 。...
组合数学不仅在基础数学研究中具有极其重要的地位, 在其它 的学科中也有重要的应用,如计算机科学、编码和密码学、物理、化学、生物等学科中均有 重要应用。 微积分...
计算机中的重要性以及在离散数学教学过程中就其内容及其与计算机科学实际应用进行...组合数学在计算机科学研究和 应用中常常要用到 。同时也广泛应用于物理学 、 ...
浅析数学在计算机科学及应用中的应用_数学_自然科学_专业资料。图1 3.4 离散...在程序设计语言的应用中,经常出现两类问 题:(1)怎么能够确定一组单词是否组合...
关键词:计算机应用数学组合数学答案哈工大计算机科学与技 1/2 相关文档推荐...由于 +6-4=5 =5<6 根据定理3可知,族中有 SDR 的集合的最大个数是...
数学在计算机中的应用_理学_高等教育_教育专区。离散数学在计算机方面的应用计算机学科主要脱胎发源于数学学科, 离散数学是现代数学的一个重要分支, 是计算机 科学中...
热门文档