《算法設計》是2021年3月人民郵電出版社出版的圖書，作者是[美] 喬恩·克萊因伯格（Jon Kleinberg），本書圍繞算法設計進行組織，對每種算法技術用多個典型範例進行分析，把算法的理論跟實際問題結合起來，具有很大的啟發性。
基本介紹
- 書名：算法設計
- 作者：[美] 喬恩·克萊因伯格（Jon Kleinberg）
- 出版社：人民郵電出版社
- ISBN：9787115546647
內容簡介,圖書目錄,作者簡介,
內容簡介
這是一本關於算法設計和分析的經典教材。本書圍繞算法設計進行組織，對每種算法技術用多個典型範例進行分析，把算法的理論跟實際問題結合起來，具有很大的啟發性。本書側重算法設計思路，每章都從實際問題出發，經過深入具體的分析引出相應算法的設計思想，並對算法的正確性和複雜性進行合理的分析和論證。本書覆蓋面廣，且含有200多道精彩的習題，最後還擴展了PSPACE問題、參數複雜性等內容。
圖書目錄
目 錄
第 1章 引言：一些典型問題 1
1.1 第 一個問題：穩定匹配 1
1.2 5個典型問題 8
帶解答的練習 12
練習 14
注釋和進一步閱讀 17
第 2章 算法分析基礎 18
2.1 計算可解性 18
2.2 增長的漸近階 21
2.3 用列表和數組實現穩定匹配算法 26
2.4 常見運行時間綜述 29
2.5 更複雜的數據結構：優先佇列 35
帶解答的練習 40
練習 41
注釋和進一步閱讀 44
第3章 圖 45
3.1 基本定義和套用 45
3.2 圖連通性和圖遍歷 48
3.3 用佇列和棧實現圖遍歷 53
3.4 二分性測試：廣度優先搜尋的套用 58
3.5 有向圖中的連通性 59
3.6 有向無環圖和拓撲排序 61
帶解答的練習 64
練習 66
注釋和進一步閱讀 69
第4章 貪心算法 70
4.1 區間調度：貪心算法保持領先 70
4.2 小化延遲的調度：交換論證 76
4.3 快取：更複雜的交換論證 80
4.4 圖的短路徑 83
4.5 小生成樹問題 87
4.6 實現Kruskal算法：Union-Find數據結構 92
4.7 聚類 97
4.8 哈夫曼碼和數據壓縮 99
4.9 小開銷樹形圖：多階段貪心算法 109
帶解答的練習 113
練習 116
注釋和進一步閱讀 125
第5章 分治 127
5.1 第 一個遞推式：歸併排序算法 127
5.2 進一步的遞推關係 130
5.3 計數逆序 134
5.4 尋找近點對 137
5.5 整數乘法 141
5.6 卷積和快速傅立葉變換 142
帶解答的練習 148
練習 150
注釋和進一步閱讀 152
第6章 動態規劃 153
6.1 加權區間調度：遞歸過程 153
6.2 動態規劃原理：備忘錄或子問題疊代 157
6.3 分段小二乘：多重選擇 159
6.4 子集和與背包：加一個變數 162
6.5 RNA二級結構：區間上的動態規劃 166
6.6 序列比對 169
6.7 通過分治線上性空間中序列比對 173
6.8 圖中的短路徑 177
6.9 短路徑和距離向量協定 182
6.10 圖中的負環 184
帶解答的練習 187
練習 190
注釋和進一步閱讀 204
第7章 網路流 205
7.1 流問題和Ford-Fulkerson算法 205
7.2 網路中的流和小割 211
7.3 選擇好的增廣路徑 214
7.4 預流推進流算法 218
7.5 第 一個套用：二分匹配問題 225
7.6 有向圖和無向圖中的不相交路徑 228
7.7 流問題的擴展 232
7.8 調查設計 236
7.9 航空公司調度 237
7.10 圖像分割 240
7.11 項目選擇 243
7.12 棒球排除 246
7.13 進一步的方向：為匹配問題增加開銷 249
帶解答的練習 253
練習 255
注釋和進一步閱讀 274
第8章 NP和計算難解性 276
8.1 多項式時間歸約 276
8.2 通過“小配件”歸約：可滿足性問題 280
8.3 有效證書和NP的定義 283
8.4 NP完全問題 285
8.5 排序問題 289
8.6 劃分問題 294
8.7 圖著色 297
8.8 數值問題 300
8.9 co-NP和NP的不對稱性 303
8.10 困難問題的部分分類 305
帶解答的練習 307
練習 309
注釋和進一步閱讀 323
第9章 PSPACE：NP之外的一類問題 324
9.1 PSPACE 324
9.2 PSPACE中的一些難題 325
9.3 在多項式空間中求解量化問題和博弈 327
9.4 在多項式空間中求解規劃問題 328
9.5 證明問題是PSPACE完全的 331
帶解答的練習 334
練習 335
注釋和進一步閱讀 336
第 10章 擴展易解性的界限 337
10.1 尋找小的頂點覆蓋 338
10.2 求解樹上的NP困難問題 340
10.3 圓弧集著色 343
10.4 圖的樹分解 349
10.5 構造樹分解 356
帶解答的練習 361
練習 363
注釋和進一步閱讀 365
第 11章 近似算法 366
11.1 貪心算法和值的界限：負載均衡問題 366
11.2 中心選址問題 370
11.3 集合覆蓋：一般貪心啟發式 374
11.4 定價方法：頂點覆蓋 378
11.5 用定價方法化：不相交路徑問題 382
11.6 線性規劃和捨入：頂點覆蓋的套用 386
11.7 再論負載均衡：更高級的LP套用 390
11.8 任意好的近似：背包問題 394
帶解答的練習 398
練習 399
注釋和進一步閱讀 404
第 12章 局部搜尋 406
12.1 最佳化問題的地形 406
12.2 Metropolis算法和模擬退火算法 409
12.3 局部搜尋在Hopfield神經網路中的套用 412
12.4 通過局部搜尋的割近似 415
12.5 選擇鄰居關係 417
12.6 用局部搜尋分類 418
12.7 回響動態和納什均衡 423
帶解答的練習 430
練習 431
注釋和進一步閱讀 433
第 13章 隨機算法 434
13.1 第 一個套用：消除爭用 435
13.2 尋找全局小割 438
13.3 隨機變數及其期望 442
13.4 MAX 3-SAT的隨機近似算法 445
13.5 隨機分治：找中位數和Quicksort 447
13.6 哈希：字典的隨機實現 452
13.7 尋找近點對：隨機方法 457
13.8 隨機快取 462
13.9 切爾諾夫界 467
13.10 負載均衡 468
13.11 分組路由 470
13.12 背景知識：一些基本機率定義 474
帶解答的練習 479
練習 483
注釋和進一步閱讀 489
後記：永遠運行的算法 491
參考文獻 497
作者簡介
作者簡介 喬恩·克萊因伯格（Jon Kleinberg），康奈爾大學計算機科學教授。他於1996年從麻省理工學院獲得博士學位。他榮獲過美國國家科學基金會事業獎、海軍研究局青年研究員獎、IBM 傑出創新獎和美國國家科學院創新研究獎等眾多獎項。 他的研究集中在算法上，特別是與網路結構和信息相關的算法，以及這些算法在信息科學、最佳化、數據挖掘以及計算生物學等方面的套用。 伊娃·塔多斯（éva Tardos），康奈爾大學計算機科學教授。她是美國藝術與科學學院院士、ACM會士。她榮獲過美國國家科學基金會總統青年研究員獎和富爾克森獎等眾多獎項。 她的研究興趣主要集中在圖和網路問題的算法設計和分析上。她因在網路流算法和網路問題的近似算法方面的工作而聞名。她近的工作重點是算法博弈論。 譯者簡介 王海鵬，軟體開發者、譯者、培訓講師。他擁有二十餘年 IT 行業經驗，翻譯了二十餘本軟體開發相關圖書，為行業內多家知名公司提供過培訓。他使用的開發語言主要有 C/C 、Java和 Lua。他專注於提高軟體開發的效率和品質，並在量化交易領域擁有豐富的經驗。
