算法概論

定　價：￥39.99

作　者：	（美國）Sanjoy Dasgupta，（美國）Christos Papadimitriou，（美國）Umesh Vazirani 著；王沛、唐揚斌、劉齊軍譯
出版社：	清華大學出版社
叢編項：	國外經(jīng)典教材
標　簽：	數(shù)值分析

購買這本書可以去

ISBN：	9787302179399	出版時間：	2008-01-01	包裝：	平裝
開本：	16	頁數(shù)：	345	字數(shù)：

內(nèi)容簡介

　　本書系統(tǒng)全面地介紹了算法的基本知識。這些知識和技巧既是高等院?！八惴ㄅc數(shù)據(jù)結構”課程的主要內(nèi)容，也是計算機科學蓬勃發(fā)展的理論基礎。本書涵蓋了絕大多數(shù)算法設計中的常用技術。在表達每一種技術時，闡述它的應用背景，強調(diào)每個算法運轉背后的簡潔數(shù)學思想，注意運用與其他技術類比的方法來說明它的特征，并提供了大量相應實際問題的例子。本書同時也注重了對每一種算法的復雜性分析。全書共10章，從基本的數(shù)字算法人手，先后介紹了分治、圖的遍歷、貪心算法、動態(tài)規(guī)劃、線性規(guī)劃等技術，對NP完全問題進行廠基本而清晰的闡述，對隨機算法、近似算法和量子算法這些近年來發(fā)展迅猛的領域也花費了一定的筆墨。書中每章后面都附有大量的習題，有利于讀者對書中內(nèi)容的理解和應用。

作者簡介

　　Sanjoy Dasgupta于2002年在加州大學伯克利分校獲得計算機科學專業(yè)的博土學位。他是AT&T實驗室的高級技術人員。他的工作重點是研究數(shù)據(jù)挖掘的算法，對業(yè)務數(shù)據(jù)的語音識別和分析的應用。他在多維數(shù)據(jù)的統(tǒng)計分析的開發(fā)算法領域獲得很重要的研究成果。

圖書目錄

第0章序言
0.1 書籍和算法
0.2 從Fibonacci數(shù)列開始
0.3 大O符號
習題
第1章數(shù)字的算法
1.1 基本算術
1.1.1 加法
1.1.2 乘法和除法
1.2 模運算
1.2.1 模的加法和乘法
1.2.2 模的指數(shù)運算
1.2.3 Euclid的最大公因數(shù)算法
1.2.4 Euclid算法的一種擴展
1.2.5 模的除法
1.3 素性測試
1.4 密碼學
1.4.1 密鑰機制：一次一密亂碼本和AES
1.4.2 RSA
1.5 通用散列表
1.5.1 散列表
1.5.2 散列函數(shù)族
習題
第2章分治算法
2.1 乘法
2.2 遞推式
2.3 合并排序
2.4 尋找中項
2.5 矩陣乘法
2.6 快速Fourier變換
2.6.1 多項式的另一種表示法
2.6.2 計算步驟的分治實現(xiàn)
2.6.3 插值
2.6.4 快速Fourier變換的細節(jié)
習題
第3章圖的分解
3.1 為什么是圖
3.2 無向圖的深度優(yōu)先搜索
3.2.1 迷宮探索
3.2.2 深度優(yōu)先搜索
3.2.3 無向圖的連通性
3.2.4 前序和后序
3.3 有向圖的深度優(yōu)先搜索
3.3.1 邊的類型
3.3.2 有向無環(huán)圖
3.4 強連通部件
3.4.1 定義有向圖的連通性
3.4.2 一個有效的算法
習題
第4章圖中的路徑
4.1 距離
4.2 廣度優(yōu)先搜索
4.3 邊的長度
4.4 Dijkstra算法
4.4.1 廣度優(yōu)先搜索的一個改進
4.4.2 另一種解釋
4.4.3 運行時間
4.5 優(yōu)先隊列的實現(xiàn)
4.5.1 數(shù)組
4.5.2 二分堆
4.5.3 d堆
4.6 含有負邊的圖的最短路徑
4.6.1 負邊
4.6.2 負環(huán)
4.7 有向無環(huán)圖中的最短路徑
習題
第5章貪心算法
5.1 最小生成樹
5.1.1 一個貪心方法
5.1.2 分割性質
5.1.3 Kruskal算法
5.1.4 一種用于分離集的數(shù)據(jù)結構
5.1.5 Prim算法
5.2 Huffman編碼
5.3 Horn公式
5.4 集合覆蓋
習題
第6章動態(tài)規(guī)劃
6.1 重新審視有向無環(huán)圖的最短路徑問題
6.2 最長遞增子序列
6.3 編輯距離
6.4 背包問題
6.5 矩陣鏈式相乘
6.6 最短路徑問題
6.7 樹中的獨立集
習題
第7章線性規(guī)劃與歸約
7.1 線性規(guī)劃簡介
7.1.1 示例：利潤最大化
7.1.2 示例：生產(chǎn)計劃
7.1.3 示例：最優(yōu)帶寬分配
7.1.4 線性規(guī)劃的變體
7.2 網(wǎng)絡流
7.2.1 石油運輸
7.2.2 最大流
7.2.3 對算法的深入觀察
7.2.4 最優(yōu)性的保證
7.2.5 算法的效率
7.3 二部圖的匹配
7.4 對偶
7.5 零和博弈(游戲)
7.6 單純形算法
7.6.1 n維空間中的頂點和鄰居
7.6.2 算法
7.6.3 補遺
7.6.4 單純形法的運行時間
7.7 后記：電路值1
習題
第8章 NP-完全問題
8.1 搜索問題
8.2 NP-完全問題
8.3 所有的歸約
習題
第9章 NP-完全問題的處理
9.1 智能窮舉搜索
9.1.1 回溯
9.1.2 分支定界
9.2 近似算法
9.2.1 頂點覆蓋
9.2.2 聚類
9.2.3 TSP
9.2.4 背包問題
9.2.5 逼近的層次
9.3 局部搜索中的啟發(fā)方法
9.3.1 重新審視旅行商問題
9.3.2 圖劃分
9.3.3 處理局部最優(yōu)
習題
第10章量子算法
10.1 量子位元、疊加狀態(tài)和度量
10.2 算法設計
10.3 量子傅立葉變換
10.4 周期性
10.5 量子電路
10.5.1 基本量子門
10.5.2 量子電路的兩種基本類型
10.5.3 量子傅立葉變換電路
10.6 將因子分解問題轉化為周期求解問題
10.7 因子分解的量子算法
習題
歷史背景及深入閱讀的資