離散數(shù)學(xué)緒論

1、1,離散數(shù)學(xué)Discrete Mathematics,徐志敏Email:xzmzg@163.comTel:15275343080,課 程 說 明,一、離散數(shù)學(xué)課程的地位和作用,離散數(shù)學(xué)是計(jì)算機(jī)專業(yè)的一門核心基礎(chǔ)課程。,1 離散數(shù)學(xué)為計(jì)算機(jī)專業(yè)的后繼課程如數(shù)據(jù)結(jié)構(gòu)、操作系統(tǒng)、數(shù)據(jù)庫(kù)、編譯原理、網(wǎng)絡(luò)和算法設(shè)計(jì)等課程提供必要的數(shù)學(xué)基礎(chǔ)。,2 為學(xué)生今后從事計(jì)算機(jī)科學(xué)和技術(shù)各方面的工作提供有力的工具。,3 離散數(shù)學(xué)是現(xiàn)代數(shù)學(xué)的一個(gè)重

2、要分支，通過該課程的學(xué)習(xí)可以提高學(xué)生的抽象思維、嚴(yán)格推理以及綜合歸納分析能力，培養(yǎng)出高素質(zhì)的人才。,二、離散數(shù)學(xué)課程的特點(diǎn),離散數(shù)學(xué)課程是應(yīng)計(jì)算機(jī)科學(xué)和技術(shù)發(fā)展的需要，綜合了高等數(shù)學(xué)的多個(gè)分支而形成的。其特點(diǎn)是以離散量為研究對(duì)象，內(nèi)容豐富，涉及面較寬。因此概念多、定理多、推理多并且內(nèi)容較為抽象。但由于它是為學(xué)生后繼專業(yè)知識(shí)的學(xué)習(xí)做必要的數(shù)學(xué)準(zhǔn)備，因此它研究的內(nèi)容均比較基礎(chǔ)，難度不大。,三、如何學(xué)好離散數(shù)學(xué),要學(xué)好這門課程，首先必須充分認(rèn)

3、識(shí)到這門課程的上述特點(diǎn)，需要做到以下幾點(diǎn)：,1 熟讀教材。準(zhǔn)確理解各個(gè)概念和定理的含義（結(jié)合多個(gè)例子來理解），必要的推理過程要看懂、理解（它可以幫助你熟悉和深刻理解定理的含義）。,2 獨(dú)立思考，大量練習(xí)。僅靠熟讀教材并不能將書本上的知識(shí) 變成你自己的知識(shí)，在熟讀教材的基礎(chǔ)上，必須通過大量練 習(xí)，獨(dú)立思考來真正獲取知識(shí)。,3 注重抽象思維能力的培養(yǎng)。數(shù)學(xué)與其他學(xué)科相比較具有較高的抽象性，而離散數(shù)學(xué)的抽象性特點(diǎn)更為顯

4、著，它有著大量抽象的概念和抽象的推理，要學(xué)好這門課程必須具有較好的抽象思維能力，才能深入地掌握課程內(nèi)容。,第一部分 數(shù)理邏輯。包括命題邏輯和謂詞邏輯。（教材的第一、二章),四、 離散數(shù)學(xué)課程的主要內(nèi)容,離散數(shù)學(xué)課程的主要內(nèi)容可以分為四個(gè)部分：,第二部分 集合論。包括集合、關(guān)系、函數(shù)和經(jīng)典集合的擴(kuò)展等。（教材的第三、四、五章）,第三部分 代數(shù)系統(tǒng)。包括代數(shù)系統(tǒng)的一般概念，幾類典型的代數(shù)系統(tǒng)。（教材的第八、九章）,第四部分 圖論。包括圖的

5、基本概念、幾種重要的圖、最短路徑和關(guān)鍵路徑等。（教材的第十章）,五、 教材及參考書,參考書： 《離散數(shù)學(xué)》 左孝凌 劉永才 上?？茖W(xué)技術(shù)文獻(xiàn)出版社。 國(guó)內(nèi)經(jīng)典著作中內(nèi)容最全的一本。,1、教材： 徐鳳生著的《離散數(shù)學(xué)及其應(yīng)用》（第2版）,成績(jī)?cè)u(píng)定及考勤,1、成績(jī)?cè)u(píng)定：平時(shí)作業(yè)、考勤等占30%，期末卷面占70%2、考勤：本門課程累計(jì)曠課5次（請(qǐng)假7次）成績(jī)記為不及格。,六. 離散數(shù)學(xué)應(yīng)

