掃一掃
關注中圖網
官方微博
本類五星書更多>
-
>
全國計算機等級考試最新真考題庫模擬考場及詳解·二級MSOffice高級應用
-
>
決戰行測5000題(言語理解與表達)
-
>
軟件性能測試.分析與調優實踐之路
-
>
第一行代碼Android
-
>
JAVA持續交付
-
>
EXCEL最強教科書(完全版)(全彩印刷)
-
>
深度學習
算法詳解 卷3 貪心算法和動態規劃 版權信息
- ISBN：9787115563347
- 條形碼：9787115563347 ; 978-7-115-56334-7
- 裝幀：平裝
- 冊數：暫無
- 重量：暫無
- 所屬分類：>
算法詳解 卷3 貪心算法和動態規劃 本書特色
1.哥倫比亞大學計算機科學系教授多年教學經驗的結晶，深入淺出帶你了解計算機科學的核心與靈魂。
2.內容豐富，邏輯清晰。細致講解算法廣泛的應用范圍，夯實計算機基礎。
3.適合程序員學習的算法秘籍。能有效培養更縝密的思維，成功應對各種場合的技術面試。
算法詳解 卷3 貪心算法和動態規劃 內容簡介
“算法詳解”系列圖書共有4卷，本書是第3卷—貪心算法和動態規劃。其中貪心算法主要包括調度、*小生成樹、聚類、哈夫曼編碼等，動態規劃主要包括背包、序列對齊、*短路徑、很好搜索樹等。本書的每一章均有小測驗和章末習題，這將為讀者的自我檢查以及進一步學習提供方便。 本書作者提供豐富而實用的資源，能夠幫助讀者提升算法思維能力。本書適合計算機專業的高校教師和學生、想要培養和訓練算法思維、計算思維的IT專業人士，以及面試官和正在準備面試的應聘者閱讀、參考。
算法詳解 卷3 貪心算法和動態規劃 目錄
目 錄
第 1章 貪心算法概述 1
1.1 貪心算法設計范例 1
1.1.1 算法設計范例 1
1.1.2 貪心算法設計范例的特性 2
1.2 一個調度問題 4
1.2.1 問題的設定 4
1.2.2 競爭時間 4
1.2.3 目標函數 5
1.2.4 小測驗1.1的答案 6
1.3 開發一種貪心算法 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 在相鄰逆序對中交換作業 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 非前綴編碼的優點 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 通過連續的歸并創建樹 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 細節 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 簡單的實現 55
*3.3 通過堆提升Prim算法的速度 56
3.3.1 探求接近線性的運行時間 56
3.3.2 堆數據結構 56
3.3.3 如何在Prim算法中使用堆 57
3.3.4 基于堆的實現的偽碼 59
3.3.5 運行時間分析 61
3.3.6 小測驗3.3的答案 61
*3.4 Prim算法：正確性證明 62
3.4.1 *小瓶頸屬性 62
3.4.2 生成樹的一些有趣結論 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算法的簡單實現 72
*3.6 通過合并查找對Kruskal算法進行加速 73
3.6.1 合并查找數據結構 73
3.6.2 基于合并查找的實現的偽碼 75
3.6.3 基于合并查找的實現的運行時間分析 76
3.6.4 合并查找的快速有余而嚴謹不足的實現：父圖 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章 動態規劃概述 93
4.1 加權獨立集合問題 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 *優子結構和推導公式 98
4.2.2 一種不成熟的遞歸方法 100
4.2.3 使用緩存的遞歸算法 101
4.2.4 一種迭代式的自底向上的實現 103
4.2.5 小測驗4.3～4.4的答案 104
4.3 一種重建算法 105
4.4 動態規劃的原則 107
4.4.1 3個步驟的配方 107
4.4.2 子問題的期望屬性 108
4.4.3 一個可重復的思維過程 109
4.4.4 動態規劃和分治算法的區別 109
4.4.5 為什么叫“動態規劃” 110
4.5 背包問題 111
4.5.1 問題定義 111
4.5.2 *優子結構和推導公式 113
4.5.3 子問題 115
4.5.4 一種動態規劃算法 115
4.5.5 例子 117
4.5.6 重建 117
4.5.7 小測驗4.5～4.6的答案 118
4.6 本章要點 119
4.7 章末習題 120
第5章 高級動態規劃 123
5.1 序列對齊 123
5.1.1 驅動力 123
5.1.2 問題定義 124
5.1.3 *優子結構 126
5.1.4 推導公式 129
5.1.5 子問題 129
5.1.6 一種動態規劃算法 130
5.1.7 重新構建 131
5.1.8 小測驗5.1～5.3的答案 132
*5.2 *優二叉搜索樹 133
5.2.1 二叉搜索樹回顧 134
5.2.2 平均搜索時間 135
5.2.3 問題定義 136
5.2.4 *優子結構 137
5.2.5 推導公式 141
5.2.6 子問題 142
5.2.7 一種動態規劃算法 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 負環 152
6.1.3 小測驗6.1的答案 154
6.2 Bellman-Ford算法 154
6.2.1 子問題 155
6.2.2 *優子結構 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 *優子結構 170
6.4.3 偽碼 172
6.4.4 檢測負環 174
6.4.5 Floyd-Warshall算法的總結和開放性問題 175
6.4.6 小測驗6.5～6.6的答案 176
6.5 本章要點 177
6.6 章末習題 178
附錄 章末習題答案節選 180
后記 算法設計工作指南 187
展開全部
算法詳解 卷3 貪心算法和動態規劃 作者簡介
蒂姆·拉夫加登（Tim Roughgarden）是哥倫比亞大學計算機科學系的教授，之前曾任教于斯坦福大學計算機科學系，他從2004年開始教授和研究算法。本書是他的《算法詳解》四部曲的第三卷，基于他從2012年開始定期舉行的在線算法課程編寫。
書友推薦
- >
二體千字文
- >
山海經
- >
大紅狗在馬戲團-大紅狗克里弗-助人
- >
伯納黛特,你要去哪(2021新版)
- >
詩經-先民的歌唱
- >
苦雨齋序跋文-周作人自編集
- >
伊索寓言-世界文學名著典藏-全譯本
- >
自卑與超越
本類暢銷
