算法詳解 卷3 貪心算法和動態(tài)規(guī)劃
定 價：69.8 元
- 作者：[美]蒂姆·拉夫加登（TimRoughgarden）
- 出版時間：2023/7/1
- ISBN：9787115563347
- 出 版 社：人民郵電出版社
- 中圖法分類：TP301.6
- 頁碼：
- 紙張：膠版紙
- 版次：
- 開本：128開
“算法詳解”系列圖書共有4卷，本書是第3卷—貪心算法和動態(tài)規(guī)劃。其中貪心算法主要包括調(diào)度、最小生成樹、聚類、哈夫曼編碼等，動態(tài)規(guī)劃主要包括背包、序列對齊、最短路徑、最佳搜索樹等。本書的每一章均有小測驗和章末習題，這將為讀者的自我檢查以及進一步學習提供方便。
本書作者提供豐富而實用的資源，能夠幫助讀者提升算法思維能力。本書適合計算機專業(yè)的高校教師和學生、想要培養(yǎng)和訓練算法思維、計算思維的IT專業(yè)人士，以及面試官和正在準備面試的應聘者閱讀、參考。
1.哥倫比亞大學計算機科學系教授多年教學經(jīng)驗的結(jié)晶，深入淺出帶你了解計算機科學的核心與靈魂。
2.內(nèi)容豐富，邏輯清晰。細致講解算法廣泛的應用范圍，夯實計算機基礎。
3.適合程序員學習的算法秘籍。能有效培養(yǎng)更縝密的思維，成功應對各種場合的技術(shù)面試。
蒂姆·拉夫加登（Tim Roughgarden）是哥倫比亞大學計算機科學系的教授，之前曾任教于斯坦福大學計算機科學系，他從2004年開始教授和研究算法。本書是他的《算法詳解》四部曲的第三卷，基于他從2012年開始定期舉行的在線算法課程編寫。
目 錄
第 1章 貪心算法概述1
1.1 貪心算法設計范例1
1.1.1 算法設計范例1
1.1.2 貪心算法設計范例的特性2
1.2 一個調(diào)度問題4
1.2.1 問題的設定4
1.2.2 競爭時間4
1.2.3 目標函數(shù)5
1.2.4 小測驗1.1的答案6
1.3 開發(fā)一種貪心算法6
1.3.1 兩種特殊情況7
1.3.2 貪心算法之間的競爭7
1.3.3 小測驗1.2～1.3的答案10
1.4 正確性證明11
1.4.1 沒有平局時的情況：高層計劃12
1.4.2 在相鄰逆序?qū)χ薪粨Q作業(yè)13
1.4.3 成本收益分析14
1.4.4 處理平局的情況15
1.4.5 小測驗1.4～1.5的答案17
1.5 本章要點18
1.6 章末習題19
第 2章 哈夫曼編碼21
2.1 編碼21
2.1.1 固定長度的二進制編碼21
2.1.2 可變長度的編碼22
2.1.3 非前綴編碼23
2.1.4 非前綴編碼的優(yōu)點23
2.1.5 問題定義24
2.1.6 小測驗2.1～2.2的答案25
2.2 編碼和樹26
2.2.1 3個例子26
2.2.2 什么樣的樹表示非前綴編碼28
2.2.3 問題定義（精練版）28
2.3 哈夫曼的貪心算法29
2.3.1 通過連續(xù)的歸并創(chuàng)建樹29
2.3.2 哈夫曼的貪心準則32
2.3.3 偽碼32
2.3.4 例子34
2.3.5 一個更復雜的例子34
2.3.6 運行時間37
2.3.7 小測驗2.3的答案37
*2.4 正確性證明38
2.4.1 高層計劃38
2.4.2 細節(jié)39
2.5 本章要點44
2.6 章末習題45
第3章 最小生成樹47
3.1 問題定義47
3.1.1 圖47
3.1.2 生成樹48
3.1.3 小測驗3.1的答案50
3.2 Prim算法51
3.2.1 例子51
3.2.2 偽碼53
3.2.3 簡單的實現(xiàn)55
*3.3 通過堆提升Prim算法的速度56
3.3.1 探求接近線性的運行時間56
3.3.2 堆數(shù)據(jù)結(jié)構(gòu)56
3.3.3 如何在Prim算法中使用堆57
3.3.4 基于堆的實現(xiàn)的偽碼59
3.3.5 運行時間分析61
3.3.6 小測驗3.3的答案61
*3.4 Prim算法：正確性證明62
3.4.1 最小瓶頸屬性62
3.4.2 生成樹的一些有趣結(jié)論65
3.4.3 定理3.4（MBP意味著MST）的證明67
3.4.4 綜合運用69
3.5 Kruskal算法69
3.5.1 例子69
3.5.2 Kruskal算法的偽碼71
3.5.3 Kruskal算法的簡單實現(xiàn)72
*3.6 通過合并查找對Kruskal算法進行加速73
3.6.1 合并查找數(shù)據(jù)結(jié)構(gòu)73
3.6.2 基于合并查找的實現(xiàn)的偽碼75
3.6.3 基于合并查找的實現(xiàn)的運行時間分析76
3.6.4 合并查找的快速有余而嚴謹不足的實現(xiàn)：父圖77
3.6.5 小測驗3.5～3.7的答案82
*3.7 Kruskal算法的正確性證明83
3.8 應用：單鏈集群85
3.8.1 集群85
3.8.2 自底向上的集群86
3.9 本章要點88
3.10 章末習題89
第4章 動態(tài)規(guī)劃概述93
4.1 加權(quán)獨立集合問題94
4.1.1 問題定義94
4.1.2 自然的貪心算法失敗了95
4.1.3 分治算法可行嗎96
4.1.4 小測驗4.1～4.2的答案97
4.2 路徑圖的WIS問題的線性時間算法98
4.2.1 最優(yōu)子結(jié)構(gòu)和推導公式98
4.2.2 一種不成熟的遞歸方法100
4.2.3 使用緩存的遞歸算法101
4.2.4 一種迭代式的自底向上的實現(xiàn)103
4.2.5 小測驗4.3～4.4的答案104
4.3 一種重建算法105
4.4 動態(tài)規(guī)劃的原則107
4.4.1 3個步驟的配方107
4.4.2 子問題的期望屬性108
4.4.3 一個可重復的思維過程109
4.4.4 動態(tài)規(guī)劃和分治算法的區(qū)別109
4.4.5 為什么叫“動態(tài)規(guī)劃”110
4.5 背包問題111
4.5.1 問題定義111
4.5.2 最優(yōu)子結(jié)構(gòu)和推導公式113
4.5.3 子問題115
4.5.4 一種動態(tài)規(guī)劃算法115
4.5.5 例子117
4.5.6 重建117
4.5.7 小測驗4.5～4.6的答案118
4.6 本章要點119
4.7 章末習題120
第5章 高級動態(tài)規(guī)劃123
5.1 序列對齊123
5.1.1 驅(qū)動力123
5.1.2 問題定義124
5.1.3 最優(yōu)子結(jié)構(gòu)126
5.1.4 推導公式129
5.1.5 子問題129
5.1.6 一種動態(tài)規(guī)劃算法130
5.1.7 重新構(gòu)建131
5.1.8 小測驗5.1～5.3的答案132
*5.2 最優(yōu)二叉搜索樹133
5.2.1 二叉搜索樹回顧134
5.2.2 平均搜索時間135
5.2.3 問題定義136
5.2.4 最優(yōu)子結(jié)構(gòu)137
5.2.5 推導公式141
5.2.6 子問題142
5.2.7 一種動態(tài)規(guī)劃算法143
5.2.8 改善運行時間145
5.2.9 小測驗5.4～5.5的答案145
5.3 本章要點146
5.4 章末習題147
第6章 再論最短路徑算法150
6.1 邊長可能為負的最短路徑150
6.1.1 單源最短路徑問題150
6.1.2 負環(huán)152
6.1.3 小測驗6.1的答案154
6.2 Bellman-Ford算法154
6.2.1 子問題155
6.2.2 最優(yōu)子結(jié)構(gòu)156
6.2.3 推導公式158
6.2.4 什么時候應該停止159
6.2.5 偽碼160
6.2.6 Bellman-Ford算法的例子161
6.2.7 Bellman-Ford算法的運行時間164
6.2.8 Internet路由165
6.2.9 小測驗6.2～6.3的答案165
6.3 所有頂點對的最短路徑問題166
6.3.1 問題定義166
6.3.2 簡化為單源最短路徑167
6.3.3 小測驗6.4的答案168
6.4 Floyd-Warshall算法168
6.4.1 子問題168
6.4.2 最優(yōu)子結(jié)構(gòu)170
6.4.3 偽碼172
6.4.4 檢測負環(huán)174
6.4.5 Floyd-Warshall算法的總結(jié)和開放性問題175
6.4.6 小測驗6.5～6.6的答案176
6.5 本章要點177
6.6 章末習題178
附錄 章末習題答案節(jié)選180
后記 算法設計工作指南187
書單推薦
