算法設(shè)計(jì)與分析

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