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

1、離散數(shù)學(xué)（Discrete Mathematics）課程代碼：2131032學(xué)分：3 學(xué)時：48 （其中：課程教學(xué)學(xué)時：48，實驗學(xué)時：0）先修課程：高等數(shù)學(xué)，線性代數(shù)適用專業(yè)：計算機科學(xué)與技術(shù)教材：離散數(shù)學(xué)，馮偉森，欒新成，石兵編著，機械工業(yè)出版社，2011開課學(xué)院：計算機與軟件學(xué)院一、課程性質(zhì)與課程目標(biāo)（一）課程性質(zhì)離散數(shù)學(xué)是高等工科院校計算機類相關(guān)專業(yè)的一門重要學(xué)科基礎(chǔ)必修課，是學(xué)習(xí)后續(xù)計算機專業(yè)課程不可或缺的數(shù)學(xué)工具，包括數(shù)據(jù)結(jié)構(gòu)、數(shù)據(jù)庫系統(tǒng)、計算機網(wǎng)絡(luò)、算法設(shè)計和人工智能等課程。該課程結(jié)合計算機學(xué)科的特點，主要研究離散量的結(jié)構(gòu)及相互關(guān)系，是一門理論性較強、應(yīng)用性較廣的課程，也是培養(yǎng)學(xué)

2、生抽象思維能力和邏輯推理能力的核心課程。（二）課程目標(biāo)課程目標(biāo)包括知識目標(biāo)和能力目標(biāo)，具體如下：課程目標(biāo)1：理解邏輯演算系統(tǒng)、集合論、圖論和代數(shù)系統(tǒng)的基本概念，掌握從基本概念出發(fā)的計算和證明方法，培養(yǎng)邏輯思維和邏輯推理能力。課程目標(biāo)2：掌握命題公式、集合運算、二元關(guān)系、函數(shù)、圖的最短路徑、代數(shù)系統(tǒng)特異元等離散結(jié)構(gòu)求解方法；通過嚴(yán)格數(shù)學(xué)證明的講授，使學(xué)生逐步習(xí)慣于以概念和公理為出發(fā)點的抽象思維方式，并初步掌握嚴(yán)謹數(shù)學(xué)論證的基本規(guī)范。課程目標(biāo)3：能夠利用邏輯演算、集合論、圖論和代數(shù)系統(tǒng)的基本概念和方法對計算機領(lǐng)域復(fù)雜工程問題進行抽象、分析、推理、求解和驗證。（三）課程目標(biāo)與專業(yè)畢業(yè)要求指標(biāo)點的對應(yīng)

3、關(guān)系本課程支撐專業(yè)培養(yǎng)計劃中的畢業(yè)要求指標(biāo)點1.1和2.1。畢業(yè)要求指標(biāo)點1.1：掌握數(shù)學(xué)與自然科學(xué)的基本概念、基本理論和基本技能，領(lǐng)會數(shù)學(xué)、物理思想方法，培養(yǎng)邏輯思維和邏輯推理能力。畢業(yè)要求指標(biāo)點2.1：應(yīng)用數(shù)學(xué)、自然科學(xué)和工程科學(xué)的基本原理，針對一個系統(tǒng)或者過程進行抽象、分析與識別，并進行問題推理、求解和驗證。課程目標(biāo)畢業(yè)要求指標(biāo)點課程目標(biāo)1課程目標(biāo)2課程目標(biāo)3畢業(yè)要求1.1畢業(yè)要求2.1二、課程內(nèi)容及教學(xué)要求（按章撰寫）本課程主要教學(xué)內(nèi)容包括：命題邏輯、集合論、圖論和代數(shù)系統(tǒng)等基本知識。數(shù)理邏輯部分主要講授命題與命題聯(lián)結(jié)詞、命題邏輯演算等。集合論部分主要介紹集合基本概念、集合的運算、函數(shù)

