• / 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,幻方的存在性问题 例
展开阅读全文
  微传网所有资源均是用户自行上传分享,仅供网友学习交流,未经上传用户书面授权,请勿作他用。
0条评论

还可以输入200字符

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

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

微传网博客

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

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

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

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

收起
展开