組合數學及套用/ACM-ICPC程式設計系列

《組合數學及套用/ACM-ICPC程式設計系列》是2012年哈爾濱工業大學出版社出版的圖書，作者是周治國。

基本介紹

• 書名：組合數學及套用/ACM-ICPC程式設計系列
• 作者：周治國 
• ISBN：9787560332888
• 頁數：200頁
• 定價：26.80元
• 出版社：哈爾濱工業大學出版社
• 出版時間：2012-3

內容簡介

《ACM-ICPC程式設計系列:組合數學及套用》以程式設計思想和方法為主線，由淺入深地介紹組合數學的基礎知識，並以經典的ACM一ICPC競賽題目為例講解組合數學在競賽中的具體套用問題。全書共分6章，分別介紹了排列組合、母函式、容斥原理與鴿巢原理、群和P61ya定理、組合計數與編碼、線性規劃的基本知識及其套用。本書結合一些ACM-ICPC競賽的經典試題，以程式設計思想和方法為主線，介紹了ACM-ICPC中所需要的組合數學基礎知識和基本理論，重點地、系統地介紹和ACM-ICPC競賽密切相關的概念、定理以及算法。

圖書目錄

第1章 排列組合

1.1 排列與組合

1.2 兩個基本計數原理

1.2.1 加法原理

1.2.2 乘法原理

1.3 特殊排列組合

1.3.1 重複排列

1.3.2 重複組合

1.3.3 不全相異的全排列

1.3.4 圓周排列

1.4 排列的生成算法

1.4.1 序數法

1.4.2 字典序法

1.4.3 鄰位互換法

1.5 組合的生成

1.6 練習題

第2章 母函式

2.1 普通母函式

2.2 整數的拆分

2.3 Ferrers圖像

2.4 指數型母函式

2.5 遞推關係

2.6 斐波那契數列

2.7 Stirling數

2.8 Catalan數

2.9 練習題

第3章 容斥原理與鴿巢原理

3.1 容斥原理

3.1.1 De Morgan定理

3.1.2 容斥原理的定義

3.2 容斥原理的套用

3.2.1 錯排問題

3.2.2 棋盤多項式與有禁區的排列

3.3 Mobius反演定理

3.4 鴿巢原理

3.5 Ramsey數

3.5.1 Ramsey問題

3.5.2 Ramsey數

3.6 套用實例

3.7 練習題

第4章 群和Polya定理

4.1 等價關係、群與置換群

4.1.1 等價關係

4.1.2 群和置換群

4.2 循環與對換

4.3 Burnside引理

4.3.1 共扼類

4.3.2 k不動置換類和等價類

4.3.3 Burnside引理

4.4 Polya定理

4.5 Polya定理套用舉例

4.6 練習題

第5章 組合計數與編碼

5.1 均衡不完全區組設計

5.1.1 均衡不完全區組設計

5.1.2 基本性質

5.1.3 由對稱BIBD構造BIBD

5.2 拉丁方

5.2.1 拉丁方的定義

5.2.2 拉丁方的構造

5.2.3 正交拉丁方

5.3 Hadamard矩陣

5.3.1 Hadamard矩陣

5.3.2 由Hadamard矩陣構造SBIBD（4t-1，2t-1，t-1）

5.4 編碼理論基礎

5.4.1 基本概念

5.4.2 Hamming碼

5.5 套用實例

5.6 練習題

第6章 線性規劃

6.1 線性規劃問題及其表示

6.1.1 線性規劃問題

6.1.2 線性規劃問題的一般形式

6.1.3 線性規劃問題的標準形式

6.1.4 一般形式向標準形式的轉化

6.2 單純性算法

6.2.1 鬆弛變數技術

6.2.2 線性規劃定理

6.2.3 單純性算法

6.2.4 特殊情況的處理

6.2.5 算法流程

6.2.6 算法實現

6.3 練習題

附錄：參考程式

參考文獻