組合數(shù)學(xué)

前言

　　本書根據(jù)作者多年講授研究生和高年級本，干斗生“組合數(shù)學(xué)”課程的教學(xué)筆記整理編撰而成。其中，主要內(nèi)容取自作者1991年所編《組合數(shù)學(xué)》講義。結(jié)合多年來在教學(xué)工作中積累的素材和現(xiàn)階段形勢發(fā)展對“組合數(shù)學(xué)”課程的新要求，在書中對原講義的內(nèi)容作了較大幅度調(diào)整，去掉了半群、范疇等章節(jié)，增加了遞歸關(guān)系、組合設(shè)計及編碼、組合算法與計算復(fù)雜性等章節(jié)，并對原講義中有些章節(jié)的內(nèi)容作了許多擴(kuò)充，補(bǔ)充了各章的習(xí)題。　　為了保持全書獨(dú)立性，對“離散數(shù)學(xué)”等先驅(qū)課程中的基本概念和術(shù)語在各章節(jié)中使用之前都有簡要說明。書中所用符號和術(shù)語力求保持與“離散數(shù)學(xué)”的習(xí)慣用法一致。其中，對最基本的邏輯符號合取“^”、析取“V”、推導(dǎo)（永真蘊(yùn)涵）、等價及集合運(yùn)算符交“n”、并“U”等常用符號的含義和用法不再進(jìn)一步解釋，直接引用?！　∮嬎銠C(jī)科學(xué)中包含著大量組合數(shù)學(xué)的知識。由于教學(xué)和應(yīng)用的需要，組合數(shù)學(xué)已成為計算機(jī)學(xué)科及與信息有關(guān)學(xué)科的基礎(chǔ)理論課程。本書涉及組合分析、圖論、抽象代數(shù)、編碼理論、組合算法及算法復(fù)雜性等組合數(shù)學(xué)的幾乎全部內(nèi)容。所選內(nèi)容基本符合《同等學(xué)歷人員申請碩士學(xué)位計算機(jī)科學(xué)與技術(shù)學(xué)科綜合水平全國統(tǒng)一考試大綱及指南》中“組合數(shù)學(xué)”的考試大綱要求。關(guān)于部分線性規(guī)劃問題，一并納入組合算法統(tǒng)一討論?！　∪珪卜职苏隆５谝徽聰?shù)論基礎(chǔ)是通讀全書的預(yù)備知識，內(nèi)容主要取自參考文獻(xiàn)[1]。其中，同余式的一般性討論是新增加部分。第二章基本計數(shù)原理，包括加法原理、乘法原理、鴿巢原理，以及排列與組合及其進(jìn)一步討論和應(yīng)用；對集合元素計數(shù)的容斥原理及應(yīng)用，因篇幅和技術(shù)處理上的需要，特別安排在第四章反演公式中，作為篩法公式的特殊情況給出。第三章對由Laplace和Euler提出的生成函數(shù)方法進(jìn)行了全面討論。第四章是反演公式，該章起點(diǎn)較高，逐漸演繹，最后給出了若干具體應(yīng)用，部分內(nèi)容請參考文獻(xiàn)[3]。第五章系統(tǒng)討論了遞歸關(guān)系，主要參考文獻(xiàn)[6]。第六章除增加了部分例題之外，基本保持原講義風(fēng)貌，主要介紹了群及幾個與計數(shù)有關(guān)的定理：Lagrange定理、Burnside定理、Polya一定理及其應(yīng)用。第七章組合設(shè)計及編碼，簡要介紹了相異及公共代表組，對均衡不完全區(qū)組的設(shè)計、正交拉丁方、Hadmard矩陣也有部分論述；最后給出了有關(guān)編碼、譯碼的基本理論。該章內(nèi)容主要參閱本書參考文獻(xiàn)[4]。第八章組合算法與計算模型，主要介紹一些經(jīng)典的組合算法設(shè)計技術(shù)及優(yōu)化問題的解決方法，并特別討論了計算模型Turing機(jī)，P及NP類語言和算法復(fù)雜性等計算機(jī)科學(xué)中核心而重要的課題；該章參考文獻(xiàn)為[5]、[6]和[8]。

內(nèi)容概要

隨著現(xiàn)代科學(xué)技術(shù)的發(fā)展，組合數(shù)學(xué)的應(yīng)用日趨廣泛。本書作者1991年所編《組合數(shù)學(xué)》講義為基礎(chǔ)，并結(jié)合多年來的教學(xué)實(shí)踐經(jīng)驗(yàn)編撰而成。全書比較完整地闡述了組合數(shù)學(xué)的基本理論。
    全書共8章。第一章介紹數(shù)論基礎(chǔ)知識，為讀者通讀全書做一些準(zhǔn)備工作；第二章是組合計數(shù)方面的經(jīng)典內(nèi)容，包括基本計數(shù)原理、鴿巢原理、Ramsey定理及排列與組合等；第三章詳細(xì)討論了生成函數(shù)技術(shù)及其應(yīng)用；第四章反演公式和第五章遞歸關(guān)系是組合數(shù)學(xué)中深入、關(guān)鍵的技術(shù)和方法；第六章通過對群的討論，引出了著名的Lagrange定理、Burnside定理和Polya定理；第七章概要闡述了組合設(shè)計與編碼理論基礎(chǔ)；第八章主要介紹了組合算法的設(shè)計和優(yōu)化問題的處理方法，并簡要介紹了計算模型Turing機(jī)、P問題、NP問題與計算復(fù)雜性及其相互關(guān)系。
    全書理論結(jié)合實(shí)際，部分章節(jié)由淺入深，形成歸納；部分章節(jié)綜合概括，以高起點(diǎn)結(jié)論推出若干應(yīng)用結(jié)果。為了鞏固概念，每章最后均有適當(dāng)數(shù)量習(xí)題。書中文字?jǐn)⑹錾鷦樱瑢?shí)例豐富，注意啟發(fā)性的同時又考慮了提高總結(jié)。

書籍目錄

1，數(shù)論基礎(chǔ)
2，基本計數(shù)原理
3，生成函數(shù)
4，反演公式
5，遞歸關(guān)系
6，群
7，組合設(shè)計及編碼
8，組合算法與計算復(fù)雜性

圖書封面

圖書標(biāo)簽Tags

無

評論、評分、閱讀與下載

---

    組合數(shù)學(xué) PDF格式下載

---