《離散數(shù)學》教學大綱
課程名稱：
| 離散數(shù)學
| 離散數(shù)學
| 離散數(shù)學
|
課程編號：
| 408008
| 420008
| 436008
|
適用專業(yè)：
| 計算機科學與技術(shù)
| 網(wǎng)絡(luò)工程
| 軟件工程
|
課程類別：
| 專業(yè)必修課
| 專業(yè)必修課
| 專業(yè)必修課
|
課程學分：
| 3
| 3
| 3
|
總學時：
| 54
| 54
| 54
|
其中：理論學時
| 54
| 54
| 54
|
實驗學時
| 0
| 0
| 0
|
先修課程：
| 高等數(shù)學、線性代數(shù)
|
一、課程的性質(zhì)、目的與任務(wù)
離散數(shù)學是現(xiàn)代數(shù)學的一個重要分支。離散數(shù)學用數(shù)學語言來描述離散系統(tǒng)的狀態(tài)、關(guān)系和變化過程，是計算機科學與技術(shù)的形式化描述語言，也是進行數(shù)量分析和邏輯推理的工具。離散數(shù)學為計算機科學和技術(shù)的發(fā)展奠定了重要的數(shù)學基礎(chǔ)，其基本思想、概念和方法廣泛滲透到計算機科學和技術(shù)的各個領(lǐng)域。
離散數(shù)學是計算機科學及相關(guān)學科的一門非常重要的專業(yè)基礎(chǔ)課。教學的目的是進一步提高學生的抽象思維和邏輯推理能力，為從事計算機的應用提供必要的描述工具和理論基礎(chǔ),并為后續(xù)課程的學習打下良好的基礎(chǔ)。
通過本課程的學習，要求學生：
1.理解命題邏輯、一階邏輯、關(guān)系、圖所包含的基本概念
2.理解研究對象所具有的性質(zhì)和相互關(guān)系
3.掌握各種典型的論證推理方法
4.在抽象思維和邏輯推理能力上有較好提高
二、課程基本內(nèi)容與要求
第一章命題邏輯
（一）教學內(nèi)容：
1.1命題與聯(lián)結(jié)詞
1.2命題公式與賦值
1.3等值演算
1.4析取范式與合取范式
1.5命題邏輯的推理理論
（二）教學要求：
教學目的：了解命題和五種聯(lián)結(jié)詞的概念，熟練掌握用五重聯(lián)結(jié)詞將復合命題符號化的方法；理解合式公式，成真和成假賦值以及公式的類型等概念，熟練掌握求真值表和判定公式類型的方法；了解等值式的概念，掌握置換定理的簡單應用，熟記24個重要等值式并熟練掌握它們的應用；熟練掌握求主析取范式和主合取范式的方法及主范式的應用；了解推理、前提、有效結(jié)論、證明的概念，理解推理的形式結(jié)熟練掌握；掌握判斷推理是否正確的方法，熟練掌握用已知的推理規(guī)則構(gòu)造證明的方法。
教學重點：命題公式與賦值，等值演算，析取與合取范式，命題邏輯的推理理論。
教學難點：主析取與主合取范式的應用，用已知的推理規(guī)則構(gòu)造證明的方法。
第二章 一階邏輯
（一）教學內(nèi)容：
2.1一階邏輯的基本概念
2.2一階邏輯公式及解釋
2.3一階邏輯等值式與前束范式
2.4一階邏輯推理理論。
（二）教學要求：
教學目的：了解個體詞、謂詞、量詞的概念。理解指定個體域與全總個體域的概念；掌握命題在全總個體域或指定個體域的符號化形式；了解合式公式、轄域、自由與約束出現(xiàn)、閉式與代換實例等概念，掌握換名規(guī)則、代換規(guī)則的應用；理解解釋的組成及公式類型，掌握在給定解釋下判斷公式真值的方法；熟練掌握求已知公式的前束范式的方法；熟練掌握在一階邏輯中構(gòu)造推理證明的方法。
教學重點：一階邏輯公式及解釋，一階邏輯等值式與前束范式，一階邏輯推理理論。
教學難點：一階邏輯公式解釋，一階邏輯前束范式，一階邏輯推理理論。
第三章集合的基本概念和運算
（一）教學內(nèi)容：
3.1集合的基本概念
3.2集合的基本運算
3.3集合恒等式
3.4有窮集合的計數(shù)。
（二）教學要求：
教學目的：理解元素與集合的隸屬關(guān)系、集合之間的包含、相等、不等、真包含關(guān)系，掌握集合的表示方法；熟練掌握集合的基本運算；掌握證明簡單的集合恒等式或包含關(guān)系的方法；掌握有窮集合的計數(shù)問題。
教學重點：集合的基本概念和運算，集合元素中的計數(shù)問題。
教學難點：冪集、有窮集合的計數(shù)。
第4章二元關(guān)系和函數(shù)
（一）教學內(nèi)容：
4.1集合的笛卡爾積與二元關(guān)系
4.2關(guān)系的運算
4.3關(guān)系的性質(zhì)
4.4關(guān)系的閉包
4.5等價關(guān)系與偏序關(guān)系
4.6函數(shù)的定義和性質(zhì)
4.7函數(shù)的復合和反函數(shù)。
（二）教學要求：
教學目的：了解有序?qū)?、二元關(guān)系、集合A到B的關(guān)系、集合A上的關(guān)系的定義，掌握笛卡兒積的運算和性質(zhì)；熟練掌握關(guān)系表達式、關(guān)系矩陣、關(guān)系圖的表示法；掌握關(guān)系的定義域只值域、逆、復合、冪的計算方法；理解自反、對稱、傳遞閉包的概念并能求出給定集合上關(guān)系的閉包；深刻理解等價關(guān)系、等價類、商集、劃分、偏序關(guān)系、偏序集、哈斯圖、偏序集中的特定元素概念，并能熟練求出等價關(guān)系的等價類、商集、偏序關(guān)系的哈斯圖及特定元素；理解函數(shù)、集合到的函數(shù)、函數(shù)的像的概念，、熟練掌握判斷函數(shù)單射、滿射、雙射的方法。會構(gòu)造雙射函數(shù)。會求復合函數(shù)和雙射函數(shù)的反函數(shù)。
教學重點：二元關(guān)系的運算，關(guān)系的閉包、等價關(guān)系與偏序關(guān)系，函數(shù)的復合和反函數(shù)。
教學難點：等價關(guān)系與偏序關(guān)系
第七章圖的基本概念
（一）教學內(nèi)容：
7.1無向圖及有向圖
7.2通路、回路和圖的連圖性
7.3圖的矩陣表示。
（二）教學要求：
教學目的：了解無向圖與有向圖的定義、頂點的度數(shù)等概念；理解零圖、平凡圖、簡單圖、完全圖、正則圖、子圖、補圖、圖的同構(gòu)等概念；熟練掌握握手定理及應用；理解通路與回路、簡單通路、簡單回路、初級通路、初級回路（圈）、無向圖頂點間的連通、有向圖頂點間的可達等概念；理解無向連通圖、連通分支、點割集、割點、邊割集、橋等概念；掌握求短程線與距離的方法。熟練掌握判斷通路與回路類型的方法；深刻理解n階有向圖的鄰接矩陣和可達矩陣的定義，熟練掌握通過鄰接矩陣求頂點間長度為k的通路數(shù)、回路數(shù)以及圖中長度為k的通路和回路數(shù)的方法。
教學重點：圖的基本概念，通路、回路和圖的連通性，圖的矩陣表示。
教學難點：圖的同構(gòu)，點連通度、邊連通度，鄰接矩陣的應用。
第八章樹
（一）教學內(nèi)容：
8.1無向樹
8.2根樹與應用。
（二）教學要求：
教學目的：了解無向樹、分支點、有向樹、根樹、根子樹等概念；掌握求對應于生成樹的基本回路和基本割集的方法；熟練掌握利用無向樹的性質(zhì)及握手定理求頂點度數(shù)的方法；熟練掌握用閉圈法求最小生成樹的方法；熟練掌握用算法求最優(yōu)樹、最佳前綴碼的方法。
教學重點：無向樹、根樹及其應用。
教學難點：求最優(yōu)樹、最佳前綴碼的方法。
第九章 二部圖、歐拉圖、哈密頓圖
（一）教學內(nèi)容：
9.1二部圖
9.2歐拉圖
9.3哈密頓圖
（二）教學要求：
教學目的：理解二部圖的判別定理，會用二部圖描敘某些實際問題；理解歐拉通路、回路和歐拉圖的概念，熟練掌握判定歐拉圖的方法；理解哈密頓通路、回路和哈密頓圖的概念，會判斷某些圖是或不是哈密頓圖。
教學重點：二部圖，二部圖中的匹配，歐拉圖，哈密頓圖。
教學難點：二部圖中的匹配，尋找哈密頓通路
三、課程各章節(jié)學時分配
序號
| 內(nèi)容
| 理論學時
|
計科
| 網(wǎng)工
| 軟工
|
1
| 命題邏輯
| 12
| 12
| 12
|
2
| 一階邏輯
| 8
| 8
| 8
|
3
| 集合的基本概念和運算
| 2
| 2
| 2
|
4
| 二元關(guān)系和函數(shù)
| 14
| 14
| 14
|
5
| 圖的基本概念
| 8
| 8
| 8
|
6
| 樹
| 4
| 4
| 4
|
7
| 二部圖、歐拉圖、哈密頓圖
| 6
| 6
| 6
|
合計
| 54
| 54
| 54
|
四、本課程課外學習與修學指導
由于該課程概念多且較為抽象，內(nèi)容多且較為零散，所以要學好本課程，要求學生多參閱相關(guān)書籍，做好預習，多做練習，掌握離散數(shù)學的基本慨念、基本理論和基本方法。
五、本課程成績的考查方法及評定標準
考核方式：閉卷考試
成績評定標準：本課程的考核是平時成績和期終考試成績相結(jié)合，平時成績的評定包括作業(yè)、出勤兩部分，平時成績占課程考核成績的30%，期末考試成績占課程考核成績的70%。
其中期未考試總分100分，基礎(chǔ)題占50%，中等難度題占40%，較難題占10%。考試題型主要有：判斷題、選擇題、填空題、簡答題、計算題、證明題、綜合應用題等。
六、教材及參考書
教材：《離散數(shù)學》，耿素云，屈婉玲編著，北京大學出版社，2002年
主要參考書：
[1]《離散數(shù)學》，劉愛民著，北京郵電大學出版社.
[2]《離散數(shù)學》，邵學才著，清華大學出版社.
[3]《離散數(shù)學》，左孝凌著，上?？萍汲霭嫔绯霭?
[4]《離散數(shù)學》，劉任任主編，中南大學出版社，2005年.
大綱撰寫人：楊麗英
大綱審閱人：袁輝勇
教學副主任：易葉青
編寫日期：2012年6月15日
