专业硕士学位论文计算机中的组合数学作者姓名学科专业工程数学指导教师培养院系Application of the Wavelet Analysis in the Fault Diagnosis of Rotating MachinesThe combination of mathematicsin the application of software engineeringCandidate：Supervisor：Beihang University, Beijing, China关于学位论文的独创性声明本人郑重声明：所呈交的论文是本人在指导教师指导下独立进行研究工作所取得的成果，论文中有关资料和数据是实事求是的。
尽我所知，除文中已经加以标注和致谢外，本论文不包含其他人已经发表或撰写的研究成果，也不包含本人或他人为获得北京航空航天大学或其它教育机构的学位或学历证书而使用过的材料。
与我一同工作的同志对研究所做的任何贡献均已在论文中作出了明确的说明。
若有不实之处，本人愿意承担相关法律责任。
学位论文作者签名：日期：年月日学位论文使用授权书本人完全同意北京航空航天大学有权使用本学位论文（包括但不限于其印刷版和电子版），使用方式包括但不限于：保留学位论文，按规定向国家有关部门（机构）送交学位论文，以学术交流为目的赠送和交换学位论文，允许学位论文被查阅、借阅和复印，将学位论文的全部或部分内容编入有关数据库进行检索，采用影印、缩印或其他复制手段保存学位论文。
保密学位论文在解密后的使用授权同上。
学位论文作者签名：日期：年月日指导教师签名：日期：年月日摘要20世纪的大事, 它改变了我们这个世界的面貌, 也带来了组合数学这个古老学科的再度辉煌, 本文从什么是组合数学、组合数学的几个著名问题以及计算机科学中的组合数学几个方面入手, 展示组合数学辉煌的明天…………………关键词：组合数学；离散数学；计算机科学Abstract20th century events, it has changed the face of our world, it also brings a combination of mathematical brilliance of this ancient discipline once again, what this paper is a combination of mathematics, combinatorics, and several well-known problem in combinatorics in computer science a few aspects, showing a brilliant future combinatorics…………………Key words:Combinatorial mathematics; discrete mathematics; Computer Science第一章组合数学的概念有人认为广义的组合数学就是离散数学, 也有人认为离散数学是狭义的组合数学和图论、代数结构、数理逻辑等的总称。
但这只是不同学者在叫法上的区别。
总之, 组合数学是一门研究离散对象的科学, 是计算机出现以后迅速发展起来的一门数学分支。
计算机科学是算法的科学, 而计算机所处理的对象大多是离散的数据, 所以离散对象的处理就成了计算机科学的核心。
现代数学分为两大类: 一类是研究连续对象的, 如分析、方程等, 另一类就是研究离散对象的组合数学。
组合数学是计算机科学、编码和密码学、物理、化学、生物等学科的理论基础, 也在企业管理、交通规划、战争指挥、金融分析、项目开发等领域起着重要作用。
微积分和近代数学的发展为近代工业革命奠定了基础, 而组合数学的发展则是奠定了现代计算机革命的基础。
计算机借助于程序来运行, 而程序就是算法, 计算机算法主要针对的是离散的对象, 正是因为有了组合算法才使计算机能够帮助人们决实际的种种问题, 成为人们生活、工作、研究的重要工具。
狭义的组合数学主要研究符合一定条件的组态对象、计数及构造等方面的问题。
组合数学研究的对象就是离散构形问题, 主要包括:构形是否存在, 即构形的存在性问题;如何做出构形, 即构形的构造性问题;可做出多少种不同的构形,即构形的计数问题;1/4找出最理想的构形, 即构形的最优化问题。
第二章组合数学中的几个著名问题1、地图着色问题地图着色问题即对世界地图着色, 每一种国家使用一种颜色。
如果要求相邻国家的颜色相异, 是否总共只需4种颜色?1852年,毕业于伦敦大学的弗南西斯·格思里(FrancisGuthrie)在一家科研单位从事地图着色工作时,发现“任何一张地图似乎只用四种颜色就能使具有共同边界的国家着上不同的色”。
用数学语言来表示,即“将平面任意地细分为不重迭的区域,每一个区域总可以用1,2,3,4这4个数字之一来标记,而不会使相邻的两个区域得到相同的数字一个多世纪以来,在“四色猜想”的研究证明过程中,由于对象问题复杂且缺乏数学通常的解题规范, 难以由人工直接验证,所以计算机科学工作者开始借助于计算机的帮助。
由此产生不少新的数学理论, 也发展了很多数学计算技巧, 如将地图的着色问题化为图论问题,丰富了图论的内容, 所引进的概念与方法刺激了拓扑学与图论的生长、发展。
不仅如此,“四色猜想”在有效地设计航空班机日程表,设计计算机的编码程序上都起到了推动作用。
1996年, NeilRobertso、Danielsan ders、PaulSeymour和RobinThomas等人使用电脑核查了633种特殊的状态对此问题进行了证明。
地图四色猜想是第一个主要由计算机完成证明的数学难题。
但是人们并不满足于计算机取得的成就,他们认为应该有可能存在一种更加简捷明快的书面证明方法。
所以直到现在,仍然有不少的数学家和众多数学爱好者都在寻找更简洁的证明方法。
2 、船夫过河问题在中小学的数学游戏中,有这样一个问题,一个船夫要把一只狼,一只羊和一棵白菜运过河。
问题是当人不在场时,狼要吃羊,羊要吃白菜,而他的船每趟只能运其中的一个。
他怎样才能把三者都运过河呢? 这就是一个很典型的线性规划的问题3 、中国邮差问题一个邮递员从邮局出发,要走完他所管辖的街道,也就是每一条路至少一次,他应该怎样选择什么样的路径,使路程最短。
这就是著名的“中国邮递员问题”,由中国组合数学家管梅谷教授提出,著名组合数学家J.Edmnds和他的合作者给出了一个解答。
这个问题存在多项式复杂度算法: 即先求出度为奇数的点,用匹配算法算出这些点间的连接方式,然后再用欧拉路径算法求解。
这是图论的问题。
第三章组合数学与计算机软件3.1 信息时代的组合数学现代数学可以分为两大类:一类是研究连续对象,如分析、方程等,另一类就是研究离散对象的组合数学。
计算机科学就是算法的科学,而计算机所处理的对象是离散的数据,研究离散对象的科学恰恰就是组合数学。
因此,在信息时代的今天,组合数学就是信息时代的数学。
3.2 组合数学在计算机软件的应用随着计算机科学的发展,组合数学也在迅猛发展,而组合数学在理论方面的推进也促进计算机科学的发展。
计算机软件空前发展的今天要求有相应的数学基础,组合数学作为大多数计算机软件设计的理论基础,它的重要性也就不言而喻。
组合数学在计算机方面的应用极其广泛。
计算机软件与各种算法的研究分不开,为了衡量一个算法的效率,必须估计用此算法解答具有给定长的输入(问题) 时需要多少步(例如算术运算、二进制比较、程序调用等的次数) 。
这要求对算法所需的计算量及存储单元数进行估算,这就是计数问题的内容,而组合数学分析主要研究内容就是计数和枚举的方法和理论。
3.3 组合数学在国外软件业的发展状况纵观全世界软件产业,美国处于绝对的垄断地位。
造成这种现象的一个根本原因就是计算机科学在美国的飞速发展。
当今计算机科学界的最权威人士很多都是研究组合数学出身的。
美国最重要的计算机科学系(MIT,Princeton,Stanford,Harvard,Yale, ⋯⋯) 都有第一流的组合数学家。
组合数学在国外早已成为十分重要的学科,甚至可以说是计算机科学的基础。
一些大公司,如IBM,A T&T 都有全世界最强的组合研究中心。
美国政府也成立了离散数学及理论计算机科学中心DIMACS (与Princeton 大学,Rut gers 大学,AT&T 联合创办的,设在Rutgers 大学) ,该中心已是组合数学理论计算机科学的重要研究阵地。
第四章计算机化简汉诺塔问题4.1 问题来源汉诺塔( Hanoi tower ) 问题源自一个古老的传说, 相传在古印度的一座神庙前, 有一根串着64 个祭神用的圆盘的柱子, 这些圆盘是按大小顺序叠放的, 大的在下, 小的在上, 僧侣们要将这些圆盘借助一个柱子移到另一个柱子上, 移动过程中一次只能移动一个, 并且要始终保证每个柱子上的圆盘大的在下, 小的在上，什么时候移完，就意味着世界末日的到来。
现我们假定三根柱子A、B、C, 圆盘的数量为n。
问题的图形描述如图1所示：4.2 分析问题当盘子数为2时,只需要将上面的一个盘子从A搬到B上,再将A柱的最下面的盘子从A 搬到C 柱上, 最后把B 上的盘子搬到C 柱上即可, 搬运次数为3次;现我们假定盘子数n时,把A柱上面的n-1盘子看成一个整体, 并设把A柱上的n-1个盘子搬到B上, 设需要的搬运次数为hn-1,则n个盘子的搬运过程类似于2个盘子,即把A柱上的n-1个盘子从A搬到B柱上,搬运次数为hn-1,再把A柱的最下面的盘子从A 搬到C柱上,搬运次数为1次,最后把B上的盘子搬到C柱上,搬运次数同样也为hn-1,总共的搬运次数为hn=2*hn-1+1。
4.3 基于JAVA 的解决方案由公式我们可以利用递推关系解决汉诺塔问题。
以下为程序中的类图。
图中出现了两个类, 类hannut a 主要用于进行递归调用, 谨记要设置递归出口; 类hannuta 1 进行输入、调用类hannut a进行递归、输出显示结果, 其中属性sum1用于存放最终结果, 字符串变量ns 来获取对话框中的字符, 属性n 则存放柱子上的圆盘数。
程序段如下:hannut a hh = new hannut a( ) ; / / 声明一个新类ns= JOpt ionPan e. sh owInp utDialog( "inputa number") ; / / 显示对话框n = Int eger. pars eInt ( n s) ; / / 从对话框获取数据, 并转换成整数sum1= hh.jiajia( n) ; / / 调用方法System.out.println( "sum = "+ sum 1) ; / /输出结果class hannuta/ / 命名类{ long jiajia( int n) / / 定义方法, 实现递归{long sum= 0; / / 存放递归结果if ( n= = 1) / / 递归出口sum = 1;elsesum = 2* jiajia( n- 1) + 1; / / 递归调用return sum; } / / 返回数值}4.4 结合组合数学化简问题上面用递推关系解答了这个计数问题, 现用母函数为工具求得计数序列的通用表达式, 从而化简递推关系。