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

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