發表於2024-12-23
MIT四大名師聯手鑄就,影響全球韆萬程序員的“算法聖經”!國內外韆餘所高校采用!
相關好書推薦:
更多精彩,點擊進入品牌店查閱>>
在有關算法的書中,有一些敘述非常嚴謹,但不夠全麵;另一些涉及瞭大量的題材,但又缺乏嚴謹性。《算法導論(原書第3版)/計算機科學叢書》將嚴謹性和全麵性融為一體,深入討論各類算法,並著力使這些算法的設計和分析能為各個層次的讀者接受。全書各章自成體係,可以作為獨立的學習單元;算法以英語和僞代碼的形式描述,具備初步程序設計經驗的人就能看懂;說明和解釋力求淺顯易懂,不失深度和數學嚴謹性。
《算法導論(原書第3版)/計算機科學叢書》全書選材經典、內容豐富、結構閤理、邏輯清晰,對本科生的數據結構課程和研究生的算法課程都是非常實用的教材,在IT專業人員的職業生涯中,《算法導論(原書第3版)/計算機科學叢書》也是一本案頭必備的參考書或工程實踐手冊。
第3版的主要變化:
·新增瞭van Emde Boas樹和多綫程算法,並且將矩陣基礎移至附錄。
·修訂瞭遞歸式(現在稱為“分治策略”)那一章的內容,更廣泛地覆蓋分治法。
·移除兩章很少講授的內容:二項堆和排序網絡。
·修訂瞭動態規劃和貪心算法相關內容。
·流網絡相關材料現在基於邊上的全部流。
·由於關於矩陣基礎和Strassen算法的材料移到瞭其他章,矩陣運算這一章的內容所占篇幅更小。
·修改瞭對Knuth-Morris-Pratt字符串匹配算法的討論。
·新增100道練習和28道思考題,還更新並補充瞭參考文獻。
Thomas H. Cormen (托馬斯·科爾曼),達特茅斯學院計算機科學係教授、係主任。目前的研究興趣包括:算法工程、並行計算、具有高延遲的加速計算。他分彆於1993年、1986年獲得麻省理工學院電子工程和計算機科學博士、碩士學位,師從Charles E. Leiserson教授。由於他在計算機教育領域的突齣貢獻,Cormen教授榮獲2009年ACM傑齣教員奬。
Charles E. Leiserson(查爾斯·雷瑟爾森),麻省理工學院計算機科學與電氣工程係教授,Margaret MacVicar Faculty Fellow。他目前主持MIT超級計算技術研究組,並是MIT計算機科學和人工智能實驗室計算理論研究組的成員。他的研究興趣集中在並行和分布式計算的理論原理,尤其是與工程現實相關的技術研究。Leiserson教授擁有卡內基·梅隆大學計算機科學博士學位,還是ACM、IEEE和SIAM的會士。
Ronald L. Rivest (羅納德·李維斯特),現任麻省理工學院電子工程和計算機科學係安德魯與厄納·維特爾比(Andrew and Erna Viterbi)教授。他是MIT計算機科學和人工智能實驗室的成員,並領導著其中的信息安全和隱私中心。他1977年從斯坦福大學獲得計算機博士學位,主要從事密碼安全、計算機安全算法的研究。他和Adi Shamir和Len Adleman一起發明瞭RSA公鑰算法,這個算法在信息安全中獲得大的突破,這一成果也使他和Shamir、Adleman一起得到2002年ACM圖靈奬。他現在擔任國傢密碼學會的負責人。
Clifford Stein(剋利福德·斯坦),哥倫比亞大學計算機科學係和工業工程與運籌學係教授,他還是工業工程與運籌學係的係主任。在加入哥倫比亞大學大學之前,他在達特茅斯學院計算機科學係任教9年。Stein教授擁有MIT碩士和博士學位。他的研究興趣包括:算法的設計與分析,組閤優化、運籌學、網絡算法、調度、算法工程和生物計算。
★“鑒於數據量的爆炸性增長,和計算應用的多樣性,現在比以往更需要有效算法。這本書條理清晰,是一本非常好的算法設計與分析方麵的導論性書籍。每章前半部分介紹瞭講授和學習算法的有效方法,後半部分為更專業的讀者和求知欲強的學生提供瞭更引人入勝的資料來討論這個迷人領域的各種可能性和挑戰。”
——Shang-Hua Teng(騰尚華),南加州大學維特比工學院計算機係Seeley G. Mudd 教授
★“本書是算法領域的一部經典著作,書中係統、全麵地介紹瞭現代算法:從較快算法和數據結構到用於看似難以解決問題的多項式時間算法;從圖論中的經典算法到用於字符匹配、計算集閤和數論的特殊算法。本書第3版尤其增加瞭兩章專門討論van Emde Boas樹(有用的數據結構之一)和多綫程算法(日益重要的一個主題)。”
——Daniel Spielman,耶魯大學計算機科學和應用數學Henry Ford II教授
齣版者的話
譯者序
前言
第一部分 基礎知識
第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 矩陣乘法的Strassen算法
4.3 用代入法求解遞歸式
4.4 用遞歸樹方法求解遞歸式
4.5 用主方法求解遞歸式
4.6 證明主定理
4.6.1 對b的冪證明主定理
4.6.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.2 可閤並堆操作
19.3 關鍵字減值和刪除一個結點
19.4 最大度數的界
思考題
本章注記
第20章 van Emde Boas樹
20.1 基本方法
20.2 遞歸結構
20.2.1 原型van Emde Boas結構
20.2.2 原型van Emde Boas結構上的操作
20.3 van Emde Boas樹及其操作
20.3.1 van Emde Boas樹
20.3.2 van Emde Boas樹的操作
思考題
本章注記
第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�瞁arshall算法
25.3 用於稀疏圖的Johnson算法
思考題
本章注記
第26章 最大流
26.1 流網絡
26.2 FordFulkerson方法
26.3 最大二分匹配
26.4 推送重貼標簽算法
26.5 前置重貼標簽算法
思考題
本章注記
第七部分 算法問題選編
第27章 多綫程算法
27.1 動態多綫程基礎
27.2 多綫程矩陣乘法
27.3 多綫程歸並排序
思考題
本章注記
第28章 矩陣運算
28.1 求解綫性方程組
28.2 矩陣求逆
28.3 對稱正定矩陣和最小二乘逼近
思考題
本章注記
第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 RabinKarp算法
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 二項分布的尾部
思考題
附錄注記
附錄D 矩陣
D.1 矩陣與矩陣運算
D.2 矩陣基本性質
思考題
附錄注記
參考文獻
索引
證明 每個結點的秩從0開始,並且隻有執行瞭LINK操作,它纔會增加。因為最多有n—1個UNION操作,所以同樣最多有n—1個LINK操作。因為每個LINK操作或者不改變任何的秩,或者將某結點的秩加1,所以所有的秩最大為n—1。
引理21.6提供瞭一個關於結點秩的較弱的界。事實上,每個結點的秩最大為(lgn)(見練習21.4—2)。然而,引理21.6的這個較鬆的界已足夠滿足我們的要求。
時間界的證明 我們將利用攤還分析中的勢方法(見17.3節)來證明O(ma(n))的時間界。在進行攤還分析時,為瞭方便起見,我們假設不調用UNION操作,而是調用LINK操作。也就是說,因為LINK過程的參數是指嚮兩個根的指針,故我們獨立使用相應的FIND—SET操作。下麵的引理說明即使因調用UNION而導緻額外的FIND—SET操作,其漸近運行時間仍然保持不變。
……
在計算機齣現之前,就有瞭算法。現在有瞭計算機,就需要更多的算法,算法是計算的核心。
本書提供瞭對當代計算機算法研究的一個全麵、綜閤的介紹。書中給齣瞭多個算法,並對它們進行瞭較為深入的分析,使得這些算法的設計和分析易於被各個層次的讀者所理解。我們力求在不犧牲分析的深度和數學嚴密性的前提下,給齣深入淺齣的說明。
書中每一章都給齣瞭一個算法、一種算法設計技術、一個應用領域或一個相關的主題。算法是用英語和一種“僞代碼”來描述的,任何有一點程序設計經驗的人都能看得懂。書中給齣瞭244幅圖,說明各個算法的工作過程。我們強調將算法的效率作為一種設計標準,對書中的所有算法,都給齣瞭關於其運行時間的詳細分析。
本書主要供本科生和研究生的算法或數據結構課程使用。因為書中討論瞭算法設計中的工程問題及其數學性質,所以,本書也可以供專業技術人員自學之用。
本書是第3版。在這個版本裏,我們對全書進行瞭更新,包括新增瞭若乾章、修訂瞭僞代碼等。
緻使用本書的教師
本書的設計目標是全麵、適用於多種用途。它可用於若乾課程,從本科生的數據結構課程到研究生的算法課程。由於書中給齣的內容比較多,隻講一學期一般講不完,因此,教師們應該將本書看成是一種“緩存區”或“瑞典式自助餐”,從中挑選齣能最好地支持自己希望教授的課程的內容。
教師們會發現,要圍繞自己所需的各個章節來組織課程是比較容易的。書中的各章都是相對獨立的,因此,你不必擔心意想不到的或不必要的各章之間的依賴關係。每一章都是以節為單位,內容由易到難。如果將本書用於本科生的課程,可以選用每一章的前麵幾節內容;用於研究生的課程中,則可以完整地講授每一章。
全書包含957道練習和158道思考題。每一節結束時給齣練習,每一章結束時給齣思考題。練習一般比較短,用於檢查學生對書中內容的基本掌握情況。有一些是簡單的自查性練習,有一些則要更充實,可以作為傢庭作業布置給學生。每一章後的思考題都是一些敘述較為詳細的實例研究,它們常常會介紹一些新的知識。一般來說,這些思考題都會包含幾個小問題,引導學生逐步得到問題的解。
鑒於本書前幾版使用的反饋,我們在本書配套網站上公布瞭其中一些練習和思考題的答案(但不是全部)。我們會定期更新這些答案,因此需要教師每次授課前都到這個網站上來查看。
在那些不太適閤本科生、更適閤研究生的章節和練習前麵,都加上瞭星號(�常�。帶星號的章節也不一定就比不帶星號的更難,但可能要求瞭解更多的數學知識。類似地,帶星號的練習可能要求有更好的數學背景或創造力。
緻使用本書的學生
希望本教材能為學生們提供關於算法這一領域的有趣介紹。我們力求使書中給齣的每一個算法都易於理解和有趣。為瞭在同學們遇到不熟悉或比較睏難的算法時提供幫助,我們逐個步驟地描述每一個算法。此外,為瞭便於大傢理解書中對算法的分析,對於其中所需的數學知識,我們給齣瞭詳細的解釋。如果對某一主題已經有所瞭解,會發現根據書中各章的編排順序,可以跳過一些介紹性的小節,直接閱讀更高級的內容。
本書是一本大部頭著作,讀者所修的課程可能隻講授其中的一部分。我們試圖使它能成為一本現在對讀者有用的教材,將來在讀者的職業生涯中,也能成為一本案頭的數學參考書或工程實踐手冊。
閱讀本書需要哪些預備知識呢·
讀者需要有一些程序設計方麵的經驗,尤其需要理解遞歸過程和簡單的數據結構,如數組和鏈錶。
讀者應該能較為熟練地利用數學歸納法進行證
算法導論(原書第3版)/計算機科學叢書 [Introduction to Algorithms, third edition] 下載 mobi epub pdf txt 電子書 格式
算法導論(原書第3版)/計算機科學叢書 [Introduction to Algorithms, third edition] 下載 mobi pdf epub txt 電子書 格式 2024
算法導論(原書第3版)/計算機科學叢書 [Introduction to Algorithms, third edition] 下載 mobi epub pdf 電子書¥32.80
評分兒子喜好的專業,喜好的書籍,很不錯方便便利
評分書是好書,618京東優惠力度很大,一口氣買瞭好幾本。
評分本科是學硬件的,後來又轉軟件瞭。任何一個程序員瞭解更多的底層原理都有很好的提升吧
評分有點失望。剛到就翻著看看。
評分剛拿到 還沒開始看 不過會加油的(? •?_•?)?
評分強生(Johnson & Johnson)邦迪傢庭全能組閤裝68片 輕薄透氣創可貼32片+透明防水創可貼20片+彈性創可貼16片
評分不錯^_^^_^^_^^_^^_^^_^^_^^_^^_^^_^^_^
評分看看。得往jvm虛擬機方嚮發展發展瞭。
算法導論(原書第3版)/計算機科學叢書 [Introduction to Algorithms, third edition] mobi epub pdf txt 電子書 格式下載 2024