《組合數(shù)學》教學大綱

《組合數(shù)學》教學大綱課程基本信息課程中文名稱：組合數(shù)學課程類別：專業(yè)選修課適用專業(yè)：數(shù)學與應(yīng)用數(shù)學、計算機專業(yè)課程地位：專業(yè)選修課總學時：30學時總學分：27、先修課程：數(shù)學分析、微分方程、高等代數(shù)課程目標1、組合數(shù)學是計算機應(yīng)用領(lǐng)域中十分重要的基礎(chǔ)理論課程，是計算機應(yīng)用技術(shù)研究生的學位專業(yè)基礎(chǔ)課。學習該課程的主要目的是使學生掌握組合數(shù)學的理論、技術(shù)和方法。應(yīng)用組合數(shù)學方法解決實際工作中的計算機應(yīng)用問題。組合數(shù)學是一門提高思維分析能力和自我構(gòu)造算法本領(lǐng)的必修課程。2、通過組合數(shù)學這門課程的學習，可以有效地鍛煉學生的論證能力，培養(yǎng)學生用組合學的思想和方法分析問題和解決問題的能力。使學生能得到嚴格的邏輯推理與抽象思維能力的訓練，建立數(shù)學模型與計算機科學實踐之間的內(nèi)在聯(lián)系，不僅可以提高專業(yè)開發(fā)能力，而且為計算機教育打好數(shù)學基礎(chǔ)。通過本課程的學習，應(yīng)達到知識和能力兩方面的目標：(1)知識方面：系統(tǒng)地學習組合數(shù)學中的排列與組合、容斥原理及其應(yīng)用、遞歸關(guān)系、生成函數(shù)、整數(shù)的分拆、鴿巢原理和定理、二分圖問題和組合設(shè)計。為解決實際問題，提高計算機專業(yè)開發(fā)能力打好知識基礎(chǔ)。(2)能力方面：使學生能得到組合數(shù)學的思想、方法和理論嚴格的邏輯推理與抽象思維能力的訓練，了解數(shù)學中的抽象思維與計算機科學實踐之間的內(nèi)在聯(lián)系，提高分析問題和解決問題的能力3、本課程開設(shè)時間比較靈活，總學時數(shù)為30學時。合問題中的一些應(yīng)用?！?.1鴿籠原理的簡單形式§2.2一般形式§2.3ramsey原理容斥原理（8學時）[教學目的與要求]所謂容斥原理是指在計數(shù)時，為了使重疊部分不被重復(fù)計算，人們研究出一種新的計數(shù)方法，這種方法的基本思想是：先不考慮重疊的情況，把包含于某內(nèi)容中的所有對象的數(shù)目先計算出來，然后再把計數(shù)時重復(fù)計算的數(shù)目排斥出去，使得計算的結(jié)果既無遺漏又無重復(fù)，這種計數(shù)的方法稱為容斥原理。本部分介紹了容斥原理和容斥原理的若干應(yīng)用。容斥原理是解決組合計數(shù)問題的一個重要工具，它研究的是有限個集合的并集形成的集合的計數(shù)的方法。本章內(nèi)容包括容斥原理一般公式、有重組合計數(shù)問題、錯位排列問題、帶禁止位、相對禁止位排列等復(fù)雜問題的計數(shù)。了解容斥原理的符號形式和一般形式，能熟練地把一些問題的計數(shù)轉(zhuǎn)化為應(yīng)用容斥原理來計數(shù)?！?.1容斥原理§3.2集合的R組合§3.3錯排問題§3.4相對位置上有限制的錯排問題母函數(shù)（10學時）[教學目的與要求]本章學習母函數(shù)的概念、性質(zhì)、表示法及母函數(shù)在排列組合中的應(yīng)用。本部分介紹普通生成函數(shù)及其應(yīng)用、指數(shù)生成函數(shù)及其應(yīng)用。使學生掌握利用常生成函數(shù)計算組合計數(shù)、利用指數(shù)生成函數(shù)計算排列計數(shù)的重要方法。本部分總的要求是：為何要引入生成函數(shù)，兩種生成函數(shù)及其應(yīng)用。概念清晰、準確?！?.1母函數(shù)的基本概念§4.2母函數(shù)的基本運算§4.3母函數(shù)在組合中的應(yīng)用§4.4整數(shù)的拆分四、教學方法理論教學五、課程考核考試六、教材與參考書教材：孫世新編《組合數(shù)學》（第三版）．電子科技大學出版社，2003。參考書目：1.《組合數(shù)學》，屈婉玲編，北京大學出版社,2.《組合數(shù)學引論》，孫淑玲編著,中國科學技術(shù)大學出版社.3.《組合數(shù)學及其算法》,楊振生編著,中國科學技術(shù)大學出版社。4.《組合數(shù)學》（第四版）盧開澄編著清華大學出版社2006年12月5.《組合數(shù)學》[美]R.A.Brualdi著馮舜璽等譯機械工業(yè)出版社2005年2月七、本課程的教學方式說明本課程的特點是理論性強，思想性強，與相關(guān)基礎(chǔ)課及專業(yè)課聯(lián)系較多，教學中應(yīng)注重啟發(fā)引導(dǎo)學生掌握重要概念的背景思想，理解重要概念的思想本質(zhì)，避免學生死記硬背。要善于將有關(guān)學科或生活中常遇到的名詞概念與組合數(shù)學的概念結(jié)合起來，使學生體會到學習組合數(shù)學的必要性。注重各教學環(huán)節(jié)（理論教學、習題課、作業(yè)、輔導(dǎo)參考）的有機聯(lián)系,特別是強化作業(yè)與輔導(dǎo)環(huán)節(jié)，使學生加深對課堂教學內(nèi)容的理解，提高分析解決問題的能力和運算能力。教學中有計劃有目的