4、、關(guān)系及其運算、等價關(guān)系與集合劃分、偏序關(guān)系等。圖論部分主要講授無向圖、有向圖、通路、回路和圖的連通性、最短路徑、關(guān)鍵路徑以及兩種特殊圖（歐拉圖和哈密頓圖）。代數(shù)部分則主要介紹二元運算及其性質(zhì)、代數(shù)系統(tǒng)及其特異元、幾個典型的代數(shù)系統(tǒng)、以及代數(shù)系統(tǒng)間的同態(tài)與同構(gòu)關(guān)系。本課程基本要求是：理解各個聯(lián)結(jié)詞的定義和關(guān)系，能夠把命題公式轉(zhuǎn)化為等價的主析取范式或主合取范式，能夠把自然語言翻譯成數(shù)學(xué)語言，并給出推證過程；理解集合的基本概念和運算，理解關(guān)系及其性質(zhì)，掌握幾個重要的關(guān)系以及偏序集特殊元素的求??；理解圖論的一些基本概念，掌握一些基本的圖論算法，包括最短路徑求解的Dijkstra算法等；理解代數(shù)系統(tǒng)的

5、基本概念，理解代數(shù)系統(tǒng)中特異元的基本概念并掌握這些元素的求解方法，理解代數(shù)系統(tǒng)之間的同態(tài)和同構(gòu)關(guān)系；針對常見的應(yīng)用問題，能應(yīng)用離散數(shù)學(xué)的基本原理進行抽象、分析、推理、求解和驗證。第1章命題邏輯教學(xué)內(nèi)容命題及其真值重言式范式聯(lián)結(jié)詞的擴充與歸約。推理規(guī)則和證明方法。（二）教學(xué)要求掌握命題、命題聯(lián)結(jié)詞的概念；理解命題公式的遞歸定義，熟練掌握命題符號化的方法，掌握命題公式真值表的求法；理解公式等值的定義，掌握運用基本等值式進行等值演算的方法。了解范式的概念，掌握求命題公式的析取范式、合取范式和主式的方法。了解與非、或非、異或等聯(lián)結(jié)詞及聯(lián)結(jié)詞的歸約。掌握常用的推理規(guī)則和證明方法。（三）重點與難點1. 重

6、點命題、命題聯(lián)結(jié)詞的概念；自然語言翻譯成數(shù)學(xué)語言；重言式與蘊含式；求命題公式的析取范式、合取范式和主式的方法；推理規(guī)則。2. 難點命題公式與翻譯；推理規(guī)則。第3章集合代數(shù)（一）教學(xué)內(nèi)容集合論的基本概念集合的運算集合的笛卡爾乘積（二）教學(xué)要求掌握子集、空集、全集、相等、密集等基本概念。理解集合的基本概念表示法；掌握集合的交、并、差和補等概念及交換律、結(jié)合律、分配律和De Morgan律等運算律，證明集合等式。掌握集合的笛卡爾乘積的運算。（三）重點與難點1.重點集合的概念與表示；集合的運算；序偶與笛卡爾積。2.難點序偶與笛卡爾積。第4章二元關(guān)系（一）教學(xué)內(nèi)容關(guān)系的基本概念關(guān)系的運算關(guān)系上的閉包運算

7、（二）教學(xué)要求理解關(guān)系及有關(guān)概念，掌握關(guān)系圖、關(guān)系矩陣及關(guān)系的特性（自反性、反自反性、對稱性、反對稱性和傳遞性）。掌握關(guān)系的合成、關(guān)系的冪關(guān)系、關(guān)系合成及其有關(guān)性質(zhì)。掌握逆關(guān)系、關(guān)系的閉包運算（自反閉包、對稱閉包和傳遞閉包）的性質(zhì)及求法。（三）重點與難點1.重點關(guān)系的概念；關(guān)系的性質(zhì)；關(guān)系的閉包運算；復(fù)合關(guān)系與逆關(guān)系。2.難點關(guān)系的閉包運算；復(fù)合關(guān)系與逆關(guān)系。第5章特殊關(guān)系（一）教學(xué)內(nèi)容次序關(guān)系等價關(guān)系和劃分函數(shù)的基本概念特殊函數(shù)類逆函數(shù)（二）教學(xué)要求掌握偏序集合、擬序集合、線序集合、良序集合及特殊元素的概念及性質(zhì)。理解等價關(guān)系、覆蓋及劃分的概念，掌握求集合的等價類方法及劃分的積與和。（三）重

