Introduction to Algorithms

Introduction to Algorithms

《IntroductiontoAlgorithms》是2005年MitPr出版的圖書,作者是Cormen,ThomasH.(EDT。

基本信息

作者: Cormen, Thomas H. (EDT)/ Leiserson, Charles E./ Rivest, Ronald L./ Stein, Clifford

出版社:Mit Pr

ISBN:0262032937

上架時間:2008-3-31

出版日期:2005 年7月

頁碼:1180

內容簡介

《Introduction to Algorithms》譯作《算法導論》,是由Thomas H.Cormen, Charles E.Leiserson 等人編寫的十分經典的計算機算法書籍。本書以相當的深度介紹了許多常用的數據結構和有效的算法,使得這些算法的設計和分析易於被各個層次的讀者所理解。本書被china-pub會員評為“2007年我最喜愛的十大技術圖書”之一,被《程式設計師》等機構評選為2006年最受讀者喜愛的十大IT圖書之一 。

《算法導論》自第一版出版以來,已經成為世界範圍內廣泛使用的大學教材和專業人員的標準參考手冊。本書全面論述了算法的內容,從一定深度上涵蓋了算法的諸多方面,同時其講授和分析方法又兼顧了各個層次讀者的接受能力。各章內容自成體系,可作為獨立單元學習。所有算法都用英文和偽碼描述,使具備初步編程經驗的人也可讀懂。全書講解通俗易懂,且不失深度和數學上的嚴謹性。第二版增加了新的章節,如算法作用、機率分析與隨機算法、線性編程等,幾乎對第一版的各個部分都作了大量修訂。

作者簡介

Thomas H.Cormen ,達特茅斯學院計算機科學系副教授

Charles E.Leiserson ,麻省理工學院計算機科學與電氣工程系教授

Ronald L.Rivest ,麻省理工學院計算機科學系Andrew與Erna Viterbi具名教授

Clifford Stein ,哥倫比亞大學工業工程與運籌學副教授

目錄

出版者的話

專家指導委員會

譯者序.

前言

第一部分 基礎知識

引言

第1章 算法在計算中的作用

1.1 算法

1.2 作為一種技術的算法

第2章 算法入門

2.1 插入排序

2.2 算法分析

2.3 算法設計

2.3.1 分治法

2.3.2 分治法分析

第3章 函式的增長

3.1 漸近記號

3.2 標準記號和常用函式

第4章 遞歸式

4.1 代換法

.4.2 遞歸樹方法

4.3 主方法

*4.4 主定理的證明

4.4.1 取正合冪時的證明

4.4.2 上取整函式和下取整函式

第5章 機率分析和隨機算法

5.1 雇用問題

5.2 指示器隨機變數

5.3 隨機算法

*5.4 機率分析和指示器隨機變數的進一步使用

5.4.1 生日悖論

5.4.2 球與盒子

5.4.3 序列

5.4.4 線上雇用問題

第二部分 排序和順序統計學

引言

第6章 堆排序

6.1 堆

6.2 保持堆的性質

6.3 建堆

6.4 堆排序算法

6.5 優先權佇列

第7章 快速排序

7.1 快速排序的描述

7.2 快速排序的性能

7.3 快速排序的隨機化版本

7.4 快速排序分析

7.4.1 最壞情況分析

7.4.2 期望的運行時間

第8章 線性時間排序

8.1 排序算法時間的下界

8.2 計數排序

8.3 基數排序

8.4 桶排序

第9章 中位數和順序統計學

9.1 最小值和最大值

9.2 以期望線性時間做選擇

9.3 最壞情況線性時間的選擇

第三部分 數據結構

引言

第10章 基本數據結構

10.1 棧和佇列

10.2 鍊表

10.3 指針和對象的實現

10.4 有根樹的表示

第11章 散列表

11.1 直接定址表

11.2 散列表

11.3 散列函式

11.3.1 除法散列法

11.3.2 乘法散列法

*11.3.3 全域散列

11.4 開放定址法

*11.5 完全散列

第12章 二叉查找樹

12.1 二叉查找樹

12.2 查詢二叉查找樹

12.3 插入和刪除

*12.4 隨機構造的二叉查找樹

第13章 紅黑樹

13.1 紅黑樹的性質

13.2 旋轉

13.3 插入

13.4 刪除

第14章 數據結構的擴張

14.1 動態順序統計

14.2 如何擴張數據結構

14.3 區間樹

第四部分 高級設計和分析技術

導論

第15章 動態規劃

15.1 裝配線調度

15.2 矩陣鏈乘法

15.3 動態規劃基礎

15.4 最長公共子序列

15.5 最優二叉查找樹

第16章 貪心算法

16.1 活動選擇問題

16.2 貪心策略的基本內容

16.3 赫夫曼編碼

*16.4 貪心法的理論基礎

*16.5 一個任務調度問題

第17章 平攤分析

17.1 聚集分析

17.2 記賬方法

17.3 勢能方法

17.4 動態表..

17.4.1 表擴張

17.4.2 表擴張和收縮

第五部分 高級數據結構

概述

第18章 b樹

18.1 b樹的定義

18.2 對b樹的基本操作

18.3 從b樹中刪除關鍵字

第19章 二項堆

19.1 二項樹與二項堆

19.1.1 二項樹

19.1.2 二項堆

19.2 對二項堆的操作

第20章 斐波那契堆

20.1 斐波那契堆的結構

20.2 可合併堆的操作

20.3 減小一個關鍵字與刪除一個結點

20.4 最大度數的界

第21章 用於不相交集合的數據結構

21.1 不相交集合上的操作

21.2 不相交集合的鍊表表示

21.3 不相交集合森林

*21.4 帶路徑壓縮的按秩合併的分析

第六部分 圖 算 法

引言

第22章 圖的基本算法

22.1 圖的表示

22.2 廣度優先搜尋

22.3 深度優先搜尋

22.4 拓撲排序

22.5 強連通分支

第23章 最小生成樹

23.1 最小生成樹的形成

23.2 kruskal算法和prim算法

第24章 單源最短路徑

24.1 bellman-ford算法

24.2 有向無迴路圖中的單源最短路徑

24.3 dijkstra算法

24.4 差分約束與最短路徑

24.5 最短路徑性質的證明

第25章 每對頂點間的最短路徑

25.1 最短路徑與矩陣乘法

25.2 floyd-warshall算法

25.3 稀疏圖上的johnson算法

第26章 最大流

26.1 流網路

26.2 ford-fulkerson方法

26.3 最大二分匹配

*26.4 壓入與重標記算法

*26.5 重標記與前移算法

第七部分 算法研究問題選編

引言

第27章 排序網路

27.1 比較網路

27.2 0-1原理

27.3 雙調排序網路

27.4 合併網路

27.5 排序網路

第28章 矩陣運算

28.1 矩陣的性質

28.2 矩陣乘法的strassen算法

28.3 求解線性方程組

28.4 矩陣求逆

28.5 對稱正定矩陣與最小二乘逼近

第29章 線性規劃

29.1 標準型和鬆弛型

29.2 將問題表達為線性規劃

29.3 單純形算法

29.4 對偶性

29.5 初始基本可行解

第30章 多項式與快速傅立葉變換

30.1 多項式的表示

30.2 dft與fft

30.3 有效的fft實現

第31章 有關數論的算法

31.1 初等數論概念

31.2 最大公約數

31.3 模運算

31.4 求解模線性方程

31.5 中國餘數定理

31.6 元素的冪

31.7 rsa公鑰加密系統

*31.8 素數的測試

*31.9 整數的因子分解

第32章 字元串匹配

32.1 樸素的字元串匹配算法

32.2 rabin-karp算法

32.3 利用有限自動機進行字元串匹配

*32.4 knuth-morris-pratt算法

第33章 計算幾何學

33.1 線段的性質

33.2 確定任意一對線段是否相交

33.3 尋找凸包

33.4 尋找最近點對

第34章 np完全性

34.1 多項式時間

34.2 多項式時間的驗證

34.3 np完全性與可歸約性

34.4 np完全性的證明

34.5 np完全問題

34.5.1 團問題

34.5.2 頂點覆蓋問題

34.5.3 哈密頓迴路問題

34.5.4 旅行商問題

34.5.5 子集和問題

第35章 近似算法

35.1 頂點覆蓋問題

35.2 旅行商問題

35.2.1 滿足三角不等式的旅行商問題

35.2.2 一般旅行商問題

35.3 集合覆蓋問題

35.4 隨機化和線性規劃

35.5 子集和問題

第八部分 附錄:數學基礎知識

引言

a 求和

a.1 求和公式及其性質

a.2 確定求和時間的界

b 集合等離散數學結構

b.1 集合

b.2 關係

b.3 函式

b.4 圖

b.5 樹

b.5.1 自由樹

b.5.2 有根樹和有序樹

b.5.3 二叉樹與位置樹

c 計數和機率

c.1 計數

c.2 機率

c.3 離散隨機變數

c.4 幾何分布與二項分布

c.5 二項分布的尾

參考文獻

索引...

相關詞條

熱門詞條

聯絡我們