組合數(shù)學及其應用課程學習指南

1、組合數(shù)學及其應用課程學習指南Combinatorics wipplications課程（任課教師）1. 教師簡介：，博士，2007 年畢業(yè)于中國傳媒大學通信與信息系統(tǒng)專業(yè)，或工學博士學位。2007 年 7 月至今，任教于中國傳媒大學計算機學院，主要從事組合優(yōu)化、圖論、圖形學等方面的。：2.電子郵箱：辦公：65783453課程基本信息：選修課程課程編碼：課程名稱：組合數(shù)學及其應用英文名稱：Combinatorics wipplications授課對象：計算機應用技術專業(yè)、計算機與理論專業(yè) 2010 級開課學期：第一學年春季學期（第 2 學期）開間：具體時間參考培養(yǎng)方案和上間：具體時間參考培養(yǎng)方案

2、和院網(wǎng)上課表院網(wǎng)上課表上課地點：具體時間參考培養(yǎng)方案和院網(wǎng)上課表學分/學時：2/32先修課程：高等數(shù)學、線性代數(shù)注： 上間和地點以院網(wǎng)上課表為準課程簡介：教學目標：組合數(shù)學是一門應用廣泛的學科。它在計算機科學、信息論、管理科學以及其它現(xiàn)代科技領域都有著重要的應用。本課程主要介紹組合數(shù)學中涉及組合計數(shù)、組合設計和編碼理論的基本原理、基本問題和基本方法。通過該課程的學習，使學生了解和掌握組合數(shù)學的基本內(nèi)容和基本方法，培養(yǎng)學生的應用意識，為學生在今后的教學或科研活動中可能的應用作準備。教學方式：1. 本課程以教師講授為主，學生聯(lián)系練習等相結合的方式進行；考核方式：1. 課后作業(yè)、出勤，占總評成績的

3、30。2. 期末作業(yè)：教師提供一套題，學生提交紙質版答卷以及“課程作業(yè)提交單”，占總評成績的 70。3. 教師在收到作業(yè)后兩周內(nèi)，給學生反饋“課程作業(yè)提交單”。組合數(shù)學是計算機出現(xiàn)以后迅速發(fā)展起來的一門數(shù)學分支。組合數(shù)學不僅在基礎數(shù)學中具有極其重要的地位，在其它的學科中也有重要的應用，如計算機科學、編碼和學、物理、化學、生物等學科中均有重要應用。本課程主要介紹組合數(shù)學中涉及組合計數(shù)、組合設計和編碼理論的基本原理、基本問題和基本方法，主要包括：排列與組合、母函數(shù)與遞推關系、容斥原理、反演公式、鴿巢原理、Plya 計數(shù)定理、區(qū)組設計與編碼理論等內(nèi)容。4. 期末提交時間：6 月 30 日提交地點：

4、綜合樓 5035.教學內(nèi)容及時間安排：重點內(nèi)容：4. 1 鴿巢原理4. 2 鴿巢原理的推廣形式4. 3 Ramsey 數(shù)4. 4 Ramsey 數(shù)的性質4. 5 Ramsey 定理第三章 容斥原理 (4 學時)重點內(nèi)容：3. 1 容斥原理3. 2 錯位排列3. 3 有限制的排列第四章 鴿巢原理 （4 學時）重點內(nèi)容：2. 1 兩個基本計數(shù)原理2. 2 排列生成算法2. 3 組合生成算法2. 4 應用舉例重點內(nèi)容：1.1 組合數(shù)學的對象1.2 組合問題典型實例第二章 排列與組合 （4 學時）第一章 引論 （2 學時）第五章 母函數(shù) （4 學時）重點內(nèi)容：5. 1母函數(shù)概念5. 2冪級數(shù)型母函數(shù)5

5、. 3整數(shù)的拆分第六章 遞歸關系 (3 學時)重點內(nèi)容：6. 1 幾個典型的遞歸關系6. 2 用母函數(shù)方法求解遞歸關系6. 3 Stirling 數(shù)第七章 Polya 定理 （3 學時）重點內(nèi)容：7. 1 群的基本概念7. 2 Burnside 引理7. 3 Polya 定理第八章 圖論基礎 （2 學時）重點內(nèi)容：8. 1 圖的基本概念8. 2 Euler 圖與 Hamilton 圖8. 3平面圖. 對偶圖與色數(shù)8. 4匹配理論8. 5網(wǎng)絡流第九章 拉丁方與區(qū)組設計 （2 學時）重點內(nèi)容：9. 1 拉丁方9. 2 完全區(qū)組設計9. 3 區(qū)組設計的構造第十章 線性規(guī)劃 （2 學時）重點內(nèi)容：10

6、. 1 LP 問題10. 2 單純形法第十一章 組合優(yōu)化算法與計算的時間復雜度理論（2 學時）1澄，盧華明編著組合數(shù)學（第三版），20032著組合數(shù)學(英文版.第 5 版) 機械工業(yè)， 20093，Alan Tucke 著應用組合數(shù)學(第 5 版) 人民郵電， 20094等編著組合理論及其應用，2005重點內(nèi)容：11. 1 Dijkstra 算法11. 2 深度優(yōu)先搜索法-DFS 算法11. 3 好算法. 壞算法和 NP 類問題11. 4 貨郎問題的近似解作業(yè)每章課后均有練習建議著組合數(shù)學及其算法 中國科學技術大學，2003 年 4 月參考資料注： 從 2011 年級起，培養(yǎng)方案中每門專業(yè)課程須填寫“X課程學習指南”，而且有學院專業(yè)指導小組組長（成員）或學院學術成員，或學院教授成員（由學院確認）的簽字，否則