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

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