组合数学12组合设计ppt课件.ppt

《组合数学12组合设计ppt课件.ppt》由会员分享，可在线阅读，更多相关《组合数学12组合设计ppt课件.ppt（73页珍藏版）》请在三一办公上搜索。

1、第10章 组合设计,组合设计，是将集合的元素分成能够满足某些特定性质的子集的排列方法。,1 模运算,一、模算符,比如：（1）27 mod 5=2,a mod n = r ,（r = 0,1,2，n-1）,（2）36 mod 12=0,（3）-18 mod 14 =10 （余数为-4，-4+14=10）,（4）-7 mod 10 = 3 （余数为-7，-7+10=3）,整数集 Z 模n后得到 集合 Zn = 0, 1, 2, 3, , n-1,钟表计时模12，星期模7，角度模360,星期九=星期二18点= 6点420度 = 60度,模运算保证了有限集上四则运算的封闭性!,二、Zn上的模运算,例1

2、 在Z15中求 7+14： （7+14）mod 15= 6,7- 11： （7- 11）mod 15= 11,7* 11： （7*11）mod 2 = 1,例2 在Z2中求 7+14： （7+14）mod 2 = 1,7- 11： （7- 11）mod 2 = 0,1、模运算的运算法则,例3 (17+27) mod 14=2,(123(-10) mod 19=(-1230) mod 19=5,另法计算: (17 mod 14)+(27 mod 14)= (3+13) mod 14 =2,(123 mod 19) (-10 mod 19)= 99 mod 19,= 81 mod 19 = 5,定

3、理 (ab) mod n= (a modn) (a mod n) (ab) mod n= (a modn) (a mod n),例4 10n mod x = (10 mod x)n,10n mod 3=(10 mod 3)n =1,10n mod 9=(10 mod 9)n =1,10n mod 5=(10 mod 5)n = 0 ( n0),56712 = 5*105 + 6*104 + 7*103 + 1*101+2*100,56712 mod 3 =,= 5 mod 3+ 6 mod 3 + 7mod3 + 1 mod 3 + 2 mod 3,= (5+6+7+1+2) mod 3 =

4、21 mod3 = 0,十进制数被3或9整除，且仅当各位数码之和能被3或9整除。,十进制数模3或模9，等于各位数码之和模3或模9。,(1723345 + 2124945) mod 3= (25 mod 3)+(27 mod 3)=1+0 =1,(1723345 * 2124945) mod 3= (25 mod 3)*(27 mod 3) = 1*0 = 0,例5,(1723347 + 2124949) mod 5= 7 mod5 + 9 mod5 = 1,(1723347 * 2124949) mod5= (7*9) mod 5 = 3,模5运算等于个位运算！,2、加法逆与减法,- a =

5、(n-a) mod n， - a 称为 a 的加法逆（负元）。,在Z10中：,做减法等于 加负元 .,若 a+b = 0 mod n，则 a与b互为加法逆。,3 乘法逆与除法：,b = a -1 可能存在，也可能不存在。,定理 a有乘法逆当且仅当 gcd(a, n) =1， 即a与n互素。,若 ab =1 mod n，则 a与 b 互为乘法逆。,若 a -1 存在，称其为a 的乘法逆（逆元）。,做除法等同于乘逆元,0 没有乘法逆元,例6 在Z10中，8的乘法逆 8-1 =？,由于 gcd (8, 10) = 2 1，8没有乘法逆。,在Z10中，没有任何数字 与8相乘 = 1 !,例7 求Z10

6、中的乘法逆,从乘法表中可以看到: 1, 3, 7, 9 有乘法逆,1-1 = 1,3-1 = 7,7-1 = 3,9-1 = 9,其余 0, 2, 4, 5, 6, 8 都没有乘法逆。,构成三对 乘法逆：(1, 1) (3,7) (9, 9）,例8 求Z11中的乘法逆,由于 11 是质数， gcd ( k, 11) = 1, 所以除 0 外，1, 2, , 10 都有乘法逆。,利用乘法表，可知有6对 乘法逆：,(1, 1) (2, 6) ( 3, 4 ) (5, 9) (7, 8) (10, 10),三、代数结构,定义 设G为一非空集合, 为定义在G上的二元运算. 如果下述条件成立, 则称代数

7、系统G, 为一个群. (1) 运算封闭性: a, bG, abG; (2) 结合律: a, b, cG, a(bc)=(ab)c; (3) 存在单位元 eG: 使得对aG, ae=ea=a; (4) aG, 存在a的逆元 a1G: 使得 aa1= a1a=e.,(5) 交换律：a，b G, ab= ba.,交换群,1、群 (group),例9 G = Zn, + （模 n +) 为一个群, 且是交换群。 单位元为 0 mod n a 的逆元是 a mod n= n-a,例10 G = Z*n, （模 n ) 为一个群, 且是交换群。 单位元为 1 mod n a 的逆元是 a -1 mod n

