复旦大学计算机科学与工程系吴永辉离散数学组合数学省公共课一等奖全国赛课获奖课件.pptx

组合数学初步第十章 鸽笼原理第十一章 排列与组合第十二章 生成函数与递推关系第1页组合数学/组合论组合数学/组合论：应用数学学科，对于算法研究变得日益主要。第2页计算机算法分类数值计算：方程组求解、积分计算非数值计算：搜索、排序、组合优化（主要是组合算法）设计和分析组合算法基础是组合数学第3页组合数学四个方面判定所提出问题解是否存在存在性问题确定有解问题其不一样解个数计数问题对可解问题去把解结构出来结构性算法从问题各种结构性算法中择优改进优化问题。第4页讲授内容组合数学中存在性问题和计数问题第5页组合数学经典教材组合数学（第3版），卢开澄，卢华明著，清华大学出版社。（有课件，可拷贝）组合数学（英文版.第3版），（美）Richard A.Brualdi，译者：冯舜玺、罗平、裴伟东。校：卢开澄、冯舜玺。Prentice Hall，机械工业出版社。第6页组合数学一、组合数学历史和发展原因二、组合数学两类普通性问题三、组合学另外两种问题四、组合数学定义第7页一、组合数学历史和发展原因1.组合数学历史渊源扎根于数学娱乐和游戏之中。2.组合数学历史和发展原因1)计算机发展,程序基础往往是求解问题组合学算法.2)组合数学对于过去极少与数学正式接触学科适用性第8页二、组合数学两类普通性问题组合数学包括将一个集合物体排列成满足一些指定规则格式。1.排列存在性:排列在什么样(充分和必要)条件下能够实现?2.排列计数和分类:假如一个排列是可能,那么就会存在各种方法实现它.此时,就能够计数并将它们分类.第9页组合学问题形式：能否排列?存在一个吗?能用多少方法?计算数目.第10页三、组合学另外两种问题研究一个已知排列结构一个最优排列第11页四、组合数学定义组合数学是研究离散结构存在、计数、分析和优化等问题一门学科。第12页第十章 鸽笼原理10.1 鸽笼原理简单形式10.2 鸽笼原理加强形式第13页10.1 鸽笼原理简单形式1,问题引入实例：某次会议有n位代表参加，每位代表认识其它代表中一些人，则最少有两个人认识人数是一样。第14页10.1 鸽笼原理简单形式2,鸽笼鸽笼定理10.1 n+1只鸽子飞回n个笼子，最少有一个鸽笼含有不少于2只鸽子。证实方法：反证证实方法：反证第15页 例367人中最少有人生日相同。例10双手套中任取11只，其中最少有两只是完整配正确。第16页3,鸽笼扩展（抽象）鸽笼扩展（抽象）定理10.2 s（s1）个元素分成t个组，那么必存在一个组最少含有s/t（这里 为“上整数”记号）个元素。证实方法：反证法。第17页证实：若每个组至多含有(s/t-1)元素，则t个组共有元素t(s/t-1)，因为s/t s/t(s/t)+1，所以有t(s/t-1)|R|，令i=|D|/|R|，则D中存在i个元素d1,d2,di，使得f(d1)=f(d2)=f(di)。证实方法：此问题相当于定理10.2，把|D|个元素分到|R|个组中去。第19页证实：在这|R|个组中有一个组最少含有i=|D|/|R|个元素。在同一组中对应函数值是相等。所以在D中最少存在i个元素d1,d2,di，使得f(d1)=f(d2)=f(di)。第20页2）例10.2 在n+1个小于或等于2n互不相等正整数中，必存在两个互质数。第21页证实：把1,2,2n这2n个数分成n个组：1,2,3,4,2n-1,2n；则问题归结为从n个组中取n+1个数，由定理10.1知，最少有2个数取自同一组，因为这两个数是相邻正整数，故互质。第22页3）例10.3 1,2,2n中任取n+1个互不相同数中，必存在两个数，其中一个数是另一个数倍数。第23页证实：因为任何正整数n能够表示成n=2ab（这里a=0,1,2,，且b为奇数）。设取出n+1个数为k1,k2,kn+1，则ki=2aibi。因为b1,b2,bn+1是奇数，共有n+1个，而在1,2,2n中只有n个不一样奇数，所以必存在i,j，使得bi=bj。不妨设kikj，则有ki/kj=2ai-aj为正整数，所以ki是kj倍数。第24页4）例10.4 一个国际象棋选手为参加国际比赛，突击训练77天，要求天天最少下一盘棋，每七天至多下12盘棋。证实：不论怎样安排总能够使他在这77天里有连续几天共下21盘棋。第25页证实：用ai表示从第1天到第i天下棋总盘数（i=1,2,77）。因为要求天天最少下一盘棋，每七天至多下12盘棋，所以1a1a2a7712(77/7)=132结构新序列：a1+21,a2+21,a77+21则有这么序列：a1,a2,a77,a1+21,a2+21,a77+21共有154个,但每个不超出153,所以必存在i,j(ji)，使得ai=aj+21，则有ai-aj=21，即在j+1,j+2,j+(i-j)连续i-j天中下了21盘棋。第26页学生思索题：证实对于k=1,2,21存在连续若干天，在此期间国际象棋大师将恰好下完k局棋(k=21为上题处理情况)。能否推断：存在连续若干天，在此期间国际象棋大师将恰好下完22局棋？第27页5)中国余数定理令m和n为二互素正整数，并令a和b为两整数，且0am-1以及0bn-1。于是，存在一个正整数x，使得x除以m余数为a，而且x除以n余数为b；即x能够写成x=pm+a同时又能够写成x=qn+b形式，这里，p和q是两个整数。第28页证实：考虑n个整数a,m+a,2m+a,(n-1)m+a，这些整数中每一个除以m都余a。假设其中两个除以n有相同余数r。令这两个数为im+a和jm+a，其中0ijn-1。所以，存在两整数qi和qj，使得im+a=qin+r及jm+a=qjn+r。则有(j-i)m=(qj-qi)n。所以n是(j-i)m一个因子。因为n与m没有除1以外公因子，所以n是j-i一个因子，然而，0ijn-1意味着0100-1，所以，由推论10.2，某个位置,使得小盘上最少有100个小段与大盘上对应段颜色相同。第38页第39页习题解析鸽笼原理用于判断是否存在满足鸽笼原理条件对象，若鸽笼原理条件成立，则存在满足条件对象。利用鸽笼原理时必须确定哪些对象相当于鸽子，而哪些对象相当于鸽笼。第40页鸽笼原理形式设函数f是从有限集X到有限集Y映射，且|X|Y|，则必存在x1,x2X，x1x2，满足f(x1)=f(x2)。第41页鸽笼原理形式例题1.20个处理器连成网络，证明至少有两个处理器与相同数目处理器直接相连。第42页 解题分析：解题分析：20个处理器编号分别为1,2,3,20，（定义域X=1,2,3,20）；ai表示与第i个处理器直接相连处理器数目（f(X)）。证实：对于某两个i,j，ij，ai=aj。第43页解：X=1,2,3,20,Y=0,1,2,19;0和19不能同时作为函数值存在，即不存在两个i,j，ij，ai=0，aj=19。所以|X|=20,|Y|20。依据鸽笼原理形式1，命题成立。第44页2.列表中有80件物品，每个物品属性为“可用”或“不可用”，共有45个“可用”物品，证实最少有两件可用物品编号差恰为9。第45页 解题分析：解题分析：ai表示第i个可用物品编号；证实：对于某两个i,j，ij，ai-aj=9。第46页证实：考虑以下两组数字：a1,a2,a45a1+9,a2+9,a45+9这两组共90个数字，取值范围为1-89。因为第一组数字两两不一样，第二组数字也是两两不一样，所以必存在两个i,j，ij，ai-aj=9。第47页习题解析10.1 在边长为2正三角形中任意放置5个点,证实最少有两个点之间距离小于1.解题关键点：确定鸽子和鸽笼第48页/*将三角形分成边长为14个正三角形*/第49页10.4 将一个圆盘分为36段，将1,2,36这36个数字任意标在每一段上，使得每一段恰有一个数字。证实：必存在相继3段，它们数字之和大于56。第50页证实：设36个小扇形分别为a1,a2,a36。ai中放数为xi，i=1,2,36。1 xi 36，且当初ij，xixj。将36个小扇形合并成12个大扇形：A1=a1a2a3,A2=a4a5a6,A12=a34a35a36，并设Aj中3数之和为yj，j=1,2,12。则第51页将1837个元素分配给12个扇形，由鸽巢原理，最少存在一个扇形，分配给它元素个数最少是 1837/12=56。所以命题成立。第52页例例设 a1,a2,a3为任意个整数，b1，b2,b3为a1,a2,a3任一排列，则 a1-b1,a2-b2,a3-b3中最少有一个是偶数第53页证实证实:由鸽巢原理，a1,a2,a3为任意个整数，设这个数被除余数为 xxy，于是b1，b2,b3 中被除余数有个x，一个y这么a1-b1,a2-b2,a3-b3被除余数必有一个为第54页10.3 证实:对于任意正整数N,必存在N一个倍数,使得它仅由数字0和7组成.第55页作业：10.1,10.2,10.5,10.6第56页鸽笼原理形式习题1）5台处理器连成网络，恰有两台与相同数量处理器相连，可能吗？第57页2）列表中有100件物品，每个物品属性为“可用”或“不可用”，共有55个“可用”物品，证实最少有两件可用物品编号差恰为4。第58页3）列表中有80件物品，每个物品属性为“可用”或“不可用”，共有50个“可用”物品，证实最少有两件不可用物品编号差恰为3或6。第59页第60页