《组合数学》PPT课件.ppt

1,组合数学 RichardA.Brualdi 著 冯舜玺 等 编译 机械工业出版社,任课教师： 廖 虎,2,办公室：软件学院四楼专业教研室 办公电话：8 8 4 5 1 1 2 8,住宅电话：8 2 4 9 5 8 7 4 移动电话：1 3 0 9 6 9 8 1 1 8 2 电子邮件：xaL,3,绪 论 组合数学是一门古老的数学分支，其思想在社会科学、信息论、生物科学以及其他传统自然科学领域得到了广泛的应用。组合数学在计算机出现以后得以迅速发展。计算机科学就是算法的科学，而计算机所处理的对象是离散的数据，所以离散对象的处理就成了计算机,4,科学的核心，而研究离散对象的科学恰恰就是离散数学和组合数学；组合数学的发展改变了传统数学中分析和代数占统治地位的局面。现代数学可以分为两大类：一类是研究连续对象的，如分析、方程等，另一类就是研究离散对象的组合数学。组合数学不仅在基础数学研究中具有极其重要的地位，在其它的学科中也有重要的应用，如计算机科学、编码和,5,密码学、物理、化学、生物等学科中均有重要应用。微积分和近代数学的发展为近代的工业革命奠定了基础。而组合数学的发展则是奠定了本世纪的计算机革命的基础。计算机之所以可以被称为电脑，就是因为计算机被人编写了程序，而程序就是算法，在绝大多数情况下，计算机的算法是针对离散的对象，而不是在作数值计算。,6,正是因为有了组合算法才使人感到，计算机好象是有思维的。 组合数学不仅在软件技术中有重要的应用价值，在企业管理，交通规划，战争指挥，金融分析等领域都有重要的应用。在美国有一家用组合数学命名的公司，他们用组合数学的方法来提高企业管理的效益，这家公司办得非常成功。,7,此外，试验设计也是具有很大应用价值的学科，它的数学原理就是组合设计。用组合设计的方法解决工业界中的试验设计问题，在美国已有专门的公司开发这方面的软件。最近，德国一位著名组合数学家利用组合数学方法研究药物结构，为制药公司节省了大量的费用，引起了制药业的关注。,8,组合数学与计算机软件 随着计算机网络的发展，计算机的使用已经影响到了人们的工作，生活，学习，社会活动以及商业活动，而计算机的应用根本上是通过软件来实现的。在美国有一种说法：将来一个国家的经济实力可以直接从软件产业反映出来。,9,我国在软件上的落后，要说出根本的原因可能并不是简单的事，除了技术和科学上的原因外，可能还跟我们的文化(汉字)，管理水平，教育水平，思想素质等诸多因素有关。除去这些人文因素以外，一个最根本的原因就是我国的信息技术的数学基础十分薄弱，这个问题不解决，我们就难成为软件强国。,10,然而问题决不是这么简单，信息技术的发展已经涉及到了很深的数学知识，而数学本身发展程度并不是单凭几个聪明的头脑去想想就行了，而更重要的是需要集体的合作和力量，就象软件的开发需要多方面的人员的合作。美国的软件之所以能领先，其关键就在于在数学基础上他们有很强的实力，有很多杰出的人才。,11,一般人可能会认为数学是一门纯粹的基础科学，1+1的解决可能不会有任何实际的意义。如果真是这样，一门纯粹学科的发展落后几年，甚至十年，关系也不大。然而中国的软件产业的发展已向数学基础提出了急切的需求：网络算法和分析、信息压缩、网络安全、编码技术、系统软件、并行算法、数学机械化和计算机推理,12,等等。此外，与实际应用有关的还有许多许多需要数学基础的算法，如运筹规划，金融工程，计算机辅助设计等。如果我们的软件产业还是把眼光一直盯在应用软件和第二次开发，那么我们在应用软件这个领域也会让国外的企业抢去很大的市场。如果我们现在在信息技术的数学基础上，大力支持和投入，那将是亡羊补牢，犹未为晚；,13,胡锦涛同志在1998年接见“五四”青年奖章获得者时发表的讲话中指出：组合数学是不同于传统的纯数学的一个分支，它还是一门应用学科，一门交叉学科。他希望中国的组合数学研究能够为国家的经济建设服务。 如果21世纪是信息社会的世纪，那么21世纪也必将是组合数学大有可为的世纪。,14,组合数学课每周上课两次，4学时，安排14周，共56学时。根据教学计划和培养目标要求，我们学习以下内容： 第一章 什么是组合数学 第二章 鸽巢原理 第三章 排列与组合 第四章 生成排列与组合 第五章 二项式系数 第六章 容斥原理及其应用 第七章 递推关系与生成函数第八章特殊计数序列,15,考核方式：期末笔试占70%，平时作业占30%， 每星期一交一次作业。由各个班长送到四楼办公室。 本课件制作由廖虎独立完成，该课件几乎可以取代教材，已经公布在学院公共实验室网上，同学们可以自己下载浏览。,16,第1章 什么是组合数学 组合数学是一门古老的数学分支，其思想在社会科学、信息论、生物科学以及其他传统自然科学领域得到了广泛的应用。组合学问题在生活中随处可见。在计算机科学领域，组合数学是算法设计理论以及算法分析理论的重要数学工具。,17,例如，计算下列赛制下总的比赛次数：n个球队参赛，每队只和其他队比赛一次;创建幻方;在纸上画一个网络，用铅笔沿着网络的线路走，在笔不离开纸面且不重复线路的条件下，笔画出网络图(一笔画);在玩扑克牌游戏中，计算满堂红(fullhoue)牌的手数，以确定出现一手满堂红牌的几率。所有这些都是组合学问题。,18,正如人们想到的，组合数学的历史渊源扎根于数学娱乐和游戏之中。过去研究过的许多问题，不论出于消遣还是出于对其美学的考虑，如今在纯科学和应用科学中都具有高度的重要性。今天，组合数学是数学的一门重要分支，而且它的影响还在继续扩大。组合数学自60年代以来急速发展的部分原因,19,就在于计算机在我们的社会中所发挥的重要影响，而且这种影响还在继续发挥。 组合数学近期发展的另一个原因是它对于那些过去很少与数学正式接触的学科的适用性。由此我们发现，组合数学的思想和技巧不仅正在用于数学应用的传统自然科学领域，而且也用于社会科学、生物科学、信息论等领域。,20,组合数学涉及到将一个集合的物体排列成满足一些指定规则的格式。如下两类一般性问题反复出现： 排列的存在性：如果有人想要排列一个集合的成员使得某些条件得以满足，那么这样一种排列是否可行就显而易见的。这是最根本的问题。如果这种排列不总是可能的，那么我们要问，这种,21,排列在什么样的(必要和充分)条件下能够实现？ 排列的计数和分类：如果一个指定的排列是可能的，那么就会存在多种方法去实现它。此时，人们就可以计数并将它们分类。 研究一个已知的排列：当人们建立起满足某些指定条件的一个排列(可能不容易)以后，可能要考察这个排列的性质和结构。,22,这样的结构可能会涉及到分类问题，也许还涉及到一些潜在的应用，它还可能牵扯到下面的问题。 构造一个最优的排列：如果有可能存在多于一个的排列，人们也许想要确定满足某些优化准则的一个排列，即找出某种规定意义下的“最好的”或“最优的”的排列。,23,因此，组合数学可以一般地描述为：组合数学是研究离散结构的存在、计数、分析和优化等问题的一门学科。 虽然某些离散结构是无限的，但本书一般把离散视为有限的。,24,一、问题描述 假设有一张普通国际象棋棋盘和32张domino牌，其形状如下:88象棋棋盘, 一张12格的多米诺牌 domino 牌。,第一章 什么是组合数学 1.1 棋盘的完美覆盖,25,每张牌恰好覆盖棋盘上相邻的两个方格。 问题（棋盘的完美覆盖问题）：是否能够把32张domino牌摆放在棋盘上，使得任何两张domino牌均不重叠，每张domino牌覆盖两个方格，并且棋盘上所有方格都被覆盖住？如果存在这种完美覆盖，那么总共有多少种不同的完美覆盖？结论：国际象棋棋盘的不同的完美覆盖总共有： 249012 = 12988816种,26,这种普通的国际象棋棋盘可以用排成m行n列的mn个方格的一般棋盘代替。此时，这种棋盘的完美覆盖就未必存在了。比如，3行3列的棋盘就确实不存在完美覆盖。那么，对于什么样的m和n存在完美覆盖呢?不难看出，当且仅当m和n中至少有一个是偶数时,mn棋盘存在完美覆盖。或者说，当且仅当棋盘的方格数是偶数时， mn棋盘存在完美覆盖。,27,再来考查用12格的多米诺骨牌覆盖去掉了两个对角处格子的88残缺棋盘，问能否用31枚骨牌完美覆盖？ 答案是否定的。证明方法很巧妙，可以先将88棋盘黑白间隔染色，去掉的两个对角处格子不是同白，就是同黑。因此，88残缺棋盘剩余的64-2=62个格子中黑格数与白格数相差为2。反之，,28,白,白,白,白,白,白,白,白,黑,黑,黑,黑,黑,黑,黑,黑,黑,黑,31,若设能用31枚12格的骨牌，若每枚覆盖相邻的2个方格，恰将残缺棋盘砌满，,29,则黑格数与白格数应该相等。这就产生了矛盾。因此，不存在要求的覆盖。如果对不去掉对角处格子的64格88完好棋盘，则存在用32枚12格的骨牌恰将其覆盖的许多方法。这时要讨论的就是确定有多少种不同覆盖方法的计数问题。,32,黑,+30,白,31,30,第一章 什么是组合数学 1.2 切割立方体,1.2 切割立方体 把一个333的立方体木块切割成27个111的小立方块。如果切割过程中允许重新排列已切割木块的位置，求完成整个切割的最 少次数。 这里的最优即指具有最少切割次数的方案，,31,采用穷举方案并比较切割次数的方法一般不可取。 本例的解法是先指出6次即可完成全部切割，即水平切2次，竖直、交叉各切2次。其次， 可以证明少于6次不能完成题目要求的切割。事实上，对中心位置产生的小立方体而言，因其也具有6个面且每个面都须被独立地切割一次才能出现。故至少需要6次才能切割完，见书中P5。,32,第一章 什么是组合数学 1.3 幻方,1.3 幻方 幻方也称为洛书、河图等，传说大禹治水时， 从河中浮起一只乌龟，乌龟的背上画有一个33 的九个方格子，格子中填有从1,29九个数，填写的规则是：横、竖、斜各自格子中数之和相等。,33,左图称为幻方，右图称为幻圆，观察幻圆的数字结构，紫色框里的数字之差的绝对值相等；沿蓝色线的数字之和相等。大家有精力也能再找出其他的数字关系来。,34,一个n阶幻方是由数字1，2，3，n2组成的nn方阵，使得方阵中每行上的数字和、每列上的数字和以及每条对角线上的数字和均等于同一个数S。称S为该幻方的幻和。 中国历史上研究33 = 9幻方也称为“九宫填数”；,35,一个n阶幻方中所有数字的和为： 1 + 2 + 3 + + n2 = =nS 故它的幻和为 S = 正好是一行(列)上数字的和，从而, 关于幻方的问题可归结为: ,36,(1) 对任意的正整数n，n阶幻方存在吗？ (2) 对某个正整数n，如果n阶幻方存在，有多少不同的形式？ (3) 构造存在的n阶幻方。 注意，给出一种算法，不仅要描述算法的步骤，而且要证明算法的正确性，并对算法进行时间分析。,37,下面是构造的7阶幻方，幻和为175 ：,38,不难看出，不可能存在2阶幻方； 够成幻方的方阵转置后仍然是个幻方。 本书中给出了n为奇数时构造幻方的方法和立体幻方的概念，由于时间和难度的关系，我们就不用再讨论。,39,第一章 什么是组合数学 1.4 四色问题,1.4 四色问题 在一张地图中每个国家均是一个连通的区域，现对地图中的每个国家着色，使得具有共同边界的两个国家涂成不同的颜色，完成这项工作至少需要几种颜色？在离散数学中我们利用对偶图已经证明用5种颜色可以对地图着色。,40,四色定理叙述起来简单，理解起来容易，它与 著名的三等分角问题一样 吸引着众多的非专业人员。 1890年heawood证明了用 5种颜色对任何地图着色。,4,2,3,1,41,第一章 什么是组合数学 1.5 36军官问题与拉丁方,1.5 36军官问题与拉丁方 设有6个不同军衔和来自6个不同团队的36名军官，问能否将他们排成66方阵，使得每行每列均有各种军衔的军官1名，并且每行和每列上的不同军衔的6名军官还分别来自不同的军团？,42,我们把一个军官表示为一个序偶（i，j），其中i表示该军官的军衔（i1，2，6），而j表示他所在的军团（j1，2，6），于是上述36军官问题可用数学语言描述成： 36个序偶（i，j）能否排成66方阵，使得这6个整数都能分别以某种顺序出现在序偶的第一个或第二个元素位置上？,43,或者：是否存在这样的两个66矩阵，其元素取自1，2，6，使得 1整数1，2，6以某种顺序出现在矩阵的每一行和每一列； 2当这两个矩阵并置时，所有36序偶（i，j） （i1，2，6）全部出现。,44,军团矩阵,军衔矩阵,以9名军官为例，设i=1, 2, 3表示军官的军衔，j=1, 2, 3 表示军官的团队，则每个军官对应一个序偶(i, j)。从而可以排出：,45,分别 我们把具有上述性质1的两个66矩阵均称为6阶拉丁方。这两个6阶拉丁方若同时具有上述性质2，则称它们是正交的。 于是36军官问题又可描述为：是否存在两个正交的6阶拉丁方？,46,第一章 什么是组合数学 1.6 最短路径问题 (14),1.6 最短路径问题 从甲地到乙地存在许多可能的路径。我们的问题是如何确定从甲地到乙地的距离最短的路径