6、用花絮,例1：在日常生活中我們常常遇到離散數(shù)學(xué)的問題。如果你仔細(xì)留心一張世界地圖，你會(huì)發(fā)現(xiàn)用一種顏色對(duì)一個(gè)國(guó)家著色，那么一共只需要四種顏色就能保證每?jī)蓚€(gè)相鄰的國(guó)家的顏色不同。這樣的著色效果能使每一個(gè)國(guó)家都能清楚地顯示出來。但要證明這個(gè)結(jié)論確是一個(gè)著名的世界難題，最終借助計(jì)算機(jī)才得以解決，最近人們才發(fā)現(xiàn)了一個(gè)更簡(jiǎn)單的證明。,例2,我國(guó)古代的河洛圖上記載了三階幻方，即把從一到九這九個(gè)數(shù)按三行三列的隊(duì)行排列，使得每行，每列，以及兩條對(duì)角線上的

7、三個(gè)數(shù)之和都是一十五。離散數(shù)學(xué)中有許多象幻方這樣精巧的結(jié)構(gòu)。1977年美國(guó)旅行者1號(hào)、2號(hào)宇宙飛船就帶上了幻方以作為人類智慧的信號(hào)。,例3,一個(gè)郵遞員從郵局出發(fā)，要走完他所管轄的街道，他應(yīng)該怎樣選擇什么樣的路徑，這就是著名的"中國(guó)郵遞員問題"，由中國(guó)離散數(shù)學(xué)家管梅谷教授提出，著名離散數(shù)學(xué)家，J. Edmonds和他的合作者給出了一個(gè)解答。,例4：一個(gè)班級(jí)的學(xué)生共計(jì)選修A、B、C、D、E、F六門課程，其中一部分人同時(shí)選

8、修D(zhuǎn)、C、A，一部分人同時(shí)選修B、C、F，一部分人同時(shí)選修B、E，還有一部分人同時(shí)選修A、B，期終考試要求每天考一門課，六天內(nèi)考完，為了減輕學(xué)生負(fù)擔(dān)，要求每人都不會(huì)連續(xù)參加考試，試設(shè)計(jì)一個(gè)考試日程表。,解：以每門課程為一個(gè)頂點(diǎn)，共同被選修的課程之間用邊相連，得圖，按題意，相鄰頂點(diǎn)對(duì)應(yīng)課程不能連續(xù)考試，不相鄰頂點(diǎn)對(duì)應(yīng)課程允許連續(xù)考試，因此，作圖的補(bǔ)圖，問題是在圖中尋找一條哈密頓道路，如C—E—A—F—D—B，就是一個(gè)符合要求的考試課程表。

9、,,,,,,,A,F,E,D,C,B,,,,,,,,,,,,,,,A,F,E,D,C,B,,,,,,,,,,,,,,,,,,,,,,A,F,E,D,C,B,,,,,,,,,,,,,尋找一條哈密頓路,C—E—A—F—D—B就是一個(gè)符合要求的考試課程表。,【例5】 一個(gè)人帶著一只狼、一只羊和一捆草要渡河，由于船太小，人做擺渡者一次只能運(yùn)送一個(gè)“乘客”，很顯然，如果人不在，狼要吃羊，羊要吃草，問人怎樣才能把它們平安地渡過河去？,解：這是通路

10、問題的一個(gè)典型實(shí)例。用f 表示人，w 表示狼，s 表示羊，h 表示草。 集合{f，w，s，h}中能平安在一起的子集有：{f，w，s，h}，{f，w，s}，{f，s，h}，{f，w，h}，{f，w}，{f，s}，{f，h}，{w，h}，{f}，{w}，{s}，{h}。用結(jié)點(diǎn)表示渡河過程中的狀態(tài)，狀態(tài)是二元組：第一元素是集合{f，w，s，h}在渡河過程中留在原岸的子集，第二元素是在彼岸的子集，將一次渡河后代表狀態(tài)變化

