计算机2011组合数学—CH.ppt

组合数学,吉林大学 计算机科学与技术学院 2011年9月,关于我,姓名：卢奕南 单位：图像处理与虚拟现实研究团队 主要研究方向：图像处理、模式识别,关于教材,内部试用版本 时间：下周一下午 地点：计算机大楼 A413 价格：每本20元 组织：请各班班长带着本班的教材费前来领取 电话参考书： 机械工业出版社：组合数学，布鲁迪 (Brualdi R.A.) (作者), 冯舜玺 (译者) 清华大学出版社：组合数学，卢开澄等 上网习题 组合数学（姜建国等），西安电子科技大学,本学期涉及到的内容： 鸽巢原理和Ramsey定理（存在性问题） 基本计数方法 容斥原理 生成函数 递推关系 Plya定理,怎样学好组合数学,组合数学经常使用的方法并不高深复杂。最主要的方法是 计数时的合理分类 组合模型的转换（一一对应）。 组合分析 数学归纳法 反证法 要学好组合数学并非易事，既需要一定的数学修养，也要进行相当的训练。 可从规模小的模型着手，从中找到规律性的东西，再推及一般。 你解决的问题越多，那么你能够解决下一个问题的可能性也越大。,7,第一章 引言,组合数学(简称组合学）是数学的一个分支, 它起源于古代的娱乐和休闲游戏。后来这些问题逐渐与数论、概率统计、拓扑学、线性规划等学科的问题交织在一起，逐渐形成一种理论。 广义的组合数学就是离散数学， 离散数学是狭义的组合数学和图论、代数结构、数理逻辑等的总称。 工程认证,组合数学中的著名问题,组合数学的起源,幻方最早记载于我国公元前500年的春秋时期大戴礼中，这说明我国人民早在2500年前就已经知道了幻方的排列规律。而在国外，公元130年，希腊人塞翁才第一次提起幻方 ； 公园1275年（宋代），杨辉的著作中出现10阶幻方问题和杨辉三角的记载； 1666年，莱布尼茨发表组合的艺术(De Art Combinatoria)，这是组合数学的第一部专著。书中首次使用了组合论（Combinatorics）一词。标志组合数学的诞生。 莱布尼茨：德国最重要的自然科学家、数学家、物理学家、历史学家和哲学家，一个举世罕见的科学天才，和牛顿（1643年1月4日1727年3月31日）同为微积分的创建人。 杨辉，中国南宋时期杰出的数学家和数学教育家。,组合分析和组合算法已经被广泛应用与计算机科学、管理科学、信息科学、电子工程、人工智能、生命科学等诸多领域中。,11,组合数学的蓬勃发展则是在计算机问世和普遍应用之后。 一方面，当我们研究的组合问题规模很大的时候，计算量会很大，计算机为求解这些问题提供了有力手段。 另一方面，在计算机科学的算法研究中 数据结构+算法+编程语言 时间复杂性和空间复杂性 计算复杂性理论、 算法设计与分析的基础课。,什么是组合数学,组合数学就是研究按照一定的规则来安排一些离散个体的问题。它涉及面广，内容庞杂（涉及到组合分析、图论、组合算法、近代密码学、编码理论等），并且仍在很快地发展着，因而还没有一个统一而有效的理论体系。 研究的对象是离散结构，一般可以用1，2，、，n表示。本书仅限于讨论n是有限的自然数的情况。 组合数学是研究离散结构的存在、计数、分析和优化等问题的一门学科。,13,组合数学的主要问题,（1）存在性问题 满足一定条件的安排的存在性. 如果某种安排不一定总存在，我们就需要研究存在的条件。 存在性是数学研究最重要的问题之一. 许多问题的存在性至今也无法解决？ 例如数论中很多难题：哥德巴赫猜想,（2）安排的枚举、分类和计数 如果所要求的安排存在，则可能有多种不同的安排。此时，需要计数不同的方案数，并将它们进行枚举和分类。 当实际问题比较复杂的时候，必须有好的数学方法来解决.,（3）构造性问题 一个组合问题，如果已经判定解是存在的，那么将所有可能的安排构造出来是一个关键问题。 与计算机算法密切相关 典型问题：组合设计,（4）优化问题 在给定的优化条件下从所有的安排方案中找出最优的安排方案。 旅行商问题(Traveling Salesman Problem ，简称TSP) 与算法分析密切相关 传统方法 现代智能方法,17,幻方问题有趣的数学游戏 幻方在娱乐数学中的地位以及它的意义非同一般，它是中国人的首创。 公元前2200年易经提到洛书与河图,1.1 幻方问题,一个n阶幻方是由整数1，2，3，n2按下述方式组成的nn方阵：该方阵每行上的整数的和、每列上的整数的和以及两条对角线中每条对角线上的整数的和都等于同一个数s,19,3阶幻方的所有整数和为15；,每一行（或列或对角线）数字的和称为幻方的和（幻和）： S= n (n2+1)/2 。,关于幻方的问题归结为 （一）存在性问题 对任意的正整数n，n阶幻方存在吗？ （二）组合计数问题 如果存在，那么应该有多少个不同的 n阶幻方。 （三）构造问题 奇数阶幻方：连续摆数法(de La Loubre法) 双偶数（4k）阶幻方：对称法 单偶数(4k+2)阶幻方：斯特雷奇法（1918）,2019年5月16日,21,（一）幻方的存在性问题 例1.1 证明了不存在2阶幻方。 对其余的正整数n，由于n阶幻方都能构造出来，当然就证明了（正整数）阶幻方的存在性。,22,例 1.1 证明不存在2阶幻方,证明：反证法。假定存在2阶幻方，如图所示：,根据幻方的定义，它的幻和是5，于是a1+ a2= a1+ a3=5，可得a2= a3，因为a1，a2，a3， a4必定彼此不同，所以不可能，矛盾。因此不存在2阶幻方。,2019年5月16日,23,（二） 幻方的构造性问题 （1）奇数阶幻方的构造,连续摆放法（de la Loubre法）。 规则为：假定构造n阶（n为奇数）幻方。 首先将1放在(n+1)/2列第1行的方格中， 然后按照副对角线方向（即行号减1，列号加1）依次把从小到大的各个数字放入相应的方格中。,2019年5月16日,24,如果行号变成0（第1行上面一行），则改成第n行相应列对应的方格。 如果列号变成n+1（第n列右面一列），则改成第1列相应行对应的方格。 如果轮到的方格已经填有数字或者到了第0行第n+1列对应的方格，则退到前一个方格正下方的方格。,25,例1.2 利用连续摆放法构造5阶幻方,即行号减1，列号加1,26,（2）偶数阶幻方的构造 当n=4k的时候，即双偶数的情况， 对称法。 先把nn的方阵分成上、下、左、右四个2k2k的方阵。 然后对于左上的2k2k方阵进行处理，每行每列任意取一半（k个）的方格做标记，如我们把这些方格涂成阴影。,27,然后按照对称轴将这种标记方式向下和向右作对称图形。经过处理后使得nn的方阵的每一行和每一列都有一半（n/2）的方格被涂成阴影。 接下来，把从1开始的数字依次往方格里面填。第一遍：从第1行第1列的方格开始往右，不是阴影，则填数字，如果是阴影的方格，不填数字，但相应的数字加1。第1行填完后，是第2行第1列的方格，依次，最后是第n行第n列的方格。,28,这样填完之后，有一半的方格被填上了数字。 第二遍，从第n行第n列的方格开始依次往左，规则同前，从1开始的数字依次往方格里面填。第n行结束之后，是第n-1行第n列的方格。依次，最后是第1行第1列的方格。 最后就得到了幻方。,2019年5月16日,29,例1.3 利用对称法构造4阶幻方,30,当n=4k+2,所谓的单偶数的情况。 首先把nn的方阵分成上、下、左、右四个(2k+1)(2k+1)的方阵,为了表达方便，依次把左上、右下、右上、左下的方阵编号为A,B,C,D。 采用连续摆数法，把1(2k+1)2放在A中做成第一个幻方；把(2k+1)2 12(2k+1)2放在B中成第二个幻方。,31,把2(2k+1)213(2k+1)2放在C中成第三个幻方。 把3(2k+1)214(2k+1)2放在D中成第四个幻方。 然后，在A的各行从第1列开始向右取m个(m=(n-2)/4)方格，但中间一行（k+1行）从第2列开始。,把这些方格中的数字与D中相应位置的数字对换。 在C中各行最后一列右起向左各取m1个方格，把这些方格中的数字与B中相应位置的数字对换。最后，就得到了幻方。,32,33,例1.4 构造6阶幻方,A C D B m=1,34,35,（三）幻方的计数问题,3阶幻方 基本形式只有一种 经过旋转和翻转可获得8种变形,1 6 6 1 8 5 7 7 5 3 9 2 2 9 4,4阶幻方 分类枚举 基本形式有880个 变形有7040个,5 阶幻方 基本形式有275305224个,6 阶及以上幻方 即使通过大型计算机的计算仍然难以获得精确的数字，目前只能估计出它的取值范围,37,2019年5月16日,1.2 拉丁方问题,2019年5月16日,38,拉丁方是另一类典型的组合数学问题 n阶拉丁方定义为由数字1,2,n构成的nn的方阵，使得在每1行、每1列中每个数字都恰好出现1次。,拉丁方存在性问题,2019年5月16日,39,2阶拉丁方是存在的,2019年5月16日,40,n阶拉丁方是存在的 构造方法如下： 第1行为（1,2,3,n） 第2行是(2,3,n,1)， 第k行为(k,k+1,n,1, ,k-1)， 第n行为（n,3, 2, 1）。,41,例1.5 设计一个药物临床试验以测试五种药物对人体的药效。这五种药物编号1,2,3,4,5。然后选取5个人，并给每人不同的药。为了消除个体对药物的反应偏差，要求在连续5天里进行测试，每人每天吃一种药物。而为了消除服药时间造成药效的偏差，要求2个人不能在同1 天吃相同的药。,42,最后满足要求的实验是要形成由1,2,3,4,5构成的55的方阵，其中每行每列中没有相同的数字，即5阶拉丁方的构造问题。,43,行（人） 列（天）,例 36军官问题 有36名军官来自六个不同的团，具有六种不同的军衔，而且每个团每种军衔的军官各有一名，能否把他们排成一个66方阵，使得对每一个团与每一种军衔，在每一行或每一列都有一位军官来自这个团，也都有一位军官有此军衔？ 是由Euler首先提出的，实际上是组合设计中的正交拉丁方问题，属于构造问题。 猜想？6、10、。,将这36名军官排成66方阵, 使得 1)每行每列都有任一军团的军官 2)每行每列都有任一军衔的军官. i :军衔, j :军团, 军官对应数偶(i, j), i, j1,6 问题等价于构造数偶(i,j)排成的6阶方阵, 使得 1) 数偶第一个数字构成拉丁方; 2) 数偶第二个数字构成拉丁方; 3) 每个数偶只出现一次.,两个拉丁方称为互相正交，即正交拉丁方. 定义:设A=(aij)nn,B=(bij)nn是两个nn拉丁方. 令C=(aij, bij)nn,若C的n2对数偶互不相同, 则称A与B正交.,上述是两个3阶正交拉丁方。2阶哪？ 36军官问题即不存在6阶正交拉丁方。 6猜想不对。,对于只有9个军官的类似问题有解：,48,1.3 涂色问题,在实际应用中，很多计数问题都可抽象成涂色问题。 作为典型的组合计数问题，根据涂色问题难度的不同，将反映出各种不同的计数技术。,49,例1.6 对正三角形的三个顶点涂以红、蓝（r和b）两种颜色，求有多少种不同的涂色方案？,解 由于只有两种颜色，我们可以采用枚举方法分类讨论。,50,涂色方案可分成四类：,（1）三点全涂红色，只有一种方案 rrr （2）三点全涂蓝色，只有一种方案 bbb,（3）两点涂红色，一点涂蓝色，因蓝色可分别涂于三个顶点之一，故有3种方案 brr，rbr，rrb,（4）由对称性可知，两点涂蓝色，一点染红的方案也有3种：,51,红色, 蓝色,52,如果考虑正三角形可以旋转，则(3),(4),(5)显然是同一个涂色方案，(6),(7),(8)也是同一个涂色方案，这样涂色方案数就变成了4种。 如果变成了空间的四面体了，即加上空间的旋转之后，涂色方法的计算将更加复杂。 要涂色的点和可选颜色的数目如再增加的话，枚举方法就不奏效了,例:棋盘的完美覆盖,mn棋盘: m行n列方格, b-牌:1行b个的方格条 mn棋盘被b-牌的一个完美覆盖是 b-牌在棋盘上的一个排列, 满足: (1) 每个格子恰好只被一张牌覆盖; (2) 每条b-牌覆盖b个方格.,定理: mn棋盘有b-牌的完美覆盖b|m或b|n.,34棋盘 66棋盘有4-牌的完美覆盖吗?,有2-牌的完美覆盖.,需要特殊技巧解决问题 例 有101名选手参加羽毛球比赛，如果采用单循环淘汰制，问产生冠军需要进行多少场比赛？ 方法一：50+25+13+6+3+2+1=100场比赛 方法二：由于每场