基本介紹
內容簡介,圖書目錄,
內容簡介
本書採用面向對象的JAVA語言作為表述手段，在保持JAVA優點的同時，儘量使算法的描述簡明、清晰。為了加深對知識的理解，各章配有難易適當的習題，以適應不同程度讀者練習的需要。
本書內容豐富,觀點新穎,理論聯繫實際。採用Java語言描述算法,簡明清晰、結構緊湊,可讀性強。本書可以作為高等院校計算機專業本科生和研究生學習計算機算法設計的教材,也可供廣大工程技術人員和自學讀者學習參考。
為了適應培養21世紀計算機人才的需要,結合我國高等院校教育工作的現狀,立足培養學生能跟上國際計算機科學技術的發展水平,更新教學內容和教學方法,本書以算法設計策略為知識單元,系統地介紹計算機算法的設計方法與分析技巧,以期為計算機科學與技術學科的學生提供廣泛而堅實的計算機算法基礎知識。
圖書目錄
第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 隨機數
.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 哈密頓迴路問題
……
