1、2020/9/3,離散數(shù)學(xué),1,離散數(shù)學(xué)Discrete Mathematics,主講教師：歐陽(yáng)柳波 URL: Email: Off.-Tel: 8821984,2020/9/3,離散數(shù)學(xué),2,研究離散結(jié)構(gòu)的數(shù)學(xué)分科。（辭海）,Discrete Math. 離散數(shù)學(xué) 研究離散量的關(guān)系的一門科學(xué)。,2020/9/3,離散數(shù)學(xué),3,Discrete Math.,計(jì)算機(jī)系統(tǒng)本身可以看成是一個(gè)有限（存儲(chǔ)空間、運(yùn)算速度）的離散結(jié)構(gòu)，所以計(jì)算機(jī)科學(xué)研究的對(duì)象大多是離散型的。由此產(chǎn)生了作為計(jì)算機(jī)科學(xué)的數(shù)學(xué)基礎(chǔ)離散數(shù)學(xué)。 離散數(shù)學(xué)是以離散量為研究對(duì)象的，其主要內(nèi)容在計(jì)算機(jī)出現(xiàn)之前已散見于各數(shù)學(xué)分支中，且其內(nèi)容

2、隨著計(jì)算機(jī)科學(xué)的發(fā)展不斷豐富和完善。,2020/9/3,離散數(shù)學(xué),4,離散數(shù)學(xué)的由來(lái)與發(fā)展: 一、古老 歷史: 計(jì)數(shù):自然數(shù) 發(fā)展: 圖論:Konigsberg七橋問(wèn)題 二、年青 新生: 計(jì)算機(jī):二進(jìn)制運(yùn)算,2020/9/3,離散數(shù)學(xué),5,現(xiàn)代科學(xué)的重要分支,離散數(shù)學(xué)是在計(jì)算機(jī)問(wèn)世之后，迅速發(fā)展起來(lái)的一門數(shù)學(xué)分支。 離散數(shù)學(xué)改變了傳統(tǒng)數(shù)學(xué)中分析和代數(shù)占統(tǒng)治地位的局面。 離散數(shù)學(xué)是一門在基礎(chǔ)數(shù)學(xué)研究中具有極為重要地位的、綜合的數(shù)學(xué)學(xué)科。 離散數(shù)學(xué)在計(jì)算機(jī)科學(xué)、編碼和密碼學(xué)、物理、化學(xué)、生物等許多學(xué)科中均有重要應(yīng)用。,2020/9/3,離散數(shù)學(xué),6,學(xué)習(xí)的目的和意義：,1、主要內(nèi)容：集合論；圖論；

3、數(shù)理邏輯；代數(shù)結(jié)構(gòu)；組合分析。 2、目的：培養(yǎng)數(shù)學(xué)抽象能力；用數(shù)學(xué)語(yǔ)言描述問(wèn)題的能力；邏輯思維能力；數(shù)學(xué)論證能力。即培養(yǎng)抽象、表示、推理、論證的能力。 3、意義：一是寫出優(yōu)秀的程序來(lái)解決實(shí)際問(wèn)題；二是能針對(duì)科研和生產(chǎn)中產(chǎn)生的問(wèn)題來(lái)建立數(shù)學(xué)模型，設(shè)計(jì)新的算法并論證算法的有效性；三是為學(xué)習(xí)專業(yè)課打好基礎(chǔ)。,2020/9/3,離散數(shù)學(xué),7,離散數(shù)學(xué)課程設(shè)置： 計(jì)算機(jī)科學(xué)專業(yè)核心課程 信息類專業(yè)必修課程 其它類專業(yè)的重要選修課程,2020/9/3,離散數(shù)學(xué),8,離散數(shù)學(xué)的后繼課程： 數(shù)據(jù)結(jié)構(gòu)、編譯技術(shù)、 算法分析與設(shè)計(jì)、人工智能、 數(shù)據(jù)庫(kù)、,2020/9/3,離散數(shù)學(xué),9,離散數(shù)學(xué)課程的學(xué)習(xí)方法: 強(qiáng)

4、調(diào)：邏輯性、抽象性 注重：概念、方法與應(yīng)用,2020/9/3,離散數(shù)學(xué),10,教材: 方世昌編. 離散數(shù)學(xué)(第二版). 西安電子科技大學(xué)出版社 參考書: Bernard Kolman. 離散數(shù)學(xué)結(jié)構(gòu)(第四版).高等教育出版 左孝凌等編. 離散數(shù)學(xué). 上海科學(xué)技術(shù)出版社 耿素云等編. 離散數(shù)學(xué). 清華大學(xué)出版社,2020/9/3,離散數(shù)學(xué),11,典型實(shí)例,離散數(shù)學(xué)無(wú)處不在。 主要應(yīng)用于在各種復(fù)雜的關(guān)系中找出最優(yōu)方案。 離散數(shù)學(xué)完全可以看成是一門量化了的關(guān)系學(xué)，量化了的運(yùn)籌學(xué)，量化了的管理學(xué)。,2020/9/3,離散數(shù)學(xué),12,1、四色猜想問(wèn)題,一張世界地圖，若用一種顏色對(duì)一個(gè)國(guó)家著色，那么只需四