8、,例11 A=a, b, c, d, G = A , 是交换群。 运算表：,单位元: a 逆元对: (a,a) , (b,d), (c,c),2、环 ( ring ),定义 设G为一非空集合, G上定义了两种二元运算 +： 构成 加法交换群 ： 满足封闭性+结合律（+交换律） 而且 * 对+ 有分配律 则称代数系统 R= G, +, 为一个环（或交换环）。,Z10 上的（+, *）运算构成交换环 R = Z10, +, ,不能进行“除法”运算,3、域 ( field ),定义 设G为一非空集合, G上定义了两种二元运算 +： 构成 加法交换群 ： 构成乘法交换群 而且 * 对+ 有分配律 则称

9、代数系统 F= G, +, 为一个域。,加减乘除 畅通无阻！,域的例子：,1、 有理数域,2、 实数域,3、 有限域 ： Zp,Galois（伽罗华）指出：有限域的元素个数必为 p n 。,因此，有限域又称伽罗华域，记为 GF( p n ),例12 GF(5) = Z5 , 在模5下可以定义四则运算。,例13 GF(2) = Z2 , 在模2下可以定义四则运算。 0+0=0；0+1=1，1+0=1，1+1=0 （异或运算） 0*0=0；0*1=0，1*0=0，1*1=1 （与运算） 加法零元：0， -0 = 0；-1=1 乘法单位元：1， 1-1 =1；0 无逆元,加法就是减法乘法就是除法,例

10、13 GF(22) 4 元素的有限域,不可能是 Z4 ，mod 4 运算中，2 无乘法逆元。,GF(22) 中的元素记为 a + bi，系数 a, b GF(2),这 4 个元素为 0, 1, i, 1+ i ,其中 i 是素多项式 x2 + x +1 = 0 在GF(2) 中的根， 满足 i 2 + i +1= 0 , 即 i 2 = - (i +1) = i +1,例13 GF(22) 4 元素的有限域,GF(22)的元素可视为GF(2)上关于 i 的1次多项式，上述运算可以视为多项式的运算。,为了保证运算的封闭性，作为关于素多项式 i 2 + i +1 = 0的模运算。,逢i 2换为 i

11、+1 即可,例13 GF(22) 4 元素的有限域,例14 GF(33) 27 个元素的有限域,GF(33)的元素可视为GF(3)上关于 i 的2次多项式,逢 i 3换为 i+2 即可,为了保证运算的封闭性，作为关于3 次素多项式 i 3 +2 i +1 = 0的模运算。,也可把 i 视为 i 3 +2 i +1 = 0 的根。,例14 GF(33) 27 个元素的有限域,逢 i 3换为 i+2 即可,2 区组设计,一、一个实用案例：,在市场调查中，需要确定消费者对7种牙膏的喜好程度。,随机抽取若干试验者，让他们对牙膏作两两对比（配对试验）。,应该选取多少试验者？每人使用哪些“牙膏进行配对比较

