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

《離散數(shù)學(xué)》課程教學(xué)大綱課程編號:02700013課程名稱：離散數(shù)學(xué)英文名稱：DiscreteMathematics課程類型:專業(yè)基礎(chǔ)課總學(xué)時：108講課學(xué)時：108實(shí)驗(yàn)學(xué)時：0學(xué)分：5適用對象:計算機(jī)科學(xué)與技術(shù)專業(yè)先修課程：高等數(shù)學(xué)、線性代數(shù)等一、課程簡介離散數(shù)學(xué)是研究離散量的結(jié)構(gòu)及其相互關(guān)系的數(shù)學(xué)學(xué)科，是現(xiàn)代數(shù)學(xué)的一個重要分支。它在各學(xué)科領(lǐng)域，特別在計算機(jī)科學(xué)與技術(shù)領(lǐng)域有著廣泛的應(yīng)用，同時離散數(shù)學(xué)也是計算機(jī)科學(xué)的許多專業(yè)課程，如程序設(shè)計語言、數(shù)據(jù)結(jié)構(gòu)、操作系統(tǒng)、編譯技術(shù)、人工智能、數(shù)據(jù)庫、算法設(shè)計與分析、理論計算機(jī)科學(xué)基礎(chǔ)等必不可少的先行課程。通過離散數(shù)學(xué)的學(xué)習(xí)，不但可以掌握處理離散結(jié)構(gòu)的描述工具和方法，為后續(xù)課程的學(xué)習(xí)創(chuàng)造條件，而且離散數(shù)學(xué)所提供的訓(xùn)練可以幫助學(xué)生提高抽象思維能力和邏輯推理能力，有益于學(xué)生嚴(yán)謹(jǐn)、完整、規(guī)范的科學(xué)態(tài)度的培養(yǎng)。為將來參與創(chuàng)新性的研究和開發(fā)工作打下堅實(shí)的基礎(chǔ)。二、課程性質(zhì)、目的和任務(wù)1.性質(zhì):本課程是為計算機(jī)專業(yè)本科開設(shè)的專業(yè)基礎(chǔ)課。2.目的:《離散數(shù)學(xué)》以研究離散量的結(jié)構(gòu)和相互之間的關(guān)系為主要目標(biāo)，在信息處理技術(shù)、計算機(jī)軟硬件的設(shè)計等領(lǐng)域都有著廣泛應(yīng)用。3.任務(wù):通過這門課程的學(xué)習(xí)，要使學(xué)生掌握離散數(shù)學(xué)的基本概念和基本原理，以現(xiàn)代數(shù)學(xué)的方法，初步掌握處理離散結(jié)構(gòu)所必須的一些基本數(shù)學(xué)工具和方法。同時，也要培養(yǎng)學(xué)生抽象思維、邏輯推理，符號演算和慎密概括的能力，從而使學(xué)生具有良好的專業(yè)理論素質(zhì)，提高學(xué)生分析和解決實(shí)際問題的能力。三、教學(xué)基本要求通過本課程的學(xué)習(xí)，使學(xué)生了解和掌握關(guān)于離散量的基本概念及其相關(guān)理論，為后繼課程的學(xué)習(xí)作必要的理論準(zhǔn)備?；疽螅海?）學(xué)習(xí)數(shù)理邏輯最基本的內(nèi)容，掌握命題邏輯及謂詞邏輯的基本概念，掌握命題演算的方法，掌握命題推理及謂詞推理的基本理論，并會用推理理論進(jìn)行邏輯論證。（2）學(xué)習(xí)集合論的基本概念及性質(zhì)，掌握集合運(yùn)算及證明的基本理論和方法；學(xué)習(xí)二元關(guān)系的概念與性質(zhì)，掌握等價關(guān)系和偏序關(guān)系，并使學(xué)生從更高層次理解函數(shù)。（3）學(xué)習(xí)代數(shù)系統(tǒng)的基本知識，掌握二元運(yùn)算的定義和性質(zhì)，了解代數(shù)系統(tǒng)的子代數(shù)和積代數(shù)、同態(tài)與同構(gòu)等概念，掌握半群、幺半群、群、環(huán)、域和格、布爾代數(shù)等代數(shù)系統(tǒng)的定義及其性質(zhì)。（4）學(xué)習(xí)圖論的基本概念及其理論，主要掌握簡單圖和一些特殊圖的性質(zhì)，包括歐拉圖和哈密爾頓圖、二部圖、平面圖等。掌握樹的基本概念及其相關(guān)運(yùn)算。學(xué)會使用圖論方法解決具體問題。四、教學(xué)內(nèi)容及要求第一章命題邏輯教學(xué)內(nèi)容：命題符號化及聯(lián)結(jié)詞；命題公式及分類；等值演算；聯(lián)結(jié)詞全功能集；對偶與范式；推理理論。基本要求：(1)理解和掌握命題邏輯中的基本概念和基本方法。(2)掌握命題、命題聯(lián)結(jié)詞、命題公式的概念、自然語言的形式化方法。(3)掌握公式的真值、等值演算的計算方法，熟悉常用的等值式。(4)熟練掌握求主合取范式與主析取范式的方法，知道范式的用途。(5)能用各種方法判別公式的類型。(6)了解其它聯(lián)結(jié)詞和聯(lián)結(jié)詞全功能集、最小聯(lián)結(jié)詞組的概念。(7)掌握命題邏輯的推理規(guī)則和證明方法，能熟練運(yùn)用這些規(guī)則進(jìn)行命題演算的推理。重點(diǎn)與難點(diǎn)：命題聯(lián)結(jié)詞的正確使用；主析取范式的求法；用各種方法判斷公式的類型；推理理論。第二章一階邏輯教學(xué)內(nèi)容：一階邏輯基本概念；一階邏輯合式公式及解釋；一階邏輯等值式；一階邏輯推理理論?；疽螅?1)掌握個體詞、謂詞與量詞的概念，正確引入量詞、轄域，正確符號化一個具體的問題。(2)掌握約束變元與自由變元的概念。(3)掌握謂詞公式的定義、解釋、公式在解釋下的真值及謂詞公式的類型的判別。(4)熟悉常用的謂詞等值式。(5)熟練掌握前束范式的求法。(6)熟練掌握UG規(guī)則、UI規(guī)則、EG規(guī)則、EI規(guī)則，能進(jìn)行謂詞演算的推理。重點(diǎn)與難點(diǎn)：重點(diǎn)是個體詞、個體域、謂詞、量詞的概念和使用；公式的解釋的；公式在解釋下的真值；求公式的前束范式。謂詞邏輯的基本推理方法。難點(diǎn)是用謂詞、量詞、邏輯聯(lián)結(jié)詞描述一個簡單命題；用解釋的方法證明等價式和蘊(yùn)涵式；謂詞演算的推理理論。第三章集合的基本概念與運(yùn)算教學(xué)內(nèi)容：集合的基本概念；集合的基本運(yùn)算；集合中元素的計數(shù)?；疽螅?1)了解集合論的基本概念、集合的幾種表示方法。(2)掌握集合上的運(yùn)算（并、交、相對補(bǔ)、絕對補(bǔ)、對稱差、冪集、子集等）及相關(guān)定律。(3)能運(yùn)用文氏圖、包含排斥原理求解有窮集計數(shù)問題。重點(diǎn)與難點(diǎn)：集合的運(yùn)算；有窮集計數(shù)問題的解法。第四章二元關(guān)系和函數(shù)教學(xué)內(nèi)容：集合的笛卡爾積與二元關(guān)系；關(guān)系的運(yùn)算；關(guān)系的性質(zhì)；關(guān)系的閉包；等價關(guān)系和偏序關(guān)系；函數(shù)的定義與性質(zhì)；函數(shù)的復(fù)合和反函數(shù)?；疽螅?1)掌握n元組與笛卡兒積的概念、性質(zhì)。(2)掌握二元關(guān)系的概念及其表示方法。(3)掌握關(guān)系的運(yùn)算、性質(zhì)與閉包。(4)掌握等價關(guān)系與等價類的概念和性質(zhì)，了解集合的劃分。(5)掌握偏序關(guān)系的概念和性質(zhì)，會畫哈斯圖，能求極大（?。┰⒆畲螅ㄐ。┰?、上（下）界、上（下）確界。(6)掌握函數(shù)的定義、復(fù)合和反函數(shù)；掌握特殊函數(shù)類（滿射、單射、雙射，特征函數(shù)），了解逆函數(shù)、特征函數(shù)。重點(diǎn)與難點(diǎn)：重點(diǎn)是二元關(guān)系的性質(zhì)；等價關(guān)系和偏序關(guān)系的性質(zhì)；難點(diǎn)是等價關(guān)系與等價類。第五章代數(shù)系統(tǒng)的一般性質(zhì)教學(xué)內(nèi)容：二元運(yùn)算及其性質(zhì)；代數(shù)系統(tǒng)及其子代數(shù)與積代數(shù)；代數(shù)系統(tǒng)的同態(tài)與同構(gòu)?；疽螅?1)熟練掌握二元運(yùn)算的定義和性質(zhì)，會判斷一元和二元運(yùn)算，指出其具有的性質(zhì)和它的特異元素。(2)了解代數(shù)系統(tǒng)的子代數(shù)和積代數(shù)、同態(tài)與同構(gòu)等概念。重點(diǎn)與難點(diǎn)：二元運(yùn)算的性質(zhì)和特異元素。第六章幾個典型的代數(shù)系統(tǒng)教學(xué)內(nèi)容：半群與群；環(huán)與域；格與布爾代數(shù)?；疽螅?1)掌握半群、獨(dú)異點(diǎn)和群的基本概念和性質(zhì)。掌握子群的判定，了解循環(huán)群和置換群。(2)掌握環(huán)和域的定義，了解環(huán)和域的性質(zhì)。(3)深刻理解和掌握格的概念和性質(zhì)，了解幾類特殊的格（有界格、有補(bǔ)格、分配格）。(4)掌握布爾代數(shù)的概念和運(yùn)算性質(zhì)及其相關(guān)理論。(5)能夠判斷給定的集合和運(yùn)算可構(gòu)成哪一類代數(shù)系統(tǒng)。重點(diǎn)與難點(diǎn)：代數(shù)系統(tǒng)的判別；格與布爾代數(shù)的基本概念和基本運(yùn)算。第七章圖的基本概念教學(xué)內(nèi)容：無向圖及有向圖；通路、回路、圖的連通性；圖的矩陣表示；最短路徑及關(guān)鍵路徑?；疽螅?1)深刻理解和掌握圖的基本概念和表示。（包括無向圖和有向圖的定義、子圖、補(bǔ)圖、圖的運(yùn)算、結(jié)點(diǎn)的次數(shù)、圖的同構(gòu)等基本概念）。(2)會畫階數(shù)較小的所有非同構(gòu)的圖。(3)掌握圖的路徑和回路、圖的連通性、點(diǎn)割集、邊割集的概念。(4)了解圖的矩陣表示，掌握有向圖的鄰接矩陣。(5)掌握圖的兩個應(yīng)用：最短路徑和關(guān)鍵路徑。重點(diǎn)與難點(diǎn)：重點(diǎn)是圖的一些基本概念。難點(diǎn)是圖的同構(gòu)。第八章一些特殊的圖教學(xué)內(nèi)容：二部圖；歐拉圖；哈密爾頓圖；平面圖?；疽螅?1)掌握二部圖的定義和判斷方法。(2)掌握歐拉圖與哈密頓圖的定義和判斷方法，并會畫圖。(3)掌握平面圖的定義和判斷條件，會畫平面圖的對偶圖。重點(diǎn)與難點(diǎn)：各種圖的判別。第九章樹教學(xué)內(nèi)容：無向樹及生成樹；根樹及其應(yīng)用。基本要求：(1)掌握樹的幾種等價定義和定理,掌握生成樹、最小生成樹的定義及生成方法，掌握基本回路和基本割集的定義和求法。(2)掌握有向樹、最優(yōu)樹，了解樹的應(yīng)用，并能解決一些具體問題。重點(diǎn)與難點(diǎn)：樹與根樹的概念及其應(yīng)用。五、實(shí)踐環(huán)節(jié)六、課外習(xí)題及課程討論1.為慶祝九七香港回歸祖國，四支足球隊進(jìn)行比賽，已知情況如下，問結(jié)論是否有效?前提:(1)若A隊得第一，則B隊或C隊獲亞軍;若C隊獲亞軍，則A隊不能獲冠軍;若D隊獲亞軍，則B隊不能獲亞軍;A隊獲第一;結(jié)論:D隊不是亞軍。2.設(shè)A={1,2,…,10}。下列哪個是A的劃分？若是劃分，則它們誘導(dǎo)的等價關(guān)系是什么？（1）B={{1,3,6},{2,8,10},{4,5,7}};（2）C={{1,5,7},{2,4,8,9},{3,5,6,10}};（3）D={{1,2,7},{3,5,10},{4,6,8},{9}}3.設(shè)<G，*>是群，H和K都是G的子群，令HK={h*s|s∈K，h∈H},KH={s*h|s∈K,h∈H},<HK,*>，<KH,*>是G的子群的充分必要條件是HK=KH。4.設(shè)<S,,⊙,′,0,1>是一布爾代數(shù)，則關(guān)系={<a,b>|a⊙b=a}是S上的偏序關(guān)系。5.一次會議有20人參加，其中每個人都在其中有不下10個朋友。這20人圍成一圓桌入席，有沒有可能使任意相鄰而坐的兩個人都是朋友？為什么？七、教學(xué)方法與手段離散數(shù)學(xué)課程內(nèi)容較抽象，因此教學(xué)方式以課堂講授為主，課堂精講與自學(xué)相結(jié)合。廣泛開展啟發(fā)式、發(fā)現(xiàn)式等教學(xué)方法，理論聯(lián)系實(shí)際，對教學(xué)中普遍存在的疑難點(diǎn)開設(shè)專題討論課、習(xí)題課。課后有書面作業(yè)，通過學(xué)校網(wǎng)絡(luò)教學(xué)平臺發(fā)布課程信息進(jìn)行師生交流。八、各教學(xué)環(huán)節(jié)學(xué)時分配章節(jié)講課習(xí)題課討論課實(shí)驗(yàn)其他合計第一章命題邏輯14100116第二章一階邏輯10100112第三章集合的基本概念與運(yùn)算8100110第四章二元關(guān)系和函數(shù)16100118第五章代數(shù)系統(tǒng)的一般性質(zhì)8100110第六章幾個典型的代數(shù)系統(tǒng)8100110第七章圖的基本概念10100112第八章一些特殊的圖10100112第九章樹610018合計909009108九、考核方式考核方式為考試。嚴(yán)格考核學(xué)生出勤情況，達(dá)到學(xué)記管理的曠課量取消考試資格。綜合成績根據(jù)平時成績和期末成績評定，平時成績占30％，期末成績占70％。十