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

《離散數(shù)學(xué)》教學(xué)大綱課程類別：專業(yè)基礎(chǔ)必修課課程代碼：B2093709總學(xué)時：80（理論學(xué)時：80）學(xué)分：5適用專業(yè)：計算機科學(xué)與技術(shù)、信息管理與信息系統(tǒng)、信息安全、軟件工程、網(wǎng)絡(luò)工程、數(shù)字媒體技術(shù)先修課程：高等數(shù)學(xué)AI-AII、線性代數(shù)A一、課程的地位、性質(zhì)和任務(wù)離散數(shù)學(xué)是現(xiàn)代數(shù)學(xué)的一個重要分支，是計算機科學(xué)與技術(shù)及相關(guān)專業(yè)的基礎(chǔ)理論核心課程，與數(shù)據(jù)結(jié)構(gòu)、編譯原理、算法分析與設(shè)計、數(shù)字邏輯、數(shù)據(jù)庫原理、人工智能等課程有密切聯(lián)系。本課程系專業(yè)基礎(chǔ)必修課，為學(xué)生學(xué)習(xí)信息與計算科學(xué)的有關(guān)課程打好理論基礎(chǔ)。ComputingCurriculum2005（CC2005）將離散數(shù)學(xué)作為其獨立、首要和核心的教學(xué)模塊。在培養(yǎng)學(xué)生掌握本課程主要內(nèi)容的同時，培養(yǎng)學(xué)生的抽象思維、邏輯推理、創(chuàng)新思維、靈活運用等諸方面的素質(zhì)和能力。二、課程教學(xué)的基本要求（1）掌握相關(guān)的概念和基本的理論知識掌握集合的基本概念：集合的表示方法、子集、冪集、補集；掌握集合的基本運算：并、交、差、補、對稱差（環(huán)和），及其性質(zhì)；掌握容斥原理，并學(xué)會運用；掌握序偶（有序?qū)Γ┡c集合的笛卡兒積；掌握二元關(guān)系的定義及其3種表示方法：集合表示法、關(guān)系圖表示法、關(guān)系矩陣表示法；掌握二元關(guān)系的5種基本類型：自反的、反自反的、對稱的、反對稱的、傳遞的二元關(guān)系；掌握二元關(guān)系的運算：復(fù)合、逆、冪、閉包；重點掌握等價關(guān)系的基礎(chǔ)知識，包括等價關(guān)系的定義、特征、等價類、商集、集合的劃分；重點掌握偏序關(guān)系的基礎(chǔ)知識，包括偏序關(guān)系的定義、哈斯圖、偏序集中的8種特殊元素；掌握函數(shù)的定義，單射、滿射、雙射的定義及其基本性質(zhì)，復(fù)合函數(shù)與逆函數(shù)（反函數(shù)）的定義及基本性質(zhì)；掌握代數(shù)系統(tǒng)的基本概念；掌握特殊運算（封閉運算，可交換運算，可結(jié)合運算，可分配運算）和特殊元素（等冪元，幺元，逆元，零元），重點是封閉運算、可結(jié)合運算、幺元、逆元；掌握同構(gòu)、同態(tài)的定義及基本性質(zhì)；掌握半群、子半群，獨異點、子獨異點的定義及基本性質(zhì)；重點掌握群的定義及性質(zhì)；掌握子群的定義及判定方法；掌握陪集的定義與性質(zhì)以及拉格朗日定理；掌握循環(huán)群和置換群的定義與性質(zhì)；掌握正規(guī)子群的定義及性質(zhì)；掌握格的定義及性質(zhì)，以及有界格、分配格、有補格的定義和性質(zhì)；了解布爾代數(shù)的定義及性質(zhì)；掌握圖的基本概念及性質(zhì)，包括：圖的定義、簡單圖、完全圖、子圖、真子圖、生成子圖、導(dǎo)出子圖、結(jié)點的度數(shù)、握手定理、圖的同構(gòu)，重點是簡單圖、握手定理、生成子圖、圖的同構(gòu)；掌握通路、回路、連通圖、連通分支、圖的連通性的概念及基本性質(zhì)；理解圖的操作，掌握圖的矩陣表示，包括關(guān)聯(lián)矩陣、鄰接矩陣、可達矩陣；掌握賦權(quán)圖及最短通路的概念，掌握Dijkstra算法并學(xué)會運用；理解Floyd算法。掌握歐拉圖、哈密頓圖的定義及判定定理；理解貨郎擔(dān)問題及最鄰近算法。掌握二部圖、完全二部圖的定義及二部圖的判定定理；掌握匹配、完全匹配的概念及霍爾定理。掌握平面圖的概念；掌握歐拉公式、庫拉托夫斯基定理；理解圖的著色問題。掌握無向樹的定義及性質(zhì)；掌握有向樹、生成樹、最小生成樹的定義，以及求生成樹和最小生成樹的算法；。掌握根樹的定義及性質(zhì)；理解k-元樹、根樹遍歷方法；掌握（葉）帶權(quán)樹、最優(yōu)樹的概念；掌握Huffman算法及其應(yīng)用。掌握命題與命題聯(lián)結(jié)詞（否定、合取、析取、蘊涵、等價）。掌握命題公式及其真值表，掌握命題的符號化。掌握命題邏輯等值演算，重點：16個基本等值式。重點掌握主析取范式與主合取范式。了解聯(lián)結(jié)詞的完備集。掌握命題邏輯的推理演算。掌握謂詞邏輯的基本概念，包括：個體詞、謂詞、函詞和量詞，謂詞公式的分類與解釋，等值演算與前束范式。掌握謂詞邏輯的推理演算。（2）具有嚴密的邏輯推理能力，能準確地表述一些概念；（3）獨立完成相應(yīng)的習(xí)題和作業(yè)，鞏固好所學(xué)的知識，為以后的學(xué)習(xí)打好基礎(chǔ)。三、理論教學(xué)內(nèi)容與學(xué)時分配1．集合（5學(xué)時）集合的概念及表示，特殊集合，集合的運算，計數(shù)問題。2．關(guān)系（11學(xué)時）關(guān)系的定義與表示，關(guān)系的性質(zhì)，關(guān)系的運算，等價關(guān)系，偏序關(guān)系。3．函數(shù)（2學(xué)時）函數(shù)的概念，函數(shù)的復(fù)合運算、逆運算。4．習(xí)題課（2學(xué)時）講解1-3中的習(xí)題。5．代數(shù)系統(tǒng)（6學(xué)時）代數(shù)系統(tǒng)的基本概念，代數(shù)運算的性質(zhì)，相互聯(lián)系的代數(shù)系統(tǒng)。6．典型代數(shù)系統(tǒng)（14學(xué)時）半群，群和特殊群，格，布爾代數(shù)。7．抽象代數(shù)習(xí)題課（2學(xué)時）講解4-5中的習(xí)題。8．圖（12學(xué)時）圖的概念，圖的連通性，圖的操作與表示，賦權(quán)圖，歐拉圖，哈密頓圖，二部圖，平面圖。9．樹（4學(xué)時）樹，生成樹，根樹。10．圖論習(xí)題課（2學(xué)時）講解8-9中的習(xí)題。11．命題邏輯（10學(xué)時）命題邏輯的基本概念，命題公式及其解釋，命題公式的分類，命題公式的等值式，命題公式的范式，命題邏輯推理。12．謂詞邏輯（6學(xué)時）謂詞邏輯的基本概念，謂詞公式的分類與解釋，謂詞公式的等值式，謂詞公式的范式，謂詞邏輯推理。13．?dāng)?shù)理邏輯習(xí)題課（2學(xué)時）講解11-12中的習(xí)題。14．總復(fù)習(xí)（2學(xué)時）四、教學(xué)方法的原則建議教學(xué)重點：等價關(guān)系，偏序關(guān)系，命題邏輯等值演算，主析取范式與主合取范式，命題邏輯推理演算中的構(gòu)造證明法，將命題符號化為謂詞公式，謂詞公式的解釋，代數(shù)系統(tǒng)的同構(gòu)和同態(tài)，群與子群，圖的同構(gòu)，歐拉圖與哈密爾頓圖。教學(xué)難點：冪集，商集，主析取范式與主合取范式，附加前提證明法（CP規(guī)則），謂詞公式的解釋，謂詞邏輯的推理演算，代數(shù)系統(tǒng)的同構(gòu)和同態(tài)，圖的同構(gòu)。教學(xué)方法的原則建議：離散結(jié)構(gòu)的內(nèi)容既“離散”，又彼此聯(lián)系。注重基本概念，強調(diào)教學(xué)內(nèi)容中各組成部分之間的聯(lián)系，突出重點，如集合運算、關(guān)系運算與代數(shù)系統(tǒng)，二元關(guān)系與有向圖，傳遞閉包與連通性，等價關(guān)系與邏輯等價，偏序關(guān)系與永真蘊含，n元關(guān)系與n元謂詞等，并引導(dǎo)學(xué)生舉一反三。五、考核方式及成績構(gòu)成考核方式：閉卷筆試。成績構(gòu)成：平時20—30％，考試成績70—80%。六、教材與參考書目推薦教材：古天龍,常亮.離散數(shù)學(xué).清華大學(xué)出版社,2012參考書目：邵學(xué)才,葉