淺談組合數(shù)學(xué)ppt課件(2)(編輯修改稿)
2025-02-13 18:14 本頁(yè)面
【文章內(nèi)容簡(jiǎn)介】 的是 R(6,6) ，那么人類(lèi)將別無(wú)選擇，只能拼死一戰(zhàn)了。 最精美的組合定理 Rota：如果要求在組合學(xué)中僅舉出一個(gè)精美的定理，那么大多數(shù)組合學(xué)家會(huì)提名Ramsey定理。 ? 1984年 Wolf獎(jiǎng)得主 Erd246。s ? 1997年 Fulkerson獎(jiǎng)得主 Kim ? 1998年 Fields獎(jiǎng)得主 Gowers ? 1999年 Wolf獎(jiǎng)得主 Lovasz ? 2022年 Steele獎(jiǎng)得主 Graham ? 2022年 G246。del獎(jiǎng)得主 Alon ? 2022年 Fields獎(jiǎng)得主 Tao 均對(duì) Ramsey理論有杰出貢獻(xiàn) Ramsey理論的哲理意義 ? 完全的無(wú)序是不可能的 (Complete disorder is impossible)。任一足夠大的結(jié)構(gòu)中必定包含一個(gè)給定大小的規(guī)則子結(jié)構(gòu)。無(wú)序無(wú)意的行為產(chǎn)生了有規(guī)律的后果，發(fā)人深思耐人尋味。 ? 古人在滿天的星斗中發(fā)現(xiàn)野獸和眾神群集于天空的圖形，以為是造物主的杰作。但根據(jù) Ramsey 定理，只要隨機(jī)分布的星星數(shù)目足夠多，就可以描繪出各種圖形的輪廓。 ? 1994年 Statistical Science的一篇論文利用統(tǒng)計(jì)方法證明：圣經(jīng)隱藏了許多訊息，而這些訊息是有意安排的，絕非文字排列偶然造成的。 1997 年 Michael Drosnin的 《 The Bible Code 》通過(guò)計(jì)算機(jī)掃讀圣經(jīng)中的 304805個(gè)字母，發(fā)現(xiàn)圣經(jīng)密碼當(dāng)中傳達(dá)的訊息除了拉賓被刺殺外，還包括美國(guó)肯尼迪和林肯兩位總統(tǒng)，以及印度總理甘地遇刺的事件，日本神戶、美國(guó)舊金山的大地震、世界末日與廣島原子彈轟炸等，種種過(guò)去與未來(lái)發(fā)生的大事件。 穩(wěn)定的婚姻問(wèn)題 ? 組合數(shù)學(xué)中有一個(gè)著名定理：如果一個(gè)村子里每一個(gè)女孩都恰好認(rèn)識(shí) k個(gè)男孩，并且每一個(gè)男孩也恰好認(rèn)識(shí) k個(gè)女孩，那么每一個(gè)女孩都可以嫁給她認(rèn)識(shí)的一個(gè)男孩，并且每一個(gè)男孩都可以娶一個(gè)他認(rèn)識(shí)的女孩。（ k 正則二部圖，一定存在一個(gè)完美匹配 ） 穩(wěn)定的婚姻問(wèn)題 ? 但是這樣的安排方法不一定是最好的。假如能找到兩對(duì)夫婦，彼此都更喜歡對(duì)方的配偶，那么這樣婚姻有潛在的不穩(wěn)定性。 ? 用圖論匹配理論中 GaleShapley算法，可以找到一種婚姻的安排方法，使得沒(méi)有上述的不穩(wěn)定情況出現(xiàn)。 穩(wěn)定的婚姻問(wèn)題 ? 這種組合數(shù)學(xué)的方法有一個(gè)實(shí)際的用途：美國(guó)的醫(yī)院在確定錄取住院醫(yī)生時(shí)，他們將考慮申請(qǐng)者的志愿的先后次序，同時(shí)也給申請(qǐng)者排序。按這樣的次序考慮出的總的方案將沒(méi)有醫(yī)院和申請(qǐng)者兩者同時(shí)后悔的情況。 實(shí)際上，高考學(xué)生的最后錄取方案也可以用這種方法。 棧排序問(wèn)題 (Knuth, 1960’s) ? 模式 : 對(duì)任意一個(gè)排列 π , 最小的元素用１代替，次小的元素用２代替 …… 以此類(lèi)推，這樣得到的排列叫 π的模式。 ? 例如 914的模式為： 312 37925 的模式為： 24513 棧排序問(wèn)題 (Knuth, 1960’s) ? 避免３１２排列 ：一個(gè)排列是避免３１２的，當(dāng)且僅當(dāng)它的任意子序列中沒(méi)有３１２模式。 ? 例如 π＝ 132564是避免 312的排列 π＝ 146235是包含 312的排列 棧排序問(wèn)題 (Knuth, 1960’s) 8 7 6 5 4 3 2 1 避免 312排列 組合數(shù)學(xué)的應(yīng)用 ? 組合數(shù)學(xué)不僅在基礎(chǔ)數(shù)學(xué)研究中具有極其重要的地位，在其它的學(xué)科如計(jì)算機(jī)科學(xué)、編碼和密碼學(xué)、物理、化學(xué)、生物等學(xué)科中，甚至在企業(yè)管理，交通規(guī)劃，戰(zhàn)爭(zhēng)指揮，金融分析，城市物流等領(lǐng)域均有重要應(yīng)用。 組合數(shù)學(xué)的應(yīng)用 ? 著名的組合數(shù)學(xué)家 Thomas Tutte 在組合數(shù)學(xué)界是泰斗級(jí)的大師。直到最近人們才知道，原來(lái)他對(duì)提前結(jié)束 “ 二戰(zhàn) ” 有著突出貢獻(xiàn)。 ? Tutte 從德軍的兩條情報(bào)密碼出發(fā)，用組合數(shù)學(xué)的方法，重建了敵人的密碼機(jī)，確定了德軍密碼的內(nèi)部結(jié)構(gòu)，從而獲得了極為重要的情報(bào)。 組合數(shù)學(xué)的應(yīng)用 ? 在美國(guó)有一家公司用組合數(shù)學(xué)的方法來(lái)提高企業(yè)管理的效益，這家公司辦得非常成功。 ? 在美國(guó)已有專(zhuān)門(mén)的公司用組合設(shè)計(jì)的方法開(kāi)發(fā)軟件，來(lái)解決工業(yè)界中的試驗(yàn)設(shè)計(jì)問(wèn)題。 ? 德國(guó)一位著名組合數(shù)學(xué)家利用組合數(shù)學(xué)方法研究藥物結(jié)構(gòu)，為制藥公司節(jié)省了大量的費(fèi)用，引起了制藥業(yè)的關(guān)注。 應(yīng)用促進(jìn)理論發(fā)展 ? 36個(gè)軍官問(wèn)題這個(gè)純粹來(lái)自智力游戲的題目孕育著艱深的數(shù)學(xué)問(wèn)題 。 Euler猜想直到二十世紀(jì)中葉才獲得解決，有兩個(gè)原因：一是理論上的準(zhǔn)備。這類(lèi)問(wèn)題用初等方法很難解決，二十世紀(jì)代數(shù)和幾何的發(fā)展為解決問(wèn)題提供了必要工具（如 Galois域上的射影幾何即有限幾何等）；二是生產(chǎn)實(shí)際的推動(dòng)。數(shù)理統(tǒng)計(jì)學(xué)家Fisher將正交拉丁方用于試驗(yàn)設(shè)計(jì)，例如，用二種原料合成某染料，每種原料有 3個(gè)水平，怎樣安排試驗(yàn)?zāi)苁姑糠N原料的各種水平各碰一次？這正好是 3階的正交拉丁方陣問(wèn)題。 Fisher的試驗(yàn)設(shè)計(jì)是一股巨大的推動(dòng)力量，把一種數(shù)學(xué)游戲變成了節(jié)約人力物力的具有重大價(jià)值的科學(xué)方法
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1