離散數(shù)學(xué)PPT教學(xué)緒論.ppt

1、離 散 數(shù) 學(xué),主講教師：程 虹 電 話：67626,第一章 緒 論,課 程 簡 介 教 學(xué) 大 綱 教 學(xué) 目 的 教 學(xué) 要 求 參 考 教 材 考 核 方 式 說 明 離 散 與 連 續(xù) 名 人 名 言,趣 味 數(shù) 學(xué) 土耳其商人和帽子的故事 理發(fā)師的頭由誰來理? 聰 明 的 囚 徒 考 試 日 程 表 的 安 排,課 程 簡 介,課程編號： 07ZB073116 課程性質(zhì)： 必修 總學(xué)時： 72學(xué)時 總學(xué)分： 4分 開課學(xué)期： 第三學(xué)期 適用專業(yè)： 計算機(jī)科學(xué)與技術(shù) 先修課程：高等數(shù)學(xué)，線性代數(shù)，計算機(jī)導(dǎo)論 后續(xù)課程：數(shù)據(jù)結(jié)構(gòu)及算法，數(shù)字邏輯 課程地位：學(xué)位課程，非常重要,教 學(xué) 大

2、綱,離散數(shù)學(xué)研究離散量的結(jié)構(gòu)和相互間的關(guān)系。其研究對象一般是有限個或可數(shù)個元素。課程以培養(yǎng)學(xué)生的抽象思維和縝密概括能力為主要教學(xué)目標(biāo)。課程內(nèi)容主要有：數(shù)理邏輯、集合論、二元關(guān)系、代數(shù)系統(tǒng)、圖論、形式語言和自動機(jī)。離散數(shù)學(xué)能夠?yàn)閷W(xué)生學(xué)習(xí)計算機(jī)專業(yè)知識與技術(shù)，從事計算機(jī)軟、硬件開發(fā)和應(yīng)用打下堅實(shí)的基礎(chǔ)。,教 學(xué) 目 的,1、了解離散數(shù)學(xué)研究的內(nèi)容以及它在計算機(jī)科學(xué)中的地位和作用。 2、理解和掌握命題邏輯和謂詞邏輯的符號化和推導(dǎo)證明方法。 3、理解和掌握集合與二元關(guān)系的性質(zhì)和應(yīng)用。 4、掌握代數(shù)系統(tǒng)（群、半群、格、環(huán)、域，布爾代數(shù)等）的性質(zhì)及主要應(yīng)用。 5、掌握常用的判別圖和樹的方法。,教 學(xué) 要

3、求,1、理解命題邏輯和謂詞邏輯的異同點(diǎn)和聯(lián)系，掌握基本概念和推理證明方法。 2、理解并掌握集合的基本運(yùn)算和性質(zhì)及其計算機(jī)科學(xué)中的應(yīng)用。 3、了解二元關(guān)系和集合的笛卡兒積，掌握關(guān)系的運(yùn)算和性質(zhì)。 4、理解函數(shù)的定義，并掌握不同種函數(shù)的性質(zhì)。 5、理解并掌握代數(shù)系統(tǒng)的性質(zhì)，掌握幾種典型的代數(shù)系統(tǒng)。 6、了解圖的基本概念，掌握它的存儲表示，并理解最短路徑和關(guān)鍵路徑的求法。 7、理解并掌握歐拉圖和哈密爾頓圖的定義及判定方法。 8、了解樹的基本概念及樹的相關(guān)應(yīng)用。 9、了解形式語言和有窮自動機(jī)。 10、能夠針對所學(xué)知識點(diǎn)，對每章后的習(xí)題做的覆蓋率達(dá)到60以上。 11、能夠做題舉一反三，盡量使用多種方法去

4、解題，鍛煉獨(dú)立思考的能力。 12、能夠從生活中、計算機(jī)課程學(xué)習(xí)中對應(yīng)找到離散數(shù)學(xué)的實(shí)際應(yīng)用實(shí)例，進(jìn)而加深理解和掌握相關(guān)的知識點(diǎn)，并能提高學(xué)習(xí)的趣味性和積極性。,參 考 教 材,推薦教材： 離散數(shù)學(xué)，第二版，左孝凌、劉永才等編著，上海科學(xué)技術(shù)文獻(xiàn)出版社 參考教材： 1、離散數(shù)學(xué)，第三版，耿素云、屈婉玲等編，清華大學(xué)出版社 2、離散數(shù)學(xué)，劉學(xué)書、袁磊等編著， 武漢大學(xué)出版社 3、離散數(shù)學(xué)導(dǎo)論， 徐潔磐編，高等教育出版社 4、離散數(shù)學(xué)，陳莉、劉曉霞編著，高等教育出版社 5、離散數(shù)學(xué)結(jié)構(gòu)，第四版（影印版），Bernard Kolman等編，高等教育出版社 6、離散數(shù)學(xué)， 朱一清編著， 電子工業(yè)出版社

