《圖解算法》是2017年9月機械工業出版社出版的圖書，作者是俞征武。
基本介紹
- 書名：圖解算法
- 作者：俞征武 著
- ISBN：978-7-111-57887-1
- 定價：59.00
- 出版時間：2017-09
- 出版社：機械工業出版社
基本信息,內容簡介,目錄,
基本信息
作者：俞征武 著 |
ISBN(書號)：978-7-111-57887-1 |
出版日期：2017-09 |
版次：1/1 |
開本：16 |
定價：￥59.00 |
內容簡介
算法是人們利用電腦解決問題的技巧。本書以輕鬆的對話方式，採用圖解的輔助說明，幫助讀者簡單、自然地掌握算法的基本概念，並養成主動思考的習慣，達到用算法解決實際問題的目的。
全書共分12章，內容包括一切從觀察開始、分而治之法、動態規劃、貪婪法、修剪與搜尋法、樹搜尋法、問題轉換、圖算法、計算幾何、算法的難題、逼近算法、隨機算法等。
本書示例豐富，圖文並茂，以易於理解的方式闡釋算法，幫助程式設計師在日常項目開發中更好地發揮算法的能量
全書共分12章，內容包括一切從觀察開始、分而治之法、動態規劃、貪婪法、修剪與搜尋法、樹搜尋法、問題轉換、圖算法、計算幾何、算法的難題、逼近算法、隨機算法等。
本書示例豐富，圖文並茂，以易於理解的方式闡釋算法，幫助程式設計師在日常項目開發中更好地發揮算法的能量
目錄
推薦序
前 言
1 一切從觀察開始
1.1 什麼是算法 2
1.2 漢諾塔問題 3
1.3 漢諾塔問題的非遞歸算法 10
1.4 發現算法的技巧 16
學習效果評測 18
2 分而治之法
2.1 何謂分而治之法 20
2.2 找出最大值 21
2.3 時間複雜度 23
2.4 二維極點問題 25
2.5 快速排序法 30
2.6 快速排序法的時間複雜度 34
2.7 尋找第 k 小值問題 40
2.8 分而治之法的技巧 47
學習效果評測 48
3 動態規劃
3.1 何謂動態規劃 50
3.2 換零錢 50
3.3 數字金字塔 54
3.4 最長相同子字元串 58
3.5 安排公司聚會 64
3.6 動態規劃的技巧 70
學習效果評測 72
4 貪婪法
4.1 何謂貪婪法 75
4.2 最小成本生成樹 75
4.3 霍夫曼編碼樹 83
4.4 貪婪法的陷阱：0-1 背包問題 88
4.5 單位時間工作調度問題 90
4.6 證明貪婪法並介紹Matroid理論 96
4.7 貪婪法的技巧 99
學習效果評測 100
5 修剪與搜尋法
5.1 何謂修剪與搜尋法 103
5.2 找壞蛋問題 104
5.3 猜數字問題 105
5.4 約瑟夫問題 106
5.5 簡化的線性規劃問題 113
5.6 修剪與搜尋法的技巧 119
學習效果評測 119
6 樹搜尋法
6.1 何謂樹搜尋法 122
6.2 樹狀解空間：n 個皇后問題 123
6.3 回溯法：塗色問題 126
6.4 廣度優先搜尋法：八數字謎題 128
6.5 加速技巧：旅行商問題 131
6.6 樹搜尋法的技巧 140
學習效果評測 141
7 問題轉換
7.1 何謂問題轉換 144
7.2 將相異代表系問題轉換成二分圖上的匹配問題 145
7.3 將二分圖上的匹配問題轉換成網路流圖問題 147
7.4 將網路流圖問題轉換成線性規劃問題 150
7.5 問題轉換的技巧 152
學習效果評測 154
8 圖算法
8.1 什麼是圖 156
8.2 連通分支 157
8.3 Dijkstra 最短路徑算法 160
8.4 Bellman-Ford 最短路徑算法 168
8.5 雙連通分支 175
8.6 圖算法的技巧 193
學習效果評測 195
9 計算幾何
9.1 何謂計算幾何 199
9.2 多邊形中的點 200
9.3 天空輪廓 203
9.4 凸包 208
9.5 最近點對 215
9.6 計算幾何的技巧 219
學習效果評測 220
10 算法的難題
10.1 什麼是 NP-Complete 224
10.2 集合 P 和集合 NP 225
10.3 滿足性問題 227
10.4 多項式時間轉換 229
10.5 NP 中的難題 230
10.6 NP-Complete 的性質 234
10.7 NP-Complete 的證明技巧 237
學習效果評測 241
11 逼近算法
11.1 什麼是逼近算法 244
11.2 最小頂點覆蓋問題 244
11.3 裝箱問題 247
11.4 平面上的旅行商問題 249
11.5 逼近算法的技巧 252
學習效果評測 252
12 隨機算法
12.1 什麼是隨機算法 256
12.2 隨機快速排序法 257
12.3 質數測試 258
12.4 最小割算法 259
12.5 隨機算法技巧 265
學習效果評測 265
參考文獻
前 言
1 一切從觀察開始
1.1 什麼是算法 2
1.2 漢諾塔問題 3
1.3 漢諾塔問題的非遞歸算法 10
1.4 發現算法的技巧 16
學習效果評測 18
2 分而治之法
2.1 何謂分而治之法 20
2.2 找出最大值 21
2.3 時間複雜度 23
2.4 二維極點問題 25
2.5 快速排序法 30
2.6 快速排序法的時間複雜度 34
2.7 尋找第 k 小值問題 40
2.8 分而治之法的技巧 47
學習效果評測 48
3 動態規劃
3.1 何謂動態規劃 50
3.2 換零錢 50
3.3 數字金字塔 54
3.4 最長相同子字元串 58
3.5 安排公司聚會 64
3.6 動態規劃的技巧 70
學習效果評測 72
4 貪婪法
4.1 何謂貪婪法 75
4.2 最小成本生成樹 75
4.3 霍夫曼編碼樹 83
4.4 貪婪法的陷阱：0-1 背包問題 88
4.5 單位時間工作調度問題 90
4.6 證明貪婪法並介紹Matroid理論 96
4.7 貪婪法的技巧 99
學習效果評測 100
5 修剪與搜尋法
5.1 何謂修剪與搜尋法 103
5.2 找壞蛋問題 104
5.3 猜數字問題 105
5.4 約瑟夫問題 106
5.5 簡化的線性規劃問題 113
5.6 修剪與搜尋法的技巧 119
學習效果評測 119
6 樹搜尋法
6.1 何謂樹搜尋法 122
6.2 樹狀解空間：n 個皇后問題 123
6.3 回溯法：塗色問題 126
6.4 廣度優先搜尋法：八數字謎題 128
6.5 加速技巧：旅行商問題 131
6.6 樹搜尋法的技巧 140
學習效果評測 141
7 問題轉換
7.1 何謂問題轉換 144
7.2 將相異代表系問題轉換成二分圖上的匹配問題 145
7.3 將二分圖上的匹配問題轉換成網路流圖問題 147
7.4 將網路流圖問題轉換成線性規劃問題 150
7.5 問題轉換的技巧 152
學習效果評測 154
8 圖算法
8.1 什麼是圖 156
8.2 連通分支 157
8.3 Dijkstra 最短路徑算法 160
8.4 Bellman-Ford 最短路徑算法 168
8.5 雙連通分支 175
8.6 圖算法的技巧 193
學習效果評測 195
9 計算幾何
9.1 何謂計算幾何 199
9.2 多邊形中的點 200
9.3 天空輪廓 203
9.4 凸包 208
9.5 最近點對 215
9.6 計算幾何的技巧 219
學習效果評測 220
10 算法的難題
10.1 什麼是 NP-Complete 224
10.2 集合 P 和集合 NP 225
10.3 滿足性問題 227
10.4 多項式時間轉換 229
10.5 NP 中的難題 230
10.6 NP-Complete 的性質 234
10.7 NP-Complete 的證明技巧 237
學習效果評測 241
11 逼近算法
11.1 什麼是逼近算法 244
11.2 最小頂點覆蓋問題 244
11.3 裝箱問題 247
11.4 平面上的旅行商問題 249
11.5 逼近算法的技巧 252
學習效果評測 252
12 隨機算法
12.1 什麼是隨機算法 256
12.2 隨機快速排序法 257
12.3 質數測試 258
12.4 最小割算法 259
12.5 隨機算法技巧 265
學習效果評測 265
參考文獻
