文档介绍：该【组合数学论文 】是由【Alone-丁丁】上传分享，文档一共【13】页，该文档可以免费在线阅读，需要了解更多关于【组合数学论文 】的内容，可以使用淘豆网的站内搜索功能，选择自己适合的文档，以下文字是截取该文章内的部分文字，如需要获得完整电子版，请下载此文档到您的设备，方便您编辑和打印。组合数学论文
生活中的组合数学
摘要:组合数学在基础理论方面和生活应用方面都发挥着越来越重要的作用,组合数学不仅在基础数学研究中具有极其重要的地位,在其他的学科中也有重要的应用,如在计算机科学、编码和密码学、物理、化学、生物等学科中均有重要应用。如果说微积分和近代数学的发展为近代的工业革命奠定了基础,那么组合数学的发展则是奠定了21世纪计算机革命的基础。因此随着计算机科学和其它许多新兴应用学科的发展,组合数学在基础理论方面和生活应用方面都发挥着越来越重要的作用,进而需要我们对其进行更加深层次的研究.
关键词:组合数学;鸽巢原理;数学游戏
引言
随着计算机的普及推广,、应用广泛的学科,同时它也是一门讲究方法,,计算机强大的计算能力为寻求组合数学问题的巧妙解法提供了无限的可能,同时组合数学也反过来有效地推动了计算机科学的发展.
组合数学在国外已有较快发展,,特别是图论研究和区组设计等方面已取得一定的成果.
组合数学的发展显然已经改变了传统数学中分析和代数占统治地位的局面,,希望借以简单的阐述引起人们对组合数学的更深层次的理解,并能够将其灵活应用于生活中.
所以我想通过一些实例和数学史上的一些故事和难题,,系统的查阅了相关文献,并结合生活中涉及组合数学的相关知识进行阐述,,
组合数学是离散数学的一个分支,其内容零散,思想方法繁多,对于长期接受连续性数学学****的我们来说,通常感到很难抓住其要领,无从下手,,如加乘法则,抽屉法则,母函数法,逐步淘汰法等等,了解这些方法有助于培养我们学生的组合思维。
组合数学是十分贴近于人们的生活的,因此组合问题在生活中非常常见。例如,求n个球队参加比赛,每队只和其他队比赛一次的总比赛场数。例如,在纸上画一个网络,用铅笔沿着网络的线路揍,在笔不离开纸面而且不重复线路的条件下,一笔画出网络图。又例如这样一个简单的组合数学问题:一个船夫要把一只狼,一只羊和一棵白菜运过河。而当人不在场时,狼要吃羊,羊要吃白菜,而他的船每趟只能运其中的一个,问人怎样才能把三者都运过河。下面介绍几种组合数学中的著名问题。
:对世界地图着色,每一个国家使用一种颜色。如果要求相邻国家的颜色相异,是否总共只需四种颜色?四色定理是一个著名的数学定理。它指出,如果将平面分成一些邻接的区域,那么可以用不多于四种颜色来给这些区域染色,使得每两个邻接区域染的颜色都不一样。另一个通俗的说法是:每个(无飞地的)地图都可以用不多于四种颜色来染色,而且没有两个邻接的区域颜色相同。被称为邻接的两个区域是指它们有一段公共的边界,而不仅仅是一个公共的交点。例如右图左下角的四色圆盘中,红色部分和绿色部分是邻接的区域,而黄色部分和红色部分则不是临界区域。
尽管四色定理最初提出是和地图染色工作有关,但四色定理本身对地图着色工作并没有特别的意义。据凯尼斯·梅在一篇文章中所言:“(实际中)用四种颜色着色的地图是不多见的,而且这些地图往往最少只需要三种颜色来染色。制图学和地图制图史相关的书籍也没有四色定理的记载。”
一些简单的地图只需要三种颜色就够了,但有时候第四种颜色也是必须的。比如说当一个区域被三个区域包围,而这三个区域又两两相邻时,就得用四种颜色才行了。“是否只用四种颜色就能为所有地图染色”的问题最早是由一位英国制图员在1852年提出的,被称为“四色问题”。人们发现,要证明宽松一点的“五定理”(即“只用五种颜色就能为所有地图染色”)很容易,但四色问题却出人意料地异常困难。曾经有许多人发表了四色问题的证明或反例,但都被证实是错误的。
1977年,数学家凯尼斯·阿佩尔(英语:KennethAppl)和沃夫冈·哈肯(英语:WolfgangHaken)借助电子计算机首次得到了一个完全的证明,四色问题也终于成为了四色定理。这是首个主要由计算机证明的定理。这个证明一开始并不为许多数学家接受,因为不少人认为这个证明无法用人手直接验证。尽管随着计算机的普及,数学界对计算机辅助证明更能接受,但仍有数学家对四色定理的证明存疑。
船夫过河问题:船夫要把一匹狼、一只羊和一棵白菜运过河。只要船夫不在场,羊就会吃白菜、狼就会吃羊。船夫的船每次只能运送一种东西。怎样把所有东西都运过河?这是线性规划的问题。
中国邮差问题:由中国组合数学家管梅谷教授提出。邮递员要穿过城市的每一条路至少一次,怎样行走走过的路程最短?这不是一个NP完全问题,存在多项式复杂度算法:先求出度为奇数的点,用匹配算法算出这些点间的连接方式,然后再用欧拉路径算法求解。
河洛图:我国古代的河洛图上记载了三阶幻方,即把从一到九这九个数按三行三列的队行排列,使得每行,每列,以及两条对角线上的三个数之和都是一十五。组合数学中有许多象幻方这样精巧的结构。1977年美国旅行者1号、2号宇宙飞船就带上了幻方以作为人类智慧的信号。
装箱问题:当你装一个箱子时,你会发现要使箱子尽可能装满不是一件很容易的事,你往往需要做些调整。从理论上讲,装箱问题是一个很难的组合数学问题,即使用计算机也是不容易解决的。
是否存在稳定婚姻的问题:假如能找到两对夫妇(如张(男)--李(女)和赵(男)--王(女)),如果张(男)更喜欢王(女),而王(女)也更喜欢张(男),那么这样就可能有潜在的不稳定性。组合数学的方法可以找到一种婚姻的安排方法,使得没有上述的不稳定情况出现(当然这只是理论上的结论)。这种组合数学的方法却有一个实际的用途:美国的医院在确定录取住院医生时,他们将考虑申请者的志愿的先后次序,同时也给申请排序。按这样的次序考虑出的总的方案将没有医院和申请者两者同时后悔的情况。实际上,高考学生的最后录取方案也可以用这种方法。
管理调度问题:我们还会遇到更复杂的调度和安排问题。例如,在生产***的曼哈顿计划中,涉及到很多工序,许多人员的安排,很多元件的生产,怎样安排各种人员的工作,以及各种工序间的衔接,从而使整个工期的时间尽可能短?这些都是组合数学典型例子。又比如,假日饭店的管理中,也严格规定了有关的工序,如清洁工的第一步是换什么,清洗什么,第二步又做什么,总之,他进出房间的次数应该最少。既然,这样一个简单的工作都需要讲究工序,那么一个复杂的工程就更不用说了。
铺地砖问题:我们知道,用形状相同的方型砖块可以把一个地面铺满(不考虑边缘的情况),但是如果用不同形状,而又非方型的砖块来铺一个地面,能否铺满呢?这不仅是一个与实际相关的问题,也涉及到很深的组合数学问题。
组合数学还可用于金融分析:组合数学还可用于金融分析,投资方案的确定,怎样找出好的投资组合以降低投资风险。南开大学组合数学研究中心开发出了"金沙股市风险分析系统"现已投放市场,为短线投资者提供了有效的风险防范工具。
总之,组合数学无处不在,它的主要应用就是在各种复杂关系中找出最优的方案。所以组合数学完全可以看成是一门量化的关系学,一门量化了的运筹学,一门量化了的管理学。
下面看看组合数学在生活中的实际应用.(以下假设和是两类互不关联、互不相同的事件.)组合数学问题在生活中非常常见。例如,求n个球队参加比赛,每队只和其他队比赛一次的总比赛场数。例如,在纸上画一个网络,用铅笔沿着网络的线路揍,在笔不离开纸面而且不重复线路的条件下,一笔画出网络图。又例如这样一个简单的组合数学问题:一个船夫要把一只狼,一只羊和一棵白菜运过河。而当人不在场时,狼要吃羊,羊要吃白菜,而他的船每趟只能运其中的一个,问人怎样才能把三者都运过河。
加法原则可定义为:设事件有种选择方式,事件有种选择方式,则选或共有种方式.
例如,大于1小于9的的奇数有3个,分别为3,5,7,9;大于1小于9的偶数有4个,分别为2,4,6,,即2,3,4,5,6,7,,.
乘法原则可以定义为:设事件有种选取方式,事件有种选取方式,那么选取以后再选取共有种方式.
例如,从3个黑人、5个白人、.
下面再用一个实例看看这两个法则是如何应用的.
例5某旅行社开辟了从北京去长白山和天山2条旅游线路,称为北线;从北京去西湖、黄山、峨眉山3条旅游线路,?如某人选定了从北京去四川,先要在西安中转,北京到西安有3种航班
可选,西安到四川又有2种航班可选,问共有多少种不同的航班配置方式?
分析由所学的概率知识可知,互不相容事件,则其和的概率等于各自概率之和,即;同理,二个独立事件同时发生的概率.
解由加法原理可知,该社共有的线路条数条.
由乘法原理可知,共有的航班配置方式种.
首先是抽屉原理,大家也许早就听说过这样的智力问题:“从10双鞋子中随便拿几只能保证有一双相配的鞋?”:“把多于个东西任意放进个抽屉,那么一定有一个抽屉放进了不止一个东西”.
因为19世纪德国数学家狄利克雷曾用这个原理证明过数学命题,所以把它叫做狄氏抽屉原理,,但利用它可以证明不少并不简单的结论.
,:“若有个鸽巢,而鸽子多余只,若每只鸽子必须进巢,则至少有一个鸽巢内的鸽子多于一只.”
下面简要举一个用鸽巢原理解决实际问题的例子.
例6一间屋内有10个人,他们当中没有人超过60岁(年龄只以整数给出):总能找出两组人(两组不含相同的人),各组的年龄和是相同的.
解设为屋内10个人的年龄构成的集合,集合的所有个不同元素之和共有,则所有可能的不同元素之和有种,记这些和为,由题设条件可知:
.
因此,由鸽巢原理原理可知S中至少有两个元素是相同的,,则把这些相同的人去掉,即为要找的两组年龄和相同的人.
:“证明在至少有6个人参加的集会上,与会者中或者有3个人以前互相认识,或者有3个人以前彼此都不认识.”.
例7试证明6个人中一定有3个人相互认识或相互不认识.
证明先考虑6个人中的任意一个人,,S表示与p不相识的人的集合.
由鸽巢原理知,,则这3个人或者彼此不相识,,,则由于这两个人都与p相识,因此有3人彼此相识,故定理结论成立.
类似的,如果S包含3个人,则这3个人或者彼此相识,,,则由于这两个人都与p也不相识,因此有3个人彼此不相识,故定理结论成立.
线性规划是最简单,应用最广泛的一种数学规划方法,,线性规划问题可以归结为一类条件极值问题.
例8某电视机厂有100台彩电的订单要在三周内交货,在第一,.
解假设表示在第周生产的彩电数,表示第周生产台彩电的费用,则此问题的数学模型为
min,
.,
.
假设表示在前周生产台彩电所得到的最小费用,则由最优原理可得出如下的递归方程
,
,
.
原问题的解就是.
由上式可知
=120,
,
.
解上面的递归方程,可得当时有最小值
.
即第一周生产10台彩电,第二周生产50台彩电,第三周生产40台彩电,可获得最小费用6600.
18世纪初在东普鲁土有这样一个问题:某条河上有两个岛屿,?(如图1上图所示).