算法設計與分析（第4版）（21世紀大學(xué)本科計算機專(zhuān)業(yè)系列教材）簡(jiǎn)介，目錄書(shū)摘

編輯推薦:

內容簡(jiǎn)介:為了適應培養我國２１世紀計算機各類(lèi)人才的需要，結合我國高等學(xué)校教育工作的現狀，立足培養學(xué)生能跟上國際計算機科學(xué)技術(shù)的發(fā)展水平，更新教學(xué)內容和教學(xué)方法，提高教學(xué)質(zhì)量，本書(shū)以算法設計策略為知識單元，系統地介紹計算機算法的設計方法與分析技巧，以期為計算機科學(xué)與技術(shù)學(xué)科的學(xué)生提供廣泛而堅實(shí)的計算機算法基礎知識。另有配套的《算法設計與分析（第4版）習題解答》，對本書(shū)的全部習題做了詳盡的解答。
本書(shū)內容豐富，觀(guān)點(diǎn)新穎，理論聯(lián)系實(shí)際。不僅可用作高等學(xué)校計算機專(zhuān)業(yè)本科生和研究生學(xué)習計算機算法設計的教材，而且也適合廣大工程技術(shù)人員和自學(xué)讀者學(xué)習參考。

作者簡(jiǎn)介:王曉東,教授，博士生導師。近年來(lái)正式出版學(xué)術(shù)著(zhù)作11部。近年在國內外學(xué)術(shù)刊物上發(fā)表學(xué)術(shù)論文60多篇。參加多項科研項目并獲獎。其中獲國家科技進(jìn)步二等獎一項，水電部科技進(jìn)步一等獎一項，福建省科技進(jìn)步三等獎一項，省水電廳科技進(jìn)步一等獎一項。

