算法設(shè)計與分析

第1章  算法引論                  
 1. 1  算法與程序                  
 1. 2  表達(dá)算法的抽象機(jī)制                  
 1. 3  描述算法                  
 1. 4  算法復(fù)雜性分析                  
 小結(jié)                  
 習(xí)題                  
                   
 第2章  遞歸與分治策略                  
 2. 1  遞歸的概念                  
 2. 2  分治法的基本思想                  
 2. 3  二分搜索技術(shù)                  
 2. 4  大整數(shù)的乘法                  
 2. 5  Strassen矩陣乘法                  
 2. 6  棋盤覆蓋                  
 2. 7  合并排序                  
 2. 8  快速排序                  
 2. 9  線性時間選擇                  
 2. 10  最接近點(diǎn)對問題                  
 2. 11  循環(huán)賽日程表                  
 小結(jié)                  
 習(xí)題                  
                   
 第3章  動態(tài)規(guī)劃                  
 3. 1  矩陣連乘問題                  
 3. 2  動態(tài)規(guī)劃算法的基本要素                  
 3. 3  最長公共子序列                  
 3. 4  凸多邊形最優(yōu)三角剖分                  
 3. 5  多邊形游戲                  
 3. 6  圖像壓縮                  
 3. 7  電路布線                  
 3. 8  流水作業(yè)調(diào)度                  
 3. 9  0-1背包問題                  
 3. 10  最優(yōu)二叉搜索樹                  
 小結(jié)                  
 習(xí)題                  
                   
 第4章  貪心算法                  
 4. 1  活動安排問題                  
 4. 2  貪心算法的基本要素                  
 4. 2. 1  貪心選擇性質(zhì)                  
 4. 2. 2  最優(yōu)子結(jié)構(gòu)性質(zhì)                  
 4. 2. 3  貪心算法與動態(tài)規(guī)劃算法的差異                  
 4. 3  最優(yōu)裝載                  
 4. 4  哈夫曼編碼                  
 4. 4. 1  前綴碼                  
 4. 4. 2  構(gòu)造哈夫曼編碼                  
 4. 4. 3  哈夫曼算法的正確性                  
 4. 5  單源最短路徑                  
 4. 5. 1  算法基本思想                  
 4. 5. 2  算法的正確性和計算復(fù)雜性                  
 4. 6  最小生成樹                  
 4. 6. 1  最小生成樹性質(zhì)                  
 4. 6. 2  Prim算法                  
 4. 6. 3  Kruskal算法                  
 4. 7  多機(jī)調(diào)度問題                  
 4. 8  貪心算法的理論基礎(chǔ)                  
 4. 8. 1  擬陣                  
 4. 8. 2  帶權(quán)擬陣的貪心算法                  
 4. 8. 3  任務(wù)時間表問題                  
 小結(jié)                  
 習(xí)題                  
                   
 第5章  回溯法                  
 5. 1  回溯法的算法框架                  
 5. 1. 1  問題的解空間                  
 5. 1. 2  回溯法的基本思想                  
 5. 1. 3  遞歸回溯                  
 5. 1. 4  迭代回溯                  
 5. 1. 5  子集樹與排列樹                  
 5. 2  裝載問題                  
 5. 3  批處理作業(yè)調(diào)度                  
 5. 4  符號三角形問題                  
 5. 5  n后問題                  
 5. 6  0-1背包問題                  
 5. 7  最大團(tuán)問題                  
 5. 8  圖的m著色問題                  
 5. 9  旅行售貨員問題                  
 5. 10  圓排列問題                  
 5. 11  電路板排列問題                  
 5. 12  連續(xù)郵資問題                  
 5. 13  回溯法的效率分析                  
 小結(jié)                  
 習(xí)題                  
                   
 第6章  分支限界法                  
 6. 1  分支限界法的基本思想                  
 6. 2  單源最短路徑問題                  
 6. 3  裝載問題                  
 6. 4  布線問題                  
 6. 5  0-1背包問題                  
 6. 6  最大團(tuán)問題                  
 6. 7  旅行售貨員問題                  
 6. 8  電路板排列問題                  
 6. 9  批處理作業(yè)調(diào)度                  
 小結(jié)                  
 習(xí)題                  
                   
 第7章  概率算法                  
 7. 1  隨機(jī)數(shù)                  
 7. 2  數(shù)值概率算法                  
 7. 2. 1  用隨機(jī)投點(diǎn)法計算n值                  
 7. 2. 2  計算定積分                  
 7. 2. 3  解非線性方程組                  
 7. 3  舍伍德算法                  
 7. 3. 1  線性時間選擇算法                  
 7. 3. 2  跳躍表                  
 7. 4  拉斯維加斯算法                  
 7. 4. 1  n后問題                  
 7. 4. 2  整數(shù)因子分解                  
 7. 5  蒙特卡羅算法                  
 7. 5. 1  蒙特卡羅算法的基本思想                  
 7. 5. 2  主元素問題                  
 7. 5. 3  素數(shù)測試                  
 小結(jié)                  
 習(xí)題                  
                   
 第8章  NP完全性理論                  
 8. 1  計算模型                  
 8. 1. 1  隨機(jī)存取機(jī)RAM                  
 8. 1. 2  隨機(jī)存取存儲程序機(jī)RASP                  
 8. 1. 3  RAM模型的變形與簡化                  
 8. 1. 4  圖靈機(jī)                  
 8. 1. 5  圖靈機(jī)模型與RAM模型的關(guān)系                  
 8. 1. 6  問題變換與計算復(fù)雜性歸約                  
 8. 2  P類與NP類問題                  
 8. 2. 1  非確定性圖靈機(jī)                  
 8. 2. 2  P類與NP類語言                  
 8. 2. 3  多項(xiàng)式時間驗(yàn)證                  
 8. 3  NP完全問題                  
 8. 3. 1  多項(xiàng)式時間變換                  
 8. 3. 2  Cook定理                  
 8. 4  一些典型的NP完全問題                  
 8. 4. 1  合取范式的可滿足性問題                  
 8. 4. 2  3元合取范式的可滿足性問題                  
 8. 4. 3  團(tuán)問題                  
 8. 4. 4  頂點(diǎn)覆蓋問題                  
 8. 4. 5  子集和問題                  
 8. 4. 6  哈密頓回路問題                  
 8. 4. 7  旅行售貨員問題                  
 小結(jié)                  
 習(xí)題                  
                   
 第9章  近似算法                  
 9. 1  近似算法的性能                  
 9. 2  頂點(diǎn)覆蓋問題的近似算法                  
 9. 3  旅行售貨員問題近似算法                  
 9. 3. 1  具有三角不等式性質(zhì)的旅行售貨員問題                  
 9. 3. 2  一般的旅行售貨員問題                  
 9. 4  集合覆蓋問題的近似算法                  
 9. 5  子集和問題的近似算法                  
 9. 5. 1  子集和問題的指數(shù)時間算法                  
 9. 5. 2  子集和問題的完全多項(xiàng)式時間近似格式                  
 小結(jié)                  
 習(xí)題                  
                   
 第10章  算法優(yōu)化策略                  
 10. 1  算法設(shè)計策略的比較與選擇                  
 10. 1. 1  最大子段和問題的簡單算法                  
 10. 1. 2  最大子段和問題的分治算法                  
 10. 1. 3  最大子段和問題的動態(tài)規(guī)劃算法                  
 10. 1. 4  最大子段和問題與動態(tài)規(guī)劃算法的推廣                  
 10. 2  動態(tài)規(guī)劃加速原理                  
 10. 2. 1  貨物儲運(yùn)問題                  
 10. 2. 2  算法及其優(yōu)化                  
 10. 3  問題的算法特征                  
 10. 3. 1  貪心策略                  
 10. 3. 2  對貪心策略的改進(jìn)                  
 10. 3. 3  算法三部曲                  
 10. 3. 4  算法實(shí)現(xiàn)                  
 10. 3. 5  算法復(fù)雜性                  
 10. 4  優(yōu)化數(shù)據(jù)結(jié)構(gòu)                  
 10. 4. 1  帶權(quán)區(qū)間最短路問題                  
 10. 4. 2  算法設(shè)計思想                  
 10. 4. 3  算法實(shí)現(xiàn)方案                  
 10. 4. 4  并查集                  
 10. 4. 5  可并優(yōu)先隊(duì)列                  
 10. 5  優(yōu)化搜索策略                  
 小結(jié)                  
 習(xí)題                  
 參考文獻(xiàn)