计算机组合数学—CHO1省名师优质课赛课获奖课件市赛课一等奖课件.ppt

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