算法設(shè)計與分析

第1章 入門
1.1 問題
1.2 算法的概念
1.3 算法的正確性
1.4 算法的效率
1.5 問題的下界
1.6 小結(jié)
習(xí)題
實驗題
第2章 漸近符號
2.1 θ符號
2.2 O符號
2.3 η符號
2.4 漸近符號的性質(zhì)
2.5 常用函數(shù)的直觀含義
2.6 小結(jié)
習(xí)題
第3章 算法分析方法
3.1 概率分析
3.2 分攤分析
3.2.1 合計方法
3.2.2 記賬方法
3.2.3 勢能方法
3.3 實驗分析
3.4 小結(jié)
習(xí)題
第4章 遞歸
4.1 算法思想
4.1.1 遞歸算法的應(yīng)用
4.1.2 遞歸與迭代
4.2 遞歸方程的求解
4.2.1 替換方法
4.2.2 遞歸樹方法
4.2.3 式：去
4.3 多項式求值實驗
4.4 小結(jié)
習(xí)題
實驗題
第5章 分治算法
5.1 算法思想
5.2 合并排序
5.3 快速排序
5.4 大整數(shù)乘法
5.5 矩陣乘法
5.6 殘缺棋盤游戲、
5.7 快速傅里葉變換(FFT)
5.8 小結(jié)
習(xí)題
實驗題
第6章 動態(tài)規(guī)劃
6.1 算法思想
6.2 裝配線調(diào)度問題
6.3 矩陣鏈乘法問題
6.4 最長公共子序列問題
6.5 0／1背包問題
6.6 最優(yōu)二叉搜索樹問題
6.7 動態(tài)規(guī)劃的基本性質(zhì)
6.8 小結(jié)
習(xí)題
實驗題
第7章 貪心算法
7.1 算法思想
7.2 任務(wù)選擇問題
7.3 背包問題
7.4 哈夫曼編碼問題
7.5 緩存維護問題
7.6 任務(wù)選擇問題實驗
7.7 小結(jié)
習(xí)題
實驗題
第8章 圖算法
8.1 圖的搜索問題
8.1.1 寬度優(yōu)先搜索
8.1.2 深度優(yōu)先搜索
8.2 最小生成樹問題
8.2.1 Kruskall算法
8.2.2 Prim算法
8.3 最短路徑問題
8.3.1 單個源點的最短路徑問題
8.3.2 所有點對的最短路徑問題
8.4 小結(jié)
習(xí)題
實驗題
第9章 網(wǎng)絡(luò)流與匹配
9.1 最大流問題
9.1.1 FordFulkerson方法
9.1.2 最短路徑增廣算法
9.1.3 Dinic算法
9.1.4 MPM算法
9.1.5 最大流問題的變形
9.2 最小費用流問題
9.2.1 消除回路算法
9.2.2 最小費用路算法
9.2.3 最小費用路算法的改進
9.3 匹配問題
9.3.1 二分圖匹配
9.3.2 一般圖的匹配
9.4 小結(jié)
習(xí)題
實驗題
第10章 線性規(guī)劃
10.1 線性規(guī)劃問題
10.1.1 線性規(guī)劃問題的標準形式
10.1.2 線性規(guī)劃問題的松弛形式
10.2 求解算法
10.2.1 圖解法
10.2.2 單純形算法
10.3 對偶
10.4 小結(jié)
習(xí)題
實驗題
第11章 NIP完全理論
11.1 判定問題
11.2 P和NP
11.3 NPC
11.3.1 NPC的定義
11.3.2 電路可滿足性問題
11.4 NPC的證明
11.4.1 可滿足性問題
11.4.2 3.CNF可滿足性問題
11。4.3 團問題
11.4.4 頂點覆蓋問題
11.5 其他NP完全問題
11.6 小結(jié)
習(xí)題
第12章 回溯
12.1 算法思想
12.2 裝載問題
12.3 0／1背包問題
12.4 著色問題
12.5 n皇后問題
12.6 旅行商問題
12.7 流水作業(yè)調(diào)度問題
12.8 零件切割問題
12.9 小結(jié)
習(xí)題
實驗題
第13章 分支限界
第14章 啟發(fā)式搜索
第15章 數(shù)論
第16章 計算幾何
參考文獻