教材RABrualdi组合数学机械工业出版社影印版.ppt
《教材RABrualdi组合数学机械工业出版社影印版.ppt》由会员分享,可在线阅读,更多相关《教材RABrualdi组合数学机械工业出版社影印版.ppt(29页珍藏版)》请在三一文库上搜索。
1、教材: R. A. Brualdi, 组合数学, 机械工业出版社(影印版, 中译第4版) 参考:1. 卢开澄, 组合数学,清华大学出版社 2. 吴文虎等, 程序设计中的组合数学, 清华大学出版社 网络教室: 组合数学,组合数学,计算机学院软件所:王贵珍 Tel: 13167532629 Email: Address: 中心教学楼905#,课 程 安 排,课程特点及最后成绩 1. 课程特点:技巧性较强。 2. 成绩评定:作业、程序设计占30,期末为闭卷笔试考试,成绩占70。, 提示: 技巧的应用来自于经验的积累,所以 解决的组合数学问题越多,那么能够解决下 一个组合数学问题的可能性就越大。,组合
2、数学研究的内容,离散结构的存在、计数、分析 和优化。,例:棋盘的完美覆盖,mn棋盘: m行n列方格, b-牌:1行b个的方格条 mn棋盘被b-牌的一个完美覆盖是 b-牌在棋盘上的一个排列, 满足: (1) 每个格子恰好只被一张牌覆盖; (2) 每条b-牌覆盖b个方格.,定理: mn棋盘有b-牌的完美覆盖b|m或b|n.,34棋盘 66棋盘有4-牌的完美覆盖吗?,有2-牌的完美覆盖.,棋盘覆盖及其变化,66棋盘用1,2,3,4如图填数,4牌在任何位置都覆盖1,2,3,4,去掉成组的1234, 多余1124。所以66棋盘不能用4牌完美覆盖。,完美覆盖,变化: 带禁止方格, 用多米诺牌(2-牌)覆盖
3、,例:Nim取子游戏,设有k1堆硬币,各堆分别含有n1,n2,nk枚硬币. 游戏规则: (1)两游戏人交替取子; (2)每人在一轮取子时只能取一堆中的硬币, 取至少一枚,至多全堆硬币; (3)所有堆都变成空堆时, 游戏结束, 最后取子的人获胜. 例1. (100, 389) 例2. (7, 8, 15),游戏人I有必胜策略,游戏人II有必胜策略,平衡态,设有游戏(n1,n2,nk), 且各数的二进制展开是 ni=aisai(s-1)ai1, i=1,2,k 若 a11+a21+ak1 (各数第1位之和), a1s+a2s+aks (各数第s位之和) 都是偶数, 则称游戏处于平衡态.,(7,8,
4、15): (100,389): (7,12,13):,平衡态,非平衡态,非平衡态,平衡态与非平衡态的转化,(7,8,15):平衡态 (100,389):非平衡态 (7,8,13):非平衡态,游戏终止时是平衡态 平衡态不能经一轮取子达到平衡态 非平衡态可经一轮取子达到平衡态(?),结论,定理: 若游戏非平衡, 则游戏人I有必胜策略; 若游戏平衡, 则游戏人II有必胜策略. 定义: 若n1,n2,nk二进展开第i位的和是奇数, 则称第i位是非平衡位. 命题: 设一游戏最大非平衡位是第j位, 则 游戏人I可以从某堆取币使游戏达到平衡态 当且仅当 该堆币数二进展开第j位是1. 注意比较与习题1.33叙
5、述的差别.,拉丁方,定义: 若A是由n个元素构成的n阶方阵, 其中每个元素在每行每列各出现一次, 则称A是拉丁方. 设A=(aij), 每个元素每行(列)只出现一次: aij=aik j=k ( aji=aki j=k ),36名军官问题,(18世纪)36军官问题: 6个地区, 6种军衔各一名. 将这36名军官排成66方阵, 使得 1)每行每列都有任一地区的军官; 2)每行每列都有任一军衔的军官. i :军衔, j :地区, 军官对应数偶(i, j), i, j0,5 问题等价于构造数偶(i,j)排成的6阶方阵, 使得 1) 数偶第一个数字构成拉丁方; 2) 数偶第二个数字构成拉丁方; 3)
6、每个数偶只出现一次.,正交拉丁方,定义:设A=(aij)nn,B=(bij)nn是两个nn拉丁方. 令C=(aij, bij)nn,若C的n2对数偶互不相同, 则称A与B正交. 36军官问题等价于构造两个正交的6阶拉丁方. 例: 3阶正交拉丁方,正交拉丁方的实际意义,正交的拉丁方的一个应用: 药物配合试验 三种治发烧药和三种治感冒药, 对三位病人试验, 要求三天内每人都服这几种药, 比较配合疗效. 这时就可用上面讨论过的3阶正交拉丁方.,行:人, 列:天 (i,j): i,发烧药 j, 感冒药,Euler的猜测,令N(n)为两两正交的n阶拉丁方的最大个数. N(1)=2, N(2)=1, N(
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 教材 RABrualdi 组合 数学 机械 工业出版社 影印
链接地址:https://www.31doc.com/p-2575348.html