计算机2011组合数学—CHO1

《计算机2011组合数学—CHO1》由会员分享，可在线阅读，更多相关《计算机2011组合数学—CHO1（55页珍藏版）》请在金锄头文库上搜索。

1、组合数学吉林大学计算机科学与技术学院2011年9月关于我姓名：卢奕南 单位：图像处理与虚拟现实研究团队主要研究方向：图像处理、模式识别关于教材内部试用版本时间：下周一下午地点：计算机大楼 A413价格：每本20元组织：请各班班长带着本班的教材费前来领取 电话：13843100175参考书：l机械工业出版社：组合数学，布 鲁迪 (Brualdi R.A.) (作者), 冯舜玺 (译 者) l清华大学出版社：组合数学，卢 开澄等上网习题组合数学（姜建国等），西安电子科技大学本学期涉及到的内容：鸽巢原理和Ramsey定理（存在性问题）基本计数方法容斥原理生成函数递推关系Plya定理怎样学好组合数学组

2、合数学经常使用的方法并不高深复杂。最主要的方法是计数时的合理分类组合模型的转换（一一对应）。组合分析数学归纳法反证法 要学好组合数学并非易事，既需要一定的数学修养，也要进 行相当的训练。 可从规模小的模型着手，从中找到规律性的东西，再推及一 般。 你解决的问题越多，那么你能够解决下一个问题的可能性也 越大。 7第一章 引言组合数学(简称组合学）是数学的一个分支, 它起源于古代的娱乐和休 闲游戏。后来这些问题逐渐与数论、概率统计、拓扑学、线性规划等 学科的问题交织在一起，逐渐形成一种理论。 广义的组合数学就是离散数学，广义的组合数学就是离散数学，离散数学是狭义的组合数学和图论、代数结构、数理逻辑

3、等的总称。离散数学是狭义的组合数学和图论、代数结构、数理逻辑等的总称。 工程认证组合数学中的著名问题计算一些物品在特定条件下分组的方法数目。这些是关于排列、 组合和整数分拆的。 地图着色问题：对世界地图着色，每一个国家使用一种颜色。如 果要求相邻国家的颜色相异，是否总共只需四种颜色？这是图论 问题。 船夫过河问题：船夫要把一匹狼、一只羊和一棵白菜运过河。只 要船夫不在场，羊就会吃白菜、狼就会吃羊。船夫的船每次只能 运送一种东西。怎样把所有东西都运过河？这是线性规划问题。 中国邮差问题：由中国组合数学家管梅谷教授提出。邮递员要穿 过城市的每一条路至少一次，怎样行走走过的路程最短？ 1856年 ，

4、哈密尔顿（Kirkman）, 旅行商问题。 任务分配问题：有一些员工要完成一些任务。各个员工完成不同 任务所花费的时间都不同。每个员工只分配一项任务。每项任务 只被分配给一个员工。怎样分配员工与任务以使所花费的时间最 少？這是线性规划的問題。 如何构造幻方。 组合数学的起源幻方最早记载于我国公元前500年的春秋时期大戴礼中，这 说明我国人民早在2500年前就已经知道了幻方的排列规律。而在 国外，公元130年，希腊人塞翁才第一次提起幻方 ；公园1275年（宋代），杨辉的著作中出现10阶幻方问题和杨辉三 角的记载； 1666年，莱布尼茨发表组合的艺术(De Art Combinatoria) ，这

5、是组合数学的第一部专著。书中首次使用了组合论（ Combinatorics）一词。标志组合数学的诞生。莱布尼茨：德国最重要的自然科学家、数学家、物理学家、历史学家和哲学家，一个举世罕 见的科学天才，和牛顿（1643年1月4日1727年3月31日）同为微积分的创建人。 杨辉，中国南宋时期杰出的数学家和数学教育家。 组合分析和组合算法已经被广泛应用与 计算机科学、管理科学、信息科学、电 子工程、人工智能、生命科学等诸多领 域中。11组合数学的蓬勃发展则是在计算机问世和普遍应用之后。一方面，当我们研究的组合问题规模很大的时候，计算量会很大，计 算机为求解这些问题提供了有力手段。另一方面，在计算机科学

6、的算法研究中数据结构+算法+编程语言时间复杂性和空间复杂性计算复杂性理论、算法设计与分析的基础课。什么是组合数学组合数学就是研究按照一定的规则来安排一些 离散个体的问题。它涉及面广，内容庞杂（涉 及到组合分析、图论、组合算法、近代密码学 、编码理论等），并且仍在很快地发展着，因 而还没有一个统一而有效的理论体系。 研究的对象是离散结构，一般可以用1，2， 、，n表示。本书仅限于讨论n是有限的 自然数的情况。组合数学是研究离散结构的存在、计数、分析 和优化等问题的一门学科。13组合数学的主要问题（1）存在性问题满足一定条件的安排的存在性满足一定条件的安排的存在性. . 如果某种安排不一定总存如果

7、某种安排不一定总存 在，我们就需要研究存在的条件。在，我们就需要研究存在的条件。存在性是数学研究最重要的问题之一存在性是数学研究最重要的问题之一. . 许多问题的存在性至今也许多问题的存在性至今也 无法解决？无法解决？例如数论中很多难题：哥德巴赫猜想例如数论中很多难题：哥德巴赫猜想 （2）安排的枚举、分类和计数如果所要求的安排存在，则可能有多如果所要求的安排存在，则可能有多 种不同的安排。此时，需要计数不同种不同的安排。此时，需要计数不同 的方案数，并将它们进行枚举和分类的方案数，并将它们进行枚举和分类 。当实际问题比较复杂的时候，必须有好的当实际问题比较复杂的时候，必须有好的 数学方法来解决

8、数学方法来解决. . （3）构造性问题一个组合问题，如果已经判定解是一个组合问题，如果已经判定解是 存在的，那么将所有可能的安排构存在的，那么将所有可能的安排构 造出来是一个关键问题。造出来是一个关键问题。与计算机算法密切相关典型问题：组合设计 （4）优化问题在给定的优化条件下从所有的安排在给定的优化条件下从所有的安排 方案中找出最优的安排方案。方案中找出最优的安排方案。l旅行商问题(Traveling Salesman Problem ，简称TSP) 与算法分析密切相关传统方法现代智能方法17幻方问题有趣的数学游戏幻方在娱乐数学中的地位以及它的意义 非同一般，它是中国人的首创。公元前2200

9、年易经提到洛书与河图1.1 幻方问题816357412一个n阶幻方是由整数1，2，3，n2按下述方式组成的nn方阵：该 方阵每行上的整数的和、每列上的整数的和以及两条对角线中每条对 角线上的整数的和都等于同一个数s 19 3阶幻方的所有整数和为15；每一行（或列或对角线）数字的和称为幻方的和（幻和） ：S= n (n2+1)/2 。关于幻方的问题归结为（一）存在性问题对任意的正整数n，n阶幻方存在吗？（二）组合计数问题如果存在，那么应该有多少个不同的n阶幻方。 （三）构造问题奇数阶幻方：连续摆数法(de La Loubre 法)双偶数（4k）阶幻方：对称法单偶数(4k+2)阶幻方：斯特雷奇法（

10、1918 ）*21（一）幻方的存在性问题 例1.1 证明了不存在2阶幻方。 对其余的正整数n，由于n阶幻方都能构造出来，当然 就证明了（正整数）阶幻方的存在性。 22例 1.1 证明不存在2阶幻方证明：反证法。假定存在2阶幻方，如图所示：a1a2 a3a4根据幻方的定义，它的幻和是5，于是a1+ a2= a1+ a3=5， 可得a2= a3，因为a1，a2，a3， a4必定彼此不同，所以不 可能，矛盾。因此不存在2阶幻方。 *23（二） 幻方的构造性问题 （1）奇数阶幻方的构造连续摆放法（de la Loubre法）。 规则为：假定构造n阶（n为奇数）幻方。首先将1放在(n+1)/2列第1行的

11、方格中，然后按照副对角线方向（即行号减1，列号加1）依次把从小 到大的各个数字放入相应的方格中。*24如果行号变成0（第1行上面一行），则改成第n行相应列对 应的方格。如果列号变成n+1（第n列右面一列），则改成第1列相应行 对应的方格。如果轮到的方格已经填有数字或者到了第0行第n+1列对应 的方格，则退到前一个方格正下方的方格。 25例1.2 利用连续摆放法构造5阶幻方 17241815 23571416 46132022 101219213 11182529即行号减1，列号加126（2 2）偶数阶幻方的构造）偶数阶幻方的构造 当当n n=4=4k k的时候，即双偶数的情况的时候，即双偶数的

12、情况， 对称法。对称法。 先把先把n n n n的方阵分成上、下、左、右的方阵分成上、下、左、右 四个四个2 2k k22k k的方阵。的方阵。 然后对于左上的然后对于左上的2 2k k22k k方阵进行处理方阵进行处理 ，每行每列任意取一半（，每行每列任意取一半（k k个）的方个）的方 格做标记，如我们把这些方格涂成阴格做标记，如我们把这些方格涂成阴 影。影。27然后按照对称轴将这种标记方式向下和向右作对称图形。经过处然后按照对称轴将这种标记方式向下和向右作对称图形。经过处 理后使得理后使得n n n n的方阵的每一行和每一列都有一半（的方阵的每一行和每一列都有一半（n n/2/2）的方格被

13、涂）的方格被涂 成阴影。成阴影。接下来，把从接下来，把从1 1开始的数字依次往方格里面填。第一遍：从第开始的数字依次往方格里面填。第一遍：从第1 1行行 第第1 1列的方格开始往右，不是阴影，则填数字，如果是阴影的方格，列的方格开始往右，不是阴影，则填数字，如果是阴影的方格， 不填数字，但相应的数字加不填数字，但相应的数字加1 1。第。第1 1行填完后，是第行填完后，是第2 2行第行第1 1列的方格列的方格 ，依次，最后是第，依次，最后是第n n行第行第n n列的方格。列的方格。28这样填完之后，有一半的方格被填上了数字。这样填完之后，有一半的方格被填上了数字。第二遍，从第第二遍，从第n n行

14、第行第n n列的方格开始依次往左，规则同列的方格开始依次往左，规则同 前，从前，从1 1开始的数字依次往方格开始的数字依次往方格里面里面填。第填。第n n行结束之后行结束之后 ，是第，是第n-n-1 1行第行第n n列的方格。依次，最后是第列的方格。依次，最后是第1 1行第行第1 1列的方列的方 格。格。最后就得到了幻方。最后就得到了幻方。*29例例1.31.3 利用对称法构造利用对称法构造4 4阶幻方阶幻方 214315812592117143106151381211659430当当n n=4=4k k+2,+2,所谓的单偶数的情况所谓的单偶数的情况。首先把首先把n n n n的方阵分成上、

15、下、左、右四个的方阵分成上、下、左、右四个 (2(2k k+1)(2+1)(2k+k+1)1)的方阵的方阵, ,为了表达方便，依次把左上、右下、为了表达方便，依次把左上、右下、 右上、左下的方阵编号为右上、左下的方阵编号为A A, ,B B, ,C C, ,D D。采用连续摆数法，把采用连续摆数法，把1 1(2(2k k+1)+1)2 2放在放在A A中做成第一个幻方中做成第一个幻方 ；把；把(2(2k k+1)+1)2 21 12(22(2k k+1)+1)2 2放在放在B B中成第二个幻方。中成第二个幻方。31把把2(22(2k k+1)+1)2 21 13(23(2k k+1)+1)2

16、2放在放在C C中成第三个幻方。中成第三个幻方。把把3(23(2k k+1)+1)2 21 14(24(2k k+1)+1)2 2放在放在D D中成第四个幻方。中成第四个幻方。然后，在然后，在A A的各行从第的各行从第1 1列开始向右取列开始向右取mm个个(m=(n-(m=(n- 2)/4)2)/4)方格，但中间一行（方格，但中间一行（k+1k+1行）从第行）从第2 2列开始。列开始。把这些方格中的数字与把这些方格中的数字与D D中相应位置的数字对换。中相应位置的数字对换。在在C C中各行最后一列右起向左各取中各行最后一列右起向左各取mm1 1个方格，把这个方格，把这 些方格中的数字与些方格中的数字与B B中相应位置的数字对换。最后，就得中相应位置的数字对换。最后，就得 到了幻方。到了幻方。3233