12、”？,（1）抽取 n 个人，每人使用全部 7 种牙膏，每人比较 21 对。,（2）抽取 7 个人，每人使用 3 种牙膏，每人比较 3 对。,完全区组,不完全区组,区组：每个人安排的牙膏品种,区组：每个试验区安排的样本品种,例1：,B1=0,1,3,B2=1,2,4,B3=2,3,5,B4=3,4,6,B5=4,5,0,B6=5,6,1,B7=6,0,2,7种牙膏样本集合 X = 0, 1, 2, 3, 4, 5, 6 ,关联矩阵,7个区组,一、平衡不完全区组设计 BIBD,样本集合： X = 0, 1, 2, , v-1 ,Balanced Incomplete Block Design,区组

13、： X 的 k 元素子集称为一个区组 Bi,区组设计（集类）：B = B1，B2, , Bb ,k = v 为完全区组设计，,k v 为不完全区组设计。,若 X 的每一对元素都在个区组中出现， 称平衡区组设计，称为设计指数。,1、BIBD 的参数,b 区组个数（ B 的大小）,v 样本个数（ X 的大小）,k 区组内样本数（Bi 的大小）,r 每个样本所属的区组数（样本重复数）, 每对样本所属的区组数（样本对重复数）,2、参数的相互关系,(1) b*k = r*v （样本使用次数）,(2) (k-1)*r = *(v-1),每个样本出现在 r 区组，共有 r*v 次 每区组含有 k 个样本，共

14、有 b*k 次所以 b*k = r*v,(3) r （配对重复数 样本重复数）,(4) b v,在BIBD 的5个参数中， 受到两个等式约束，只有三个独立参数。 通常设计指数 为指定的已知数，另外两个需要根据实际需求确定。,例2 v=16, k=14, b=12, r=3 , 能否构成 BIBD?,例3 v=9, k=3, b=12, r = 4, 能否构成 BIBD?,关联矩阵 A: 12*9,AA: 9*9对角线上恰好是 r = 4其他位置恰好是 =1,对角线占优，可逆,例4 v=16 排成4*4方阵，X= xij | i , j =1,2,3,4,为了证明这是一个BIBD，还需要证明每个

15、配对(x, y) 恰好恰好被测试2次（出现在2个区组中）即证明= 2。,相当于16种牙膏被测试选择16个人作测试每人使用6种牙膏，每种牙膏被6人使用,二、对称平衡不完全区组设计 SBIBD,Symmetric Balanced Incomplete Block Design,1、SBIBD 的参数,（1）b = v 区组个数 = 样本数,（2）k = r 每区组样本数=每样本所在区组数,SBIBD 仅有两个独立参数，给定，只须确定k。,例1 是一个SBIBD ：v=b=7, k = r =3,=1例3 是一个SBIBD ：v=b=16, k = r =6,=2,2、SBIBD 的构造方法,（1

16、）差分集：若 X 的k 元子集在 mod v 下的减法表（差分表）中，任意两个不同元素的差分值都恰好出现次，则称该子集为 “差分集”。,例5：v =7, k = 3, B = 0, 1, 3 是差分集。其差分表（减法表，mod7）为：,共有 k(k-1) = 3*2 = 6 对差分分别等于 1, 2, , 6 ，根据鸽巢原理，每个差分值都出现且仅出现1次。,2、SBIBD 的构造方法,（1）差分集：,例6：v =7, k = 3, B = 0, 1, 4 不是差分集。其差分表（减法表，mod7）为：,共有 k(k-1) = 3*2 = 6 对差分分别等于 1, 3, 4, 6 ， 1和6出现1

17、次， 3和4出现2次。,（2）利用差分集构造 SBIBD：,例7：mod7 差分集 B = 0, 1, 3 导出 SBIBD 为：,B = 0, 1, 3 B1 = B+1= 1, 2, 4 B2 = B+2= 2, 3, 5 B3 = B+3= 3, 4, 6 B4 = B+4= 4, 5, 0 B5 = B+5= 5, 6, 1 B6 = B+6= 6, 0, 2 ,定理：设 B 是 Zv 的 k 元差分集（k v）, 则由 B 可扩展出一个 SBIBD： B = B, B+1, , B+v-1 ,证明： Zv = 0, 1, , v-1, k v, 不完全；b = v, 对称。 只需验证

