《组合数学》PPT课件

《《组合数学》PPT课件》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、组合数学吉林大学计算机科学与技术学院2009年9月2021年10月6日2参考教材组合数学，屈婉玲编。北京大学出版社，1989年11月。组合数学（第四版），卢开澄等。清华大学出版社，2006年12月。组合数学(英文版·第5版)，(美)布鲁迪(Brualdi,R.A.)著。机械工业出版社，2009年3月。2021年10月6日3第一章引言计算机算法数值计算如：解方程组，求积分等非数值计算如：搜索，排序，组合优化等高等数学组合数学2021年10月6日4一、什么是组合数学二、组合数学的主要内容三、组合数学的几个例子

2、四、组合数学的学习方法四色问题对世界地图着色，每一个国家使用一种颜色，那么只需要四种颜色就能保证每两个相邻的国家的颜色不同2021年10月6日5装箱问题当你装一个箱子时，你会发现要使箱子尽可能装满不是一件很容易的事，你往往需要做些调整。从理论上讲，装箱问题是一个很难的组合数学问题，即使用计算机也是不容易解决的。2021年10月6日6过河问题一个船夫要把一只狼，一只羊和一棵白菜运过河。问题是当人不在场时，狼要吃羊，羊要吃白菜，而他的船每趟只能运其中的一个。他怎样才能把三者都运过河呢？2021年10月6日72

3、021年10月6日8一个邮递员从邮局出发，再返回邮局，如果他必须走过他所管辖的每条街道至少一次，问如何选择路线，使得路程最短？中国邮路问题2021年10月6日9n阶幻方把1，2，…，n2这n2个数字排成n×n的方阵，并使得每一行、每一列、每一条对角线上的n个数字之和都相等，称这样的方阵为n阶幻方，又称为纵横图。棋盘完美覆盖问题2021年10月6日102021年10月6日11组合数学简称组合学,Combinatorics组合数学是数学的一个分支,它起源于古代的娱乐和休闲。1666年莱布尼兹所著《组合学论文》

4、一书问世，这是组合数学第一部专著。一、什么是组合数学2021年10月6日12组合数学是研究离散结构的存在、计数、分析和优化等问题的一门学科。组合数学是研究事物在给定模式下的配置，研究这种配置的存在性，所有可能配置的计数和分类，以及配置的各种性质。2021年10月6日13二、组合数学的主要内容(1)组合分析，基础，为后面的讨论作准备。主要研究存在性问题、组合计数问题、构造或枚举问题。(2)组合优化，讨论线性规划及整数规划问题。(3)组合设计，是将集合的元素分成满足某些所述性质的子集的排列方法。(4)组合算法

5、，如：搜索法。动态规划。优先策略与分治策略。分类与查找，重点在于算法的分析。2021年10月6日14本学期涉及到的内容：鸽巢原理和Ramsey定理（存在性问题）排列和组合二项式系数包含排斥原理递推关系生成函数Polya定理组合计数问题2021年10月6日15组合数学应用领域1，计算机科学2，管理科学3，信息科学4，电子工程5，人工智能6，生命科学2021年10月6日16算法复杂性，算法的时间复杂性和空间复杂性分析,要用到组合数学的知识，组合计数。近代密码学，好的密码，对它的破译等价于某一NPC类困难问题，

6、这样的密码是不可破的。编码理论，研究的是通信中如何纠错与检错。组合设计。图论，较成熟的组合数学的分支，已独立。主要应用于网络流理论，电路网络以及TSP。2021年10月6日17(1)存在性问题对于模式要证明或否定它的存在计数和分类问题讨论对不同的方案进行计数，并对它们进行分类问题2021年10月6日18(3)构造性问题通过程序化的方法把相应的模式枚举或构造出来(4)优化问题寻找满足某种标准下“最好”或“最优”的一个模式2021年10月6日19一个3阶方阵，其元素是1到9的正整数，每行、每列以及两条对角线的

7、和都是15。杨辉称其为纵横图，在著《详解九章算法》（1261年）中曾研究三阶幻方，并给出它的构造方法还给出了4至10阶的幻方。519372486三、组合数学的几个例子§1.1幻方问题123564789927564381927564381927564381九子斜排，上下对易，左右相更，四维挺出，戴九履一，左三右七，二四为肩，六八为足2021年10月6日21一个n阶幻方是由整数1，2，3…，n2按下述方式组成的n×n方阵：该方阵每行上的整数的和、每列上的整数的和以及两条对角线中每条对角线上的整数的和都等于同一

8、个数s2021年10月6日223阶幻方的所有整数和为15；2阶幻方的所有整数和为5；每一行（或列或对角线）数字的和称为幻方的和（幻和）：S=n(n2+1)/2。2021年10月6日23关于幻方的问题归结为：（1）存在性问题对任意的正整数n，n阶幻方存在吗？（2）组合计数问题如果存在，那么应该有多少个不同的n阶幻方。（3）构造问题怎样构造n阶幻方？2021年10月6日24幻方的存在性问题例1.1证明不存在2阶幻方。对其余的正整数