《算法設計與分析(第4版)》是由王曉東編著,清華大學出版社2018年10月出版的普通高等教育“十一五”國家級規劃教材、21世紀大學本科計算機專業系列教材。該書既可用作高等學校計算機專業本科生和研究生學習計算機算法設計的教材,而且也適合工程技術人員和自學讀者學習參考。
全書共分11章,由算法引論、遞歸與分治策略、動態規劃、章貪心算法、回溯法、分支限界法、機率算法、NP完全性理論與近似算法、串與序列的算法、算法最佳化策略、線上算法設計組成。
基本介紹
- 中文名:算法設計與分析(第4版)
- 作者:王曉東
- 類別:21世紀大學本科計算機專業系列教材等
- 出版社:清華大學出版社
- 出版時間:2018年10月1日
- 開本:185mm×260mm
- 裝幀:平裝
- ISBN:9787302510109
- 字數:550千字
成書過程
修訂過程
出版工作
責任編輯 | 封面設計 | 責任校對 | 責任印製 |
張瑞慶 | 何鳳霞 | 梁毅 | 沈露 |
內容簡介
教材目錄
第1章算法引論1 | 7.2.3解非線性方程組195 |
1.1算法與程式1 | 7.3舍伍德算法197 |
1.2表達算法的抽象機制1 | 7.3.1線性時間灶察台選擇算法198 |
1.3描述算法3 | 7.3.2跳躍表200 |
1.4算法複雜性分析10 | 7.4拉斯維加斯算法205 |
小結13 | 7.4.1n後問題206 |
習題14 | 7.4.2整數因子分解209 |
第2章遞歸與分治策略16 | 7.5蒙特卡羅算法211 |
2.1遞歸的概念16 | 7.5.1蒙特卡羅算法的基本思想211 |
2.2分治法的基本思想21 | 7.5.2主元素問題213 |
2.3二分搜尋技術23 | 7.5.3素數測試214 |
2.4大整數的乘法23 | 小結217 |
2.5Strassen矩陣乘法24 | 習題217 |
2.6棋盤覆蓋26 | 第8章NP完全性理論與近似算法221 |
2.7合併排序28 | 8.1P類與NP類問題221 |
2.8快速排序30 | 8.1.1非確定性圖靈機222 |
2.9線性時間選擇33 | 8.1.2P類與NP類語言222 |
2.10最接近點對問題35 | 8.1.3多項式時間驗證224 |
2.11循環賽日程表43 | 8.2NP完全問題225 |
小結44 | 8.2.1多項式時間變換225 |
習題44 | 8.2.2Cook定理226 |
第3章動態規劃50 | 8.3一些典型的NP完全問題229 |
3.1矩陣連乘問題50 | 8.3.1合取範式的可滿足性問題230 |
3.2動態規划算法的基本要素55 | 8.3.23元合取範式的可滿足性問題230 |
3.3最長連晚坑照公共子序列58 | 8.3.3團問題231 |
3.4凸多邊形最優三角剖分61 | 8.3.4頂點覆蓋問題232 |
3.5多邊形遊戲64 | 8.3.5子集和問題233 |
3.6圖像壓縮67 | 8.3.6哈密頓迴路問題235 |
3.7電路布線69 | 8.3.7旅行售貨員問題238 |
3.8流水作業調度72 | 8.4近似算法的性能238 |
3.90\|1背包問題75 | 8.5頂點覆蓋問題的近似算法240 |
3.10最優二叉搜尋樹80 | 8.6旅行售貨員問題近似算法241 |
小結83 | 8.6.1具有三角不等式性質的旅行售貨員問題242 |
習題83 | 8.6.2一般的烏蜜踏旅行售貨員問題243 |
第4章貪心算法85 | 8.7集合覆蓋問題的近似算法244 |
4.1活動安排問題85 | 8.8子集和問題的近似算法246 |
4.2貪心算法的基本要素88 | 8.8.1子集和問題的指數時間算法247 |
4.2.1貪心選擇性質88 | 8.8.2子集和問題的完全多項式時間近似格式台霸台247 |
4.2.2最優子結構性質89 | 小結250 |
4.2.3貪心算法與動態規划算法的差異89 | 習題250 |
4.3最優裝載91 | 第9章串與序列的算法253 |
4.4哈夫曼編碼92 | 9.1子串搜尋算法253 |
4.4.1前綴碼93 | 9.1.1串的基本概念253 |
4.4.2構造哈夫曼編碼93 | 9.1.2KMP算法255 |
4.4.3哈夫曼算法的正確性95 | 9.1.3RabinKarp算法258 |
4.5單源最短路徑96 | 9.1.4多子串搜尋與AC自動機260 |
4.5.1算法基本思想97 | 9.2後綴數組與最長公共子串266 |
4.5.2算法的正確性和計算複雜性98 | 9.2.1後綴數組的基本概念266 |
4.6最小生成樹99 | 9.2.2構造後綴數組的倍前綴算法267 |
4.6.1最小生成樹性質99 | 9.2.3構造後綴數組的DC3分治法270 |
4.6.2Prim算法100 | 9.2.4最長公共前綴數組與最長公共擴展算法274 |
4.6.3Kruskal算法102 | 9.2.5最長公共子串算法276 |
4.7多機調度問題104 | 9.3序列比較算法277 |
4.8貪心算法的理論基礎106 | 9.3.1編輯距離算法277 |
4.8.1擬陣106 | 9.3.2最長公共單調子序列280 |
4.8.2帶權擬陣的貪心算法107 | 9.3.3有約束最長公共子序列281 |
4.8.3任務時間表問題109 | 小結284 |
小結113 | 習題285 |
習題113 | 第10章算法最佳化策略288 |
第5章回溯法115 | 10.1算法設計策略的比較與選擇288 |
5.1回溯法的算法框架115 | 10.1.1最大子段和問題的簡單算法288 |
5.1.1問題的解空間115 | 10.1.2最大子段和問題的分治算法289 |
5.1.2回溯法的基本思想116 | 10.1.3最大子段和問題的動態規划算法291 |
5.1.3遞歸回溯117 | 10.1.4最大子段和問題與動態規划算法的推廣291 |
5.1.4疊代回溯118 | 10.2動態規劃加速原理294 |
5.1.5子集樹與排列樹119 | 10.2.1貨物儲運問題294 |
5.2裝載問題120 | 10.2.2算法及其最佳化295 |
5.3批處理作業調度126 | 10.3問題的算法特徵298 |
5.4符號三角形問題128 | 10.3.1貪心策略298 |
5.5n後問題130 | 10.3.2對貪心策略的改進299 |
5.601背包問題133 | 10.3.3算法三部曲299 |
5.7最大團問題136 | 10.3.4算法實現300 |
5.8圖的m著色問題138 | 10.3.5算法複雜性305 |
5.9旅行售貨員問題140 | 10.4最佳化數據結構306 |
5.10圓排列問題142 | 10.4.1帶權區間最短路問題306 |
5.11電路板排列問題144 | 10.4.2算法設計思想306 |
5.12連續郵資問題147 | 10.4.3算法實現方案308 |
5.13回溯法的效率分析149 | 10.4.4並查集311 |
小結152 | 10.4.5可並優先佇列314 |
習題152 | 10.5最佳化搜尋策略318 |
第6章分支限界法153 | 小結324 |
6.1分支限界法的基本思想153 | 習題324 |
6.2單源最短路徑問題156 | 第11章線上算法設計325 |
6.3裝載問題158 | 11.1線上算法設計的基本概念325 |
6.4布線問題166 | 11.2頁調度問題327 |
6.501背包問題170 | 11.3勢函式分析329 |
6.6最大團問題175 | 11.4k服務問題330 |
6.7旅行售貨員問題178 | 11.4.1競爭比的下界330 |
6.8電路板排列問題181 | 11.4.2平衡算法331 |
6.9批處理作業調度184 | 11.4.3對稱移動算法332 |
小結189 | 11.5Steiner樹問題334 |
習題189 | 11.6線上任務調度336 |
第7章機率算法190 | 11.7負載平衡337 |
7.1隨機數191 | 小結338 |
7.2數值機率算法193 | 習題338 |
7.2.1用隨機投點法計算π值193 | 辭彙索引340 |
7.2.2計算定積分194 | 參考文獻345 |
教學資源
- 配套教材
- 課程資源
教材特色
- 按照計算機算法設計策略為知識單元,採用流行且適合於Internet環境的面向對象程式設計語言Java組織編。
- 書中涵蓋的算法設計策略全面,包括用於問題精確求解的遞歸與分治策略、動態規划算法貪心策略、回溯算法和分支限界算法,用於求解NP難題的近似算法、串與序列的算法、隨機化算法等。
- 以問題驅動的方式組織內容,先介紹一種算法設計策略的基本思想,然後從解決計算機科學與套用中出現的實際問題入手,由簡到繁地描述幾個經典的精巧算法,同時對每個算法所需要的時間和空間進行分析。
- 廣度與深度兼顧,理論與實踐並重。著重強調提高學生的綜合素質的最終目標,用廣度與深度兼顧的教學策略,培養學生的專業興趣,樹立正確的專業思想。
- 各章配有難易適當的習題,分為理論分析型和套用實踐型兩種,理論分析型的習題側重於算法理論的拿提與擴展,套用實踐的習題期重於算法的實現與具體套用。
作者簡介
教學資源
- 配套教材
- 課程資源
教材特色
- 按照計算機算法設計策略為知識單元,採用流行且適合於Internet環境的面向對象程式設計語言Java組織編。
- 書中涵蓋的算法設計策略全面,包括用於問題精確求解的遞歸與分治策略、動態規划算法貪心策略、回溯算法和分支限界算法,用於求解NP難題的近似算法、串與序列的算法、隨機化算法等。
- 以問題驅動的方式組織內容,先介紹一種算法設計策略的基本思想,然後從解決計算機科學與套用中出現的實際問題入手,由簡到繁地描述幾個經典的精巧算法,同時對每個算法所需要的時間和空間進行分析。
- 廣度與深度兼顧,理論與實踐並重。著重強調提高學生的綜合素質的最終目標,用廣度與深度兼顧的教學策略,培養學生的專業興趣,樹立正確的專業思想。
- 各章配有難易適當的習題,分為理論分析型和套用實踐型兩種,理論分析型的習題側重於算法理論的拿提與擴展,套用實踐的習題期重於算法的實現與具體套用。