一、課程描述及課程目標(biāo)

離散數(shù)學(xué)(Discrete mathematics)是研究離散量的結(jié)構(gòu)及其相互關(guān)系的數(shù)學(xué)學(xué)科,，是現(xiàn)代數(shù)學(xué)的一個(gè)重要分支,。它在各學(xué)科領(lǐng)域，特別在計(jì)算機(jī)科學(xué)與技術(shù)相關(guān)領(lǐng)域有著廣泛的應(yīng)用,。

教學(xué)內(nèi)容以基本概念,、結(jié)論、算法,、推理與證明方法,，以及一般應(yīng)用方法的介紹為主，主要內(nèi)容包括數(shù)理邏輯,、集合論,、與圖論等內(nèi)容。

通過本課程的學(xué)習(xí),，要求學(xué)生理解離散數(shù)學(xué)的基本概念,、結(jié)論、算法,、應(yīng)用方法及適用范圍,；了解和掌握處理離散結(jié)構(gòu)的描述工具和方法；提高抽象思維和嚴(yán)格的邏輯推理能力,，為后續(xù)課程的學(xué)習(xí)及將來(lái)從事計(jì)算機(jī)軟硬件技術(shù)開發(fā)打好必要的理論基礎(chǔ),。

二、課程內(nèi)容

（一）第1章 命題邏輯

主要知識(shí)點(diǎn):

1.1命題與邏輯聯(lián)結(jié)詞

1.2命題公式及公式分類

1.3等值式與等值演算

1.4范式與主范式

1.5推理理論

教學(xué)要求:通過本章學(xué)習(xí),，了解命題概念,，掌握五種聯(lián)結(jié)詞與真值表的構(gòu)造；理解命題公式的概念,，掌握命題公式類型的判斷,；理解等值式的概念，掌握命題公式的等值演算,；理解析取范式與合取范式的概念,，掌握主析取范式與主合取范式的求解方法；理解推理的形式結(jié)構(gòu)與推理定律,，掌握形式證明的方法與技巧,。

重點(diǎn):主析取范式與主合取范式及命題邏輯的推理理論,。

難點(diǎn):主析取范式與主合取范式的求解、推理理論及應(yīng)用,。

采用的教學(xué)方法:知識(shí)點(diǎn)講解,、習(xí)題講解。

講授學(xué)時(shí):8學(xué)時(shí)

講解習(xí)題:1學(xué)時(shí)

（二）第2章 謂詞邏輯

主要知識(shí)點(diǎn):

2.1基本概念

2.1謂詞公式

2.3謂詞邏輯蘊(yùn)含式和等值式

2.4前束范式

2.5謂詞邏輯推理理論

教學(xué)要求:通過本章學(xué)習(xí),，理解謂詞,、量詞、變?cè)?、個(gè)體域等概念,；掌握用謂詞、量詞,、聯(lián)結(jié)詞構(gòu)造謂詞邏輯公式的方法,。理解一階邏輯公式的概念及其解釋，掌握簡(jiǎn)單一階邏輯公式類型的判斷方法,；理解一階邏輯置換規(guī)則,、換名規(guī)則、代替規(guī)則,，掌握一階邏輯基本等值式的使用；掌握一階邏輯公式前束公式的求解方法,；能夠以謂詞邏輯作為工具,，將命題符號(hào)化，并能用推理規(guī)則進(jìn)行邏輯證明,。

重點(diǎn):一階邏輯的概念與表示,，一階邏輯公式及其解釋，一階邏輯的等值式與置換規(guī)則,，一階邏輯的推理理論,。

難點(diǎn):一階邏輯公式類型的判斷和一階邏輯的推理證明。

采用的教學(xué)方法:知識(shí)點(diǎn)講解,、習(xí)題講解,。

講授學(xué)時(shí):8學(xué)時(shí)

講解習(xí)題:1學(xué)時(shí)

（三）第3章 關(guān)系

主要知識(shí)點(diǎn):

3.1笛卡兒積

3.2關(guān)系的概念與表示方法

3.3關(guān)系的運(yùn)算

3.4關(guān)系的性質(zhì)

3.5關(guān)系的閉包

3.6關(guān)系等價(jià)與劃分