5、種顏色，即可以保證每?jī)蓚€(gè)相鄰的國(guó)家顏色不同。 世界近代三大數(shù)學(xué)難題之一。1852年，英國(guó)弗南西斯格思里(Francis Guthrie)提出四色猜想。 1976年，在J. Koch的算法的支持下，美國(guó)數(shù)學(xué)家阿佩爾(Kenneth Appel)與哈肯(Wolfgang Haken)在美國(guó)伊利諾斯大學(xué)的兩臺(tái)不同的電子計(jì)算機(jī)上，用了1200個(gè)小時(shí)，作了100億判斷，終于完成了四色定理的證明。 最近人們發(fā)現(xiàn)了更簡(jiǎn)單的證明。,2020/9/3,離散數(shù)學(xué),13,2.出差派遣問(wèn)題,A，B，C，D四人中要派兩個(gè)人出差，按下述三個(gè)條件有幾種派法？ 如何派？ 若A去則C和D中要去一個(gè)人； B和C不能都去； C去則

6、D要留下,2020/9/3,離散數(shù)學(xué),14,3、船夫過(guò)河問(wèn)題,船夫要把一匹狼、一只羊和一棵白菜運(yùn)過(guò)河。 只要船夫不在場(chǎng),羊就會(huì)吃白菜、狼就會(huì)吃羊。 船夫的船每次只能運(yùn)送一種東西。 怎樣才能把三者都運(yùn)過(guò)河?,2020/9/3,離散數(shù)學(xué),15,4、工作調(diào)度和安排問(wèn)題,如在生產(chǎn)原子彈的曼哈頓計(jì)劃中，涉及到很多工序、很多人員安排、很多元件生產(chǎn) 怎樣合理調(diào)度各種人員的工作？ 怎樣科學(xué)安排各種工序間的銜接？ 怎樣計(jì)劃使整個(gè)工期的時(shí)間盡可能短？,2020/9/3,離散數(shù)學(xué),16,5、航空調(diào)度和航班設(shè)定問(wèn)題,怎樣周密設(shè)定各個(gè)航班，以滿足不同旅客轉(zhuǎn)機(jī)的需求？ 怎樣同時(shí)也使得每個(gè)機(jī)場(chǎng)的各個(gè)航班的起降分布合理？ 另

7、外，在一些航班有延誤的特殊情況下，怎樣作出科學(xué)的調(diào)整？,2020/9/3,離散數(shù)學(xué),17,6、交通規(guī)劃與管理問(wèn)題,哪些地方可能是阻塞要地？ 哪些地方應(yīng)設(shè)單行道？ 立交橋建在哪里最合適？ 紅綠燈怎樣設(shè)置最合理？,2020/9/3,離散數(shù)學(xué),18,7、中國(guó)郵路問(wèn)題,一個(gè)郵遞員送信，要走完他負(fù)責(zé)投遞的全部街道，完成任務(wù)后回到郵局，應(yīng)按怎樣的路線走，他所走的路程才會(huì)最短呢？ 由我國(guó)數(shù)學(xué)家管梅谷在1962年首先提出的，因此，在國(guó)際上稱為中國(guó)郵路問(wèn)題。,2020/9/3,離散數(shù)學(xué),19,8、工程工序管理問(wèn)題,世界著名的假日飯店在其科學(xué)的管理中嚴(yán)格規(guī)定了有關(guān)工序： 清潔工第一步是換什么，洗什么？第二步又做什

8、么？ 同時(shí)需要確保他進(jìn)出房間的次數(shù)最少？ 一個(gè)如此簡(jiǎn)單的工作都要講究工程工序管理，那么更復(fù)雜的的工作就更不用說(shuō)了。,2020/9/3,離散數(shù)學(xué),20,9、地面鋪磚問(wèn)題,用形狀相同的方形磚塊，無(wú)疑可將地面鋪滿（不考慮邊緣的特殊情況） 而如用不同形狀，又非方形的磚塊來(lái)鋪地面時(shí)，能否鋪滿？ 這一常見的實(shí)際的簡(jiǎn)單問(wèn)題，也涉及到很深的數(shù)學(xué)原理。,2020/9/3,離散數(shù)學(xué),21,10、網(wǎng)絡(luò)布局問(wèn)題,一個(gè)通信網(wǎng)絡(luò)怎樣布局最節(jié)??？ 美國(guó)的貝爾實(shí)驗(yàn)室和IBM公司都有世界一流的組合數(shù)學(xué)家在研究這個(gè)問(wèn)題。 該問(wèn)題關(guān)系到巨大的經(jīng)濟(jì)效益。,2020/9/3,離散數(shù)學(xué),22,11、金融分析問(wèn)題,投資方案的確定。 怎樣找

9、出好的投資組合以降低投資風(fēng)險(xiǎn)。 南開大學(xué)組合數(shù)學(xué)研究中心開發(fā)出“金沙股市風(fēng)險(xiǎn)分析系統(tǒng)”，已投放市場(chǎng)，為短線投資者提供有效的風(fēng)險(xiǎn)防范工具。,2020/9/3,離散數(shù)學(xué),23,12、一筆畫問(wèn)題,所謂一筆畫，就是從圖形上的某點(diǎn)出發(fā)，筆不離開紙，而且每條線都只畫一次不準(zhǔn)重復(fù)。 什么樣的圖形能一筆畫成呢？,2020/9/3,離散數(shù)學(xué),24,13、螞蟻比賽問(wèn)題,甲乙兩只螞蟻進(jìn)行比賽： 從他們所在的結(jié)點(diǎn)出發(fā)，在圖中走過(guò)所有的點(diǎn)，最后到達(dá)C處，如果他們的速度相同，問(wèn)誰(shuí)先到達(dá)目的地？,2020/9/3,離散數(shù)學(xué),25,14、哥尼斯堡七橋問(wèn)題,18世紀(jì)時(shí)，歐洲有一個(gè)風(fēng)景秀麗的小城哥尼斯堡，那里有七座橋。如圖所示。當(dāng)時(shí)哥尼斯堡的居民中流傳著一道難題：一個(gè)人怎樣才能一次走遍七座橋，每座橋