18、Zv中每对元素(x, y) 出现在 分组中。 = k(k-1) / (v-1) 任取 p, qZv 且 p q, p-q 0. B 是差分集，对 x, y B, x-y = p-q 在 B 有个解 每一对这样的 (x,y), 取 j = p-x , 则 p = x+j , q = y+j 可知 p, q B+j 中, (p, q) 配对出现次，均衡。 所以，B是SBIBD。,例8：X = Z11，( mod 11) , k=5, 差分集 B = 0, 2, 3, 4, 8 ，= 2,B = 0, 2, 3, 4, 8 B1 = B+1= 1, 3, 4, 5, 9 B2 = B+2= 2, 4

19、, 5, 6, 10 B3 = B+3= 3, 5, 6, 7, 0 B4 = B+4= 4, 6, 7, 8, 1 B5 = B+5= 5, 7, 8, 9, 2 B6 = B+6= 6, 8, 9, 10, 3 B7 = B+7= 7, 9, 10, 0, 4 B8 = B+8= 8, 10, 0, 1, 5 B9 = B+9= 9, 0, 1, 2, 6 B10 = B+10= 10, 1, 2, 3, 7 ,三、Steiner 三元系统（k=3）,1、 k = 1 无实际搭配意义， k = 2 每组仅含一对元素，设计简单,例9 设 v = 6, k = 2, = 1。 求 BIBD,0

20、,1, 0,2,0, 3, 0,4, 0,5, 0,6,1,2, 1,3, 1,4, 1,5, 1,6, 2,3, 2,4, 2,5, 2,6, 3,4, 3,44,5,2、 k = 3 ： Steiner 三元系统,定理：在三元 Steiner 系统中， r = (v-1)/2 , b = v(v-1)/6 当=1时， v = 6n+1 或 6n+3,3、 由低阶构造高阶三元系统,定理：设B1、B2是有v和w个样本, 且=1 的 Steiner 三元系统，则必可构造出有vw 个样本且=1的 Steiner 三元系统,构造方法：,样本A,样本B,样本C,例9 构造一个 3*3 的三元 Stei

21、ner 系统 BIBD,=1，r =(v-1)/2 = (9-1)/2 = 4,例9 构造一个 3*3 的三元 Steiner 系统 BIBD,直观解释为： 9个女生每天排成三人一行进行训练， 可以连续 4天不同的排队，使每个女生 与她的每个同学相遇且仅相遇1次。,4、Kirkman 三元系统,例10 （Kirkman 女生问题） 15个女生排成 5 排、每排3人进行训练，能否连 续训练7天，使每个女生与她的每个同学相遇（ 在同一排）且仅相遇1次？,构成 Kirkman 三元系统的条件：,对每个n, 是否存在 v= 6n+3 的可解类？,n= 0 , v=3, OK,n= 1 , v=9, O

22、K,n= 3, v=21, OK,直至 1971年，Ray-Chaudhuri& Wilson才给出对所有n的构造方法。,指数=1的可解Steiner三元系统称为 Kirkman 三元系统。,n= 2 , v=15, OK,例11 构造 v = 21 的 Kirkman 三元系统。,X1=0,1,2, B1= 0,1,2X2=0,1, , 6 ，,B = 0, 1, 3 B1 = B+1= 1, 2, 4 B2 = B+2= 2, 3, 5 B3 = B+3= 3, 4, 6 B4 = B+4= 4, 5, 0 B5 = B+5= 5, 6, 1 B6 = B+6= 6, 0, 2 ,B2 由

