• / 64
  • 下载费用:10 金币  

组合数学CH01.ppt

关 键 词:
组合数学CH01.ppt
资源描述:
组合数学,吉林大学 计算机科学与技术学院 2012年9月,2019年9月8日,2,参 考 教 材,组合数学,屈婉玲编。北京大学出版社,1989年11月。 组合数学(第四版),卢开澄等。清华大学出版社, 2006年12月。 组合数学(英文版·第5版) ,(美)布鲁迪(Brualdi,R.A.)著。机械工业出版社,2009年3月。,2019年9月8日,3,第一章 引言,计算机算法,2019年9月8日,4,一、什么是组合数学二、组合数学的主要内容三、组合数学的几个例子四、组合数学的学习方法,四色问题,对世界地图着色,每一个国家使用一种颜色,那么只需要四种颜色就能保证每两个相邻的国家的颜色不同,2019年9月8日,5,装箱问题,当你装一个箱子时,你会发现要使箱子尽可能装满不是一件很容易的事,你往往需要做些调整。从理论上讲,装箱问题是一个很难的组合数学问题,即使用计算机也是不容易解决的。,2019年9月8日,6,过河问题,一个船夫要把一只狼,一只羊和一棵白菜运过河。问题是当人不在场时,狼要吃羊,羊要吃白菜,而他的船每趟只能运其中的一个。他怎样才能把三者都运过河呢?,2019年9月8日,7,2019年9月8日,8,一个邮递员从邮局出发 ,再返回邮局,如果他必须走过他所管辖的每条街道至少一次,问如何选择路线,使得路程最短?,中国邮路问题,2019年9月8日,9,n阶幻方把1,2,…,n2这n2个数字排成n×n的方阵,并使得每一行、每一列、每一条对角线上的n个数字之和都相等,称这样的方阵为n阶幻方,又称为纵横图。,棋盘完美覆盖问题,2019年9月8日,10,2019年9月8日,11,组合数学简称组合学, Combinatorics,组合数学是数学的一个分支, 它起源于古代的娱乐和休闲。1666年莱布尼兹所著《组合学论文》一书问世,这是组合数学第一部专著。,一、什么是组合数学,2019年9月8日,12,组合数学是研究离散结构的存在、计数、分析和优化等问题的一门学科。组合数学是研究事物在给定模式下的配置,研究这种配置的存在性,所有可能配置的计数和分类,以及配置的各种性质。,2019年9月8日,13,二、组合数学的主要内容,(1)组合分析,基础,为后面的讨论作准备。主要研究存在性问题、组合计数问题、构造或枚举问题。(2)组合优化,讨论线性规划及整数规划问题。(3)组合设计, 是将集合的元素分成满足某些所述性质的子集的排列方法。 (4)组合算法,如:搜索法。动态规划。优先策略与分治策略。分类与查找,重点在于算法的分析。,2019年9月8日,14,本学期涉及到的内容: 鸽巢原理和Ramsey定理(存在性问题) 排列和组合 二项式系数 包含排斥原理 递推关系 生成函数 Polya定理,,组合计数问题,2019年9月8日,15,组合数学应用领域1,计算机科学2,管理科学3,信息科学4,电子工程5,人工智能6,生命科学,2019年9月8日,16,算法复杂性,算法的时间复杂性和空间复杂性分析, 要用到组合数学的知识,组合计数。近代密码学,好的密码,对它的破译等价于某一NPC类困难问题,这样的密码是不可破的。编码理论,研究的是通信中如何纠错与检错。组合设计。图论,较成熟的组合数学的分支,已独立。 主要应用于网络流理论,电路网络以及TSP。,2019年9月8日,17,(1) 存在性问题 对于模式要证明或否定它的存在,计数和分类问题讨论对不同的方案进行计数,并对它们进行分类问题,2019年9月8日,18,(3) 构造性问题 通过程序化的方法把相应的模式枚举或构造出来,(4) 优化问题寻找满足某种标准下“最好”或“最优”的一个模式,2019年9月8日,19,一个3阶方阵,其元素是1到9的正整数,每行、每列以及两条对角线的和都是15。 杨辉称其为纵横图,在著《详解九章算法》(1261年)中曾研究三阶幻方,并给出它的构造方法还给出了4至10阶的幻方。,三、组合数学的几个例子,§1.1 幻方问题,,,,九子斜排,上下对易, 左右相更,四维挺出, 戴九履一,左三右七, 二四为肩,六八为足,2019年9月8日,21,一个n阶幻方是由整数1,2,3…,n2按下述方式组成的n×n方阵:该方阵每行上的整数的和、每列上的整数的和以及两条对角线中每条对角线上的整数的和都等于同一个数s,2019年9月8日,22,3阶幻方的所有整数和为15;2阶幻方的所有整数和为5;,每一行(或列或对角线)数字的和称为幻方的和(幻和):S= n (n2+1)/2 。,2019年9月8日,23,关于幻方的问题归结为:(1)存在性问题对任意的正整数n,n阶幻方存在吗? (2)组合计数问题如果存在,那么应该有多少个不同的n阶幻方。 (3)构造问题怎样构造n阶幻方?,2019年9月8日,24,幻方的存在性问题 例1.1 证明不存在2阶幻方。 对其余的正整数n,由于n阶幻方都能构造出来,当然就证明了(正整数)阶幻方的存在性。,2019年9月8日,25,例 1.1 证明不存在2阶幻方,证明:反证法。假定存在2阶幻方,如图所示:,根据幻方的定义,它的幻和是5,于是a1+ a2= a1+ a3=5,可得a2= a3,因为a1,a2,a3, a4必定彼此不同,所以不可能,矛盾。因此不存在2阶幻方。,2019年9月8日,26,幻方的构造性问题 (1)奇数阶幻方的构造,连续摆放法(de la Loubère法)。 规则为:假定构造n阶(n为奇数)幻方。 首先将1放在 (n+1)/2列第1行的方格中, 然后按照副对角线方向(即行号减1,列号加1)依次把从小到大的各个数字放入相应的方格中。,2019年9月8日,27,如果行号变成0(第1行上面一行),则改成第n行相应列对应的方格。 如果列号变成n+1(第n列右面一列),则改成第1列相应行对应的方格。 如果轮到的方格已经填有数字或者到了第0行第n+1列对应的方格,则退到前一个方格正下方的方格。,2019年9月8日,28,例1.2 利用连续摆放法构造5阶幻方,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,2019年9月8日,29,(2)偶数阶幻方的构造当n=4k的时候,即双偶数的情况, 对称法。 先把n×n的方阵分成上、下、左、右四个2k×2k的方阵。 然后对于左上的2k×2k方阵进行处理,每行每列任意取一半(k个)的方格做标记,如我们把这些方格涂成阴影。,2019年9月8日,30,然后按照对称轴将这种标记方式向下和向右作对称图形。经过处理后使得n×n的方阵的每一行和每一列都有一半(n/2)的方格被涂成阴影。 接下来,把从1开始的数字依次往方格里面填。第一遍:从第1行第1列的方格开始往右,不是阴影,则填数字,如果是阴影的方格,不填数字,但相应的数字加1。第1行填完后,是第2行第1列的方格,依次,最后是第n行第n列的方格。,2019年9月8日,31,这样填完之后,有一半的方格被填上了数字。 第二遍,从第n行第n列的方格开始依次往左,规则同前,从1开始的数字依次往方格里面填。第n行结束之后,是第n-1行第n列的方格。依次,最后是第1行第1列的方格。 最后就得到了幻方。,2019年9月8日,32,例1.3 利用对称法构造4阶幻方,2019年9月8日,33,当n=4k+2,所谓的单偶数的情况。 首先把n×n的方阵分成上、下、左、右四个(2k+1)×(2k+1)的方阵,为了表达方便,依次把左上、右下、右上、左下的方阵编号为A,B,C,D。 采用连续摆数法,把1~(2k+1)2放在A中做成第一个幻方;把(2k+1)2+1~2(2k+1)2放在B中成第二个幻方。,2019年9月8日,34,把2(2k+1)2+1~3(2k+1)2放在C中成第三个幻方。 把3(2k+1)2+1~4(2k+1)2放在D中成第四个幻方。 然后,在A的各行从第1列开始向右取m个(m=(n-2)/4)方格,但中间一行(k+1行)从第2列开始。,把这些方格中的数字与D中相应位置的数字对换。 在C中各行最后一列起向左各取m-1个方格,把这些方格中的数字与B中相应位置的数字对换。最后,就得到了幻方。,35,2019年9月8日,2019年9月8日,36,例1.4 构造6阶幻方,2019年9月8日,37,2019年9月8日,38,幻方的计数问题,3阶幻方基本形式只有一种经过旋转和翻转可获得8种变形,4阶幻方分类枚举基本形式有880个变形有7040个,5阶幻方基本形式有275305224个,6阶及以上幻方即使通过大型计算机的计算仍然难以获得精确的数字,目前只能估计出它的取值范围,39,2019年9月8日,§1.2 拉丁方问题,2019年9月8日,40,n阶拉丁方定义为由数字1,2,…,n构成的n×n的方阵,使得在每1行、每1列中每个数字都恰好出现1次。,拉丁方是另一类典型的组合数学问题,拉丁方存在性问题,2019年9月8日,41,2阶拉丁方是存在的,2019年9月8日,42,n阶拉丁方是存在的 构造方法如下: 第1行为(1,2,3…,n) 第2行是(2,3,…,n,1),… 第k行为(k,k+1,…,n,1, …,k-1),…, 第n行为(n,…,3, 2, 1)。,2019年9月8日,43,例1.5 设计一个药物临床试验以测试五种药物对人体的药效。这五种药物编号1,2,3,4,5。然后选取5个人,并给每人不同的药。为了消除个体对药物的反应偏差,要求在连续5天里进行测试,每人每天吃一种药物。而为了消除服药时间造成药效的偏差,要求2个人不能在同1 天吃相同的药。,2019年9月8日,44,最后满足要求的实验是要形成由1,2,3,4,5构成的5×5的方阵,其中每行每列中没有相同的数字,即5阶拉丁方的构造问题。,2019年9月8日,45,正交拉丁方,2019年9月8日,46,将两个n阶拉丁方重叠在一起时,所有t2个组合各出现一次,则称这两个拉丁方是相互正交的。,2019年9月8日,47,3阶正交拉丁方,并置方阵,2019年9月8日,48,36军官问题有36名军官来自六个不同的军团,具有六种不同的军衔,而且每个团每种军衔的军官各有一名,能否把他们排成一个66方阵,使得对每一个军团与每一种军衔,在每一行或每一列都有一位军官来自这个团,也都有一位军官有此军衔? 是由Euler首先提出的,实际上是组合设计中的6阶正交拉丁方问题,2019年9月8日,49,能否编成方阵,使得每行每列的军衔不重复,每行每列的军团不重复,问题简述为:,2019年9月8日,50,(1)一个有序对(i,j) 表示一个军官,其中:i表示他的军衔类别(i=1,,6), j表示他所在的军团 (j=1,, 6),,问题转化为:36个有序对(i, j) (i=1,2,,6;j=1,2,,6) 能否排成一个66阵列, 使得每行(或列)中,整数1,2,,6以某种次序出现于有序对的第一位置;又以另一种次序(不一定相同)出现于有序对的第二位置。,2019年9月8日,51,(2)分裂成别两个66阵列,一个对应于有序对的第一个位置,即军衔方阵;另一个对应于有序对的第二个位置,即军团方阵,军衔方阵,军团方阵,2019年9月8日,52,问题转化为: 是否存在阵列,满足:(1) 整数1-6以某种次序出现在阵列的每行(或列)中; 且(2) 两个阵列并置时, 所有36个有序对(i,j) 都会出现。 满足第一个条件的每个方阵称为拉丁方,满足第二个条件的两个拉丁方称为互相正交,即正交拉丁方.,2019年9月8日,53,上述是两个3阶正交拉丁方。36军官问题即是否存在6阶正交拉丁方。,9个军官问题,军衔方阵,军团方阵,并置方阵,2019年9月8日,54,§1.3 涂色问题,在实际应用中,很多计数问题都可抽象成涂色问题。 作为典型的组合计数问题,根据涂色问题难度的不同,将反映出各种不同的计数技术。,2019年9月8日,55,例1.6 对正三角形的三个顶点涂以红、蓝(r和b)两种颜色,求有多少种不同的涂色方案?,解 由于只有两种颜色,我们可以采用枚举方法分类讨论。,2019年9月8日,56,涂色方案可分成四类:,(1)三点全涂红色,只有一种方案 rrr (2)三点全涂红色,只有一种方案 bbb,(3)两点涂红色,一点涂蓝色,因蓝色可分别涂于三个顶点之一,故有3种方案 brr,rbr,rrb,(4)由对称性可知,两点涂蓝色,一点染红的方案也有3种:,2019年9月8日,57,,,,,,,,,,,,,,,,,,,,,,,,,,,,,红色, 蓝色,,,2019年9月8日,58,如果考虑正三角形可以旋转,则(3),(4),(5)显然是同一个涂色方案,(6),(7),(8)也是同一个涂色方案,这样涂色方案数就变成了4种。 如果变成了空间的四面体了,即加上空间的旋转之后,涂色方法的计算将更加复杂。 要涂色的点和可选颜色的数目如再增加的话,枚举方法就不奏效了,一笔画问题,2019年9月8日,59,四、组合数学的学习方法,组合数学经常使用的方法并不高深复杂。最主要的方法是计数时的合理分类和组合模型的转换(一一对应)。要学好组合数学并非易事,既需要一定的数学修养,也要进行相当的训练。可从规模小的模型着手,从实际出发分析它,从中找到规律性的东西,再推及一般。你解决的问题越多,那么你能够解决下一个问题的可能性也越大。,2019年9月8日,60,解题方法一类是常规方法从组合学基本概念、基本定理出发解题鸽巢原理、相异代表系定理解存在性问题等等。利用容斥原理、二项式定理、Polya定理解计数问题;特征根方法、生成函数方法解递推关系式; 这类方法通常比较容易掌握,将在以后各章里分别学到并学会它们,,2019年9月8日,61,另一类方法,通常与问题所涉及的组合学概念无关1.数学归纳法,2. 反证法,3.一一对应技术。把一个组合问题转化成另一个组合问题。4.数论方法,特别是利用整数的奇偶性、整除性等效论性质进行分析推理的方法。5.殊途同归方法,即从不同角度讨论计数问题以建立组合等式。,2019年9月8日,62,特殊技巧的例子:一一对应例1 有101名选手参加羽毛球比赛,如果采用单循环淘汰制,问产生冠军需要进行多少场比赛?,解2: 因为每场比赛都要产生一个失败者,而每个失败者只能失败一次,所以比赛的场数与失败者的人数相等.又因为冠军是唯一的胜利者,其它100个人都失败过,所以要比赛100场。,解1: 50+25+13+6+3+2+1=100,2019年9月8日,63,例2 有一个边长为3的立方体木块,要把它切割成27个边长为1的小立方体,如果在切割的过程中可以重新排列被切割的木块,证明至少需要6次才能完成任务?,(分析)设具有最少切割次数的方案是最优,如果我们先列出所有可能的切割方案,然后从中由出最优的方案,这是相当麻烦的,我们采用另一种解法.,2019年9月8日,64,解 首先可以看到6次是可以完成整个切割的.左图就给出了这样的一种方案;其次,我们来证明少于6次是不能完成整个切割的.因为在27个小立方体中有一个处在原来大立方体的中心,它的每一个面都是由切割而产生的.又因为每切一次只能产生一个面,所以切割次数不能少于它的面数,因此至少要6次切割才能完成。,
展开阅读全文
  微传网所有资源均是用户自行上传分享,仅供网友学习交流,未经上传用户书面授权,请勿作他用。
0条评论

还可以输入200字符

暂无评论,赶快抢占沙发吧。

关于本文
本文标题:组合数学CH01.ppt
链接地址:https://www.weizhuannet.com/p-9821256.html
微传网是一个办公文档、学习资料下载的在线文档分享平台!

网站资源均来自网络,如有侵权,请联系客服删除!

 网站客服QQ:80879498  会员QQ群:727456886

copyright@ 2018-2028 微传网络工作室版权所有

     经营许可证编号:冀ICP备18006529号-1 ,公安局备案号:13028102000124

收起
展开