11、的結(jié)點(diǎn)間連邊，得圖5.1.7。容易看出，一條真路就是一種渡河方案。,圖 5.1.7,用f 表示人，w 表示狼，s 表示羊，h 表示草。＜原岸，彼岸＞,例6 網(wǎng)絡(luò)計(jì)劃技術(shù),我們還會(huì)遇到更復(fù)雜的調(diào)度和安排問題。例如，在生產(chǎn)原子彈的曼哈頓計(jì)劃中，涉及到很多工序，許多人員的安排，很多元件的生產(chǎn)，怎樣安排各種人員的工作，以及各種工序間的銜接，從而使整個(gè)工期的時(shí)間盡可能短？這些都是離散數(shù)學(xué)典型例子。,假日飯店的管理中，也嚴(yán)格規(guī)定了有關(guān)的工序，如

12、清潔工的第一步是換什么，清洗什么，第二步又做什么，總之，他進(jìn)出房間的次數(shù)應(yīng)該最少。既然，這樣一個(gè)簡(jiǎn)單的工作都需要講究工序，那么一個(gè)復(fù)雜的工程就更不用說了。 庫(kù)房和運(yùn)輸?shù)墓芾硪彩堑湫偷碾x散數(shù)學(xué)問題。怎樣安排運(yùn)輸使得庫(kù)房充分發(fā)揮作用，進(jìn)一步來說，貨物放在什么地方最便于存?。ㄈ绱鎯?chǔ)時(shí)間短的應(yīng)該放在容易存取的地方）。,一個(gè)通訊網(wǎng)絡(luò)怎樣布局最節(jié)??？ 美國(guó)的貝爾實(shí)驗(yàn)室和IBM公司都有世界一流的離散數(shù)學(xué)家在研究這個(gè)問題，這個(gè)問題

13、直接關(guān)系到巨大的經(jīng)濟(jì)利益。 我們知道，用形狀相同的方型磚塊可以把一個(gè)地面鋪滿（不考慮邊緣的情況），但是如果用不同形狀，而又非方型的磚塊來鋪一個(gè)地面，能否鋪滿呢？這不僅是一個(gè)與實(shí)際相關(guān)的問題，也涉及到很深的離散數(shù)學(xué)問題。,航空調(diào)度和航班的設(shè)定也是離散數(shù)學(xué)的問題。怎樣確定各個(gè)航班以滿足 不同旅客轉(zhuǎn)機(jī)的需要，同時(shí)也使得每個(gè)機(jī)場(chǎng)的航班起落分布合理。此外，在一些航班有延誤等特殊情況下，怎樣作最合理的調(diào)整，這些都是離散數(shù)學(xué)的問題。對(duì)于城市的交通

14、管理，交通規(guī)劃，哪些地方可能是阻塞要地，哪些地方 應(yīng)該設(shè)單行道，立交橋建在哪里最合適，紅綠燈怎樣設(shè)定最合理， 如此等等，全是離散數(shù)學(xué)的問題。,離散數(shù)學(xué)中有一個(gè)著名問題：是否存在穩(wěn)定婚姻的問題。假如能找到兩對(duì)夫婦（如張（男）--李（女）和趙（男）--王（女）），如果張（男）更喜歡王（女），而王（女）也更喜歡張（男），那么這樣就可能有潛在的不穩(wěn)定性。 離散數(shù)學(xué)的方法可以找到一種婚姻的安排方法，使得沒有上述的不穩(wěn)定情況出現(xiàn)（

15、當(dāng)然這只是理論上的結(jié)論）。 這種離散數(shù)學(xué)的方法卻有 一個(gè)實(shí)際的用途：美國(guó)的醫(yī)院在確定錄取住院醫(yī)生時(shí)，他們將考慮申請(qǐng)者的志愿的先后次序，同時(shí)也給申請(qǐng)排序。按這樣的 次序考慮出的總的方案將沒有醫(yī)院和申請(qǐng)者兩者同時(shí)后悔的情況。 實(shí)際上，高考學(xué)生的最后錄取方案也可以用這種方法。,總之，離散數(shù)學(xué)無處不在，它的主要應(yīng)用就是在各種復(fù)雜關(guān)系中找出最優(yōu)的方案。所以離散數(shù)學(xué)完全可以看成是一門量化的關(guān)系學(xué)，一門量化了的運(yùn)籌學(xué)，一門量化了的管理