《淺談組合數學》ppt課件 (2)-全文預覽
【正文】 ? 完全的無序是不可能的 (Complete disorder is impossible)。s用如下比喻說明其困難程度：一伙外星人入侵地球，要求一年內求得 R(5,5)，否則將滅絕人類！那么也許人類能集中所有計算機和專家來求出它以自保；但如果外星人問的是 R(6,6) ，那么人類將別無選擇，只能拼死一戰(zhàn)了。 ? 推廣為一般問題則得到如下的 Ramsey數問題： Ramsey定理 ? Ramsey(19031930)：給定任意正整數 p和 q，總存在一個最小正整數 R(p,q)，使得 R(p,q)個人中或者有 p 個人互相認識，或者有 q 個人互不相識。 相識問題 ? 1958年，美國的 《 數學月刊 》 上登載著這樣一個有趣的問題： “ 任何 6個人的聚會，其中總會有 3個人相互認識，或 3個人相互不認識 ” 。 ? AppelHaken(1976)： 給出計算機證明 （ 1200小時 100億個判斷）。 ? 直到 1976年 6月，美國數學家 K. Appel與 W. Haken，在 3臺不同的電子計算機上，用了 1200小時，才終于完成了 “ 四色猜想 ” 的證明，從而使 四色猜想 成為了 四色定理 。比如一個著名的世界難題 “ 四色猜想 ” ：一張地圖，用一種顏色對一個地區(qū)著色，那么一共只需要四種顏色就能保證每兩個相鄰的地區(qū)顏色不同。 K246。nigsberg城，河上建有七座橋 ，能否設計散步路線，走過所有七座橋，每座橋恰好經過一次而回到同一地點？ ? Euler1736年證明了不可能存在這樣的路線。 上圖為三階洛書 幻方問題 ? 組合數學中有許多象幻方這樣精巧的結構。 組合數學概述 ? 吳文俊 院士指出，每個時代都有它特殊的要求，使得數學出現一個新的面貌，產生一些新的數學分支，組合數學這個新的分支也是在時代的要求下產生的。計算機之所以可以被稱為電腦，就是因為計算機被人編寫了程序，而程序就是算法，在絕大多數情況下，計算機的算法是針對離散的對象，而不是在作數值計算。淺談組合數學 組合數學概述 ? 現代數學根據所研究的對象可分為兩類： 連續(xù)數學：以微積分為基礎，傳統(tǒng)主流； 離散數學：伴隨計算機科學，方興未艾。而組合數學的發(fā)展則是奠定了本世紀的計算機革命的基礎。 ? 1666年 Leibniz著 《 Dissertatio de arte binatoria》 ,首次使用了組合一詞。 組合數學歷史及典型問題 ? 傳說在公元前 23世紀大禹治水的時候，在黃河支流洛水中，浮現出一個 大烏龜，甲上背有 9種花點的圖案，人們將圖案中的花點數了一下，競驚奇地發(fā)現 9種花點數正巧是 1—9這 9個數，各數位置的排列也相當奇妙，橫的 3行、縱的 3列以及兩對角線上各自的數字之和都為 15。 1 1， 1 1， 2， 1 1， 3， 3， 1 1， 4， 6， 4， 1 1， 5， 10， 10， 5， 1 1， 6， 15， 20， 15， 6， 1 七橋問題 ? 近代圖論的歷史可追溯到 18世紀的 七橋問題 —Pregel河橫穿 K246。 ? 對任意的非空連通圖，若它是 歐拉的 , 當且僅當它沒有奇度點。 拉丁方陣與 正交拉丁方陣 每名軍官對應一個有序對（軍團，軍銜） 以 9名軍官為例： 軍團陣列 軍銜陣列 并置陣列 （拉丁方陣） （拉丁方陣） （ 正交拉丁方陣） 1 2 3 1 2 3 ( 1 , 1 ) ( 2 , 2 ) ( 3 , 3 )3 1 2 2 3 1 ( 3 , 2 ) ( 1 , 3 ) ( 2 , 1 )2 3 1 3 1 2 ( 2 , 3 ) ( 3 , 1 ) ( 1 , 2 )? ? ? ? ? ?? ? ? ? ? ???? ? ? ? ? ?? ? ? ? ? ?? ? ? ? ? ? 36 軍官問題 (歐拉 1779) The Great Frederic的閱兵難題 歐拉的困惑 拉丁方陣 : 1221??????1 2 32 3 13 1 2????????1 2 4 32 3 1 43 4 2 14 1 3 2????????????正交拉丁方陣 : 1 2 33 1 22 3 1????????1 2 32 3 13 1 2????????1 2 33 1 2231 2 32 3 131 1 2????????Euler 猜想 ? 不存在 6階正交拉丁方 ? 不存在 4k+2階正交拉丁方 現在的結論 ? 對任正整數 n≠2,6， 存在 n 階正交拉丁方
教學課件相關推薦
鄂ICP備17016276號-1