组合数学CH01.ppt
《组合数学CH01.ppt》由会员分享,可在线阅读,更多相关《组合数学CH01.ppt(64页珍藏版)》请在三一办公上搜索。
1、组合数学,2023年3月31日,2,参 考 教 材,组合数学,屈婉玲编。北京大学出版社,1989年11月。组合数学(第四版),卢开澄等。清华大学出版社,2006年12月。组合数学(英文版第5版),(美)布鲁迪(Brualdi,R.A.)著。机械工业出版社,2009年3月。,2023年3月31日,3,第一章 引言,计算机算法,2023年3月31日,4,一、什么是组合数学 二、组合数学的主要内容 三、组合数学的几个例子 四、组合数学的学习方法,四色问题,对世界地图着色,每一个国家使用一种颜色,那么只需要四种颜色就能保证每两个相邻的国家的颜色不同,2023年3月31日,5,装箱问题,当你装一个箱子时
2、,你会发现要使箱子尽可能装满不是一件很容易的事,你往往需要做些调整。从理论上讲,装箱问题是一个很难的组合数学问题,即使用计算机也是不容易解决的。,2023年3月31日,6,过河问题,一个船夫要把一只狼,一只羊和一棵白菜运过河。问题是当人不在场时,狼要吃羊,羊要吃白菜,而他的船每趟只能运其中的一个。他怎样才能把三者都运过河呢?,2023年3月31日,7,2023年3月31日,8,一个邮递员从邮局出发,再返回邮局,如果他必须走过他所管辖的每条街道至少一次,问如何选择路线,使得路程最短?,中国邮路问题,2023年3月31日,9,n阶幻方 把1,2,n2这n2个数字排成nn的方阵,并使得每一行、每一列
3、、每一条对角线上的n个数字之和都相等,称这样的方阵为n阶幻方,又称为纵横图。,棋盘完美覆盖问题,2023年3月31日,10,2023年3月31日,11,组合数学简称 组合学,Combinatorics,组合数学是数学的一个分支,它起源于古代的娱乐和休闲。1666年莱布尼兹所著组合学论文一书问世,这是组合数学第一部专著。,一、什么是组合数学,2023年3月31日,12,组合数学是研究离散结构的存在、计数、分析和优化等问题的一门学科。组合数学是研究事物在给定模式下的配置,研究这种配置的存在性,所有可能配置的计数和分类,以及配置的各种性质。,2023年3月31日,13,二、组合数学的主要内容,(1)
4、组合分析,基础,为后面的讨论作准备。主要研究存在性问题、组合计数问题、构造或枚举问题。(2)组合优化,讨论线性规划及整数规划问题。(3)组合设计,是将集合的元素分成满足某些所述性质的子集的排列方法。(4)组合算法,如:搜索法。动态规划。优先策略与分治策略。分类与查找,重点在于算法的分析。,2023年3月31日,14,本学期涉及到的内容:鸽巢原理和Ramsey定理(存在性问题)排列和组合二项式系数包含排斥原理递推关系生成函数Polya定理,组合计数问题,2023年3月31日,15,组合数学应用领域 1,计算机科学 2,管理科学 3,信息科学 4,电子工程 5,人工智能 6,生命科学,2023年3
5、月31日,16,算法复杂性,算法的时间复杂性和空间复杂性分析,要用到组合数学的知识,组合计数。近代密码学,好的密码,对它的破译等价于某一NPC类困难问题,这样的密码是不可破的。编码理论,研究的是通信中如何纠错与检错。组合设计。图论,较成熟的组合数学的分支,已独立。主要应用于网络流理论,电路网络以及TSP。,2023年3月31日,17,(1)存在性问题对于模式要证明或否定它的存在,计数和分类问题 讨论对不同的方案进行计数,并对它们进行分类问题,2023年3月31日,18,(3)构造性问题 通过程序化的方法把相应的模式枚举或构造出来,(4)优化问题 寻找满足某种标准下“最好”或“最优”的一个模式,
6、2023年3月31日,19,一个3阶方阵,其元素是1到9的正整数,每行、每列以及两条对角线的和都是15。杨辉称其为纵横图,在著详解九章算法(1261年)中曾研究三阶幻方,并给出它的构造方法还给出了4至10阶的幻方。,三、组合数学的几个例子,1.1 幻方问题,九子斜排,上下对易,左右相更,四维挺出,戴九履一,左三右七,二四为肩,六八为足,2023年3月31日,21,一个n阶幻方是由整数1,2,3,n2按下述方式组成的nn方阵:该方阵每行上的整数的和、每列上的整数的和以及两条对角线中每条对角线上的整数的和都等于同一个数s,2023年3月31日,22,3阶幻方的所有整数和为15;2阶幻方的所有整数和
7、为5;,每一行(或列或对角线)数字的和称为幻方的和(幻和):S=n(n2+1)/2。,2023年3月31日,23,关于幻方的问题归结为:(1)存在性问题 对任意的正整数n,n阶幻方存在吗?(2)组合计数问题 如果存在,那么应该有多少个不同的n阶幻方。(3)构造问题 怎样构造n阶幻方?,2023年3月31日,24,幻方的存在性问题 例1.1 证明不存在2阶幻方。对其余的正整数n,由于n阶幻方都能构造出来,当然就证明了(正整数)阶幻方的存在性。,2023年3月31日,25,例 1.1 证明不存在2阶幻方,证明:反证法。假定存在2阶幻方,如图所示:,根据幻方的定义,它的幻和是5,于是a1+a2=a1
8、+a3=5,可得a2=a3,因为a1,a2,a3,a4必定彼此不同,所以不可能,矛盾。因此不存在2阶幻方。,2023年3月31日,26,幻方的构造性问题(1)奇数阶幻方的构造,连续摆放法(de la Loubre法)。规则为:假定构造n阶(n为奇数)幻方。首先将1放在(n+1)/2列第1行的方格中,然后按照副对角线方向(即行号减1,列号加1)依次把从小到大的各个数字放入相应的方格中。,2023年3月31日,27,如果行号变成0(第1行上面一行),则改成第n行相应列对应的方格。如果列号变成n+1(第n列右面一列),则改成第1列相应行对应的方格。如果轮到的方格已经填有数字或者到了第0行第n+1列对
9、应的方格,则退到前一个方格正下方的方格。,2023年3月31日,28,例1.2 利用连续摆放法构造5阶幻方,2023年3月31日,29,(2)偶数阶幻方的构造 当n=4k的时候,即双偶数的情况,对称法。先把nn的方阵分成上、下、左、右四个2k2k的方阵。然后对于左上的2k2k方阵进行处理,每行每列任意取一半(k个)的方格做标记,如我们把这些方格涂成阴影。,2023年3月31日,30,然后按照对称轴将这种标记方式向下和向右作对称图形。经过处理后使得nn的方阵的每一行和每一列都有一半(n/2)的方格被涂成阴影。接下来,把从1开始的数字依次往方格里面填。第一遍:从第1行第1列的方格开始往右,不是阴影
10、,则填数字,如果是阴影的方格,不填数字,但相应的数字加1。第1行填完后,是第2行第1列的方格,依次,最后是第n行第n列的方格。,2023年3月31日,31,这样填完之后,有一半的方格被填上了数字。第二遍,从第n行第n列的方格开始依次往左,规则同前,从1开始的数字依次往方格里面填。第n行结束之后,是第n-1行第n列的方格。依次,最后是第1行第1列的方格。最后就得到了幻方。,2023年3月31日,32,例1.3 利用对称法构造4阶幻方,2023年3月31日,33,当n=4k+2,所谓的单偶数的情况。首先把nn的方阵分成上、下、左、右四个(2k+1)(2k+1)的方阵,为了表达方便,依次把左上、右下



- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 组合 数学 CH01

链接地址:https://www.31ppt.com/p-3999603.html