“離散數(shù)學(xué)”課程教學(xué)大綱課程編號(hào):08012060課程名稱：《離散數(shù)學(xué)》/DiscreteMathematics學(xué)時(shí)：64學(xué)時(shí)學(xué)分：4適用專業(yè)：計(jì)算機(jī)相關(guān)專業(yè)開課學(xué)期：第4學(xué)期開課部門：數(shù)學(xué)與計(jì)算機(jī)科學(xué)學(xué)院先修課程：線性代數(shù)、高等數(shù)學(xué)考核要求：課程成績按百分制計(jì)算，其中考試成績占80%，平時(shí)作業(yè)課堂考核占20%。使用教材及主要參考書：王元元等著，《計(jì)算機(jī)科學(xué)中的離散結(jié)構(gòu)》，左孝凌等著，《離散數(shù)學(xué)》，上?？茖W(xué)技術(shù)文獻(xiàn)出版社,2001年方世昌著編，《離散數(shù)學(xué)》,西安電子科技大學(xué)出版社，2001年一、課程的性質(zhì)和任務(wù)《離散數(shù)學(xué)》是計(jì)算機(jī)科學(xué)與技術(shù)專業(yè)教學(xué)中最為重要的核心基礎(chǔ)課程，它是學(xué)習(xí)專業(yè)理論不可少的數(shù)學(xué)工具，是計(jì)算科學(xué)專業(yè)的專業(yè)必修課程。通過學(xué)習(xí)本課程,培養(yǎng)學(xué)生的抽象思維和慎密概括的能力，使學(xué)生具有良好的開拓專業(yè)理論的素質(zhì)和使用所學(xué)知識(shí)，分析和解決實(shí)際問題的能力?！峨x散數(shù)學(xué)》是現(xiàn)代數(shù)學(xué)的一個(gè)重要分支,為學(xué)生今后從事計(jì)算機(jī)科學(xué)各方面的工作提供重要的工具。二、教學(xué)目的與要求本課程主要有數(shù)理邏輯、集合論、圖論、代數(shù)系統(tǒng)等內(nèi)容，是一門理論性較強(qiáng)，應(yīng)用性較廣的課程。課程的教學(xué)組織應(yīng)為計(jì)算科學(xué)專業(yè)的學(xué)生提供必要的數(shù)學(xué)基礎(chǔ)和展示離散數(shù)學(xué)的實(shí)用性為目的，使專業(yè)學(xué)生理解嚴(yán)謹(jǐn)?shù)臄?shù)學(xué)概念的重要性以及這些概念對(duì)應(yīng)用的作用，進(jìn)一步提高抽象思維和邏輯推理的能力；。離散數(shù)學(xué)課程教學(xué)的目標(biāo)，使學(xué)生學(xué)會(huì)特定的一些數(shù)學(xué)事實(shí)并知道怎樣應(yīng)用，教會(huì)學(xué)生做數(shù)學(xué)思維和解決應(yīng)用問題。為此，應(yīng)將數(shù)學(xué)推理、組合分析、離散結(jié)構(gòu)、算法思考以及應(yīng)用和建模等手段，作為核心內(nèi)容和課程主線，有機(jī)地交融在一起并體現(xiàn)到對(duì)學(xué)生是否真正掌握課程知識(shí)的考核中。三、學(xué)時(shí)分配章節(jié)教學(xué)內(nèi)容學(xué)時(shí)分配小計(jì)講課試驗(yàn)上機(jī)討論/習(xí)題第一章集合代數(shù)62第二章兩個(gè)常用數(shù)學(xué)原理31第三章邏輯代數(shù)-命題演算82第四章邏輯代數(shù)-謂詞演算62第六章計(jì)數(shù)62第八章圖82第九章二分圖、平面圖和樹82第十章關(guān)系42四、教學(xué)中應(yīng)注意的問題本課程以課堂講授為主，精講多練，注重理論聯(lián)系實(shí)際。各章中平行的內(nèi)容可安排學(xué)生自學(xué)，以提高學(xué)生獨(dú)立思考和解決問題的能力?！峨x散數(shù)學(xué)》課程涉及的概念較多，解題方法靈活多樣，更需要分析和解決問題的能力，因此必須通過做練習(xí)題來加深對(duì)概念的理解和掌握，熟悉基本公式、基本方法的運(yùn)用，從而達(dá)到理解、掌握所學(xué)知識(shí)的目的。因此獨(dú)立完成作業(yè)是學(xué)好本課程的重要手段。在教學(xué)中，通過習(xí)題的布置，使學(xué)生深入理解基本原理及概念，提高分析和解決問題的能力。作業(yè)分為必做和選做兩類。必做作業(yè)是基本教學(xué)所要求的，每個(gè)學(xué)生都要認(rèn)真完成；選做作業(yè)涉及提高部分的內(nèi)容，供不同層次的學(xué)生選做。每次課后布置3-5題作業(yè)。教學(xué)過程中，有關(guān)定義、定理、性質(zhì)、特征等概念的內(nèi)容要求，由低到高分“知道、了解、理解”三個(gè)層次。五、課程教學(xué)內(nèi)容第一章集合代數(shù)1.基本內(nèi)容：集合的概念和表示，集合的運(yùn)算，集合的歸納定義方法2.教學(xué)要求：掌握集合的概念和表示，熟練掌握集合的并、交、差、補(bǔ)、差運(yùn)算并通過文氏圖加深理解，會(huì)做笛卡爾積的運(yùn)算；理解集合的包含與相等、冪集等基本概念。熟練掌握集合的基本運(yùn)算，并能用以證明集合恒等式。掌握集合相等的互為子集和利用性質(zhì)的證明方法，掌握包含關(guān)系的證明方法。3.教學(xué)重點(diǎn)、難點(diǎn)：集合相等的性質(zhì)，集合包含的性質(zhì)第二章兩種常用數(shù)學(xué)原理1.基本內(nèi)容：歸納原理、鴿籠原理2.教學(xué)要求：掌握歸納原理的數(shù)學(xué)思想和證明方法；掌握鴿籠原理及其應(yīng)用3.教學(xué)重點(diǎn)、難點(diǎn)：歸納原理和鴿籠原理的理解第三章邏輯代數(shù)-命題演算1.基本內(nèi)容：命題和邏輯聯(lián)結(jié)詞、邏輯等價(jià)式和邏輯蘊(yùn)含式、范式2.教學(xué)要求：熟練掌握命題的概念和表示法；熟練掌握對(duì)命題的符號(hào)化；理解命題概念，會(huì)判斷語句是否命題；掌握命題的基本等值公式和蘊(yùn)含式，掌握用有關(guān)的定理證明；掌握命題等價(jià)的證明方法，和命題的范式和主范式的求解方法，掌握用主析取范式判斷兩個(gè)公式是否等價(jià)的方法；掌握如何將實(shí)際問題轉(zhuǎn)化為邏輯問題。3.教學(xué)重點(diǎn)、難點(diǎn)：命題公式的等價(jià)和蘊(yùn)含的證明。第四章邏輯代數(shù)-謂詞演算1.基本內(nèi)容：謂詞演算的基本概念、謂詞演算永真式2.教學(xué)要求：理解謂詞、量詞、變?cè)?、個(gè)體域等概念；掌握用謂詞、量詞、聯(lián)接詞構(gòu)造謂詞邏輯公式的方法；熟練掌握任意和存在量詞的意義；會(huì)將謂詞邏輯作為工具，將命題符號(hào)化，熟練掌握對(duì)命題的符號(hào)化；掌握謂詞公式中常用的等價(jià)式和蘊(yùn)含式；掌握命題等價(jià)的證明方法。3.教學(xué)重點(diǎn)、難點(diǎn)：常用的謂詞公式的等價(jià)式和蘊(yùn)含式。第六章計(jì)數(shù)1.基本內(nèi)容：計(jì)數(shù)基本性質(zhì)、排列組合、重集的排列和組合2.教學(xué)要求：掌握乘法、加法原理及其包含排斥原理；掌握排列和組合的計(jì)數(shù)；掌握重集的排列和組合及其禁位計(jì)數(shù)3.教學(xué)重點(diǎn)、難點(diǎn)：排列、組合和重集的排列與組合。第八章圖1.基本內(nèi)容：圖的基礎(chǔ)知識(shí)，路徑、回路及連通性，歐拉圖與哈密爾頓圖，圖的矩陣表示2.教學(xué)要求：掌握?qǐng)D的基本知識(shí)；掌握路徑、回路和連通性的概念；熟練掌握歐拉圖與漢密爾頓圖的定義，理解相關(guān)定理及其應(yīng)用；掌握歐拉回路和漢密爾頓回路的求解方法；掌握?qǐng)D的矩陣表示，可達(dá)矩陣和路徑矩陣求法。.3.教學(xué)重點(diǎn)、難點(diǎn)：圖的連通性，歐拉回路和漢密爾頓回路的求解，圖的矩陣的應(yīng)用。第九章二分圖、平面圖和樹1.基本內(nèi)容：二分圖，平面圖和樹2.教學(xué)要求：掌握二分圖，平面圖和樹的基本概念；掌握二分圖的判定，掌握匹配的概念和最大匹配的求解方法及其匹配的應(yīng)用；理解平面圖、極大平面圖的定義及相關(guān)定理，掌握平面圖的歐拉公式和平面圖的性質(zhì)，知道非平面圖的定義和判定定理；掌握求最小生成樹的卡魯斯科爾算法，掌握完全二叉樹的性質(zhì)和算術(shù)表達(dá)式的二元位置樹的表示法和三種遍歷方法，掌握樹的應(yīng)用。3.教學(xué)重點(diǎn)、難點(diǎn)：求最大匹配的匈牙利算法，求最小生成樹的卡魯斯科爾算法，算術(shù)表達(dá)式的二叉樹表示法和波蘭式和逆波蘭式第十章關(guān)系1.基本內(nèi)容：二元關(guān)系，等價(jià)關(guān)系與等價(jià)類，序關(guān)系2.教學(xué)要求：理解二元關(guān)系的概念及其性質(zhì)；掌握二