內容提要
為了適應培養21世紀計算機人才的需要，結合我國高等院校教育工作的現狀，立足培養學生能跟上國際計算機科學技術的發展水平，更新教學內容和教學方法，本書以算法設計策略為知識單元，系統地介紹計算機算法的設計方法與分析技巧，以期為計算機科學與技術學科的學生提供廣泛而堅實的計算機算法基礎知識。
本書內容豐富，觀點新穎，理論聯繫實際。採用Java語言描述算法，簡明清晰、結構緊湊，可讀性強。本書可以作為高等院校計算機專業本科生和研究生學習計算機算法設計的教材，也可供廣大工程技術人員和自學讀者學習參考。
編輯推薦
本書採用面向對象的JAVA語言作為表述手段，在保持JAVA優點的同時，儘量使算法的描述簡明、清晰。為了加深對知識的理解，各章配有難易適當的習題，以適應不同程度讀者練習的需要。
目錄
第1章 算法引論
1.1 算法與程式
1.2 表達算法的抽象機制
1.3 描述算法
1.4 算法複雜性分析
小結
習題
第2章 遞歸與分治策略
2.1 速歸的概念
2.2 分治法的基本思想
2.3 二分搜尋技術
2.4 大整數的乘法
2.5 Strassen矩陣乘法
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.9 0-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 最小生成樹性質
4 6.2 Prim算法
4.6.3 Kruskal算法
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.5 n後問題
5.6 0-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.5 0-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.1 n後問題
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.3 RAM模型的變形與簡化
8.1.4 圖靈機
8.1.5 圖靈機模型與RAM模型的關係
8.1.6 問題變換與計算複雜性歸約
8.2 P類與NP類問題
8.2.1 非確定性圖靈機
8.2.2 P類與NP類語言
8.2.3 多項式時間驗證
8.3 NP完全問題
8.3.1 多項式時間變換
8.3.2 Cook定理
8.4 一些典型的NP完全問題
8.4.1 合取範式的可滿足性問題
8.4.2 3元合取範式的可滿足性問題
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 算法實現
10 3.5 算法複雜性
10.4 最佳化數據結構
10.4.1 帶權區間最短路問題
10.4.2 算法設計思想
10.4.3 算法實現方案
10.4.4 並查集
10.4.5 可並優先佇列
10.5 最佳化搜尋策略
小結
習題
參考文獻
作者簡介
耿國華,教授,博士生導師,高等學校教學名師,享受國務院政府津貼,西北大學信息科學與技術學院副院長,教育部文科計算機基礎教學指導委員會副主任,陝西省計算機學會副理事長,陝西省計算機教育學會副理事長,陝西省計算機學會人工智慧與模式識別專業委員會副主任,西北大學計算機軟體開發中心主任,長期從事智慧型信息處理、模式識別、信息可視化技術研究。