5、7、離散數(shù)學(xué)，喬維聲編，西安電子科技大學(xué)出版社 8、離散數(shù)學(xué)，第四版，Richard Johnsonbaugh著，電子工業(yè)出版社,考 核 方 式 說 明,1、考查方式：筆試（閉卷） 2、筆試時間：120分鐘 3、成績構(gòu)成：結(jié)業(yè)考試成績（占70%）,平時成績(占30%，包括作業(yè)、提問、測驗(yàn)等) 4、主要題型：本課程命題范圍涵蓋課程的大部分章節(jié)。試題難易程度分為：較易占50%，中等難度占40%，較難占10%。在題型結(jié)構(gòu)上，主要由選擇題、填空題、判斷題、畫圖題和計算（綜合）題，其中客觀題（包括選擇題、填空題、判斷題等）占40%；主觀題（包括畫圖題和計算（綜合）題等）占60%。 5、考核范圍：第2章第

6、11章,離 散 與 連 續(xù),“離散數(shù)學(xué)”是研究離散數(shù)量關(guān)系和離散結(jié)構(gòu)數(shù)學(xué)模型的數(shù)學(xué)分支的統(tǒng)稱。 “離散”與“連續(xù)”是數(shù)量關(guān)系中一對極為深刻的矛盾，它們之間的對立與統(tǒng)一是數(shù)學(xué)發(fā)展的重要動力之一?！半x散”是“連續(xù)”的否定，即“不連續(xù)”；“連續(xù)”則是指事物、數(shù)量的一種屬性，這種屬性使它們?nèi)菀妆环指罨蚪Y(jié)合，并且不會因此而喪失它們原有的本性。例如，實(shí)數(shù)是連續(xù)的，整數(shù)則是離散的；馬鈴薯是離散的，而馬鈴薯羹則是連續(xù)的。,近50年來，數(shù)字電子計算機(jī)的飛速發(fā)展與廣泛應(yīng)用，極大地沖擊了現(xiàn)代數(shù)學(xué)。由于數(shù)字電子計算機(jī)是一個離散結(jié)構(gòu)，它只能處理離散的或離散化了的數(shù)量關(guān)系，因此，無論計算機(jī)科學(xué)本身，還是與計算機(jī)科學(xué)及其應(yīng)

7、用密切相關(guān)的現(xiàn)代科學(xué)研究領(lǐng)域，都面臨這樣一些問題：如何高速、有效地處理離散的對象和離散的數(shù)量關(guān)系，如何對離散結(jié)構(gòu)建立離散數(shù)學(xué)模型，又如何將已用連續(xù)數(shù)量關(guān)系建立起來的數(shù)學(xué)模型離散化，從而可由計算機(jī)加以處理。于是，人們開始重新認(rèn)識離散數(shù)量關(guān)系的研究意義，重新重視討論離散數(shù)量關(guān)系的數(shù)學(xué)分支，并取得新的發(fā)展。離散數(shù)學(xué)學(xué)科的出現(xiàn)和發(fā)展是上述事實(shí)的邏輯結(jié)果。,名 人 名 言,1、（緒論）宏偉的樂隊里缺少不了樂器之王鋼琴，高聳入云的數(shù)學(xué)大廈里也缺少不了“離散”（數(shù)學(xué)），“連續(xù)”和“離散”像兩支翅膀， 它把人類從地上帶向天堂！“有限”與“無窮”象一把鋒利的寶劍，它無往不勝，無堅不摧！ 2、學(xué)習(xí)數(shù)學(xué)吧！即便你還

8、是一個孩童，學(xué)習(xí)它能培養(yǎng)你的耐性，更能發(fā)揮你的思考力及創(chuàng)造力！ 3、(集合論技術(shù))連續(xù)的形象：“剪不斷，理還亂，是離愁，恰似一江春水向東流?！蹦咸?，李后主詞 4、離散的形象：“枯藤老樹昏鴉，小橋流水人家，古道西風(fēng)瘦馬，夕陽西下，斷腸人在天涯?！?元.馬致遠(yuǎn) 5、(圖論)“現(xiàn)在應(yīng)該使用圖的概念滲入所有的數(shù)學(xué)教學(xué)，圖表示了一個系統(tǒng)的可能狀態(tài)以及連接這些狀態(tài)的算子。,離散數(shù)學(xué)的趣味應(yīng)用 1、土耳其商人和帽子的故事,一個土耳其商人，想找一個十分聰明的助手協(xié)助他經(jīng)商，有兩個人前來應(yīng)聘，這個商人為了試一試哪一個聰明些，就把兩個人帶進(jìn)一間漆黑的屋子里，他打開電燈后：“這張桌子上有五頂帽子，兩頂是紅色的，三頂

