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

《離散數(shù)學(xué)》課程考試大綱一、考試對象本課程考試大綱適用于計算機科學(xué)與技術(shù)（含卓越工程師班）、信息管理與信息系統(tǒng)、信息安全、軟件工程、網(wǎng)絡(luò)工程、數(shù)字媒體技術(shù)專業(yè)的學(xué)生。二、考試依據(jù)本課程考試大綱是以本課程的教學(xué)大綱和指定的教材為依據(jù)制定的。本課程指定的教材為古天龍等主編的、清華大學(xué)出版社出版的《離散數(shù)學(xué)》。三、考核知識點和考核要求第1章集合考核知識點:1．集合，元素，集合的表示，全集，空集2．集合的包含、相等，子集，冪集3．集合的并、交、補、差、對稱差等運算及其運算律4．容斥原理考核要求:1．理解集合的概念，容斥原理．2．理解集合的包含、子集、相等和冪集等概念，熟練掌握集合的表示方法和集合的并、交、補、差和對稱差等運算，會用文氏圖表示集合的各種運算．3．掌握用集合運算基本等值式證明集合恒等式的方法．4．掌握利用容斥原理進行計數(shù)的方法.第2章關(guān)系考核知識點:1．有序?qū)偷芽▋悍e2．關(guān)系及其運算性質(zhì)3．二元關(guān)系的矩陣與圖4．復(fù)合關(guān)系與逆關(guān)系5．二元關(guān)系的性質(zhì)6．等價關(guān)系與等價類7．偏序關(guān)系與哈斯圖，極大(小)元，最大(小)元，上(下)界，上確界，下確界考核要求:1．了解有序?qū)偷芽▋悍e的概念，掌握笛卡兒積的運算．2．理解關(guān)系的概念：包括二元關(guān)系、空關(guān)系、全關(guān)系、恒等關(guān)系．掌握關(guān)系的集合表示、關(guān)系矩陣和關(guān)系圖，掌握關(guān)系的運算．3．掌握求復(fù)合關(guān)系和逆關(guān)系的方法．4．理解關(guān)系的性質(zhì)(自反性和反自反性、對稱性和反對稱性、傳遞性)，掌握其判別方法．5．理解等價關(guān)系和偏序關(guān)系概念，掌握等價關(guān)系、偏序關(guān)系的判定，掌握等價類、劃分的求法和作偏序關(guān)系哈斯圖的方法．知道極大(小)元，最大(小)元的概念，會求極大(小)元、最大(小)元、最小上界和最大下界．第3章函數(shù)考核知識點：函數(shù)、函數(shù)的逆運算、函數(shù)的復(fù)合運算單射、滿射和雙射考核要求：1．理解函數(shù)概念：函數(shù)，函數(shù)的復(fù)合運算和函數(shù)的逆運算．2．理解單射、滿射和雙射等概念，掌握其判別方法．第4章代數(shù)系統(tǒng)考核知識點：1.運算、運算的封閉性2.代數(shù)系統(tǒng)、子代數(shù)系統(tǒng)3.交換律、結(jié)合律、分配律、吸收律、等冪律、消去律4.等冪元、幺元、零元、逆元、可消去元5.同構(gòu)、同態(tài)、同態(tài)核、同態(tài)的基本性質(zhì)考核要求：1.掌握代數(shù)系統(tǒng)的基本概念：運算、運算的封閉性、交換律、結(jié)合律、分配律、吸收律、等冪律、消去律、等冪元、幺元、零元、逆元、可消去元．2.理解代數(shù)系統(tǒng)、子代數(shù)系統(tǒng)的概念．3.掌握同構(gòu)、同態(tài)的定義及基本性質(zhì)；理解同態(tài)核．第5章典型的代數(shù)系統(tǒng)考核知識點：1.半群、子半群、獨異點、子獨異點、群、子群2.元素的階、群的階、群的性質(zhì)、子群的性質(zhì)3.交換群、生成元、循環(huán)群考核要求：掌握半群、子半群、獨異點、子獨異點、群、子群的定義及基本性質(zhì).掌握群的階、元素的階、生成元；掌握子群的判定方法.理解交換群的定義，掌握循環(huán)群的定義與性質(zhì).第6章圖考核知識點:1.圖、簡單圖、完全圖、子圖、生成子圖、導(dǎo)出子圖2.頂點的度數(shù)、握手定理、圖的同構(gòu)、通路、回路、圖的連通性、圖的操作、關(guān)聯(lián)矩陣、鄰接矩陣、可達矩陣、邊權(quán)矩陣、賦權(quán)圖、最短路徑，Dijkstra算法3.歐拉圖、哈密頓圖、二部圖考核要求:掌握圖的基本概念：圖、簡單圖、完全圖、子圖、生成子圖、導(dǎo)出子圖的定義.掌握頂點的度數(shù)、握手定理的應(yīng)用；掌握圖的同構(gòu)；掌握通路、回路、圖的連通性的概念及基本性質(zhì).理解圖的操作；掌握關(guān)聯(lián)矩陣、鄰接矩陣，理解可達矩陣、邊權(quán)矩陣；掌握賦權(quán)圖及最短路徑的概念，掌握用Dijkstra算法求賦權(quán)圖中的最短路徑；掌握歐拉圖、哈密頓圖的定義及判定定理；理解二部圖的定義及判定定理.第7章樹考核知識點:無向樹、賦權(quán)樹、生成樹、最小生成樹、求最小生成樹的算法、有向樹、根樹、有序樹、根樹的遍歷、二叉樹、最優(yōu)樹、前綴碼、最佳前綴碼、Huffman算法考核要求:掌握無向樹的定義及性質(zhì)；掌握賦權(quán)樹、生成樹、最小生成樹的定義及求最小生成樹的算法.掌握有向樹的定義及性質(zhì)；掌握根樹、有序樹的定義，理解根樹的遍歷；掌握二叉樹的定義及性質(zhì)；掌握最優(yōu)樹、前綴碼、最佳前綴碼的定義，Huffman算法及其應(yīng)用.第8章命題邏輯考核知識點：1．命題與聯(lián)結(jié)詞(否定、析取、合取、蘊含、等價)，真值與真值表2．命題公式的等值式與蘊涵式，等值演算3．析取范式、合取范式、極小(大)項，主析取范式、主合取范式的概念與求法4．命題邏輯的推理理論考核要求：1．理解命題聯(lián)結(jié)詞概念，掌握命題符號化及判斷語句是不是命題的方法．2．熟練掌握求給定公式真值表的方法．3．掌握基本等值式以及用真值表法和等值演算法判別公式類型和公式等值的方法．4．了解析取(合取)范式概念，理解極小(大)項的概念和主析取(合取)范式概念，熟練掌握用基本等值式或真值表將公式化為主析取(合取)范式的方法．5．掌握命題邏輯推理的的直接證明方法與間接證明方法．第9章謂詞邏輯考核知識點：1．謂詞，量詞，個體詞，個體域，變元2．謂詞公式的解釋3．前束范式的概念與求法4．謂詞公式的等值式與蘊涵式5．謂詞邏輯的推理理論考核要求：1．理解謂詞、量詞、個體詞、個體域、全域、原子公式、謂詞公式和變元等概念．掌握謂詞公式的符號化.2．掌握在有限個體域下消去公式的量詞和求公式在給定解釋下真值的方法．3．掌握謂詞演算的等值式和重言蘊含式