●章算法引論
1.1算法與程序
1.2表達算法的抽像機制
1.3描述算法
1.4算法復雜性分析
小結
習題
第2章遞歸與分治策略
2.1遞歸的概念
2.2分治法的基本思想
2.3二分搜索技術
2.4大整數的乘法
2.5Strassen矩陣乘法
2.6棋盤覆蓋
2.7合並排序
2.8快速排序
2.9線性時間選擇
2.10最接近點對問題
2.11循環賽日程表
小結
習題
第3章動態規劃
3.1矩陣連乘問題
3.2動態規劃算法的基本要素
3.3公共子序列
3.4凸多邊形很優三角剖分
3.5多邊形遊戲
3.6圖像壓縮
3.7電路布線
3.8流水作業調度
3.90-1背包問題
3.10很優二叉搜索樹
小結
習題
第4章貪心算法
4.1活動安排問題
4.2貪心算法的基本要素
4.2.1貪心選擇性質
4.2.2很優子結構性質
4.2.3貪心算法與動態規劃算法的差異
4.3很優裝載
4.4哈夫曼編碼
4.4.1前綴碼
4.4.2構造哈夫曼編碼
4.4.3哈夫曼算法的正確性
4.5單源最短路徑
4.5.1算法基本思想
4.5.2算法的正確性和計算復雜性
4.6最小生成樹
4.6.1最小生成樹性質
4.6.2Prim算法
4.6.3Kruskal算法
4.7多機調度問題
4.8貪心算法的理論基礎
4.8.1擬陣
4.8.2帶權擬陣的貪心算法
4.8.3任務時間表問題
小結
習題
第5章回溯法
5.1回溯法的算法框架
5.1.1問題的解空間
5.1.2回溯法的基本思想
5.1.3遞歸回溯
5.1.4迭代回溯
5.1.5子集樹與排列樹
5.2裝載問題
5.3批處理作業調度
5.4符號三角形問題
5.5n後問題
5.60-1背包問題
5.7優選團問題
5.8圖的m著色問題
5.9旅行售貨員問題
5.10圓排列問題
5.11電路板排列問題
5.12連續郵資問題
5.13回溯法的效率分析
小結
習題
第6章分支限界法
6.1分支限界法的基本思想
6.2單源最短路徑問題
6.3裝載問題
6.4布線問題
6.50-1背包問題
6.6優選團問題
6.7旅行售貨員問題
6.8電路板排列問題
6.9批處理作業調度
小結
習題
第7章概率算法
7.1隨機數
7.2數值概率算法
7.2.1用隨機投點法計算π值
7.2.2計算定積分
7.2.3解非線性方程組
7.3舍伍德算法
7.3.1線性時間選擇算法
7.3.2跳躍表
7.4拉斯維加斯算法
7.4.1n後問題
7.4.2整數因子分解
7.5蒙特卡羅算法
7.5.1蒙特卡羅算法的基本思想
7.5素問題
7.5.3素數測試
小結
習題
第8章NP接近性理論與近似算法
8.1P類與NP類問題
8.1.1非確定性圖靈機
8.1.2P類與NP類語言
8.1.3多項式時間驗證
8.2NP接近問題
8.2.1多項式時間變換
8.2.2Cook定理
8.3一些典型的NP接近問題
8.3.1合取範式的可滿足性問題
8.3合取範式的可滿足性問題
8.3.3團問題
8.3.4頂點覆蓋問題
8.3.5子集和問題
8.3.6哈密頓回路問題
8.3.7旅行售貨員問題
8.4近似算法的性能
8.5頂點覆蓋問題的近似算法
8.6旅行售貨員問題近似算法
8.6.1具有三角不等式性質的旅行售貨員問題
8.6.2一般的旅行售貨員問題
8.7集合覆蓋問題的近似算法
8.8子集和問題的近似算法
8.8.1子集和問題的指數時間算法
8.8.2子集和問題的接近多項式時間近似格式
小結
習題
第9章串與序列的算法
9.1子串搜索算法
9.1.1串的基本概念
9.1.2KMP算法
9.1.3Rabin-Karp算法
9.1.4多子串搜索與AC自動機
9.2後綴數組與公共子串
9.2.1後綴數組的基本概念
9.2.2構造後綴數組的倍前綴算法
9.2.3構造後綴數組的DC3分治法
9.2.4公共前綴數組與公共擴展算法
9.2.5公共子串算法
9.3序列比較算法
9.3.1編輯距離算法
9.3.2公共單調子序列
9.3.3有約束公共子序列
小結
習題
0章算法優化策略
10.1算法設計策略的比較與選擇
10.1.1優選子段和問題的簡單算法
10.1.2優選子段和問題的分治算法
10.1.3優選子段和問題的動態規劃算法
10.1.4優選子段和問題與動態規劃算法的推廣
10.2動態規劃加速原理
10.2.1貨物儲運問題
10.2.2算法及其優化
10.3問題的算法特征
10.3.1貪心策略
10.3.2對貪心策略的改進
10.3.3算法三部曲
10.3.4算法實現
10.3.5算法復雜性
10.4優化數據結構
10.4.1帶權區間最短路問題
10.4.2算法設計思想
10.4.3算法實現方案
10.4.4並查集
10.4.5可並優先隊列
10.5優化搜索策略
小結
習題
1章在線算法設計
11.1在線算法設計的基本概念
11.2頁調度問題
11.3勢函數分析
11.4k服務問題
11.4.1競爭比的下界
11.4.2平衡算法
11.4.3對稱移動算法
11.5Steiner樹問題
11.6在線任務調度
11.7負載平衡
小結
習題
詞彙索引
參考文獻
