|
-- 會員 / 註冊 --
|
|
|
|
算法設計 ( 簡體 字) |
作者:[美] 喬恩·克萊因伯格(Jon Kleinberg) | 類別:1. -> 程式設計 -> 演算法 |
譯者: |
出版社:人民郵電出版社 | 3dWoo書號: 54185 詢問書籍請說出此書號!【缺書】 NT售價: 595 元 |
出版日:3/1/2021 |
頁數:503 |
光碟數:0 |
|
站長推薦: |
印刷:黑白印刷 | 語系: ( 簡體 版 ) |
|
加入購物車 │加到我的最愛 (請先登入會員) |
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 |
序: |
|