掃一掃
關注中圖網
官方微博
本類五星書更多>
-
>
全國計算機等級考試最新真考題庫模擬考場及詳解·二級MSOffice高級應用
-
>
決戰行測5000題(言語理解與表達)
-
>
軟件性能測試.分析與調優實踐之路
-
>
第一行代碼Android
-
>
JAVA持續交付
-
>
EXCEL最強教科書(完全版)(全彩印刷)
-
>
深度學習
算法詳解(卷4)——NP-HARD問題算法 版權信息
- ISBN：9787115609120
- 條形碼：9787115609120 ; 978-7-115-60912-0
- 裝幀：平裝
- 冊數：暫無
- 重量：暫無
- 所屬分類：>
算法詳解(卷4)——NP-HARD問題算法 本書特色
1.專業作者：哥倫比亞大學計算機科學系教授蒂姆·拉夫加登豐富的教學經驗和深入的研究成果使得這本書成為算法領域的專業之作。
2.實戰導向：本書是《算法詳解》四部曲的第四卷，主要介紹NP-Hard問題算法。全書內容豐富、結構清晰，提供了快速識別NP-Hard問題的方法和處理NP的算法工具，適合讀者提升算法思維能力。
3.自測習題：每章都提供了小測驗和章末習題，這不僅能夠幫助讀者加深對算法的理解，還能夠培養讀者的獨立思考能力。
4.能力提升：無論是計算機專業的高校教師和學生，還是想要培養和訓練算法思維與計算思維的IT專業人士，甚至是正在準備面試的應聘者和面試官，本書都能夠有效提升算法能力。
算法詳解(卷4)——NP-HARD問題算法 內容簡介
算法詳解系列圖書共有4卷，本書是第4卷——NP-Hard問題算法。全書共有6章，主要介紹了快速識別NP-Hard問題的方法和處理NP的算法工具。本書的每一章均有小測驗、章末習題，這為讀者的自我檢查以及進一步學習提供了方便。 本書提供了豐富而實用的資料，能夠幫助讀者提升算法思維能力。本書適合計算機專業的高校教師和學生，想要培養和訓練算法思維與計算思維的IT專業人士，以及正在準備面試的應聘者和面試官閱讀參考。
算法詳解(卷4)——NP-HARD問題算法 目錄
第 1章 什么是NP問題 1
1.1 MST和TSP：算法的難解之謎 2
1.1.1 *小生成樹問題 2
1.1.2 旅行商問題 3
1.1.3 解決TSP的嘗試和失敗 4
1.1.4 小測驗1.1?C1.2的答案 6
1.2 讀者的不同專業層次 7
1.3 容易的問題和困難的問題 8
1.3.1多項式時間的算法 9
1.3.2 多項式時間與指數級時間 10
1.3.3 容易的問題 11
1.3.4 相對難以處理 12
1.3.5 困難的問題 12
1.3.6 P≠NP猜想 14
1.3.7 NP問題的臨時定義 14
1.3.8 隨機化和量子算法 15
1.3.9 微妙性 15
1.4 NP問題的算法策略 16
1.4.1 通用、正確、快速（選擇其二） 17
1.4.2 通用性的妥協 18
1.4.3 正確性的妥協 19
1.4.4 *壞情況運行時間的妥協 20
1.4.5 關鍵思路 21
1.5 證明NP問題：一個簡單的方案 21
1.5.1 轉化 22
1.5.2 使用轉化來設計快速算法 23
1.5.3 使用轉化對NP問題進行擴展 25
1.5.4 無環*短路徑是NP問題 26
1.5.5 小測驗1.3的答案 30
1.6 新手錯誤和可接受的不準確說法 30
1.7 本章要點 33
1.8 章末習題 34
1.8.1 挑戰題 36
1.8.2 編程題 37
第 2章 正確性的妥協：高效的不準確算法 38
2.1 完成工時*小化 38
2.1.1 問題定義 39
2.1.2 貪心算法 40
2.1.3 Graham算法 41
2.1.4 運行時間 42
2.1.5 近似的正確性 42
2.1.6 定理2.1的證明 44
2.1.7 *長處理時間優先（LPT） 46
2.1.8 定理2.4的證明 49
2.1.9 小測驗2.1?C2.3的答案 50
2.2 *大覆蓋 51
2.2.1 問題定義 51
2.2.2 更多的應用 53
2.2.3 一種貪心算法 54
2.2.4 GreedyCoverage算法的糟糕例子 55
2.2.5 近似正確性 57
2.2.6 一個關鍵的輔助結論 58
2.2.7 定理2.6的證明 60
2.2.8 小測驗2.4?C2.5的答案 61
*2.3 影響*大化 62
2.3.1 社交網絡的瀑布模型 62
2.3.2 例子 63
2.3.3 影響*大化問題 64
2.3.4 一種貪心算法 65
2.3.5 近似正確性 66
2.3.6 影響是覆蓋函數的一個加權和 66
2.3.7 定理2.8的證明 67
2.3.8 小測驗2.6的答案 69
2.4 TSP的2-OPT啟發式算法 70
2.4.1 處理TSP 70
2.4.2 通過2-變換改進路線 72
2.4.3 2-OPT算法 74
2.4.4 運行時間 75
2.4.5 解決方案質量 76
2.4.6 小測驗2.7?C2.8的答案 76
2.5 局部搜索的原則 77
2.5.1 可行解決方案的元圖（Meta-Graph） 77
2.5.2 局部搜索算法設計范例 79
2.5.3 三個建模決策 80
2.5.4 兩個算法設計決策 83
2.5.5 運行時間和解決方案質量 84
2.5.6 避免不好的局部*優解 84
2.5.7 什么時候應該使用局部搜索？ 86
2.5.8 小測驗2.9?C2.10的答案 86
2.6 本章要點 87
2.7 章末習題 88
2.7.1 挑戰題 91
2.7.2 編程題 96
第3章 速度的妥協：準確的非高效算法 98
3.1 TSP的Bellman-Held-Karp算法 98
3.1.1 底線：窮舉搜索 98
3.1.2 動態規劃 99
3.1.3 *優子結構 100
3.1.4 推導公式 102
3.1.5 子問題 103
3.1.6 Bellman-Held-Karp算法 104
3.1.7 小測驗3.1的答案 105
*3.2 通過顏色編碼尋找*長路徑 106
3.2.1 動機 107
3.2.2 問題定義 107
3.2.3 子問題的初次試探 108
3.2.4 顏色編碼 109
3.2.5 計算*低成本全色路徑 110
3.2.6 正確性和運行時間 113
3.2.7 隨機化挽救危局 114
3.2.8 *終的算法 116
3.2.9 運行時間和正確性 117
3.2.10 再論PPI網絡 118
3.2.11 小測驗3.2?C3.4的答案 118
3.3 問題特定的算法與萬能魔盒 119
3.3.1 轉化和萬能魔盒 119
3.3.2 MIP和SAT解決程序 120
3.3.3 將要學習的和不會學習的 121
3.3.4 再論新手易犯的錯誤 121
3.4 混合整數規劃解決程序 121
3.4.1 例子：背包問題 122
3.4.2 更基本意義上的MIP 124
3.4.3 MIP解決程序：一些起點 125
3.5 可滿足性解決程序 126
3.5.1 示例：圖形著色 126
3.5.2 可滿足性 127
3.5.3 把圖形著色問題表達為SAT 128
3.5.4 SAT解決程序：一些起點 130
3.6 本章要點 130
3.7 章末習題 132
3.7.1 挑戰題 134
3.7.2 編程題 137
第4章 證明NP問題 138
4.1 再論轉化 138
4.2 3-SAT問題和Cook-Levin定理 140
4.3 整體思路 142
4.3.1 再論新手易犯的錯誤 142
4.3.2 18個轉化 142
4.3.3 為什么要啃艱澀的NP問題證明？ 144
4.3.4 小測驗4.1的答案 145
4.4 一個轉化模板 145
4.5 獨立子集問題是NP問題 147
4.5.1 主要思路 147
4.5.2 定理4.2的證明 150
*4.6 有向漢密爾頓路徑問題是NP問題 152
4.6.1 變量的編碼和真值指派 153
4.6.2 約束條件的編碼 154
4.6.3 定理4.4的證明 156
4.7 TSP是NP問題 158
4.7.1 無向漢密爾頓路徑問題 158
4.7.2 定理4.7的證明 159
4.8 子集求和問題是NP問題 161
4.8.1 基本方法 161
4.8.2 例子：4頂點環路 162
4.8.3 例子：5頂點環路 163
4.8.4 定理4.9的證明 164
4.9 本章要點 165
4.10 章末習題 166
第5章 P、NP及相關概念 170
*5.1 難處理性的累積證據 171
5.1.1 通過轉化創建一個案例 171
5.1.2 為TSP選擇集合C 172
*5.2 決策、搜索和優化 173
*5.3 NP：具有容易識別的解決方案的問題 174
5.3.1 復雜類NP的定義 174
5.3.2 NP中的問題實例 175
5.3.3 NP問題是可以通過窮舉搜索解決的 176
5.3.4 NP問題 176
5.3.5 再論Cook-Levin定理 177
5.3.6 小測驗5.1的解決方案 179
*5.4 P≠NP猜想 180
5.4.1 多項式時間可解決的NP問題 180
5.4.2 P≠NP猜想的正式定義 180
5.4.3 P≠NP猜想的狀態 181
*5.5 指數級時間假設 183
5.5.1 NP問題需要指數級的時間嗎？ 183
5.5.2 強指數級時間假設（SETH） 184
5.5.3 容易問題的運行時間下界 185
*5.6 NP完全問題 187
5.6.1 Levin轉化 187
5.6.2 NP中*難的問題 189
5.6.3 NP完全問題的存在 189
5.7 本章要點 191
5.8 章末習題 192
第6章 案例研究：FCC激勵拍賣 195
6.1 無線頻譜再利用 195
6.1.1 從電視到移動電話 195
6.1.2 無線頻譜的一次*近重分配 196
6.2 回購執照的啟發式貪心算法 198
6.2.1 4個臨時的簡化假設 198
6.2.2 遭遇加權獨立子集問題 199
6.2.3 啟發式貪心算法 200
6.2.4 多頻道情況 202
6.2.5 遭遇圖形著色問題 203
6.2.6 小測驗6.1的答案 204
6.3 可行性檢查 205
6.3.1 改編為可滿足性問題 205
6.3.2 加入邊際約束條件 206
6.3.3 重新安置問題 206
6.3.4 技巧#1：預解決程序（尋求一種容易的解決之道） 207
6.3.5 技巧#2：預處理和簡化 208
6.3.6 技巧#3：SAT解決程序的組合 210
6.3.7 容忍失敗 211
6.3.8 小測驗6.2的答案 211
6.4 降序時鐘拍賣的實現 212
6.4.1 拍賣和算法 212
6.4.2 例子 213
6.4.3 重新實現FCCGreedy算法 214
6.4.4 是時候提供補償了 216
6.5 *終結果 217
6.6 本章要點 218
6.7 章末習題 218
6.7.1 挑戰題 220
6.7.2 編程題 220
后記 算法設計實戰指南 221
附錄 問題提示和答案 224
1.1 MST和TSP：算法的難解之謎 2
1.1.1 *小生成樹問題 2
1.1.2 旅行商問題 3
1.1.3 解決TSP的嘗試和失敗 4
1.1.4 小測驗1.1?C1.2的答案 6
1.2 讀者的不同專業層次 7
1.3 容易的問題和困難的問題 8
1.3.1多項式時間的算法 9
1.3.2 多項式時間與指數級時間 10
1.3.3 容易的問題 11
1.3.4 相對難以處理 12
1.3.5 困難的問題 12
1.3.6 P≠NP猜想 14
1.3.7 NP問題的臨時定義 14
1.3.8 隨機化和量子算法 15
1.3.9 微妙性 15
1.4 NP問題的算法策略 16
1.4.1 通用、正確、快速（選擇其二） 17
1.4.2 通用性的妥協 18
1.4.3 正確性的妥協 19
1.4.4 *壞情況運行時間的妥協 20
1.4.5 關鍵思路 21
1.5 證明NP問題：一個簡單的方案 21
1.5.1 轉化 22
1.5.2 使用轉化來設計快速算法 23
1.5.3 使用轉化對NP問題進行擴展 25
1.5.4 無環*短路徑是NP問題 26
1.5.5 小測驗1.3的答案 30
1.6 新手錯誤和可接受的不準確說法 30
1.7 本章要點 33
1.8 章末習題 34
1.8.1 挑戰題 36
1.8.2 編程題 37
第 2章 正確性的妥協：高效的不準確算法 38
2.1 完成工時*小化 38
2.1.1 問題定義 39
2.1.2 貪心算法 40
2.1.3 Graham算法 41
2.1.4 運行時間 42
2.1.5 近似的正確性 42
2.1.6 定理2.1的證明 44
2.1.7 *長處理時間優先（LPT） 46
2.1.8 定理2.4的證明 49
2.1.9 小測驗2.1?C2.3的答案 50
2.2 *大覆蓋 51
2.2.1 問題定義 51
2.2.2 更多的應用 53
2.2.3 一種貪心算法 54
2.2.4 GreedyCoverage算法的糟糕例子 55
2.2.5 近似正確性 57
2.2.6 一個關鍵的輔助結論 58
2.2.7 定理2.6的證明 60
2.2.8 小測驗2.4?C2.5的答案 61
*2.3 影響*大化 62
2.3.1 社交網絡的瀑布模型 62
2.3.2 例子 63
2.3.3 影響*大化問題 64
2.3.4 一種貪心算法 65
2.3.5 近似正確性 66
2.3.6 影響是覆蓋函數的一個加權和 66
2.3.7 定理2.8的證明 67
2.3.8 小測驗2.6的答案 69
2.4 TSP的2-OPT啟發式算法 70
2.4.1 處理TSP 70
2.4.2 通過2-變換改進路線 72
2.4.3 2-OPT算法 74
2.4.4 運行時間 75
2.4.5 解決方案質量 76
2.4.6 小測驗2.7?C2.8的答案 76
2.5 局部搜索的原則 77
2.5.1 可行解決方案的元圖（Meta-Graph） 77
2.5.2 局部搜索算法設計范例 79
2.5.3 三個建模決策 80
2.5.4 兩個算法設計決策 83
2.5.5 運行時間和解決方案質量 84
2.5.6 避免不好的局部*優解 84
2.5.7 什么時候應該使用局部搜索？ 86
2.5.8 小測驗2.9?C2.10的答案 86
2.6 本章要點 87
2.7 章末習題 88
2.7.1 挑戰題 91
2.7.2 編程題 96
第3章 速度的妥協：準確的非高效算法 98
3.1 TSP的Bellman-Held-Karp算法 98
3.1.1 底線：窮舉搜索 98
3.1.2 動態規劃 99
3.1.3 *優子結構 100
3.1.4 推導公式 102
3.1.5 子問題 103
3.1.6 Bellman-Held-Karp算法 104
3.1.7 小測驗3.1的答案 105
*3.2 通過顏色編碼尋找*長路徑 106
3.2.1 動機 107
3.2.2 問題定義 107
3.2.3 子問題的初次試探 108
3.2.4 顏色編碼 109
3.2.5 計算*低成本全色路徑 110
3.2.6 正確性和運行時間 113
3.2.7 隨機化挽救危局 114
3.2.8 *終的算法 116
3.2.9 運行時間和正確性 117
3.2.10 再論PPI網絡 118
3.2.11 小測驗3.2?C3.4的答案 118
3.3 問題特定的算法與萬能魔盒 119
3.3.1 轉化和萬能魔盒 119
3.3.2 MIP和SAT解決程序 120
3.3.3 將要學習的和不會學習的 121
3.3.4 再論新手易犯的錯誤 121
3.4 混合整數規劃解決程序 121
3.4.1 例子：背包問題 122
3.4.2 更基本意義上的MIP 124
3.4.3 MIP解決程序：一些起點 125
3.5 可滿足性解決程序 126
3.5.1 示例：圖形著色 126
3.5.2 可滿足性 127
3.5.3 把圖形著色問題表達為SAT 128
3.5.4 SAT解決程序：一些起點 130
3.6 本章要點 130
3.7 章末習題 132
3.7.1 挑戰題 134
3.7.2 編程題 137
第4章 證明NP問題 138
4.1 再論轉化 138
4.2 3-SAT問題和Cook-Levin定理 140
4.3 整體思路 142
4.3.1 再論新手易犯的錯誤 142
4.3.2 18個轉化 142
4.3.3 為什么要啃艱澀的NP問題證明？ 144
4.3.4 小測驗4.1的答案 145
4.4 一個轉化模板 145
4.5 獨立子集問題是NP問題 147
4.5.1 主要思路 147
4.5.2 定理4.2的證明 150
*4.6 有向漢密爾頓路徑問題是NP問題 152
4.6.1 變量的編碼和真值指派 153
4.6.2 約束條件的編碼 154
4.6.3 定理4.4的證明 156
4.7 TSP是NP問題 158
4.7.1 無向漢密爾頓路徑問題 158
4.7.2 定理4.7的證明 159
4.8 子集求和問題是NP問題 161
4.8.1 基本方法 161
4.8.2 例子：4頂點環路 162
4.8.3 例子：5頂點環路 163
4.8.4 定理4.9的證明 164
4.9 本章要點 165
4.10 章末習題 166
第5章 P、NP及相關概念 170
*5.1 難處理性的累積證據 171
5.1.1 通過轉化創建一個案例 171
5.1.2 為TSP選擇集合C 172
*5.2 決策、搜索和優化 173
*5.3 NP：具有容易識別的解決方案的問題 174
5.3.1 復雜類NP的定義 174
5.3.2 NP中的問題實例 175
5.3.3 NP問題是可以通過窮舉搜索解決的 176
5.3.4 NP問題 176
5.3.5 再論Cook-Levin定理 177
5.3.6 小測驗5.1的解決方案 179
*5.4 P≠NP猜想 180
5.4.1 多項式時間可解決的NP問題 180
5.4.2 P≠NP猜想的正式定義 180
5.4.3 P≠NP猜想的狀態 181
*5.5 指數級時間假設 183
5.5.1 NP問題需要指數級的時間嗎？ 183
5.5.2 強指數級時間假設（SETH） 184
5.5.3 容易問題的運行時間下界 185
*5.6 NP完全問題 187
5.6.1 Levin轉化 187
5.6.2 NP中*難的問題 189
5.6.3 NP完全問題的存在 189
5.7 本章要點 191
5.8 章末習題 192
第6章 案例研究：FCC激勵拍賣 195
6.1 無線頻譜再利用 195
6.1.1 從電視到移動電話 195
6.1.2 無線頻譜的一次*近重分配 196
6.2 回購執照的啟發式貪心算法 198
6.2.1 4個臨時的簡化假設 198
6.2.2 遭遇加權獨立子集問題 199
6.2.3 啟發式貪心算法 200
6.2.4 多頻道情況 202
6.2.5 遭遇圖形著色問題 203
6.2.6 小測驗6.1的答案 204
6.3 可行性檢查 205
6.3.1 改編為可滿足性問題 205
6.3.2 加入邊際約束條件 206
6.3.3 重新安置問題 206
6.3.4 技巧#1：預解決程序（尋求一種容易的解決之道） 207
6.3.5 技巧#2：預處理和簡化 208
6.3.6 技巧#3：SAT解決程序的組合 210
6.3.7 容忍失敗 211
6.3.8 小測驗6.2的答案 211
6.4 降序時鐘拍賣的實現 212
6.4.1 拍賣和算法 212
6.4.2 例子 213
6.4.3 重新實現FCCGreedy算法 214
6.4.4 是時候提供補償了 216
6.5 *終結果 217
6.6 本章要點 218
6.7 章末習題 218
6.7.1 挑戰題 220
6.7.2 編程題 220
后記 算法設計實戰指南 221
附錄 問題提示和答案 224
展開全部
算法詳解(卷4)——NP-HARD問題算法 作者簡介
蒂姆·拉夫加登（Tim Roughgarden）是哥倫比亞大學計算機科學系的教授，之前曾任教于斯坦福大學計算機科學系，他從2004年開始教授和研究算法。本書是他的《算法詳解》四部曲的第三卷，基于他從2012年開始定期舉行的在線算法課程編寫。
書友推薦
- >
我從未如此眷戀人間
- >
羅庸西南聯大授課錄
- >
龍榆生：詞曲概論/大家小書
- >
詩經-先民的歌唱
- >
二體千字文
- >
【精裝繪本】畫給孩子的中國神話
- >
上帝之肋:男人的真實旅程
- >
名家帶你讀魯迅:故事新編
本類暢銷
