本書系統(tǒng)地介紹了算法設(shè)計與分析的基本內(nèi)容,并對討論的算法進行了詳盡分析。全書共8章,內(nèi)容包括算法基礎(chǔ)、基本算法設(shè)計和分析技術(shù)(分治法、動態(tài)規(guī)劃、貪心法、回溯法和分枝限界法)、圖算法以及NP完全性理論。書中以類高級程序設(shè)計語言對算法所作的簡明描述,使得稍微具有程序設(shè)計語言知識的人即可讀懂。此外,書中以大量圖例說明每個算法的工作過程,使得算法更加易于理解和掌握。
本書可作為高等院校與計算機相關(guān)的各專業(yè)算法設(shè)計課程的教材,也可作為計算機領(lǐng)域的相關(guān)科研人員的參考書。此外,本書還可供參加ACM程序設(shè)計大賽的算法愛好者參考。
第1章 算法基礎(chǔ)
1.1 算法 ?
1.1.1 冒泡排序 ?
1.1.2 循環(huán)不變式和冒泡排序算法的正確性 ?
1.1.3 偽代碼使用約定
1.2 算法分析 ?
1.2.1 冒泡排序算法分析 ?
1.2.2 最壞情況和平均情況分析 ?
1.2.3 增長的數(shù)量級
1.3 算法的運行時間 ?
1.3.1 函數(shù)增長 ?
1.3.2 漸近表示
習題
第2章 分治法
2.1 遞歸與遞歸方程 ?
2.1.1 遞歸的概念 ?
2.1.2 替換方法 ?
2.1.3 遞歸樹方法 ?
2.1.4 主方法
2.2 分治法 ?
2.2.1 分治法的基本思想 ?
2.2.2 二叉查找算法
2.3 分治法應(yīng)用實例 ?
2.3.1 找最大值與最小值 ?
2.3.2 Strassen矩陣乘法 ?
2.3.3 整數(shù)相乘 ?
2.3.4 歸并排序 ?
2.3.5 快速排序 ?
2.3.6 線性時間選擇 ?
2.3.7 最近點對問題
習題
第3章 動態(tài)規(guī)劃
3.1 用表代替遞歸
3.2 -1背包問題
3.3 矩陣鏈乘問題
3.4 動態(tài)規(guī)劃的基本元素
3.5 備忘錄方法
3.6 裝配線調(diào)度問題
3.7 最長公共子序列
3.8 最優(yōu)二分檢索樹
3.9 凸多邊形最優(yōu)三角剖分
習題
第4章 貪心法
4.1 背包問題
4.2 活動選擇問題
4.3 貪心算法的基本元素
4.4 哈夫曼編碼
4.5 最小生成樹算法 ?
4.5.1 最小生成樹的基本原理 ?
4.5.2 Kruskal算法 ?
4.5.3 Prim算法 ?
4.5.4 Boruvka算法 ?
4.5.5 比較與改進
4.6 貪心算法的理論基礎(chǔ)
4.7 作業(yè)調(diào)度問題
習題
第5章 回溯法
5.1 回溯法的基本原理
5.2 n-皇后問題
5.3 子集和數(shù)問題
5.4 -1背包問題
5.5 著色問題
習題
第6章 分枝限界法
6.1 分枝限界法的基本思想
6.2 -1背包問題
6.3 作業(yè)調(diào)度問題
習題
第7章 圖算法
7.1 圖的表示
7.2 廣度優(yōu)先搜索
7.3 Dijkstra算法
7.4 Bellman Ford算法
7.5 Floyd Warshall算法
習題
第8章 NP完全性
8.1 P類問題和NP類問題 ?
8.1.1 復雜類P和復雜類NP ?
8.1.2 NP中的有趣問題
8.2 NP完全性 ?
8.2.1 多項式時間歸約和NP難度 ?
8.2.2 Cook定理
8.3 典型的NP完全問題 ?
8.3.1 CNF?3SAT問題和3SAT問題 ?
8.3.2 頂點覆蓋問題 ?
8.3.3 團問題和集合覆蓋問題 ?
8.3.4 子集和數(shù)問題與背包問題 ?
8.3.5 哈密爾頓回路問題和TSP問題
習題
附錄A 習題選解
附錄B 索引
參考文獻