《離散數(shù)學(xué)I》課程教學(xué)大綱

1、離散數(shù)學(xué)I課程教學(xué)大綱一、課程基本信息課程代碼：12130118課程英文名稱：Discrete Mathematics課程面向?qū)I(yè)：信息與計算科學(xué)專業(yè)課程類型：必修課 先修課程：高等代數(shù) 學(xué)分：4 總學(xué)時：64 (其中理論學(xué)時：64 實驗學(xué)時：0 ) 二、課程性質(zhì)與目的本課程是現(xiàn)代數(shù)學(xué)的重要分支，是計算科學(xué)的理論基礎(chǔ)，對于培養(yǎng)學(xué)生的邏輯思維和抽象思維以及分析問題解決問題的能力有重要作用。通過本課程的學(xué)習(xí)，使學(xué)生初步掌握離散數(shù)學(xué)的基本理論和方法，了解離散數(shù)學(xué)與計算科學(xué)中的數(shù)據(jù)結(jié)構(gòu)與算法分析、可計算性與計算復(fù)雜性、程序設(shè)計語言、人工智能與機器人、網(wǎng)絡(luò)、計算機圖形學(xué)、操作系統(tǒng)、編譯理論以及人機通訊等

2、課程的緊密聯(lián)系，為學(xué)好這些課程打好基礎(chǔ)。三、課程教學(xué)內(nèi)容與要求第一部分：數(shù)理邏輯1、教學(xué)內(nèi)容與要求（1）命題邏輯的基本概念與方法：熟練掌握命題與聯(lián)結(jié)詞的表示法和運算關(guān)系；掌握命題公式的翻譯與真值表；掌握基本的等值式，會用等值演算法驗證等值式；掌握析取范式與合取范式相關(guān)概念，會求命題公式的主析取范式與主合取范式；掌握推理的形式結(jié)構(gòu)，掌握自然推理系統(tǒng)。（2）一階邏輯的基本概念與方法：掌握一階邏輯命題的符號化方法；了解一階邏輯公式及其解釋方法；掌握邏輯等值式及其置換規(guī)則；了解一階邏輯的前束范式；掌握一階邏輯的推理理論。2、教學(xué)重點命題與聯(lián)結(jié)詞的表示法和運算關(guān)系，命題公式的翻譯與真值表，基本的等值式，

3、求命題公式的主析取范式與合取范式，推理的形式結(jié)構(gòu)；3、教學(xué)難點邏輯等值式及其置換規(guī)則，一階邏輯的推理理論。第二部分：集合論1、教學(xué)內(nèi)容與要求（1）集合代數(shù)：熟練掌握集合的基本概念、運算；熟練掌握集合的恒等式；了解關(guān)系、關(guān)系的運算；熟練掌握關(guān)系的性質(zhì)；熟練掌握等價關(guān)系與偏序關(guān)系；了解集合的基數(shù)。（2）函數(shù)論：了解函數(shù)的定義與性質(zhì)；了解復(fù)合函數(shù)與反函數(shù)。2、教學(xué)重點：集合的恒等式，關(guān)系的性質(zhì)3、教學(xué)難點：等價關(guān)系與偏序關(guān)系第三部分：代數(shù)結(jié)構(gòu)1、教學(xué)內(nèi)容與要求（1）代數(shù)系統(tǒng)：了解代數(shù)系統(tǒng)的概念，熟練掌握二元運算及其基本性質(zhì)；了解半群與獨異點；熟練掌握群的定義與性質(zhì)；掌握子群的概念與性質(zhì)；掌握陪集與拉

4、格朗日定理；掌握正規(guī)子群與商群；熟練掌握群的同構(gòu)與同態(tài)；熟練掌握循環(huán)群，了解置換群；了解環(huán)與域的基本概念與性質(zhì)，了解格與布爾代數(shù)。2、教學(xué)重點群的定義與性質(zhì)，子群的概念與性質(zhì)，陪集與拉格朗日定理3、教學(xué)難點 正規(guī)子群與商群，群的同構(gòu)與同態(tài)，循環(huán)群第四部分：圖論1、教學(xué)內(nèi)容與要求（1）圖的基本概念：熟練掌握圖的基本概念；熟悉通路與回路及二部圖；掌握圖的矩陣表示；了解歐拉圖與哈密頓圖。（2）樹：掌握無向樹的基本概念及其性質(zhì)；掌握生成樹；熟練掌握根樹及其運用。（3）平面圖及其著色：掌握平面圖的概念；熟練掌握歐拉公式，了解平面圖的對偶圖；了解平面圖的判斷方法；了解圖的著色（4）支配集、覆蓋集、獨立集與

5、匹配：了解支配集、覆蓋集、獨立集的基本概念；了解圖的匹配2、教學(xué)重點：圖的基本概念，通路與回路及二部圖，圖的矩陣表示3、教學(xué)難點：無向樹的基本概念及其性質(zhì)，平面圖的概念，歐拉公式四、學(xué)時分配學(xué)時分配表序號教 學(xué) 內(nèi) 容學(xué)時課堂講授實驗課習(xí)題課討論課其它1第一部分：分?jǐn)?shù)理邏輯1422第二部分：集合論83第三部分：代數(shù)結(jié)構(gòu)2224第四部分；圖論142小計586比例91%9%合計64五、教學(xué)環(huán)節(jié)與教學(xué)要求如果本校計算機系使用本教學(xué)大綱，由于學(xué)時數(shù)安排比較少，可以適當(dāng)采取“少而精”的原則將部分內(nèi)容選講。在具體講授時，部分算法可以要求學(xué)生編寫出具體的計算程序。六、課程考核辦法閉卷考試七、教材與主要參考書1、離散數(shù)學(xué)（第2版）耿素云高等教育出版社2004 2、離散數(shù)學(xué)習(xí)題集數(shù)理邏輯與集合論分冊耿素云北京大學(xué)出版社19933、離散數(shù)學(xué)習(xí)題集圖論分冊耿素云北京大學(xué)出版社1