9、是黑色的。現(xiàn)在，我把燈關(guān)掉，而且把帽子擺的位置弄亂，然后我們?nèi)齻€人每人摸一頂帽子戴在頭上，在我開燈后，請你們盡快的說出自己頭上戴的帽子是什么顏色的?！闭f完之后，商人將電燈關(guān)掉，然后三人都摸了一頂帽子戴在頭上，同時商人將余下的兩頂帽子藏了起來，接著把電燈打開，這時，那兩個有應(yīng)試者看到商人頭上戴的是一頂紅帽子，過了一會兒，其中一個人便喊到：“我戴的是黑帽子?！闭垎栠@個人猜得對嗎？是怎么推導(dǎo)出來的？ 答案分析,2、理發(fā)師的頭由誰來理?,在一個小鎮(zhèn)上，有一個理發(fā)師公開宣布：他給而且只給小鎮(zhèn)上所有不給自己理發(fā)的人理發(fā)，現(xiàn)在要問: 這位理發(fā)師的頭由誰來理? 答案分析,3、聰 明 的 囚 徒,古希臘有個國王

10、，對處死囚徒的方法作了兩種規(guī)定：一種是砍頭，一種是絞刑。并且他自恃聰明的做出一種規(guī)定：囚徒可以說一句話，并且這句話是馬上可以驗(yàn)證其真假。如果囚徒說的是真話，那么處以絞刑，如果囚徒說的是假話，那么處以砍頭。許多囚徒或者是因?yàn)檎f了假話而被砍頭或者因?yàn)檎f了真話而被處以絞刑。 有一位極其聰明的囚徒，當(dāng)輪到他來選擇處死方法時，他說出一句巧妙的話，結(jié)果使這個國王按照哪種方法處死他，都違背自己的決定，只得將他放了。 試問：這囚徒說的是句什么話？ 答案分析,4、考試日程表的安排,考慮七天安排七門考試的問題，要使同一教員舉行的任何兩門考試不要安排在接連的兩天內(nèi)進(jìn)行。假如每個教員最多舉行四次考試，證明安排這樣的考

11、試日程表總是可能的。 答案分析,土耳其商人和帽子的答案分析,設(shè)P1表示“猜對的人戴紅帽子”；P2表示“猜對的人戴黑帽子”； Q1表示“另一個人戴紅帽子”；Q2表示“另一個人戴黑帽子”；R1表示“商人戴紅帽子”?，F(xiàn)在知道R1為真，又知道另一個人沒有作出斷定，即既不能斷定Q1為真，也不能斷定Q2為真。根據(jù)題設(shè)條件，可得如下公式：R1P1Q2：如果商人和猜對的人戴的都是紅帽子，那么另一個戴的就是黑帽子，因?yàn)榧t帽子只有兩頂。R1Q1P2：如果商人和另一個戴的都是紅帽子，那么猜對的人戴的就是黑帽子。P1P2：如果猜對的人戴的不是紅帽子，那么他戴的就是黑帽子。Q1Q2：如果另一個人戴的不是紅帽子，那么他戴

12、的就是黑帽子。推演步驟如下：設(shè)P1（1）P1（根據(jù)假設(shè)）；（2）R1（根據(jù)題設(shè)）（3）R1P1（合取構(gòu)成）；（4）R1P1Q2（根據(jù)題設(shè)）（5）Q2（3）（4）分離）。這就是說，“另一個人戴黑帽子”這個判定是必然可以作出的，但是這與題設(shè)條件（即“另一個沒有作出判定”）相矛盾，因此，P1為假，即P1為真，故可得：（6）P1；（7）P1P2（根據(jù)題設(shè)）；（8）P2（6）（7）分離）。這就是說，“猜對的人戴著黑帽子”是真的，所以猜對的人肯定的說：“我戴的是黑帽子”。 返 回,理發(fā)師的頭誰來剃的答案分析,如果理發(fā)師的頭由別人給他理，即理發(fā)師自己不給自己理發(fā)，那么按規(guī)定這位理發(fā)師的頭應(yīng)該有自己理。如果理發(fā)師的頭由他自己理，按規(guī)定他只給那些不給自己理發(fā)的人理發(fā)，那么理發(fā)師的頭不能由他自己理，即理發(fā)師的頭應(yīng)該由別人來理。這就產(chǎn)生了矛盾: 理發(fā)師的頭既不能由別人理，也不能由他自己理，所以這位理發(fā)師的規(guī)定是一個悖論。 返 回,聰明的囚徒的答案分析,聰明的囚徒所說的話，應(yīng)使國王無論怎么處置他都帶來矛盾，這句話就是“國王決定砍我的頭”。如果這和國王規(guī)定一致，是說真話，因而按國王決定的處死方法，講真話應(yīng)處以絞刑，這樣就造成了國王的規(guī)定（砍頭）同國王決定的處死方法相矛盾。如果這和國王的規(guī)定不一致，是說的假話，因而按照國王決定的處死方法，講假話予以砍頭，這樣又