《离散数学》课件 第23章 组合计数定理.ppt

***************************要求鸽巢原理简单形式及其应用熟悉组合数、排列数、多项式系数、错位排列数、Fibonacci数、Catalan数、第二类Stirling数的定义及性质恒等式证明、组合数序列求和求解实际的组合计数问题*离散数学在计算机

科学中的应用实例建模集合、关系、函数图代数系统离散概率分析组合图论概率数理逻辑*问题1:单链聚类网络最小费用的连通网络路由算法单链聚类——数据分析有一组离散的数据，任何两个数据i,j之间有对称的相似度函数d(i,j)，求对这组数据的k-划分，使得存在k个聚类C1,C2,…,Ck，两个聚类Cs,Ct之间的距离D(Cs,Ct)=min{d(i,j)|i?Cs,j?Ct}k-聚类的最小间隔D=min{D(Cs,Ct)|1?st?k}求使得D最大的k聚类.*结点集合：{1,2,3,4,5,6,7,8,9,10}最大间隔3-聚类:{C1,C2,C3}最大间隔：D=min{30,35,40}=30Kruskal算法：加边直到构成k个连通分支C1一个3-聚类的实例*124376891055682349303540C1C2C3聚类问题的背景根据测试数据的相似性做出分类分析数据挖掘图像处理系统划分电路设计根据不同优化目标形成不同类型的聚类问题，其中某些单链聚类问题可以使用最小生成树的模型*问题2网络优化背景树状连通网络，每条线路有传输延迟，只能改进K条线路，以降低传输延迟，如何选择？实例节点集V={1,2,…,n}，E={e1,e2,…,en-1}，K?n-1wt是边et的传输延迟，t=1,2,…,n-1，W(i,j)是i到j的延迟(从i到j路径上所有边延迟之和)对ei改进后，边上的延迟减少了pwi，p1为常数问题选A?E,|A|=K,使得*贪心法设计与分析改进ei之后总延迟减少了选择A后总延迟是贪心法计算ci，i=1,2,…,n-1排序ei使得c1?c2?…?cn-1A={e1,e2,…,eK}可以证明得到最优解*ei*SiSi’问题3：Slepian译码表k维线性码C——[n,k]码：的k维子空间v=x1v1+x2v2+…+xkvk,v1,v2,…,vk为一组基实例:[7,4]码，红色码是一组基C={0000000,0001011,0010101,0011110,0100110,0101101,0110011,0111000,1000111,1001100,1010010,1011001,1100001,1101010,1110100,1111111}*C构成群C关于向量加法封闭，加法满足结合律，单位元是n维0向量，码v的逆元就是v自己C是的子群C的陪集C+a，其中a?*错误向量CC+0001C+0010C+00110000011010011111000101111000111000100100101111010011010110101100实例：[4,2]码C={0000,0110,1001,1111}纠错——Slepian译码表发送v