目錄:目錄CONTENTS
第1章算法引論1
1.1算法與程序1
1.2表達算法的抽象機制1
1.3描述算法3
1.4算法復雜性分析10
小結13
習題14
第2章遞歸與分治策略16
2.1遞歸的概念16
2.2分治法的基本思想21
2.3二分搜索技術(shù)23
2.4大整數的乘法23
2.5Strassen矩陣乘法24
2.6棋盤(pán)覆蓋26
2.7合并排序28
2.8快速排序30
2.9線(xiàn)性時(shí)間選擇33
2.10最接近點(diǎn)對問(wèn)題35
2.11循環(huán)賽日程表43
小結44
習題44
第3章動(dòng)態(tài)規劃50
3.1矩陣連乘問(wèn)題50
3.2動(dòng)態(tài)規劃算法的基本要素55
3.3最長(cháng)公共子序列58
3.4凸多邊形最優(yōu)三角剖分61
3.5多邊形游戲64
3.6圖像壓縮67
3.7電路布線(xiàn)69
3.8流水作業(yè)調度72
3.90\|1背包問(wèn)題75
3.10最優(yōu)二叉搜索樹(shù)80
小結83
習題83
目錄算法設計與分析(第4版)第4章貪心算法85
4.1活動(dòng)安排問(wèn)題85
4.2貪心算法的基本要素88
4.2.1貪心選擇性質(zhì)88
4.2.2最優(yōu)子結構性質(zhì)89
4.2.3貪心算法與動(dòng)態(tài)規劃算法的差異89
4.3最優(yōu)裝載91
4.4哈夫曼編碼92
4.4.1前綴碼93
4.4.2構造哈夫曼編碼93
4.4.3哈夫曼算法的正確性95
4.5單源最短路徑96
4.5.1算法基本思想97
4.5.2算法的正確性和計算復雜性98
4.6最小生成樹(shù)99
4.6.1最小生成樹(shù)性質(zhì)99
4.6.2Prim算法100
4.6.3Kruskal算法102
4.7多機調度問(wèn)題104
4.8貪心算法的理論基礎106
4.8.1擬陣106
4.8.2帶權擬陣的貪心算法107
4.8.3任務(wù)時(shí)間表問(wèn)題109
小結113
習題113
第5章回溯法115
5.1回溯法的算法框架115
5.1.1問(wèn)題的解空間115
5.1.2回溯法的基本思想116
5.1.3遞歸回溯117
5.1.4迭代回溯118
5.1.5子集樹(shù)與排列樹(shù)119
5.2裝載問(wèn)題120
5.3批處理作業(yè)調度126
5.4符號三角形問(wèn)題128
5.5n后問(wèn)題130
5.601背包問(wèn)題133
5.7最大團問(wèn)題136
5.8圖的m著(zhù)色問(wèn)題138
5.9旅行售貨員問(wèn)題140
5.10圓排列問(wèn)題142
5.11電路板排列問(wèn)題144
5.12連續郵資問(wèn)題147
5.13回溯法的效率分析149
小結152
習題152
第6章分支限界法153
6.1分支限界法的基本思想153
6.2單源最短路徑問(wèn)題156
6.3裝載問(wèn)題158
6.4布線(xiàn)問(wèn)題166
6.501背包問(wèn)題170
6.6最大團問(wèn)題175
6.7旅行售貨員問(wèn)題178
6.8電路板排列問(wèn)題181
6.9批處理作業(yè)調度184
小結189
習題189
第7章概率算法190
7.1隨機數191
7.2數值概率算法193
7.2.1用隨機投點(diǎn)法計算π值193
7.2.2計算定積分194
7.2.3解非線(xiàn)性方程組195
7.3舍伍德算法197
7.3.1線(xiàn)性時(shí)間選擇算法198
7.3.2跳躍表200
7.4拉斯維加斯算法205
7.4.1n后問(wèn)題206
7.4.2整數因子分解209
7.5蒙特卡羅算法211
7.5.1蒙特卡羅算法的基本思想211
7.5.2主元素問(wèn)題213
7.5.3素數測試214
小結217
習題217
第8章NP完全性理論與近似算法221
8.1P類(lèi)與NP類(lèi)問(wèn)題221
8.1.1非確定性圖靈機222
8.1.2P類(lèi)與NP類(lèi)語(yǔ)言222
8.1.3多項式時(shí)間驗證224
8.2NP完全問(wèn)題225
8.2.1多項式時(shí)間變換225
8.2.2Cook定理226
8.3一些典型的NP完全問(wèn)題229
8.3.1合取范式的可滿(mǎn)足性問(wèn)題230
8.3.23元合取范式的可滿(mǎn)足性問(wèn)題230
8.3.3團問(wèn)題231
8.3.4頂點(diǎn)覆蓋問(wèn)題232
8.3.5子集和問(wèn)題233
8.3.6哈密頓回路問(wèn)題235
8.3.7旅行售貨員問(wèn)題238
8.4近似算法的性能238
8.5頂點(diǎn)覆蓋問(wèn)題的近似算法240
8.6旅行售貨員問(wèn)題近似算法241
8.6.1具有三角不等式性質(zhì)的旅行售貨員問(wèn)題242
8.6.2一般的旅行售貨員問(wèn)題243
8.7集合覆蓋問(wèn)題的近似算法244
8.8子集和問(wèn)題的近似算法246
8.8.1子集和問(wèn)題的指數時(shí)間算法247
8.8.2子集和問(wèn)題的完全多項式時(shí)間近似格式247
小結250
習題250
第9章串與序列的算法253
9.1子串搜索算法253
9.1.1串的基本概念253
9.1.2KMP算法255
9.1.3RabinKarp算法258
9.1.4多子串搜索與AC自動(dòng)機260
9.2后綴數組與最長(cháng)公共子串266
9.2.1后綴數組的基本概念266
9.2.2構造后綴數組的倍前綴算法267
9.2.3構造后綴數組的DC3分治法270
9.2.4最長(cháng)公共前綴數組與最長(cháng)公共擴展算法274
9.2.5最長(cháng)公共子串算法276
9.3序列比較算法277
9.3.1編輯距離算法277
9.3.2最長(cháng)公共單調子序列280
9.3.3有約束最長(cháng)公共子序列281
小結284
習題285
第10章算法優(yōu)化策略288
10.1算法設計策略的比較與選擇288
10.1.1最大子段和問(wèn)題的簡(jiǎn)單算法288
10.1.2最大子段和問(wèn)題的分治算法289
10.1.3最大子段和問(wèn)題的動(dòng)態(tài)規劃算法291
10.1.4最大子段和問(wèn)題與動(dòng)態(tài)規劃算法的推廣291
10.2動(dòng)態(tài)規劃加速原理294
10.2.1貨物儲運問(wèn)題294
10.2.2算法及其優(yōu)化295
10.3問(wèn)題的算法特征298
10.3.1貪心策略298
10.3.2對貪心策略的改進(jìn)299
10.3.3算法三部曲299
10.3.4算法實(shí)現300
10.3.5算法復雜性305
10.4優(yōu)化數據結構306
10.4.1帶權區間最短路問(wèn)題306
10.4.2算法設計思想306
10.4.3算法實(shí)現方案308
10.4.4并查集311
10.4.5可并優(yōu)先隊列314
10.5優(yōu)化搜索策略318
小結324
習題324
第11章在線(xiàn)算法設計325
11.1在線(xiàn)算法設計的基本概念325
11.2頁(yè)調度問(wèn)題327
11.3勢函數分析329
11.4k服務(wù)問(wèn)題330
11.4.1競爭比的下界330
11.4.2平衡算法331
11.4.3對稱(chēng)移動(dòng)算法332
11.5Steiner樹(shù)問(wèn)題334
11.6在線(xiàn)任務(wù)調度336
11.7負載平衡337
小結338
習題338
詞匯索引340
參考文獻345