淺談組合數(shù)學(xué)ppt課件(2)(已修改)
2025-01-29 18:14 本頁(yè)面
【正文】 淺談組合數(shù)學(xué) 組合數(shù)學(xué)概述 ? 現(xiàn)代數(shù)學(xué)根據(jù)所研究的對(duì)象可分為兩類： 連續(xù)數(shù)學(xué)：以微積分為基礎(chǔ)，傳統(tǒng)主流； 離散數(shù)學(xué)：伴隨計(jì)算機(jī)科學(xué)，方興未艾。 ? 計(jì)算機(jī)出現(xiàn)以后，由于離散對(duì)象的處理是計(jì)算機(jī)科學(xué)的核心，研究離散對(duì)象的組合數(shù)學(xué)得到迅猛發(fā)展 。 ? 微積分和近代數(shù)學(xué)的發(fā)展為近代的工業(yè)革命奠定了基礎(chǔ)。而組合數(shù)學(xué)的發(fā)展則是奠定了本世紀(jì)的計(jì)算機(jī)革命的基礎(chǔ)。計(jì)算機(jī)之所以可以被稱為電腦，就是因?yàn)橛?jì)算機(jī)被人編寫(xiě)了程序，而程序就是算法，在絕大多數(shù)情況下，計(jì)算機(jī)的算法是針對(duì)離散的對(duì)象，而不是在作數(shù)值計(jì)算。正是因?yàn)橛辛私M合算法才使人感到，計(jì)算機(jī)好象是有思維的。 組合數(shù)學(xué)概述 ? 組合數(shù)學(xué)（ Combinatorial Mathematics) 也稱組合學(xué) (Combinatorics) 或離散數(shù)學(xué) (Discrete Mathematics) ? 組合數(shù)學(xué)是一門(mén)研究離散對(duì)象的科學(xué) ，狹義的組合數(shù)學(xué)主要研究滿足一定條件的組態(tài)（也稱組合模型）的存在、計(jì)數(shù)以及構(gòu)造等方面的問(wèn)題。 ? 1666年 Leibniz著 《 Dissertatio de arte binatoria》 ,首次使用了組合一詞。 組合數(shù)學(xué)概述 ? 吳文俊 院士指出，每個(gè)時(shí)代都有它特殊的要求，使得數(shù)學(xué)出現(xiàn)一個(gè)新的面貌，產(chǎn)生一些新的數(shù)學(xué)分支，組合數(shù)學(xué)這個(gè)新的分支也是在時(shí)代的要求下產(chǎn)生的。 ? 最近， 吳文俊 院士又指出，信息技術(shù)很可能會(huì)給數(shù)學(xué)本身帶來(lái)一場(chǎng)根本性的變革，而組合數(shù)學(xué)則將顯示出它的重要作用。 ? GianCarlo Rota教授曾提出要向中國(guó)領(lǐng)導(dǎo)人呼吁，組合數(shù)學(xué)是計(jì)算機(jī)軟件產(chǎn)業(yè)的基礎(chǔ)，中國(guó)最終一定能成為一個(gè)軟件大國(guó)，但是要實(shí)現(xiàn)這個(gè)目標(biāo)的一個(gè)突破點(diǎn)就是發(fā)展組合數(shù)學(xué)。 組合數(shù)學(xué)歷史及典型問(wèn)題 ? 傳說(shuō)在公元前 23世紀(jì)大禹治水的時(shí)候，在黃河支流洛水中，浮現(xiàn)出一個(gè) 大烏龜，甲上背有 9種花點(diǎn)的圖案，人們將圖案中的花點(diǎn)數(shù)了一下，競(jìng)驚奇地發(fā)現(xiàn) 9種花點(diǎn)數(shù)正巧是 1—9這 9個(gè)數(shù)，各數(shù)位置的排列也相當(dāng)奇妙，橫的 3行、縱的 3列以及兩對(duì)角線上各自的數(shù)字之和都為 15。 上圖為三階洛書(shū) 幻方問(wèn)題 ? 組合數(shù)學(xué)中有許多象幻方這樣精巧的結(jié)構(gòu)。 ? 1977年美國(guó)旅行者 1號(hào)、 2號(hào)宇宙飛船就帶上了幻方以作為人類智慧的信號(hào)。 神 農(nóng) 幻 方 4 9 23578 1 62200BC 1 15 14 4 12 6 7 9 8 10 11 5 13 3 2 16 15世紀(jì) ４ 階 幻 方 賈憲三角 ? 中國(guó)最早的組合數(shù)學(xué)理論可追溯到宋朝時(shí)期的 ” 賈憲三角 ” , 后來(lái)被楊輝引用 , 所以普遍稱之為 ” 楊輝三角 ” , 這在西方是 1654年由帕斯卡提出，但比中國(guó)晚了 400多年。 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 七橋問(wèn)題 ? 近代圖論的歷史可追溯到 18世紀(jì)的 七橋問(wèn)題 —Pregel河橫穿 K246。nigsberg城，河上建有七座橋 ，能否設(shè)計(jì)散步路線，走過(guò)所有七座橋，每座橋恰好經(jīng)過(guò)一次而回到同一地點(diǎn)？ ? Euler1736年證明了不可能存在這樣的路線。 Euler環(huán)游（一筆畫(huà)） ? Euler于 1736年給以否定： 圖有這樣的路線當(dāng)且僅當(dāng) 每個(gè)點(diǎn)連接偶數(shù)條邊。 ? 圖論的起源 Euler 定理 ? 如果一個(gè)圖包含一條經(jīng)過(guò)每條邊恰好一次的閉途徑，則稱這個(gè)圖為 歐拉圖 。 ? 對(duì)任意的非空連通圖，若它是 歐拉的 , 當(dāng)且僅當(dāng)它沒(méi)有奇度點(diǎn)。 K246。nigsberg橋?qū)?yīng)的圖 三十六軍官問(wèn)題 ? 普魯士腓特烈大帝在一次檢閱中要求： 從不同的 6個(gè)軍團(tuán)各選 6種不同軍銜的 6名軍官共 36人，排成一個(gè) 6行 6列的方隊(duì)，使得各行各列的 6名軍官恰好來(lái)自不同的軍團(tuán)而且軍銜各不相同。 ? Euler（ 1779） ：辦不到 ! 但末能給出嚴(yán)格的證明 。 拉丁方陣與 正交拉丁方陣 每名軍官對(duì)應(yīng)一個(gè)有序?qū)Γㄜ妶F(tuán)，軍銜） 以 9名軍官為例： 軍團(tuán)陣列 軍銜陣列 并置陣列 （拉丁方陣） （拉丁方陣） （ 正交拉丁方陣） 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 )? ? ? ? ? ?? ? ? ? ? ???? ? ? ? ? ?? ? ? ? ? ?? ? ?
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1