组合数学在计算机研究中的作用.doc

组合数学在计算机研究中的作用1 组合数学简介现代数学可以分为两大类：一类是研究连续对象的，如分析、方程等；另一类就是研究离散对象的组合数学。广义的组合数学就是离散数学，也有人认为离散数学是狭义的组合数学和图论、代数结构、数理逻辑等的总称。但这只是不同学者在叫法上的区别。总之，组合数学是一门研究离散对象的科学。狭义的组合数学主要研究满足一定条件的组态（也称组合模型）的存在、计数以及构造等方面的问题。计算机出现以后，由于离散对象的处理是计算机科学的核心，研究离散对象的组合数学得到迅猛发展。与传统的数学课程相比，组合数学研究的是一些离散的事物之间存在的数学关系，包括存在性问题、计数性问题、构造性问题以及最优化问题等，其主要内容是计数和枚举。计数问题是组合学中研究得最多的内容，它出现在所有的数学分支中。2 组合数学在计算机科学方面的作用对离散对象的处理是计算机科学的核心，而研究离散量的科学是组合数学。组合数学的发展奠定了20世纪计算机革命的基础，而计算机的出现又促进了组合数学本身的大发展。组合数学的萌芽可以溯源至公元前两千多年中国的大禹治水时代， 尽管它所涉及的有些问题最初是以数学游戏的形式出现的， 但在后来实际背景的影响下，获得了新的生命。随着计算机科学的发展，组合数学也在迅猛发展，而组合数学在理论方面的推进也促进计算机科学的发展。计算机软件空前发展的今天要求有相应的数学基础，组合数学作为大多数计算机软件设计的理论基础，它的重要性也就不言而喻。组合数学在计算机方面的应用极其广泛。计算机软件与各种算法的研究分不开，为了衡量一个算法的效率，必须估计用此算法解答具有给定长的输入(问题) 时需要多少步(例如算术运算、二进制比较、程序调用等的次数) 。这要求对算法所需的计算量及存储单元数进行估算，这就是计数问题的内容，而组合数学分析主要研究内容就是计数和枚举的方法和理论。当今计算机科学界的最权威人士很多都是研究组合数学出身的。美国最重要的计算机科学系（MIT，Princeton，Stanford，Harvard，Yale，。）都有第一流的组合数学家。计算机科学通过对软件产业的促进，带来了巨大的效益，这已是不争之事实。组合数学在国外早已成为十分重要的学科，甚至可以说是计算机科学的基础。中国在软件技术上远远落后于美国，而在组合数学上则更是落后于美国和欧洲。如果中国只是想在软件技术上跟着西方走，而不在组合数学上下功夫，那么中国的软件将一直处于落后的状态。组合数学无处不在，它的主要应用就是在各种复杂关系中找出最优的方案。我国在软件上的落后，要说出根本的原因可能并不是很简单的事，除了技术和科学上的原因外，可能还跟我们的文化，管理水平，教育水平，思想素质等诸多因素有关。除去这些人文因素以外，一个最根本的原因就是我国的信息技术的数学基础十分薄弱，这个问题不解决，我们就难成为软件强国。值得注意的是，印度有很好的统计和组合数学基础，这可能也是印度的软件产业近几年有很大发展的原因。中国的软件产业的发展已向数学基础提出了急切的需求：网络算法和分析，信息压缩，网络安全，编码技术，系统软件，并行算法，数学机械化和计算机推理，等等。此外，与实际应用有关的还有许多许多需要数学基础的算法，如运筹规划，金融工程，计算机辅助设计等。3 组合数学的基本思想组合数学其内容驳杂，方法繁多，对长期接受连续型数学的初学者而言， 往往感到抓不住要领， 无所适从， 特别是对繁多而新颖的各种组合方法感到茫然。组合数学中的很多方法， 如鸽巢原理、加法乘法法则、逐步淘汰法等等，对训练我们的组合思维，解决计算机算法中遇到的问题十分有益。组合数学有它特有的思想方法与技巧， 有很多方法简单得几乎不需要什么证明，但它可以用来解决许多有趣而且十分困难的问题，并能常常得到一些令人意想不到的结果。组合数学研究的问题有些看似简单，却很难得到解答。组合数学中有两种最常用的思想方法与技巧。一是对应与转化， 一是分类与递推。这两种思想方法在其他领域中与学科中也有广泛的应用。3。1对应与转化在两个事物之间建立一一对应，从而把一个组合问题转化成另一个组合问题。 这是解决组合计数问题常用的思想方法与技巧。在日常社会生活中， 我们常常用到这种思想方法。 如某次会议在有额定座位的大礼堂举行，要清查到会的人数， 有两种办法。一是直接数到会的人数，一是数空座位数。当到会的人数比较多时，后一种清查方法显然省事。只所以可以如此办事，是因为人数与座位数是一一对应的。例如有100名选手参加乒乓球比赛， 如果采用单循环淘汰制， 问要产生一个冠军需要进行多少场比赛?通常可以采用下面的方法来计算: 每两个选手一组， 先进行第一轮比赛， 要赛50场。得胜的50人再每两个选手一组进行第二轮比赛， 要赛25场，照这样分析总共要进行50+25+12+6+3+2+1=99场比赛。如果换一种思想考虑问题， 采用下面的方法计算，问题就变得简单多了。解: 因为每一场比赛要淘汰一个人，即淘汰一个人要进行一场比赛，现产生一个冠军，要淘汰99人，故要进行99场比赛。此法在组合数学中经常使用，其思想很容易理解。设有一个集合A，欲确定其元素的个数，如果直接求A 的元素的个数比较困难， 可找另一集合B，如果在集A与集B之间能建立一一对应关系，且B的元素的个数能确定，则A的元素个数也能得到。此法关键点是B的确定。3。2分类与递推把一个复杂的问题，切分成几块处理，并找出它们之间的关系，这就是分类与递推。分类在组合数学中使用频率也较高，特别是在组合恒等式的证明中使用较多。此方法的基本思想是：设有某一集合A，根据某一准则(具体问题具体确定) ，将A分成若干两两不交子集之并，再来解决所要解决的问题。把一个复杂的计数问题分割成若干块分别进行计算，如此得到一个递推公式，进而可以得到复杂问题的完全解决。在组合计数中到处都可以见到。通过对计数问题的分类从而导出一个递推公式，下面例子充分说明了这一点。从m个人中选n个人(mn) ，有种选法。这选法数也可以按照下面的办法实现，将从m个人中选n个人分为两类，一类含m个人中的某成员a，有种选法，另一类不含m个人中的成员a，有种选法，这是一个分类，因而有递推式=+当然，组合数学中，还有许多思想方法和技巧。比如，包含数学归纳法，容斥原理，生成函数，Polya定理等。这些方法是组合数学中最基本的方法，往往为人们所忽视。这些方法看似简单，但要灵活运用它们却是不易， 这些方法运用得好，往往能起到意想不到的效果，掌握好这些方法，对培养人们的组合思维十分有益。4 组合数学学习中应注意的问题作为一名计算机软件专业的博士生，应该充分认识到组合数学的重要性，在实际的学习中需要加强计算机数学即组合数学的学习。基于冯诺依曼体系结构的程序设计过程，是“分析问题建立数学模型选择数据结构设计算法翻译成计算机语言”的过程。在这个过程中，最后一步才是通常所说的编程序。所以，掌握数学的抽象思维十分重要，说其直接来源于组合数学的学习也不过分。计算机专业的组合数学学习的目的，一方面，给其他课程提供必要的数学基础；另一方面，通过学习组合数学，培养和提高了抽象思维和逻辑推理能力，为今后学习和工作，参加科学研究，攀登科技高峰，打下坚实的数学基础。在实际的学习的过程中要把重点放在思想方法学习上，并有意锻炼分析问题和解决问题的能力。创新意识和创新能力应该是研究生的基本而又重要的素质之一，组合数学中进行创新能力培养的内容很多，我们应该去发现、思考、解决和创新。比如，容斥原理的应用是比较抽象和困难的问题，应该对问题先思考什么，后考虑什么，再要想什么，这样按层次进行分析，使解决问题的思路清晰，层次分明，提高分析解决问题的能力。博士生的工作要体现有研究性，因此更需要这种创新能力，在学习组合数学中应该吸收各种问题解决的技巧。如组合数学中组合恒等式问题，至少已经发现有上千个组合恒等式，这些恒等式在许多计算分析中起着十分重要的作用。又如计数的问题，有原理、定理、公式、方法，内容很多，对于软件系统的开发有重大的帮助作用，可以有效的提高专业技术能力。5 实际应用组合数学解决计算机学科问题下面用一些实际的例子来体现组合数学在解决计算机算法问题中起到的作用。5。1容斥原理容斥原理是组合数学中重要的计数原理，国内外许多学者对容斥原理及其应用进行了研究。王光兴等研究了基于容斥原理的桥网络及无线通信网络的可靠性，提供了一个计算无线网络的ST可靠性算法和一个计算无线网络的ST可靠性算法。王光兴、孔繁甲基于容斥原理和不交和公式提出一个新的拓扑公式，改进了相应的Satyanarayanna算法。罗铸楷对布尔代数上自动机理论进行了研究，根据循环矩阵中的周期性、循环矩阵的解数和容斥原理提出了计算一般循环自动机的模型的具体步骤。吴国柱等研究了容斥原理在组合数学及数论中的若干应用。在国外，Kaniadakis等研究了由容斥原理产生相互作用粒子的非线性规范量子论。5。2禁位排列、棋盘多项式应用容斥原理可以求解限位排列和禁位排列问题。我国陈永川对容斥原理和限位排列的q-模拟进行了研究。谢云鹏等对一类限位数排列的计数问题进行了研究，利用广义容斥原理，给出了求解限位圆排列数的一般公式。韩玮等对相对禁排数的递推算法进行了研究，给出了相对禁排数的简单易行的递推算法。在国外，伦敦大学的Tarzi对当作限位排列对称的容斥原理进行了研究。Albert对限位排列与队列跳跃等进行了研究。Elizalde对用于精确限位排列的双射进行了研究。Atkinson对限位排列与环积进行了研究。棋盘多项式也称为车多项式，通过它可以求得各种禁排数。我国的宋传宁等利用棋盘多项式得到了两个恒等式。顾永跟提出一种用棋盘多项式求完美对集的算法。李有梅等给出了常用的两类禁区棋盘的棋盘多项式工州。德国的Oberschelp对匹配多项式与车理论进行了研究，给出了关于一个已知图的匹配多项式的一个算子公式。Fielder对车多项式的生成元进行了研究，提出并讨论了一种用于计算任意有穷棋盘的车多项式的容斥方法的表适应。Farren对匹配多项式及其与车多项式关系进行了研究。Nijenhuis做了关于积和式和车多项式的零点的研究。Yueh做了车多项式与色多项式间的系数关系的研究。Kremer对带有禁止子序列和不可分映射的排列进行了研究。5。3错位排列错位排列问题自古以来就是组合学发展史上的一个重要问题。从16世纪初的孟特马特研究的“相遇”的纸牌游戏开始，到随后的伯努利欧拉错装信封问题等，都是组合数学中经典的错位排列问题，其解决方式主要采用了组合学中的基本方法(递归法)和基本原理(容斥原理)。目前，该问题仍然吸引着众多的研究者。房亮等在基于错位排列、真假值行列式的概念及性质的基础上，提出了解错位排列的一种有效方法真假值行列式法。李志荣利用指数发生函数证明了错排问题，且利用错排数的指数发生函数得出了一组有关错排数问题的新的恒等式圆；周国平通过变更错排问题的限制条件，同时利用棋盘多项式的性质建立递归关系，从而推出了两个问题的排列数公式；Mikawa，Kenji等人通过最多交换四个元素来研究生成错位排列的方法；AMOS OLAGUNJU研究了使用反演表的方法来揭示错位排列区别于普通排列的系统特征。5。4正整数的分拆正整数的分拆问题是组合数学、图论、数论以及分析理论研究的重要课题之一，尤其在寻找各种分拆数的计数公式（递推关系，显式表达式）；寻找有关分拆数的恒等式（如Eu1er恒等式，Rogers-Ramanjuan恒等式）；对拆数P(n)上界的估计；对拆数的母函数的确定；对拆数性质的组合证明等始终都是分拆理论研究的重要课题，并且己经有了很丰富的成果。郭育红研究了正整数n的一些带约束条件的分拆问题，同时给出了计算其中三类分拆数的递推关系。陈星、王迪吉研究了满足一种条件的分拆，且得出了在该种条件下的计数公式，从而为一些整数分拆的计数提供了方便；郭秀英，孙秋杰对一类整数分拆问题，采用了构造证明的方法，给出了一个很好的性质，同时对K-长序列的计数问题利用反拆及排列的给出了间接的计数公式；王立欣等在论文“正整数n的m-分拆及其应用”中引入了两个新概念，正整数n的m-分拆和正整数n的真m-分拆，得出结论：n的分拆恰好是n的m-分拆的一个特例，而n的真m-分拆在二分图的(整)和图研究中有实际应用；Rodseth等人研究了如何来枚举一个正整数的M分拆及一个数m的M分拆的个数比；Hegyvari与Norbert研究了关于整数分拆的交叉特性。5。5排列组合排列组合的思想随着人类计数的需要而产生，是组合计数的基础，而组合计数所要解决的主要问题则是求满足一定条件的总方案数。排列组合作为组合学中的两个基本概念，在实际生活中不仅应用广泛，而且在培养人的数学能力、思维能力，提高人的综合素质方面所起的作用也是功不可没的，因此古今中外不少学者都对其尤其是对排列数和组合数进行了深入的研究。赵天玉从组合的杨辉三角出发，利用编码映射和树结构遍历的方法，设计出了两个新的组合生成算法，并且给出了组合构造与其序号之间的函数对应关系；齐鑫，修丽强等依据软件工程的思想，提出了一种利用哈希表对键进行排序，间接操作排列元素，求解全排列的方法；李欣，范慧玲等提出了一种实现从多个集合当中的每个集合中选取一个元素以形成一种方案从而生成所有可能的组合方案的算法；李曼生在“全排列问题的求解算法及相关应用”论文中给出了1至n的全排列问