8、點與難點1.重點等價關(guān)系與等價類；序關(guān)系；特殊元素的概念和求法。2.難點等價關(guān)系與等價類；序關(guān)系。第6章函數(shù)（一）教學(xué)內(nèi)容函數(shù)的基本概念特殊函數(shù)類逆函數(shù)集合的基數(shù)、可數(shù)集和不可數(shù)集（二）教學(xué)要求理解函數(shù)的概念，掌握函數(shù)的合成運算。理解滿射、單射和雙射函數(shù)的概念，了解置換、特征函數(shù)的概念及運算。理解逆函數(shù)和規(guī)范映射的概念及性質(zhì)。掌握集合基數(shù)的概念會判斷一個集合是可數(shù)集還是不可數(shù)集（三）重點與難點1.重點滿射、單射和雙射函數(shù)的概念和判斷；逆函數(shù)與復(fù)合函數(shù)；可數(shù)集和不可數(shù)集的判斷。2.難點可數(shù)集和不可數(shù)集的判斷。第8章基本計數(shù)方法（一）教學(xué)內(nèi)容1. 容斥原理2. 鴿巢原理（二）教學(xué)要求理解容斥原理和

9、鴿巢原理的原理。會應(yīng)用容斥原理和鴿巢原理去解決實際問題。（三）重點與難點1.重點容斥原理及其應(yīng)用；鴿巢原理及其應(yīng)用。2.難點應(yīng)用容斥原理和鴿巢原理解決實際問題。第10章圖的基本概念（一）教學(xué)內(nèi)容圖的基本概念路徑和回路圖的矩陣表示（二）教學(xué)要求理解圖的基本概念，了解幾類特殊的圖。理解路徑與回路及有關(guān)概念（基本路徑、簡單路徑、基本回路和簡單回路），了解連通圖的概念（強連通、單向連通、弱連通、強分圖、單向分圖和弱分圖）。掌握圖的矩陣表示（鄰接矩陣和可達性矩陣）。（三）重點與難點1.重點圖的基本概念；握手定理；連通性；圖的表示。2.難點應(yīng)用握手定理解決實際問題。第11章樹及其應(yīng)用（一）教學(xué)內(nèi)容無向樹及

10、其性質(zhì)生成樹（二）教學(xué)要求理解無向樹和生成樹的概念掌握用Kruskal算法求最小生成樹。（三）重點與難點1.重點樹的基本概念；生成樹的概念；Kruskal算法求最小生成樹。2.難點Kruskal算法求最小生成樹。第13章歐拉圖與哈密頓圖（一）教學(xué)內(nèi)容歐拉回路與歐拉圖哈密頓回路與哈密頓圖（二）教學(xué)要求掌握歐拉路徑、歐拉回路和歐拉圖的判別法。理解哈密爾頓路徑、哈密爾頓回路和哈密爾頓圖的概念，掌握哈密頓圖的判定。（三）重點與難點1.重點歐拉圖的概念和判定；哈密頓圖的概念和判定。2.難點哈密頓圖的判定。第14章代數(shù)系統(tǒng)教學(xué)內(nèi)容二元運算及其性質(zhì)代數(shù)系統(tǒng)及其特異元廣群、半群和群（二）教學(xué)要求理解二元運算的

