百科名片
作/譯者：(美)霍羅威茨 馮博琴
頁數：452 重約：0.707KG
定價：￥55.00
內容提要
本書是計算機算法在設計與分析文獻的一本經典著作。書中介紹了算法和算法性能的基本知識,基本的數據結構知識,重點討論了不同的算法設計策略,研究了下界理論等,提供了計算機算法的設計技術和有效的算法分析,以及大量的詳細實例和實際套用。同時,對NP難和NP完全問題能否有效求解進行了分析。本書還匯聚了各種隨機算法與並行算法的充分比較。
圖書目錄
第1章 導論
1.1 什麼是算法
1.2 算法規範
1.2.1 引言
1.2.2 遞歸算法
1.3 性能分析
1.3.1 空間複雜度
1.3.2 時間複雜度
1.3.3 漸近符號 (O、 Ω、 Θ)
1.3.4 實際複雜度
1.3.5 性能度量
1.4 隨機算法
1.4.1 機率論基礎
1.4.2 隨機算法: 非形式化的描述
1.4.3 識別重複元素
1.4.4 素數測試
1.4.5 優點與缺點
1.5 參考文獻和讀物
第2章 基本數據結構
2.1 棧和佇列
2.2 樹
2.2.1 術語
2.2.2 二叉樹
2.3 字典
2.3.1 二叉查找樹
2.3.2 代價分攤
2.4 優先佇列
2.4.1 堆
2.4.2 堆排序
2.5 集合和不相交集合的並
2.5.1 概述
2.5.2 並和查找操作
2.6 圖
2.6.1 概述
2.6.2 定義
2.6.3 圖的表示方法
2.7 參考文獻和讀物
第3章 分治算法
3.1 一般方法
3.2 二叉查找
3.3 查找最大值和最小值
3.4 歸併排序
3.5 快速排序
3.5.1 性能度量
3.5.2 隨機排序算法
3.6 選擇
3.6.1 最壞情況下的最優算法
3.6.2 Select2的實現
3.7 Strassen矩陣乘法
3.8 凸包
3.8.1 幾種原始幾何方法
3.8.2 QuickHull算法
3.8.3 Graham掃描算法
3.8.4 一個O(nlogn)的分治算法
3.9 參考文獻和讀物
3.10 附加習題
第4章 貪心算法
4.1 一般方法
4.2 背包問題
4.3 樹節點分割
4.4 帶有期限的作業順序問題
4.5 最小代價生成樹
4.5.1 Prim算法
4.5.2 Kruskal算法
4.5.3 一個最優隨機算法(*)
4.6 磁帶的最優存儲
4.7 最優歸併模式
4.8 單源最短路徑
4.9 參考文獻和讀物
4.10 附加習題
第5章 動態規劃
5.1 一般方法
5.2 多部圖
5.3 每一對頂點之間的最短路徑
5.4 單源最短路徑: 普通權值
5.5 最優二叉查找樹(*)
5.6 串編輯
5.7 0/1背包
5.8 可靠性設計
5.9 旅行商問題
5.10 流水作業調度
5.11 參考文獻和讀物
5.12 附加習題
第6章 基本的查找和遍歷技術
6.1 二叉樹算法
6.2 圖算法
6.2.1 廣度優先搜尋和遍歷
6.2.2 深度優先搜尋和遍歷
6.3 連通分支和生成樹
6.4 雙連通分支和DFS算法
6.5 參考文獻和讀物
第7章 回溯
7.1 一般方法
7.2 8皇后問題
7.3 子集求和問題
7.4 圖的著色
7.5 哈密頓迴路
7.6 背包問題
7.7 參考文獻和讀物
7.8 附加習題
第8章 分支限界法
8.1 一般方法
8.1.1 最小代價查找
8.1.2 15拼板: 一個例子
8.1.3 LC查找的控制抽象
8.1.4 限界
8.1.5 FIFO分支限界法
8.1.6 LC分支限界法
8.2 0/1背包問題
8.2.1 LC分支限界法求解
8.2.2 FIFO分支限界法求解
8.3 旅行商問題(*)
8.4 效率因素
8.5 參考文獻和讀物
第9章 代數問題
9.1 一般方法
9.2 計算和插值
9.3 快速傅立葉變換
9.3.1 FFT的原地版本
9.3.2 一些保留問題
9.4 模運算
9.5 更快的計算和插值
9.6 參考文獻和讀物
第10章 下界理論
10.1 比較樹
10.1.1 有序查找
10.1.2 排序
10.1.3 選擇
10.2 喻示和對立論
10.2.1 歸併
10.2.2 最大和次大
10.2.3 狀態空間方法
10.2.4 選擇
10.3 通過規約求下界
10.3.1 尋找凸包
10.3.2 不相交集合問題
10.3.3 即時中值查找
10.3.4 三角矩陣相乘
10.3.5 下三角矩陣求逆
10.3.6 計算傳遞閉包
10.4 解決代數問題的技術(*)
10.5 參考文獻和讀物
第11章 難與完全問題
11.1 基本概念
11.1.1 非確定性算法
11.1.2 難和完全類
11.2 Cook定理(*)
11.3 難的圖問題
11.3.1 團判定問題
11.3.2 節點覆蓋判定問題
11.3.3 色數判定問題
11.3.4 有向哈密頓迴路(*)
11.3.5 旅行商判定問題
11.3.6 與/或圖判定問題
11.4 難的調度問題
11.4.1 調度相同的處理器
11.4.2 流水作業調度
11.4.3 作業安排調度
11.5 難的代碼生成問題
11.5.1 帶有公共子表達式的代碼生成
11.5.2 實現並行賦值指令
11.6 一些簡化的難問題
11.7 參考文獻和讀物
11.8 附加習題
第12章 近似算法
12.1 概述
12.2 絕對近似
12.2.1 平面圖著色
12.2.2 最多程式存儲問題
12.2.3 難的絕對近似
12.3 ε近似
12.3.1 獨立任務的調度
12.3.2 裝箱問題
12.3.3 難的ε近似問題
12.4 多項式時間近似方案
12.4.1 獨立任務的調度
12.4.2 0/1背包
12.5 完全多項式時間近似方案
12.5.1 捨入法
12.5.2 區間劃分法
12.5.3 分割法
12.6 機率上的好算法(*)
12.7 參考文獻和讀物
12.8 附加習題
第13章 PRAM算法
13.1 概述
13.2 計算模型
13.3 基本技術和算法
13.3.1 前綴計算
13.3.2 表排序
13.4 選擇
13.4.1 使用n?2個處理器選擇最大值
13.4.2 使用n個處理器選擇最大值
13.4.3 在整數中選擇最大值
13.4.4 使用n?2個處理器的一般選擇問題
13.4.5 一個工作最優的隨機算法(*)
13.5 歸併
13.5.1 對數時間算法
13.5.2 奇偶歸併
13.5.3 工作最優的算法
13.5.4 O(log logm)時間算法
13.6 排序
13.6.1 奇偶歸併排序
13.6.2 隨機選擇算法
13.6.3 Preparata算法
13.6.4 Reischuk隨機算法(*)
13.7 圖問題
13.7.1 計算傳遞閉包的另一種算法
13.7.2 每一對頂點之間的最短路徑
13.8 計算凸包
13.9 下界
13.9.1 平均情況下排序的下界
13.9.2 尋找最大值
13.10 參考文獻和讀物
13.11 附加習題
第14章 格線算法
14.1 計算模型
14.2 分組路由
14.2.1 線性陣列中的分組路由
14.2.2 格線上PPR的貪心算法
14.2.3 具有小佇列的隨機算法
14.3 基本算法
14.3.1 廣播
14.3.2 前綴計算
14.3.3 數據集中
14.3.4 稀疏枚舉排序
14.4 選擇
14.4.1 n=p(*)時的隨機算法
14.4.2 n>p(*)時的隨機選擇
14.4.3 n>p時的確定性算法
14.5 歸併
14.5.1 線上性陣列上的順序號歸併
14.5.2 線性陣列上的奇偶歸併
14.5.3 在格線上的奇偶歸併
14.6 排序
14.6.1 線上性陣列上的排序
14.6.2 在格線上的排序
14.7 圖問題
14.7.1 傳遞閉包的n×n格線算法
14.7.2 每一對頂點之間的最短路徑
14.8 計算凸包
14.9 參考文獻和讀物
14.10 附加習題
第15章 超立方體算法
15.1 計算模型
15.1.1 超立方體
15.1.2 蝶形網路
15.1.3 其他網路的嵌入
15.2 PPR路由
15.2.1 貪心算法
15.2.2 隨機算法
15.3 基本算法
15.3.1 廣播
15.3.2 前綴計算
15.3.3 數據集中
15.3.4 稀疏枚舉排序
15.4 選擇
15.4.1 n=p(*)時的隨機算法
15.4.2 n>p(*)時的隨機選擇
15.4.3 n>p時的確定性算法
15.5 歸併
15.5.1 奇偶歸併
15.5.2 雙調諧歸併
15.6 排序
15.6.1 奇偶歸併排序
15.6.2 雙調諧排序
15.7 圖問題
15.8 計算凸包
15.9 參考文獻和讀物
15.10 附加習題
索引
編輯推薦與評論
本書作者均是世界著名的計算機科學家,在計算機科學理論和算法領域做出了傑出的貢獻。本書著重在計算機科學發展領域中,推動新的計算機算法的設計和分析,是一本經典著作,也是計算機算法方面的重要參考書。書中為讀者提供了計算機算法的設計技術,對計算機算法的實際設計提供了有效的算法分析。在計算機算法設計方面提供了大量的詳細實例和實際套用,並致力於隨機算法和並行算法富有成效的深入研究和開發。本書為讀者提供了當前流行的對象設計語言C++的實現版本,以及現代計算機科學發展和研究的最新研究成果。
作者介紹
Ellis Horowitz於威斯康星-邁迪遜大學獲得計算機科學博士學位,從事數據結構、算法和軟體設計等領域的計算機科學教育。他是美國國家科學基金會主要調查員。