3.7偏序關(guān)系

教學(xué)要求:通過本章學(xué)習(xí)，理解笛卡兒積與二元關(guān)系的概念,，掌握關(guān)系的表示,、運(yùn)算與性質(zhì)；理解關(guān)系閉包的定義,，掌握關(guān)系閉包的求解方法,；理解等價(jià)關(guān)系、劃分與偏序關(guān)系的定義,，掌握等價(jià)關(guān)系和偏序關(guān)系的結(jié)構(gòu),。

重點(diǎn):等價(jià)關(guān)系與偏序關(guān)系的結(jié)構(gòu)及應(yīng)用,、關(guān)系的閉包與算法。

難點(diǎn):關(guān)系的閉包與算法,。

采用的教學(xué)方法:知識(shí)點(diǎn)講解,、習(xí)題講解。

講授學(xué)時(shí):8學(xué)時(shí)

講解習(xí)題:1學(xué)時(shí)

（四）第4章 函數(shù)

主要知識(shí)點(diǎn):

4.1函數(shù)的概念

4.2特殊函數(shù)

4.3逆函數(shù)與復(fù)合函數(shù)

4.4幾個(gè)重要的函數(shù)

4.5函數(shù)的應(yīng)用

教學(xué)要求:通過本章學(xué)習(xí),，理解函數(shù)的基本概念,，掌握函數(shù)的性質(zhì)；掌握逆函數(shù)和復(fù)合函數(shù)的基本概念與性質(zhì),；,。

重點(diǎn):逆函數(shù)和復(fù)合函數(shù)的性質(zhì)。

難點(diǎn):逆函數(shù)和復(fù)合函數(shù)的性質(zhì),。

采用的教學(xué)方法:知識(shí)點(diǎn)講解,、習(xí)題講解。

講授學(xué)時(shí):5學(xué)時(shí)

講解習(xí)題:1學(xué)時(shí)

（五）第5章 圖論

主要知識(shí)點(diǎn):

5.1圖的定義及相關(guān)概念

5.2通路,、回路與連通圖

5.3圖的矩陣表示

5.4歐拉圖與哈密頓圖

5.5最短路徑問題與貨郎擔(dān)問題

5.6平面圖和圖的著色

教學(xué)要求:通過本章學(xué)習(xí),，了解圖論的基本內(nèi)容及其在計(jì)算機(jī)領(lǐng)域中的應(yīng)用；理解圖的基本概念,、子圖與補(bǔ)圖概念,，通路與回路的概念、圖的連通性與連通度的概念,、歐拉圖與漢密爾頓圖的概念,、樹及最優(yōu)樹的概念；掌握?qǐng)D的表示方法,、圖的可達(dá)性與連通性的判斷,；掌握?qǐng)D的通路與回路的判斷、圖的連通性的判斷,；掌握歐拉圖與漢密爾頓圖的判定方法,；掌握求最小生成樹的Kruskal算法、求最優(yōu)樹的Huffman算法,。

重點(diǎn):握手定理及其推論的應(yīng)用,、圖中通路和回路應(yīng)用、圖中的可達(dá)性和連通性的求解方法,、歐拉圖判定,、哈密頓圖判定、最短路徑及應(yīng)用,、最小生成樹,。

難點(diǎn):圖的連通性的有關(guān)定理、圖的同構(gòu)及哈密爾頓圖的判定。

采用的教學(xué)方法:知識(shí)點(diǎn)講解,、習(xí)題講解,。

講授學(xué)時(shí):7學(xué)時(shí)

講解習(xí)題:2學(xué)時(shí)

（六）第6章 樹

主要知識(shí)點(diǎn):

6.1無(wú)向樹及性質(zhì)

6.2根樹

6.3生成樹

6.4樹的應(yīng)用

教學(xué)要求:通過本章學(xué)習(xí)，了解樹,、生成樹,、最小生成樹的基本概念，掌握求最優(yōu)二叉樹的Huffman算法,，以及求最小生成樹的Kruskal算法和Prim算法,。

重點(diǎn):二叉樹的遍歷及搜索，Huffman算法,，最小生成樹以及Kruskal算法和Prim算法,。

