内容簡介
本書主要取材于反映當今計算機科學與技術學科中算法設計及分析發展潮流方面的内容。内容除包括國外一些比較成熟的算法技術，例如基本的随機算法以及近似算法，還包括一些最新的研究成果，例如基于近似和随機思想的混合算法：随機近似算法、在線算法、現代啟發式算法等。
目錄
第1章算法引論
1.1算法與程序
1.2表達算法的抽象機制
1.3描述算法
1.4算法複雜性分析
小結
習題
第2章遞歸與分治策略
2.1速歸的概念
2.2分治法的基本思想
2.3二分搜索技術
2.4大整數的乘法
2.5Strassen矩陣乘法
2.6棋盤複蓋
2.7合并排序
2.8快速排序
2.9線性時間選擇
2.10最接近點對問題
2.11循環賽日程表
小結
習題
第3章動态規劃
3.1矩陣連乘問題
3.2動态規劃算法的基本要素
3.3最長公共子序列
3.4凸多邊形最優三角剖分
3.5多邊形遊戲
3.6圖像壓縮
3.7電路布線
3.8流水作業調度
3.90-1背包問題
3.10最優二叉搜索樹
小結
習題
第4章貪心算法
4.1活動安排問題
4.2貪心算法的基本要素
4.2.1貪心選擇性質
4.2.2最優子結構性質
4.2.3貪心算法與動态規劃算法的差異
4.3最優裝載
4.4哈夫曼編碼
4.4.1前綴碼
4.4.2構造哈夫曼編碼
4.4.3哈夫曼算法的正确性
4.5單源最短路徑
4.5.1算法基本思想
4.5.2算法的正确性和計算複雜性
4.6最小生成樹
4.6.1最小生成樹性質
46.2Prim算法
4.6.3Kruskal算法
4.7多機調度問題
4.8貪心算法的理論基礎
4.8.1拟陣
4.8.2帶權拟陣的貪心算法
4.8.3任務時間表問題
小結
習題
第5章回溯法
5.1回溯法的算法框架
5.1.1問題的解空間
5.1.2回溯法的基本思想
5.1.3遞歸回溯
5.1.4叠代回溯
5.1.5子集樹與排列樹
5.2裝載問題
5.3批處理作業調度
5.4符号三角形問題
5.5n後問題
5.60-1背包問題
5.7最大團問題
5.8圖的m着色問題
5.9旅行售貨員問題
5.10圓排列問題
5.11電路闆排列問題
5.12連續郵資問題
5.13回溯法的效率分析
小結
習題
第6章分支限界法
6.1分支限界法的基本思想
6.2單源最短路徑問題
6.3裝載問題
6.4布線問題
6.50-1背包問題
6.6最大團問題
6.7旅行售貨員問題
6.8電路闆排列問題
6.9批處理作業調度
小結
習題
第7章概率算法
7.1随機數
7.2數值概率算法
7.2.1用随機投點法計算л值
7.2.2計算定積分
7.2.3解非線性方程組
7.3舍伍德算法
7.3.1線性時間選擇算法
7.3.2跳躍表
7.4拉斯維加斯算法
7.4.1n後問題
7.4.2整數因子分解
7.5蒙特卡羅算法
7.5.1蒙特卡羅算法的基本思想
7.5.2主元素問題
7.5.3素數測試
小結
習題
第8章NP完全性理論
8.1計算模型
8.1.1随機存取機RAM
8.1.2随機存取存儲程序機RASP
8.1.3RAM模型的變形與簡化
8.1.4圖靈機
8.1.5圖靈機模型與RAM模型的關系
8.1.6問題變換與計算複雜性歸約
8.2P類與NP類問題
8.2.1非确定性圖靈機
8.2.2P類與NP類語言
8.2.3多項式時間驗證
8.3NP完全問題
8.3.1多項式時間變換
8.3.2Cook定理
8.4一些典型的NP完全問題
8.4.1合取範式的可滿足性問題
8.4.23元合取範式的可滿足性問題
8.4.3團問題
8.4.4頂點複蓋問題
8.4.5子集和問題
8.4.6哈密頓回路問題
8.4.7旅行售貨員問題
小結
習題
第9章近似算法
9.1近似算法的性能
9.2頂點複蓋問題的近似算法
9.3旅行售貨員問題近似算法
9.3.1具有三角不等式性質的旅行售貨員問題
9.3.2一般的旅行售貨員問題
9.4集合複蓋問題的近似算法
9.5子集和問題的近似算法
9.5.1子集和問題的指數時間算法
9.5.2子集和問題的完全多項式時間近似格式
小結
習題
第10章算法優化策略
10.1算法設計策略的比較與選擇
10.1.1最大子段和問題的簡單算法
10.1.2最大子段和問題的分治算法
10.1.3最大子段和問題的動态規劃算法
10.1.4最大子段和問題與動态規劃算法的推廣
10.2動态規劃加速原理
10.2.1貨物儲運問題
10.2.2算法及其優化
10.3問題的算法特征
10.3.1貪心策略
10.3.2對貪心策略的改進
10.3.3算法三部曲
10.3.4算法實現
103.5算法複雜性
10.4優化數據結構
10.4.1帶權區間最短路問題
10.4.2算法設計思想
10.4.3算法實現方案
10.4.4并查集
10.4.5可并優先隊列
10.5優化搜索策略
小結
習題
