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

目录目录 摘要 1 1 组合数学概述 1 2 组合数学在生活中的应用 1 3 组合数学与计算机软件 1 3 1 信息时代的组合数学 2 3 2 组合数学在计算机软件的应用 2 3 3 组合数学与计算机软件的关系 2 3 4 组合数学在国外软件业的发展状况 2 4 Ramsey 数在计算机科学中的应用 3 4 1 Ramsey 定理和 Ramsey 数 3 4 2 信息检索 3 参考文献 5 1 组合数学在计算机中的应用组合数学在计算机中的应用 摘要 摘要 介绍了组合数学的概念 起源与研究的主要内容 分析了组合数学的特点以及其在生 活中的应用 阐述了组合数学与计算机软件的联系 并着重通过两个例子说明了 Ramsey 数在 计算机科学的信息检索中的重要应用 关键词 组合数学 组合算法 Ramsey 数 信息检索 1 组合数学概述 组合数学概述 组合数学 又称为离散数学 但有时人们也把组合数学和图论加在一起算成是离散数 学 组合数学是计算机出现以后迅速发展起来的一门数学分支 计算机科学就是算法的科 学 而计算机所处理的对象是离散的数据 所以离散对象的处理就成了计算机科学的核心 而研究离散对象的科学恰恰就是组合数学 组合数学的发展改变了传统数学中分析和代数 占统治地位的局面 现代数学可以分为两大类 一类是研究连续对象的 如分析 方程等 另一类就是研究离散对象的组合数学 组合数学不仅在基础数学研究中具有极其重要的地 位 在其它的学科中也有重要的应用 如计算机科学 编码和密码学 物理 化学 生物 等学科中均有重要应用 微积分和近代数学的发展为近代的工业革命奠定了基础 而组合 数学的发展则是奠定了本世纪的计算机革命的基础 计算机之所以可以被称为电脑 就是 因为计算机被人编写了程序 而程序就是算法 在绝大多数情况下 计算机的算法是针对 离散的对象 而不是在作数值计算 正是因为有了组合算法才使人感到 计算机好象是有 思维的 2 组合数学在生活中的应用 组合数学在生活中的应用 在日常生活中我们常常遇到组合数学的问题 如果你仔细留心一张世界地图 你会发 现用一种颜色对一个国家着色 那么一共只需要四种颜色就能保证每两个相邻的国家的颜 色不同 这样的着色效果能使每一个国家都能清楚地显示出来 但要证明这个结论确是一 个著名的世界难题 最终借助计算机才得以解决 最近人们才发现了一个更简单的证明 当你装一个箱子时 你会发现要使箱子尽可能装满不是一件很容易的事 你往往需要 做些调整 从理论上讲 装箱问题是一个很难的组合数学问题 即使用计算机也是不容易 解决的 航空调度和航班的设定也是组合数学的问题 怎样确定各个航班以满足 不同旅客 转机的需要 同时也使得每个机场的航班起落分布合理 此外 在一些航班有延误等特殊 情况下 怎样作最合理的调整 这些都是 组合数学的问题 组合数学在企业管理 交通规划 战争指挥 金融分析等领域都有重要的应用 在美 国有一家用组合数学命名的公司 他们用组合数学的方法来提高企业管理的效益 这家公 司办得非常成功 此外 试验设计也是具有很大应用价值的学科 它的数学原理就是组合 设计 用组合设计的方法解决工业界中的试验设计问题 在美国已有专门的公司开发这方 面的软件 最近 德国一位著名组合数学家利用组合数学方法研究药物结构 为制药公司 节省了大量的费用 引起了制药业的关注 总之 组合数学无处不在 它的主要应用就是在各种复杂关系中找出最优的方案 所 以组合数学完全可以看成是一门量化的关系学 一门量化了的运筹学 一门量化了的管理 学 3 组合数学与计算机软件 组合数学与计算机软件 随着计算机网络的发展 计算机的使用已经影响到了人们的工作 生活 学习 社会 2 活动以及商业活动 而计算机的应用根本上是通过软件来实现的 3 1 信息时代的组合数学 现代数学可以分为两大类 一类是研究连续对象 如分析 方程等 另一类就是研究离散 对象的组合数学 计算机科学就是算法的科学 而计算机所处理的对象是离散的数据 研究离 散对象的科学恰恰就是组合数学 因此 在信息时代的今天 组合数学就是信息时代的数学 3 2 组合数学在计算机软件的应用 随着计算机科学的发展 组合数学也在迅猛发展 而组合数学在理论方面的推进也促进计 算机科学的发展 计算机软件空前发展的今天要求有相应的数学基础 组合数学作为大多数 计算机软件设计的理论基础 它的重要性也就不言而喻 组合数学在计算机方面的应用极其广泛 计算机软件与各种算法的研究分不开 为了衡 量一个算法的效率 必须估计用此算法解答具有给定长的输入 问题 时需要多少步 例如算 术运算 二进制比较 程序调用等的次数 这要求对算法所需的计算量及存储单元数进 行估算 这就是计数问题的内容 而组合数学分析主要研究内容就是计数和枚举的方法和理论 3 3组合数学与计算机软件的关系 我国在软件上的落后 要说出根本的原因可能并不是很简单的事 除了技术和科学上 的原因外 可能还跟我们的文化 管理水平 教育水平 思想素质等诸多因素有关 除去 这些人文因素以外 一个最根本的原因就是我国的信息技术的数学基础十分薄弱 这个问 题不解决 我们就难成为软件强国 然而问题决不是这么简单 信息技术的发展已经涉及 到了很深的数学知识 而数学本身也已经发展到了很深 很广的程度并不是单凭几个聪明 的头脑去想想就行了 而更重要的是需要集体的合作和力量 就象软件的开发需要多方面 的人员的合作 美国的软件之所以能领先 其关键就在于在数学基础上他们有很强的实力 有很多杰出的人才 一般人可能会认为数学是一门纯粹的基础科学 1 1 的解决可能不会 有任何实际的意义 如果真是这样 一门纯粹学科的发展落后几年 甚至十年 关系也不 大 然而中国的软件产业的发展已向数学基础提出了急切的需求 网络算法和分析 信息 压缩 网络安全 编码技术 系统软件 并行算法 数学机械化和计算机推理 等等 此 外 与实际应用有关的还有许多许多需要数学基础的算法 如运筹规划 金融工程 计算 机辅助设计等 如果我们的软件产业还是把眼光一直盯在应用软件和第二次开发 那么我 们在应用软件这个领域也会让国外的企业抢去很大的市场 如果我们现在在信息技术的数 学基础上 大力支持和投入 那将是亡羊补牢 犹未为晚 只要我们能抢回信息技术的数 学基地 那么我们还有可能在软件产业的竞争中 扭转局面 甚至反败为胜 吴文俊院士 开创和领导的数学机械化研究 为中国在信息技术领域占领了一个重要的阵地 有了雄厚 的数学基础 自然就有了软件开发的竞争力 这样的阵地多几个 我们的软件产业就会产 生新的局面 值得注意的是 印度有很好的统计和组合数学基础 这可能也是印度的软件 产业近几年有很大发展的原因 3 4 组合数学在国外软件业的发展状况 纵观全世界软件产业的情况 易见一个奇特的现象 美国处于绝对的垄断地位 造成 这种现象的一个根本的原因就是计算机科学在美国的飞速发展 当今计算机科学界的最权 威人士很多都是研究组合数学出身的 美国最重要的计算机科学系 MIT Princeton Stanford Harvard Yale 都有第一流的组合数学家 计算机科学 3 通过对软件产业的促进 带来了巨大的效益 这已是不争之事实 组合数学在国外早已成 为十分重要的学科 甚至可以说是计算机科学的基础 一些大公司 如 IBM AT t 是正整数 且 qi t i 1 2 n 则存在最小的正 整数 r 记作 r q1 q2 qn t 使得 对任意 m 元集合 s 若 m E r 当把 S 的所有 t 元子集 放到 n 个盒子里时 那么存在某个 i 1 N n 成立 据此定理 对充分大的 m 就信息检索来说 用有序表结构是最有效的方法 利用下述两个引理 立即可得此定理的证明 引理 1 若 m 2 n 1 n 2 对于按置换排序的表结构 无论采用何种策略 在最坏 情形下要确定 x 是否在 S 中至少需要 log2 n 1 次检查 引理 2 给定 n 存在数 N n 具有下述性质 若 m N n 且给定一个 m n 2 表结 构 则存在有 2 n 1 个键的集合 K 使得对应于 K 的 n 元子集的表形成按置换排序的表结构 5 参考文献参考文献 1 杨骅飞 组合数学及其应用 M 北京 北京理工大学出版社 1992 2 杨振生 组合数学及其算法 M 合肥 中国科学技术大学出版社 1997 3 卢开澄 卢华明 组合数学 第 3 版 M 北京 清华大学出版