《简述组合数学应用》由会员分享，可在线阅读，更多相关《简述组合数学应用（7页珍藏版）》请在金锄头文库上搜索。
1、序言组合数学也称为组合论，组合学。是一门古老而又崭新的学科。传说早在4000 多年前的大禹时期就观察到了神龟背上的幻方， 北宋数学家， 贾宪著有 皇帝九章细草 、 算法教古集 ，以及非常著名的杨辉三角都是组合数学的早期表现。 但是在没有现代科学技术出现特别是计算机技术出现之前组合数学发展遇到了瓶颈。 直到近代计算机技术的大力发展， 给组合数学又带来了一次新生。 与传统的数学课程相比， 组合数学研究的是一些离散的事物之间存在的数学关系， 包括存在性问题， 计数性问题， 构造性问题以及最优化问题， 其主要内容是计数和枚举。 计数问题是组合学中研究得最多的问题， 它出现在所有的数学分支中。 组合数学
2、不仅在基础数学中具有极其重要的地位，在其他学科中也有重要的作用，如计算机科学、编码和密码学、物理、化学、生物等学科中，甚至在企业管理，交通规则，战争指导，金融分析，城市物流等领域具有重要应用。具有重要的应用。 组合数学的发展奠定了本世纪的计算机革命的基础。 计算机应用的灵魂是算法， 对计算机来说它的算法针对的都是离散的对象而组合数学主要研究的是构造算法对离散数据进行处理， 因此在组合数学的发展对计算的发展起到至关重要的作用。组合数学的应用1. 组合数学在计算机科学方面的应用1.1 组合数学在无线传感器网络中的应用近年来无线传感网络在军事，科研和日常生活中扮演着越来越重要的角色。但是关于无线传感
3、网络的技术也遇到了很大的困难。无线传感网络节点在民用方面： 主要用来长时间不间断的收集周围环境的数据，但是由于节点能量有限， 存储有限，数据如果不加处理就传输，则会造成很大的网络带宽浪费， 能量浪费甚至造成节点存储溢出。 因此这时候我们就可以利用组合学中的生成函数的相关知识， 将节点收集到的数据进行压缩， 然后再进行传输，这样就可以解决上述问题。无线传感网络节点由于它们能量有限需要给其不定时的充电， 现在先进的充电方式是用充电小车周游节点覆盖区域对每个节点进行充电， 如何使充电小车能够更高效的对节点充电， 我们可以将此类问题抽象看成组合数学中图论中的知识：将整个网络区域抽象成图， 其中无线传感
4、网节点为图中的顶点， 节点之间的路径为图中的边。从而这类问题可以看成是组合数学中旅行商问题的实例 1 ，通过构造多条哈密尔顿回路，并求的代价最小的那条回路来解决此类问题。无线传感网络在国防， 军事等领域也有广泛的应用。 随着应用的普及， 传感器网络的安全也显得日益重要， 尤其是其中最基础和最关键的密钥管理问题。 在节点能量以及计算和通信能力非常有限的无线传感器网络中，一般采用密钥预分配机制实现安全引导， 在部署之初为节点预分配若干密钥， 使得部署后不同节点之间通过共享密钥保障安全基础，然后进行进一步的密钥协商2 。但是由于无线传感器网络要求具备规模， 开放暴露环境和节点能力严格受限等特殊性，
5、使得许多指标都难易达到较好的水平，但是进来有人利用组合数学中区组设计的知识，提出了一种新的无线传感器网络密钥预分配方案， 提高了共享概率， 减小了密钥路径长度， 扩大了网络规模， 增强了密钥强度， 并降低密钥共享的复杂性和提高节点部署的实际可行性。1.2 组合数学在计算机软件以及信息化方面的应用组合数学在计算机科学方面的应用极其广泛3 。 计算机软件与各种算法的研究分不开， 为了衡量一个算法的效率， 必须估计用此算法计算具有给定长度的输入时需要多少步，例如算术运算， 二进制比较，程序调用等的次数。这要求对算法所需的计算量以及存储单元数进行估算， 这就是计数问题的内容， 而组合数学分析主要研究内
6、容就是计数和枚举的方法和理论。纵观全世界软件产业， 美国处于绝对的垄断地位， 造成这种现象的一个根本原因是计算机科学在美国的飞速发展。 当今计算机科学界最权威的人士很多都是研究组合数据出身的。美国最重要的计算机科学系 MIT ， Princeton ， Stanford ，Yale 等都有第一流的组合数学家。组合数学在国外早已成为十分重要的学科。甚至可以说是计算机科学的基础。一些大公司，如 IBM ， AT&T 都有全世界最强的组合研究中心。 美国政府也成立了离散数学及理论计算机科学中心DIMACS ，该中心已成为组合数学理论和计算机科学的重要研究阵地。信息检索是计算机科学中的一个基本而又重要
7、的问题。 如何组织数据， 使用什么样的查找方法， 对检索的效率有很大的影响。 大家所熟知的在有序表结构上的二分搜索算法是一种很有效的方法， 那么二分搜索是最好的算法吗？ Yao 利用组合数学中的 Ramsey 相关知识对这一问题做了肯定的回答。网络是当今计算机发展的一个特点， 是进入信息社会的巨大推动力。 分组交换网是采用分组交换技术的网络， 它从终端或计算机接收报文， 把报文分割成分组， 并按某种策略选择最佳路径在网络中传输， 到达目的地后在将分组合并成报文交给目的终端或计算机。但是在设计分组网路的时候，要考虑一个n 个顶点的网络在不出现C4 的条件下， 中间的设施的最少个数是多少？ BEL
8、L 分组交换网络则通过 Ramsey 数的相关知识解决了此类问题。2. 组合数学在生活中的应用在日常生活中我们常常遇到组合数学的问题 4 。 如果你仔细留心一张世界地图， 你会发现用一种颜色对一个国家着色， 那么一共只需要四种颜色就能保证每两个相邻的国家的颜色不同。这样的着色能使每一个国家都能清楚地显示出来，这就是组合数学中的地图着色原理。我国古代的河洛图上记载了三阶幻方， 即把从一到九个数按三行三列的队行排列，使得每行，每列，以及两条对角线上的三个数只和都是15 。组合数学中有许多像幻方这样精巧的结构。 1977 年美国旅行者 1 号， 2 号宇宙飞船就带上了幻方以作为人类智慧的信号。航空调
9、度和航班的设定也是组合数学的问题。 怎样确定各个航班以满足， 不同旅客转机的需要， 同时也使得每个机场的航班起落分布合理。 此外， 在一些航班有延误等特殊情况下，怎样合理调整，这些都是组合数学的问题。对于城市的交通管理， 交通规划， 哪些地方可能是阻塞要地， 哪些地方应该设单行道， 立交桥应该建在哪里最合适， 红绿灯怎样设定最合理， 如此等等全是组合数学的问题。库房和运输的管理也是典型的组合数学问题。 怎样安排运输使得库房充分发挥作用，进一步来说，货物放在什么地方最便于存取。我们知道， 用形状相同的方形砖块可以把一个地面铺满， 但是如果用不同形状， 而用非方型的砖块来铺一个地面， 能否铺满呢？
10、这不仅是一个与实际相关的问题，也设计到深奥的组合数学问题。组合数学中有一个著名问题： 是否存在稳定婚姻的问题。 假如能找到两对夫妇 A 和 B ，如果A 中的男主人更喜欢B 中的女主人，或者A 中的女主人喜欢B中的男主人 （或者相反亦然） 那么这样就可能有不稳定性。 组合数学的方法可以找到一种婚姻的安排方法， 使得没有上述的不稳定情况出现。 同时这种组合学方法的一个实际用途是： 美国的医院在确定录取住院医生时， 他们将考虑申请者的志愿先后顺序， 同时也给申请排序， 按这样的次序考虑出的总的方案将没有医院和申请者两者同时后悔的情况。而我国前几年的高考录取方案也采取这种方法。随着中国经济快速的增长
11、，城市化是未来中国的发展方向。人大通过的 “十五”规划，把物流业作为战略重点列入要打理发展的新兴服务产业。如何制定一个运输计划使生产地到销售地的产品运输量最大。 这就是组合数学中的网络最大流问题。组合数学还可用于融资分析， 投资方案的确定， 怎样找出好的投资组合以降低投资风险。也涉及到组合数学深奥的知识。总结总之， 组合数学无处不在， 它的主要应用就是在各种复杂关系中找出最优的方案，所以组合数学完全可以看成是一门量化了的关系学，一门量化了的运筹学，一门量化了的管理学。这篇论文只是介绍了组合数学在无线传感器网络，计算机 软件和信息化以及人们日常生活中应用的一小部分，希望借此论文可以激发起我们对组
12、合数学的关注，学会在生活中运用组合数学来解决具体的问题，作为计算机专业的学生，我们必须把组合数学的学习放在一个重要的位置上，掌握基本的组合学原理，培养专业的数学思维，这样才能在以后的工作学习中掌握主动和先 机。作为富有生命力的数学分支，组合数学这个古老而又年轻的学科，正在迸发出勃勃生机推动着各行各业的发展。参考文献1 . Li Jianzhong ； -Approximation to Data Streams in Sensor Networks . INFOCOM 20132 .夏戈明，黄尊国 基于对称平衡不完全区组设计的无线传感器网络密钥预分配 方案J计算机研究与发展，2008(15)154-1643 .陈家 组合数学在计算及科学中的应用J成都信息工程学院学报， 2006(21):94-974 .陈永川 话说组合数学J科学中国人，2003(5):15-17Welcome ToDownload !欢迎您的下载，资料仅供参考！