11、定義，熟練掌握二元運算性質(zhì)的判斷及證明。理解代數(shù)系統(tǒng)的基本概念。理解代數(shù)系統(tǒng)中特異元（單位元、逆元）的基本概念，掌握這些元素的求解方法。理解代數(shù)系統(tǒng)廣群、半群、群、環(huán)和域的基本概念，掌握特殊代數(shù)系統(tǒng)的判定方法。（三）重點與難點1.重點二元運算及其性質(zhì)的判斷及證明；代數(shù)系統(tǒng)的特異元；特殊代數(shù)系統(tǒng)的判斷與證明。2.難點二元運算性質(zhì)的判斷及證明；代數(shù)系統(tǒng)的特異元求??；特殊代數(shù)系統(tǒng)的判斷與證明。第15章半群與群教學(xué)內(nèi)容子群和正規(guī)子群群的同態(tài)與同構(gòu)（二）教學(xué)要求了解子群、子群的陪集以及正規(guī)子群的概念。掌握群的同態(tài)和同構(gòu)定義，會證明。（三）重點與難點1.重點群的同態(tài)和同構(gòu)的證明。2.難點群的同態(tài)和同構(gòu)的證

12、明。第16章環(huán)與域教學(xué)內(nèi)容環(huán)和域（二）教學(xué)要求掌握環(huán)和域的定義，判斷與證明。（三）重點與難點1.重點環(huán)和域的判斷與證明。2.難點環(huán)和域的判斷與證明。三、學(xué)時分配及教學(xué)方法章教學(xué)形式及學(xué)時分配主要教學(xué)方法支撐的課程目標(biāo)課堂教學(xué)實驗上機課程實踐小計第1章命題邏輯1010講授、案例、演示、討論課程目標(biāo)1， 2，3第3章集合代數(shù)22講授、案例、自學(xué)課程目標(biāo)1， 2第4章二元關(guān)系33講授、案例、對比、討論課程目標(biāo)1， 2， 3第5章特殊關(guān)系33講授、案例、對比、討論課程目標(biāo)1， 2， 3第6章函數(shù)44講授、案例、討論課程目標(biāo)1， 2， 3第8章基本計數(shù)方法22講授、案例、討論課程目標(biāo)1， 2， 3第10

13、章圖的基本概念44講授、案例、演示、討論課程目標(biāo)1， 2第11章樹及其應(yīng)用33講授、案例、演示、討論課程目標(biāo)1， 2第13章歐拉圖與哈密頓圖33講授、案例、研究型、討論課程目標(biāo)1， 2， 3第14章代數(shù)系統(tǒng)22講授、案例、研究型、討論課程目標(biāo)1， 2， 3第15章半群與群44講授、案例、研究型、討論課程目標(biāo)1， 2， 3第16章環(huán)與域22講授、案例、研究型、討論課程目標(biāo)1， 2， 3習(xí)題課66講授、討論課程目標(biāo)1， 2， 3合計4848注：1.課程實踐學(xué)時按相關(guān)專業(yè)培養(yǎng)計劃列入表格； 2.主要教學(xué)方法包括講授法、討論法、演示法、研究型教學(xué)方法（基于問題、項目、案例等教學(xué)方法）等。四、課程考核

14、1. 課程考核方式包括期末考試、平時表現(xiàn)考核?？己诵问娇己艘罂己藱?quán)重備注平時作業(yè)及期中考試課后完成2025個習(xí)題，主要考核學(xué)生對每節(jié)課知識點的復(fù)習(xí)、理解和掌握度，計算全部作業(yè)的平均成績再按30%計入總成績；可讓學(xué)生查閱資料，了解本課程相關(guān)技術(shù)發(fā)展情況，自主學(xué)習(xí)并完成。30%根據(jù)平時作業(yè)得分取平均值或結(jié)合期中測試和考勤情況期末考試試卷題型包括選擇題、填空題、判斷題、計算題、應(yīng)用題和證明題等，以卷面成績的70%計入課程總成績。70%期末考試采用閉卷筆試。五、參考書目及學(xué)習(xí)資料左孝凌等編，離散數(shù)學(xué)(第一版)，上?？茖W(xué)技術(shù)文獻出版社，1982。段禪倫、魏仕民編著，離散數(shù)學(xué)(第一版)，北京大學(xué)出版社，2006。耿素云、屈婉