計算機(jī)算法的設(shè)計與分析

內(nèi)容概要

本書是一部設(shè)計與分析領(lǐng)域的經(jīng)典著作，著重介紹了計算機(jī)算法設(shè)計領(lǐng)域的基本原則和根本原理。書中深入分析了一些計算機(jī)模型上的算法，介紹了一些和設(shè)計有效算法有關(guān)的數(shù)據(jù)結(jié)構(gòu)和編程技術(shù)，為讀者提供了有關(guān)遞歸方法、分治方法和動態(tài)規(guī)劃方面的詳細(xì)實例和實際應(yīng)用，并致力于更有效算法的設(shè)計和開發(fā)。同時，對NP完全等問題能否有效求解進(jìn)行了分析，并探索了應(yīng)用啟發(fā)式算法解決問題的途徑。另外，本書還提供了大量富有指導(dǎo)意義的習(xí)題。    本書可以作為高等院校計算機(jī)算法設(shè)計與分析課程的本科生或研究生教材，也可以作為計算機(jī)理論研究人員、計算機(jī)算法設(shè)計人員的參考書。

作者簡介

Alfred V.Aho博士，是哥倫比亞大學(xué)計算機(jī)科學(xué)系主管本科生教學(xué)的副主任，IEEE Fellow，美國科學(xué)與藝術(shù)學(xué)院及國家工程學(xué)院院士，曾獲得IEEE的馮·諾伊曼獎。他是《編譯原理》（Compiler:Principles,Techniques,and Tools）的第一作者。他目前的研究方向為量子計算、程式設(shè)計語

書籍目錄

出版者的話譯者序前言第1章 計算模型　1.1 算法和復(fù)雜度　1.2 隨機(jī)存取計算機(jī)　1.3 RAM程序的計算復(fù)雜度　1.4 存儲程序模型　1.5 RAM的抽象　1.6 一種基本的計算模型：圖靈機(jī)　1.7 圖靈機(jī)模型和RAM模型的關(guān)系　1.8 簡化ALGOL——一種高級語言第2章 有效算法的設(shè)計　2.1 數(shù)據(jù)結(jié)構(gòu)：表、隊列和堆棧　2.2 集合的表示　2.3 圖　2.4 樹　2.5 遞歸　2.6 分治法　2.7 平衡　2.8 動態(tài)規(guī)劃　2.9 后記第3章 排序和順序統(tǒng)計　3.1 排序問題　3.2 基數(shù)排序　3.3 比較排序　3.4 堆排序——O（n log n）的比較排序算法　3.5 快速排序——期望時間為O（n log n）的排序算法　3.6 順序統(tǒng)計學(xué)　3.7 順序統(tǒng)計的期望時間第4章 集合操作問題的數(shù)據(jù)結(jié)構(gòu)　4.1 集合的基本操作　4.2 散列法　4.3 二分搜索　4.4 二叉查找樹　4.5 最優(yōu)二叉查找樹　4.6 簡單的不相交集合合并算法　4.7 UNION-FIND問題的樹結(jié)構(gòu)　4.8 UNION-FIND算法的應(yīng)用和擴(kuò)展　4.9 平衡樹方案　4.10 字典和優(yōu)先隊列　4.11 可合并堆　4.12 可連接隊列　4.13 劃分　4.14 本章小結(jié)第5章 圖算法　5.1 最小代價生成樹　5.2 深度優(yōu)先搜索　5.3 雙連通性　5.4 有向圖的深度優(yōu)先搜索　5.5 強(qiáng)連通性　5.6 路徑查找問題　5.7 傳遞閉包算法　5.8 最短路徑算法　5.9 路徑問題與矩陣乘法　5.10 單源問題　5.11 有向無環(huán)圖的支配集：概念整合第6章 矩陣乘法及相關(guān)操作　6.1 基礎(chǔ)知識　6.2 Strassen矩陣乘法算法　6.3 矩陣求逆　6.4 矩陣的LUP分解　6.5 LUP分解的應(yīng)用　6.6 布爾矩陣的乘法第7章 快速傅里葉變換及其應(yīng)用　7.1 離散傅里葉變換及其逆變換　7.2 快速傅里葉變換算法　7.3 使用位操作的FFT　7.4 多項式乘積　7.5 Schonhage-Strassen整數(shù)相乘算法第8章 整數(shù)與多項式計算　8.1 整數(shù)和多項式的相似性　8.2 整數(shù)的乘法和除法　8.3 多項式的乘法和除法　8.4 模算術(shù)　8.5 多項式模算術(shù)和多項式計值　8.6 中國余數(shù)　8.7 中國余數(shù)和多項式的插值　8.8 最大公因子和歐幾里得算法　8.9 多項式GCD的漸近快速算法　8.10 整數(shù)的GCD　8.11 再論中國余數(shù)　8.12 稀疏多項式第9章 模式匹配算法　9.1 有窮自動機(jī)和正則表達(dá)式　9.2 正則表達(dá)式的模式識別　9.3 子串識別　9.4 雙向確定型下推自動機(jī)　9.5 位置樹和子串標(biāo)識符第10章 NP完全問題　10.1 非確定型圖靈機(jī)問題　10.2 P類和NP類　10.3 語言和問題　10.4 可滿足性問題的NP完全性　10.5 其他NP完全問題　10.6 多項式空間界問題第11章 一些可證難的問題　11.1 復(fù)雜度層次　11.2 確定型圖靈機(jī)的空間層次　11.3 一個需要指數(shù)時間和空問的問題　11.4 一個非基本的問題第12章 算術(shù)運(yùn)算的下界　12.1 域　12.2 再論直線狀代碼　12.3 問題的矩陣表述　12.4 面向行的矩陣乘法的下界　12.5 面向列的矩陣乘法的下界　12.6 面向行和列的矩陣乘法的下界　12.7 預(yù)處理附錄 算法的C/C++代碼參考文獻(xiàn)

圖書封面

圖書標(biāo)簽Tags

無

評論、評分、閱讀與下載

---

    計算機(jī)算法的設(shè)計與分析 PDF格式下載

---