《程式設計中的組合數學》是2005年5月清華大學出版社出版的圖書，作者是孫賀。
基本介紹
- 中文名：程式設計中的組合數學
- 作者：孫賀
- 叢書名：ACM/ICPC國際大學生程式設計競賽
- 出版社：清華大學出版社
- ISBN：9787302108009
基本信息,圖書簡介,圖書目錄,
基本信息
ISBN：7302108005
開本：32開
頁碼：162
定價：￥19.00
圖書簡介
本書系統地介紹了與程式設計競賽有關的組合數學的基本理論和算法設計與分析的常用方法。全書共分8章，分別為：算法基礎、組合數學初探、排列與組合、容斥原理、母函式、擬陣、貪心算法和Pólya定理。本書突出組合數學算法的設計與最佳化，從而更便於參加程式設計競賽的讀者學習組合數學。
本書可作為ACM/ICPC國際大學生程式設計競賽和國際信息學奧林匹在競賽（IOI）的培訓教材，也可供從事組合數學與算法研究的人員參考。
圖書目錄
第1章 算法基礎
1.1 算法
1.2 時間複雜度與空間複雜度
1.3 P類與NP類
習題1
第2章 組合數學初探
2.1 組合數學的起源
2.2 組合數學的研究的問
習題2
第3章 排列與組合
3.1 基本概念
3.2 分拆與置換的表示
3.3 排列與組合的生成算法
3.4 購票問題
3.5 “方程的解”問題
習題3
第4章 容斥原理
4.1 基本概念
4.2 “被毀壞的玉米地”問題
問題4
第5章 母函式
5.1 普通型母函式
5.2 指數型母函式
5.3 質數分解問題
5.4 “紅色病毒”問題
5.5 “自共軛Ferrers圖”問題
5.6 常見組合計數方法之比較
5.7 NPC問題的代數化
習題5
第6章 擬陣
6.1 基本概念
6.2 擬陣的基本性質
6.3 擬陣與貪心算法
習題6
第7章 貪心算法
7.1 貪心算法的概念與特點
7.2 最佳瀏覽路線問題
7.3 貪心算法與近似計算
習題7
第8章 Pólya定理
8.1 群與置換群
8.2 Burnside引理
8.3 Pólya定理
習題8
附錄A 閱讀本書的預備知識
A1 集合論
A2 圖論
A3 初等數論
A4 級數
索引
參考文獻
