组合数学-浅谈组合数学与计算机科学

《组合数学-浅谈组合数学与计算机科学》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、浅谈组合数学与计算机科学摘要：组合数学，又称为离散数学，是一门研究离散对象的科学。组合数学是计算机出现以后迅速发展起来的一门数学分支，随着计算机科学的日益发展，组合数学的重要性也日渐凸显。关键词：组合数学计算机欧拉回路Abstract:Thecombinationofmathematics,alsoknownasdiscretemathematics,isastudyofdiscreteobjects.Acombinationofcomputermathematicsisabranchofmathematicsdevelopedrapidlysince,withtheincreasingimp

2、ortanceofthedevelopmentofcomputerscience,combinatorialmathematicshasbecomemoreprominent.Keywords:CombinatoricsComputerEulercircuit1.组合数学简述组合数学是一门古老而又新兴的数学分支。我国古人早在《河图》、《洛书》中已对一些有趣的组合问题给出了正确的解答。近代随着计算机的出现,组合数学这门学科得到了迅猛的发展,成为了一个重要的数学分支。组合数学的发展改变了传统数学中分析和代数占统治地位的局面。组合数学主要研究符合一定条件的组态对象、计数及构造等方面的问题。离散构形问

3、题是组合数学的主要研究内容，主要包括：①构形构形的存在性问题；②构形的构造性问题；③构形的计数问题；④构形的最优化问题。现代数学可以分为两大类：一类是研究连续对象的，如分析、方程等;另一类就是研究离散对象的组合数学。组合数学不仅在基础数学研究中具有极其重要的地位，在其它的学科中也有重要的应用，如在计算机科学、编码和密码学、物理、化学、生物等学科中均有重要应用。微积分和近代数学的发展为近代的工业革命奠定了基础。而组合数学的发展则是奠定了本世纪的计算机革命的基础。电子计算机处理的信息，都是仅用“0”与“1”两个简单数字表示的信息，或者是用这种数字进行了编码的信息。所以离散对象的处理就成了计算机科学

4、的核心，而组合数学是一门研究离散对象的科学。现代数学的研究内容主要包括两个方面：一方面类是研究连续对象的，如分析、代数等，另一方面就是研究离散对象的组合数学。2.组合数学的几种基本思想方法除了各种形式的数学归纳法之外,那就是映射原则,(2)递归原则,(3)序化原则,(4)反演原则。这四大原则在处理各类组合学问题时又进一步具体化为种种技巧,因此又可叫作映射技巧(包括双射技巧、变换技巧、生成函数技巧等),递归技巧,序化技巧(包括偏序化技巧、良序化技巧)及嵌入反演技巧等。无论是组合计数问题或是结构分析问题,映射法是最常用也是最有效的方法。但如何引用合适的映射去解决间题往往需要洞察力和技巧。递归原则常

5、用于处理“应用组合学”问题,它是一种特殊的数学模型方法,因为由递归分析导出的差分方程及初始条件往往可以看成为原型间题的数学模型。序化原则(Prineipleofordering)是“计算组合学”(Computational。ombinatories)中最基本的方法原则。事实上,任何组合计算对象只有经过适当的序化后,即经过良序化或者偏序化之后才能上机去计算。嵌入反演技巧是发现和证明各种代数组合恒等式的重要方法,有时也可用来求解包含未知函数的代数组合方程。以上所述只是经典组合数学中的常见方法,是属于组合学内部体系中的方法。事实上,现代组合学还借用了其他学科的许多方法,例如代数学诸分支中的方法、解析

6、函数论方法、渐近分析方法、数论方法、概率论及统计数学方法等。近年以来,非标准分析方法也已开始进入组合数学领域,但成果还不多,正待继续发展。3.组合数学中经典问题组合数学中的经典问题主要包括：①棋盘完美覆盖；②切割立方体；③幻方；④四色问题；⑤36军官问题；⑥最短路径；⑦NIM取子问题；⑧羊狼菜过河问题；⑨中国邮递员问题；⑩稳定婚姻问题。以下重点介绍四色问题和中国邮递员问题。3.1四色问题四色问题即使用四种不同的颜色对世界地图着色，要求相邻国家的颜色相异。采用数学语言对本问题进行形式化描述如下：将平面任意地细分为不相重迭的区域，每一个区域总可以用1，2，3，4这4个数字之一来标记，而不会使相邻的

7、两个区域得到相同的数字。一个多世纪以来，在四色问题的研究证明过程中，由于对象问题复杂且缺乏数学通常的解题规范，人工直接验证不可行。本世纪70年代，电子计算机的迅速发展和广泛应用使四色问题的研究出现了转机。美国伊利诺斯大学的阿佩尔、哈肯等人在研究了前人各种证明方法和思想的基础后，从1972年起，开始了用计算机证明四色问题的研究工作。终于在1976年彻底解决了四色问题，整个证明过程在计算机上花费了12