計算機演演算法

《計算機演演算法》主要講述、分析了各種演演算法的基本原理和解題技巧，以五種通用的演演算法設計技術為主線論述了分治策略、貪心策略、動態規劃策略、分支限界法、回溯法等問題，對演演算法的時間和空間複雜性進行了分析。在內容的選材上注重基本理論和具體實例的結合，以便於讀者理解。《計算機演演算法》還對概率演演算法、近似演演算法、密碼演演算法和NP問題進行了簡單的介紹。

《計算機演演算法》可作為計算機系本科學生及研究生的教材，也可作為計算機科學研究和軟體開發技術人員的參考用書。

作者：胡金初

定價：21元

印次：1-1

ISBN：9787811235609

出版日期：2009.03.01

印刷日期：2009.03.23

本教材的內容包括：1. 演演算法分析原理 2. 數據抽象與基本數據結構 3. 遞歸與歸納 4. 分類 5. 選擇 6. 動態集合與查找 7. 圖與圖的遍歷 8. 圖的優化問題與貪心演演算法9. 傳遞閉包 10. 動態編程 11. 字元串匹配 12. 多項式與矩陣 13. NP-完備性問題 14. 并行演演算法，實例與技術。本教材提供在學習現代計算機演演算法時經常會遇到的許多問題的答案，幫助學生更好地理解、掌握演演算法分析與設計課程。包括多個練習題，這些練習題不僅涉及到一些經典問題，而且包括一些重要的應用程序中的熱點問題，如文字處理中的排版、數據壓縮、資料庫系統和Internet搜索引擎等方面的演演算法問題，這些都是現代軟體系統的基本組成部分。為了幫助學生學習計算機演演算法，本教材提供習題庫以及大量的程序例子。

第1章 緒論

1.1 演演算法的時間複雜性

1.2 演演算法的空間複雜性

1.3 兩個演演算法的分析實例

1.4 演演算法設計技術

1.4.1 分治方法

1.4.2 回溯法

1.4.3 貪心法

1.4.4 動態規劃法

1.4.5 分支限界法

1.4.6 遞歸方程解的展開式

習題

第2章 排序演演算法

2.1 插入演演算法

2.1.1 直接插入排序

2.1.2 折半插入排序

2.1.3 希爾排序

2.2 選擇排序

2.2.1 直接選擇排序

2.2.2 堆排序

2.3 交換排序

2.3.1 冒泡排序

2.3.2 快速排序

2.4 歸併排序

2.5 基數排序

2.6 外部排序

2.6.1 歸併排序

2.6.2 多步歸併演演算法

2.7 各種內部排序方法的比較討論

習題

第3章 查找樹

3.1 二分查找樹

3.2 2—3—4樹

3.3 紅黑樹

3.4 8樹

習題

第4章 圖的演演算法

4.1 基本概念

4.2 圖的表示方法

4.3 圖的遍歷

4.4 所有點對之間的最短路徑

4.5 最小生成樹

習題

第5章 串匹配

5.1 簡單的字元串匹配演演算法

5.2 Knuth—Morris—Pratt（KMP）字元串匹配

5.3 BM演演算法

5.4 RK演演算法

習題

第6章 分治演演算法

6.1 二分搜索

6.2 求最大元和最小元

6.3 大整數乘法

6.4 矩陣乘法演演算法

6.5 矩陣乘積的Winograd演演算法

習題

第7章 貪心演演算法

7.1 背包問題

7.2 帶時限的作業排序

7.3 單源最短路徑問題

7.4 最小生成樹問題

7.5 Dijkstra各點之間最短路徑的優化演演算法

習題

第8章 回溯法

8.1 n皇后問題

8.2 圖的著色問題

8.3 0—1背包問題

8.4 哈密頓迴路

8.5 子集和數

習題

第9章 動態規劃法

9.1 最長公共子序列問題

9.2 矩陣連乘問題

9.3 多階段決策過程最優化問題

9.4 0—1背包問題

9.5 流水線調度問題

習題

第10章 分支限界法

10.1 分支限界的策略

10.2 0－1背包問題

習題

第11章 概率演演算法

11.l 隨機數

11.2 數值概率演演算法

11.3 蒙特卡羅演演算法

11.4 拉斯維加斯演演算法

11.5 舍伍德演演算法

習題

第12章 幾何問題演演算法

12.1 直線相交問題的演演算法

12.2 點是否包含在多邊形內部

12.3 求凸包問題

習題

第13章 NP完全問題

13.1 不確定演演算法和不確定圖靈機

13.2 NP難度和NP完全問題

13.3 COOK定理

13.4 幾個NP完全問題

習題

第14章 密碼學演演算法

14.1 什麼是密碼

14.2 基本數論

14.3 背包公鑰密碼

14.4 RSA演演算法

14.5 數字簽名

習題

第15章 近似演演算法

15.1 任務調度近似演演算法.

15.2 頂點覆蓋問題近似演演算法

15.3 旅行商問題的近似解

15.4 子集和數問題的近似演演算法

習題

第16章 并行演演算法

16.1 并行計算機

16.2 并行演演算法的基本概念

16.3 并行演演算法的描述

16.4 SIMD-SM上的非線性方程求根同步并行演演算法

16.5 SIMD-SM上的同步并行求和演演算法

16.6 SIMD-CC超立方機器上的同步并行求和演演算法

16.7 MIMD-SM上的非同步并行求和演演算法

習題

參考文獻