基本介紹
- 書名：計算機算法的設計與分析
- 作者：阿霍，霍普克勞夫特，烏爾曼
- 譯者：黃林鵬，王德俊，張仕
- 頁數：417
- 出版社：機械工業出版社
- 出版時間：2007-7-1
圖書簡介,內容簡介,作者簡介,編輯推薦,目錄,
圖書簡介
出版時間：2007-7-1
版 次：1
頁 數：417
印刷時間：2007-7-1
紙 張：膠版紙
I S B N：9787111215431
包 裝：平裝
內容簡介
本書可以作為高等院校計算機算法設計與分析課程的本科生或研究生教材，也可以作為計算機理論研究人員、計算機算法設計人員的參考書。
作者簡介
Alfred V.Aho博士，是哥倫比亞大學計算機科學系主管本科生教學的副主任，IEEE Fellow，美國科學與藝術學院及國家工程學院院士，曾獲得IEEE的馮·諾伊曼獎。他是《編譯原理》（Compiler:Principles,Techniques,and Tools）的第一作者。他的研究方向為量子計算、程式設計語言、編譯器和算法等。
編輯推薦
本書可以作為高等院校計算機算法設計與分析課程的本科生或研究生教材，也可以作為計算機理論研究人員、計算機算法設計人員的參考書。
目錄
出版者的話
譯者序
前言
第1章 計算模型
1.1 算法和複雜度
1.2 隨機存取計算機
1.3 RAM程式的計算複雜度
1.4 存儲程式模型
1.5 RAM的抽象
1.6 一種基本的計算模型：圖靈機
1.7 圖靈機模型和RAM模型的關係
1.8 簡化ALGOL——一種高級語言
第2章 有效算法的設計
2.1 數據結構：表、佇列和堆疊
2.2 集合的表示
2.3 圖
2.4 樹
2.5 遞歸
2.6 分治法
2.7 平衡
2.8 動態規劃
2.9 後記
第3章 排序和順序統計
3.1 排序問題
3.2 基數排序
3.3 比較排序
3.4 堆排序——O(n log n)的比較排序算法
3.5 快速排序——期望時間為O(n log n)的排序算法
3.6 順序統計學
3.7 順序統計的期望時間
第4章 集合操作問題的數據結構
4.1 集合的基本操作
4.2 散列法
4.3 二分搜尋
4.4 二叉查找樹
4.5 最優二叉查找樹
4.6 簡單的不相交集合合併算法
4.7 UNION-FIND問題的樹結構
4.8 UNION-FIND算法的套用和擴展
4.9 平衡樹方案
4.10 字典和優先佇列
4.11 可合併堆
4.12 可連線佇列
4.13 劃分
4.14 本章小結
第5章 圖算法
5.1 最小代價生成樹
5.2 深度優先搜尋
5.3 雙連通性
5.4 有向圖的深度優先搜尋
5.5 強連通性
5.6 路徑查找問題
5.7 傳遞閉包算法
5.8 最短路徑算法
5.9 路徑問題與矩陣乘法
5.10 單源問題
第6章 矩陣乘法及相關操作
6.1 基礎知識
6.2 Strassen矩陣乘法算法
6.3 矩陣求逆
6.4 矩陣的LUP分解
6.5 LUP分解的套用
6.6 布爾矩陣的乘法
第7章 快速傅立葉變換及其套用
7.1 離散傅立葉變換及其逆變換
7.2 快速傅立葉變換算法
7.3 使用位操作的FFT
7.4 多項式乘積
7.5 Schonhage-Strassen整數相乘算法
第8章 整數與多項式計算
8.1 整數和多項式的相似性
8.2 整數的乘法和除法
8.3 多項式的乘法和除法
8.4 模算術
8.5 多項式模算術和多項式計值
8.6 中國餘數
8.7 中國餘數和多項式的插值
8.8 最大公因子和歐幾里得算法
8.9 多項式GCD的漸近快速算法
8.10 整數的GCD
8.11 再論中國餘數
8.12 稀疏多項式
第9章 模式匹配算法
9.2 正則表達式的模式識別
9.3 子串識別
9.4 雙向確定型下推自動機
9.5 位置樹和子串標識符
第10章 NP完全問題
10.1 非確定型圖靈機問題
10.2 P類和NP類
10.3 語言和問題
10.4 可滿足性問題的NP完全性
lO.5 其他NP完全問題
10.6 多項式空間界問題
第11章 一些可證難的問題
11.1 複雜度層次
11.2 確定型圖靈機的空間層次
11.3 一個需要指數時間和空問的問題
11.4 一個非基本的問題
第12章 算術運算的下界
12.1 域
12.2 再論直線狀代碼
12.3 問題的矩陣表述
12.4 面向行的矩陣乘法的下界
12.5 面向列的矩陣乘法的下界
12.6 面向行和列的矩陣乘法的下界
12.7 預處理
附錄 算法的C/C++代碼
參考文獻