難點(diǎn):Huffman算法、Kruskal算法,、Prim算法,。

采用的教學(xué)方法:知識(shí)點(diǎn)講解、習(xí)題講解,。

講授學(xué)時(shí):7學(xué)時(shí)

講解習(xí)題:2學(xué)時(shí)

三,、課程的預(yù)期學(xué)習(xí)成果

在本門課程結(jié)束時(shí)，學(xué)生應(yīng)該能夠:

1. 掌握析取范式與合取范式的求法,，自然推理系統(tǒng)的推理理論,；一階邏輯的推理理論，在一階邏輯中構(gòu)造推理證明的方法,。

2.掌握二元關(guān)系的運(yùn)算,、關(guān)系的性質(zhì)、關(guān)系的閉包,，掌握等價(jià)關(guān)系和劃分及偏序關(guān)系，掌握判斷函數(shù)單射,、滿射,、雙射的方法。

3. 掌握?qǐng)D的矩陣表示,，求最短路程與路線的方法,；掌握用閉圈法求最小生成樹的方法，用算法求最優(yōu)樹,、最佳前綴碼的方法,。

4. 提高學(xué)生的抽象思維和邏輯推理能力上有較好提高

四、課程要求

（一）出勤

學(xué)生應(yīng)積極參與課堂教學(xué)并完成相關(guān)的作業(yè),。

（二）閱讀資料

學(xué)生應(yīng)認(rèn)真進(jìn)行課前預(yù)習(xí),，閱讀教材和指定參考書及重要的參考文獻(xiàn)。

（三）課堂演示

結(jié)合理論課教學(xué)內(nèi)容,，教師課堂內(nèi)容和習(xí)題講解,、同學(xué)討論,。

（四）課程實(shí)驗(yàn)

本課程是理論的課程，不安排課外實(shí)踐作為課程內(nèi)容,。

（五）小考與期末考

課程中隨機(jī)問答,。期末考試形式為閉卷筆試。

（六）學(xué)術(shù)誠(chéng)信

按中山大學(xué)南方學(xué)院相關(guān)規(guī)定執(zhí)行,。

（七）剽竊的定義以及相應(yīng)的懲罰

剽竊是嚴(yán)重違反學(xué)校規(guī)章制度的行為,。一經(jīng)發(fā)現(xiàn)，將上報(bào)相關(guān)部門,，并受到包括開除學(xué)籍在內(nèi)的嚴(yán)厲處罰,。

五、課程資料

（一）教科書-必讀

1. 王瑞胡等主編,，離散數(shù)學(xué)及其應(yīng)用,，清華大學(xué)出版社，2014

（二）教科書-強(qiáng)烈推薦

1. 耿素云,，屈婉玲編著,，《離散數(shù)學(xué)》北京大學(xué)出版社，2002年2. 操作系統(tǒng)真象還原,，鄭鋼,，人民郵電出版社，2016

（三）文章-必讀

近年《計(jì)算機(jī)學(xué)報(bào)》,、《軟件學(xué)報(bào)》等國(guó)內(nèi),、國(guó)際期刊雜志刊登的文章。

（四）文章-強(qiáng)烈推薦

無(wú)

（五）其他參考資料

1. Kenneth.Rosen 著,，袁崇義 屈婉玲 等譯,《離散數(shù)學(xué)及其應(yīng)用》（原書第6版）, 機(jī)械工業(yè)出版社 2011

六,、教學(xué)活動(dòng)以及對(duì)于預(yù)期學(xué)習(xí)成果的評(píng)估

（一）教學(xué)活動(dòng)

1、個(gè)人預(yù)習(xí)

2,、課堂講授

3,、課堂問答

4、習(xí)題講解

5,、案例討論

6,、期中測(cè)驗(yàn)

7、期末考試

（二）對(duì)預(yù)期學(xué)習(xí)成果的考察

七,、評(píng)估的程序和方法

（一）評(píng)分體系

1、出勤率: 10%

2,、課堂參與: 15%

3,、課后作業(yè): 15%

4、期末考試: 60%

（二）評(píng)分標(biāo)準(zhǔn)及要求

八,、教學(xué)進(jìn)度與學(xué)時(shí)分配表