組合數(shù)學

前言

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

內容概要

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

書籍目錄

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

圖書封面

圖書標簽Tags

無

評論、評分、閱讀與下載

---

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

---