《淺談組合數(shù)學(xué)》ppt課件 (2)-預(yù)覽頁(yè)
【正文】 四色問題 ? 在日常生活中我們常?？梢杂龅浇M合數(shù)學(xué)的問題。 ? 此后數(shù)學(xué)家 Heawood 花費(fèi)了畢生的精力致力于四色研究，于 1890年證明了五色定理（ 每個(gè)平面圖都是 5頂點(diǎn)可著色的 ）。五色定理。那么如何選擇一條盡可能短的路線。 ? 五個(gè)點(diǎn)的則不然。 Ramsey數(shù) R(p,q) p,q 3 4 5 6 7 8 9 3 6 9 14 18 23 28 36 4 18 25 35–41 49–61 56–84 69–115 5 43–49 58–87 80–143 101–216 121–316 6 102–165 111–298 127–495 169–780 7 205–540 216–1031 232–1713 8 282–1870 317–3583 9 565–6588 Ramsey數(shù)的計(jì)算 ? Ramsey數(shù)的計(jì)算是對(duì)人類智力的挑戰(zhàn)！例如 R(4,5)=25 (1993年計(jì)算機(jī) 11年的計(jì)算量 ) ? Erd246。s ? 1997年 Fulkerson獎(jiǎng)得主 Kim ? 1998年 Fields獎(jiǎng)得主 Gowers ? 1999年 Wolf獎(jiǎng)得主 Lovasz ? 2022年 Steele獎(jiǎng)得主 Graham ? 2022年 G246。 ? 古人在滿天的星斗中發(fā)現(xià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í)的女孩。 穩(wěn)定的婚姻問題 ? 這種組合數(shù)學(xué)的方法有一個(gè)實(shí)際的用途：美國(guó)的醫(yī)院在確定錄取住院醫(yī)生時(shí)，他們將考慮申請(qǐng)者的志愿的先后次序，同時(shí)也給申請(qǐng)者排序。 ? 例如 914的模式為： 312 37925 的模式為： 24513 棧排序問題 (Knuth, 1960’s) ? 避免３１２排列 ：一個(gè)排列是避免３１２的，當(dāng)且僅當(dāng)它的任意子序列中沒有３１２模式。 ? Tutte 從德軍的兩條情報(bào)密碼出發(fā)，用組合數(shù)學(xué)的方法，重建了敵人的密碼機(jī)，確定了德軍密碼的內(nèi)部結(jié)構(gòu)，從而獲得了極為重要的情報(bào)。 應(yīng)用促進(jìn)理論發(fā)展 ? 36個(gè)軍官問題這個(gè)純粹來自智力游戲的題目孕育著艱深的數(shù)學(xué)問題 。 Fisher的試驗(yàn)設(shè)計(jì)是一股巨大的推動(dòng)力量，把一種數(shù)學(xué)游戲變成了節(jié)約人力物力的具有重大價(jià)值的科學(xué)方法。其本質(zhì)就是如何將一個(gè)集合中的元素組合成一定的子集系以滿足一定的要求。 網(wǎng)絡(luò)流問題 ? 隨著中國(guó)經(jīng)濟(jì)快速的增長(zhǎng)，城市化是未來中國(guó)的發(fā)展方向。 網(wǎng)絡(luò)流問題 ? 1956年 Ford 和 Fulkerson 提出了關(guān)于網(wǎng)絡(luò)流問題的一個(gè)重要定理。 網(wǎng)絡(luò)可靠性問題 ? 一個(gè)通訊網(wǎng)絡(luò)怎樣布局穩(wěn)定性最好，而且費(fèi)用最節(jié)??？ ? 美國(guó)的貝爾實(shí)驗(yàn)室和 IBM公司都有世界一流的組合數(shù)學(xué)家在研究這個(gè)問題，這個(gè)問題直接關(guān)系到巨大的經(jīng)濟(jì)利益。最短新路徑之長(zhǎng) N比原來只連三點(diǎn)的最短路徑 O要短。寄信的規(guī)則很簡(jiǎn)單，就是任何收信者只能把信寄給自己熟識(shí)的人。asi et ，任意兩個(gè)網(wǎng)頁(yè)間的鏈接最多為 19次。 ? 如果將基因看作網(wǎng)絡(luò)中的頂點(diǎn)，將他們之間的作用看作網(wǎng)絡(luò)中的邊，那么每一次大規(guī)模實(shí)驗(yàn)將給我們帶來關(guān)于基因交互作用網(wǎng)絡(luò)的一些信息。 ? “ 二、九、四；七、五、三；六、一、八 ” 《 大戴禮記 此外，他還構(gòu)造出了五階、六階、七階、八階、九階和十階幻方 (百子圖 )。 楊輝三角 ? 楊輝（南宋）著 《 詳解九章算法 》 (1261年 )中曾引賈憲（北宋）的 “ 開方作法本源 ”圖。s 1303 Identity Implies Bombieri39。sKoRado定理 ? FranklGraham： Erd246。 ? Erd246。 中國(guó)郵遞員問題 ? 管梅谷（ 1960）： 郵遞員從郵局出發(fā)送信，要求對(duì)轄區(qū)內(nèi)每條街都至少通過一次再回郵局，怎樣選擇一條最短路線 ? ? 現(xiàn)實(shí)生活中很多問題可以轉(zhuǎn)化為中國(guó)郵遞員問題。 GilbertPollak猜想 ? 1990年，堵丁柱和黃光明合作證明了 GilbertPollak猜想 (1968)。 機(jī)器證明 —— 吳消元法 ? 1976年 吳文俊 教授開始進(jìn)行研究幾何定理的機(jī)器證明，并在很短的時(shí)間內(nèi)取得重大突破。 ? 吳方法不僅可證明已有的幾何定理，而且可以自動(dòng)發(fā)現(xiàn)新的定理。 ——當(dāng)符合要求的安排并非顯然存在或不存在時(shí)，首要的問題是證明或否定它的存在 . ——當(dāng)符合要求的安排顯然存在，或者已證明它存在時(shí)，求出這類安排的各抒己見，或者把它分類 . （組合設(shè)計(jì)） ——把滿足某種條件的安排構(gòu)造出來 . ——給出最優(yōu)標(biāo)準(zhǔn)，找出滿足給定條件的最優(yōu)安排 . 組合數(shù)學(xué)的分支 ? 組合分析 ? 代數(shù)組合 ? 極值集論 ? 圖 論 ? 組合設(shè)計(jì) ? 組合優(yōu)化 ? 組合算法
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1