23、差分集导出：,导出 X = 3x7 矩阵,2、同行的元素，要在B2中。共3x7=21组：,B = 0, 1, 3 B1 = B+1= 1, 2, 4 B2 = B+2= 2, 3, 5 B3 = B+3= 3, 4, 6 B4 = B+4= 4, 5, 0 B5 = B+5= 5, 6, 1 B6 = B+6= 6, 0, 2 ,1、同列的元素，要在B1中。共7组：,B = 0, 1, 3 B1 = B+1= 1, 2, 4 B2 = B+2= 2, 3, 5 B3 = B+3= 3, 4, 6 B4 = B+4= 4, 5, 0 B5 = B+5= 5, 6, 1 B6 = B+6= 6,

24、0, 2 ,3、不同行不同列。 列1,2,3, 行取0,1,3时，按非攻击车位置，构造6个区组：,列1,2,3, 行取B2的其他区组，类似处理。 共可构造 6x7 = 42 个区组。全部 7+21+42=70个区组。,2 拉丁方（LS）,一、拉丁方（LS）,拉丁方的定义,A=,A=,A(0) =,A(1)=,A(2)=,A(3)=,改变数字排列顺序， 仍然是一个拉丁方。 用一个 n 阶拉丁方可以 构造出 n! 个拉丁方。,标准拉丁方,二、拉丁方的构造方法,方法1 加法表,定理1,证明：,方法2 仿射运算,定理 2,证明：,例1 在 Z5 上，取 r = 3, 构造拉丁方 L35,由于 5 是素

25、数，1, 2, 3, 4 在 Z5 上都有逆，可构造出 4 个相应的拉丁方,定理 3,例2 在 Z3 上,每个有序数偶恰好出现一次。,三、正交拉丁方（OLS）,1、定义：,设有两个 n 阶拉丁方 A，B, 若在AxB 中 Zn 的每个有序数偶 ( i, j ) 恰好出现一次， 则称A与B是正交拉丁方，记为 OLS。,例3,A、B是一对正交拉丁方（OLS）。,例4,使用正交拉丁方（OLS）可以安排双因素实验， 使A、B的各个水平的搭配恰好各实验一次。,小麦产量受到播种量和施肥量两个因素的影响。 播种量分成4个等级: 0, 1, 2, 3 施肥量也分成4个等级：0, 1, 2, 3 两两搭配会有1

26、6种情况，如何设计实验？,而且能很好地保证地块条件的均匀性。,例5 （36军官问题）,来自6个不同国家、6种不同军衔的36名军官，能否 排成 6x6 的方阵，使每行和每列上的军官来自不同 的国家且有不同的军衔？,这是 6 阶 OLS 的存在性问题。,这个问题由欧拉最先提出。 欧拉指出，对 n =2k+1 和 n = 4k ，可以构造出 OLS， 但是欧拉猜测 n=4k+2 时 不存在 OLS。,n=2，不存在OLS。 1910年，Tarry 证明了 n=6 时不存在 OLS。 1960年前后，Bose、Parke、Shrikhande 三人证明了 对 n = 4k+2 (k 1) 都可以构造出

27、 OLS。,他们三人的工作，彻底否定了欧拉猜想。,四、相互正交拉丁方（MOLS）,1、定义：,设有 A1, A2, , Ak 均为 n 阶拉丁方, 若它们中的任意两对 Ai, Aj 都是OLS , 则称 A1, A2, , Ak 是相互正交拉丁方， 记为 MOLS。,定理 4,证明：,证明：,定理 5,证明：,例6 构造 3 个基于F(22) 的 4 阶的 MOLS,例6 构造 3 个基于F(22) 的 4 阶的 MOLS,定理 6,定理 7,n是素数，或素数的幂，能取等号，有n-1个MOLS,五、用低阶 MOLS 构造高阶 MOLS,定理 8,方法：,例7,重新标号,定理 9,定理 10,证明：,定理 10,六、MOLS 与 BIBD,定理11：,构造方法：,例 8,构造方法：,反向操作，由上述BIBD 可得 MOLS !,习题10（第4版）221,19，20，2326，28，29，30, 3142，44, 46, 47, 49,