離散數(shù)學(Discrete mathematics)是研究離散量的結(jié)構(gòu)及其相互關(guān)系的數(shù)學學科,是現(xiàn)代數(shù)學的一個重要分支,。它在各學科領(lǐng)域,,特別在計算機科學與技術(shù)相關(guān)領(lǐng)域有著廣泛的應用。
教學內(nèi)容以基本概念,、結(jié)論,、算法,、推理與證明方法,,以及一般應用方法的介紹為主,主要內(nèi)容包括數(shù)理邏輯,、集合論,、與圖論等內(nèi)容。
通過本課程的學習,,要求學生理解離散數(shù)學的基本概念,、結(jié)論、算法,、應用方法及適用范圍,;了解和掌握處理離散結(jié)構(gòu)的描述工具和方法;提高抽象思維和嚴格的邏輯推理能力,,為后續(xù)課程的學習及將來從事計算機軟硬件技術(shù)開發(fā)打好必要的理論基礎(chǔ),。
(一)第1章 命題邏輯
主要知識點:
1.1命題與邏輯聯(lián)結(jié)詞
1.2命題公式及公式分類
1.3等值式與等值演算
1.4范式與主范式
1.5推理理論
教學要求:通過本章學習,了解命題概念,,掌握五種聯(lián)結(jié)詞與真值表的構(gòu)造,;理解命題公式的概念,掌握命題公式類型的判斷,;理解等值式的概念,,掌握命題公式的等值演算;理解析取范式與合取范式的概念,,掌握主析取范式與主合取范式的求解方法,;理解推理的形式結(jié)構(gòu)與推理定律,掌握形式證明的方法與技巧,。
重點:主析取范式與主合取范式及命題邏輯的推理理論,。
難點:主析取范式與主合取范式的求解、推理理論及應用,。
采用的教學方法:知識點講解,、習題講解。
講授學時:8學時
講解習題:1學時
(二)第2章 謂詞邏輯
主要知識點:
2.1基本概念
2.1謂詞公式
2.3謂詞邏輯蘊含式和等值式
2.4前束范式
2.5謂詞邏輯推理理論
教學要求:通過本章學習,,理解謂詞,、量詞、變元,、個體域等概念,;掌握用謂詞、量詞,、聯(lián)結(jié)詞構(gòu)造謂詞邏輯公式的方法,。理解一階邏輯公式的概念及其解釋,掌握簡單一階邏輯公式類型的判斷方法,;理解一階邏輯置換規(guī)則,、換名規(guī)則、代替規(guī)則,,掌握一階邏輯基本等值式的使用,;掌握一階邏輯公式前束公式的求解方法;能夠以謂詞邏輯作為工具,,將命題符號化,,并能用推理規(guī)則進行邏輯證明。
重點:一階邏輯的概念與表示,,一階邏輯公式及其解釋,,一階邏輯的等值式與置換規(guī)則,一階邏輯的推理理論,。
難點:一階邏輯公式類型的判斷和一階邏輯的推理證明,。
采用的教學方法:知識點講解,、習題講解。
講授學時:8學時
講解習題:1學時
(三)第3章 關(guān)系
主要知識點:
3.1笛卡兒積
3.2關(guān)系的概念與表示方法
3.3關(guān)系的運算
3.4關(guān)系的性質(zhì)
3.5關(guān)系的閉包
3.6關(guān)系等價與劃分
3.7偏序關(guān)系
教學要求:通過本章學習,,理解笛卡兒積與二元關(guān)系的概念,,掌握關(guān)系的表示、運算與性質(zhì),;理解關(guān)系閉包的定義,,掌握關(guān)系閉包的求解方法;理解等價關(guān)系,、劃分與偏序關(guān)系的定義,,掌握等價關(guān)系和偏序關(guān)系的結(jié)構(gòu)。
重點:等價關(guān)系與偏序關(guān)系的結(jié)構(gòu)及應用,、關(guān)系的閉包與算法,。
難點:關(guān)系的閉包與算法。
采用的教學方法:知識點講解,、習題講解,。
講授學時:8學時
講解習題:1學時
(四)第4章 函數(shù)
主要知識點:
4.1函數(shù)的概念
4.2特殊函數(shù)
4.3逆函數(shù)與復合函數(shù)
4.4幾個重要的函數(shù)
4.5函數(shù)的應用
教學要求:通過本章學習,理解函數(shù)的基本概念,,掌握函數(shù)的性質(zhì),;掌握逆函數(shù)和復合函數(shù)的基本概念與性質(zhì);,。
重點:逆函數(shù)和復合函數(shù)的性質(zhì),。
難點:逆函數(shù)和復合函數(shù)的性質(zhì)。
采用的教學方法:知識點講解,、習題講解,。
講授學時:5學時
講解習題:1學時
(五)第5章 圖論
主要知識點:
5.1圖的定義及相關(guān)概念
5.2通路、回路與連通圖
5.3圖的矩陣表示
5.4歐拉圖與哈密頓圖
5.5最短路徑問題與貨郎擔問題
5.6平面圖和圖的著色
教學要求:通過本章學習,,了解圖論的基本內(nèi)容及其在計算機領(lǐng)域中的應用,;理解圖的基本概念、子圖與補圖概念,,通路與回路的概念,、圖的連通性與連通度的概念,、歐拉圖與漢密爾頓圖的概念,、樹及最優(yōu)樹的概念;掌握圖的表示方法,、圖的可達性與連通性的判斷,;掌握圖的通路與回路的判斷、圖的連通性的判斷,;掌握歐拉圖與漢密爾頓圖的判定方法,;掌握求最小生成樹的Kruskal算法,、求最優(yōu)樹的Huffman算法。
重點:握手定理及其推論的應用,、圖中通路和回路應用,、圖中的可達性和連通性的求解方法、歐拉圖判定,、哈密頓圖判定,、最短路徑及應用、最小生成樹,。
難點:圖的連通性的有關(guān)定理,、圖的同構(gòu)及哈密爾頓圖的判定。
采用的教學方法:知識點講解,、習題講解,。
講授學時:7學時
講解習題:2學時
(六)第6章 樹
主要知識點:
6.1無向樹及性質(zhì)
6.2根樹
6.3生成樹
6.4樹的應用
教學要求:通過本章學習,了解樹,、生成樹,、最小生成樹的基本概念,掌握求最優(yōu)二叉樹的Huffman算法,,以及求最小生成樹的Kruskal算法和Prim算法,。
重點:二叉樹的遍歷及搜索,Huffman算法,,最小生成樹以及Kruskal算法和Prim算法,。
難點:Huffman算法、Kruskal算法,、Prim算法,。
采用的教學方法:知識點講解、習題講解,。
講授學時:7學時
講解習題:2學時
在本門課程結(jié)束時,學生應該能夠:
1. 掌握析取范式與合取范式的求法,,自然推理系統(tǒng)的推理理論,;一階邏輯的推理理論,在一階邏輯中構(gòu)造推理證明的方法,。
2.掌握二元關(guān)系的運算,、關(guān)系的性質(zhì)、關(guān)系的閉包,,掌握等價關(guān)系和劃分及偏序關(guān)系,,掌握判斷函數(shù)單射、滿射,、雙射的方法,。
3. 掌握圖的矩陣表示,,求最短路程與路線的方法;掌握用閉圈法求最小生成樹的方法,,用算法求最優(yōu)樹,、最佳前綴碼的方法。
4. 提高學生的抽象思維和邏輯推理能力上有較好提高
(一)出勤
學生應積極參與課堂教學并完成相關(guān)的作業(yè),。
(二)閱讀資料
學生應認真進行課前預習,閱讀教材和指定參考書及重要的參考文獻,。
(三)課堂演示
結(jié)合理論課教學內(nèi)容,,教師課堂內(nèi)容和習題講解、同學討論,。
(四)課程實驗
本課程是理論的課程,,不安排課外實踐作為課程內(nèi)容。
(五)小考與期末考
課程中隨機問答,。期末考試形式為閉卷筆試,。
(六)學術(shù)誠信
按中山大學南方學院相關(guān)規(guī)定執(zhí)行。
(七)剽竊的定義以及相應的懲罰
剽竊是嚴重違反學校規(guī)章制度的行為,。一經(jīng)發(fā)現(xiàn),,將上報相關(guān)部門,并受到包括開除學籍在內(nèi)的嚴厲處罰,。
(一)教科書-必讀
1. 王瑞胡等主編,離散數(shù)學及其應用,,清華大學出版社,,2014
(二)教科書-強烈推薦
1. 耿素云,屈婉玲編著,,《離散數(shù)學》北京大學出版社,,2002年2. 操作系統(tǒng)真象還原,鄭鋼,,人民郵電出版社,,2016
(三)文章-必讀
近年《計算機學報》、《軟件學報》等國內(nèi),、國際期刊雜志刊登的文章,。
(四)文章-強烈推薦
無
(五)其他參考資料
1. Kenneth.Rosen 著,,袁崇義 屈婉玲 等譯,《離散數(shù)學及其應用》(原書第6版), 機械工業(yè)出版社 2011
(一)教學活動
1,、個人預習
2、課堂講授
3,、課堂問答
4,、習題講解
5,、案例討論
6、期中測驗
7,、期末考試
(二)對預期學習成果的考察
預期學習成果 | 教學活動 | 學習成果考察內(nèi)容:作業(yè)/課程實驗 |
第1章 命題邏輯 | 1,2,3,4,5,7 | 課后作業(yè)P7(1,2),,P10(1,2,3),,P15(1,8,9),, P21(7),,P29(1,2) |
第2章 謂詞邏輯 | 1,2,3,4,5,7 | 課后作業(yè)P33(1,3),, P38(1), P42(2),,P44(1),, P47(1) |
第3章 關(guān)系 | 1,2,3,4,5,7 | 課后作業(yè)P59(1,2),P66(1,2),, P70(2),, P74(3,4), P80(1,2),, P89(2),, P94(2) |
第4章 函數(shù) | 1,2,3,4,5,7 | 課后作業(yè)P101(1,4),, P103(1,2),,P107(1,2) |
第5章 圖論 | 1,2,3,4,5,7 | 課后作業(yè)P158(1),P160(3),, P166(3,4),, P171(1,2),P175(1),,P179(1) |
第6章 樹 | 1,2,3,4,5,7 | 課后作業(yè)P188(1,2),, P196(3), P202(2,3),, |
(一)評分體系
1、出勤率: 10%
2,、課堂參與: 15%
3,、課后作業(yè): 15%
4、期末考試: 60%
(二)評分標準及要求
課堂參與度 (10%+15%) |
1)全勤 2)課前預習 3)積極回答課堂問題及參與課堂討論 |
課后作業(yè)(15%) |
1)按時按量完成課后作業(yè)內(nèi)容 2)能正確完成課后作業(yè) 3)作業(yè)格式,、書寫符合規(guī)范 |
期末考試 (60%) |
1)按時參加期末考試 2)正確解答試卷的問題 3)格式書寫符合規(guī)范 |
周次 | 課程要點 | 理論學時 | 討論學時 | 習題學時 |
1 | 命題與邏輯聯(lián)結(jié)詞,命題公式及公式分類 | 3 | ||
2 | 等值式與等值演算,范式與主范式 | 3 | ||
3 | 推理理論 | 2 | 1 | |
4 | 謂詞邏輯基本概念,,謂詞公式 | 3 | ||
5 | 謂詞邏輯蘊含式和等值式,,前束范式 | 3 | ||
6 | 謂詞邏輯推理理論 | 2 | 1 | |
7 | 笛卡兒積,關(guān)系的概念與表示方法,,關(guān)系的運算,, | 3 | ||
8 | 關(guān)系的性質(zhì),關(guān)系的閉包,, | 3 | ||
9 | 關(guān)系等價與劃分,,偏序關(guān)系 | 2 | 1 | |
10 | 函數(shù)的概念,特殊函數(shù),逆函數(shù)與復合函數(shù) | 3 | ||
11 | 幾個重要的函數(shù),,函數(shù)的應用 | 2 | 1 | |
12 | 圖的定義及相關(guān)概念,,通路、回路與連通圖 | 3 | ||
13 | 圖的矩陣表示,,歐拉圖與哈密頓圖 | 2 | 1 | |
14 | 最短路徑問題與貨郎擔問題,,平面圖和圖的著色 | 2 | 1 | |
15 | 無向樹及性質(zhì),根樹 | 3 | ||
16 | 生成樹 | 2 | 1 | |
17 | 樹的應用 | 2 | 1 | |
18 | 復習,、答疑 | 3 | ||
19 | ||||
20 | ||||
總學時 |