定 價：49.9 元
叢書名：21世紀(jì)大學(xué)本科計算機(jī)專業(yè)系列教材
- 作者：王曉東
- 出版時間：2018/10/1
- ISBN：9787302510109
- 出 版 社：清華大學(xué)出版社
- 中圖法分類：TP301.6
- 頁碼：
- 紙張：膠版紙
- 版次：
- 開本：16開
為了適應(yīng)培養(yǎng)我國２１世紀(jì)計算機(jī)各類人才的需要，結(jié)合我國高等學(xué)校教育工作的現(xiàn)狀，立足培養(yǎng)學(xué)生能跟上國際計算機(jī)科學(xué)技術(shù)的發(fā)展水平，更新教學(xué)內(nèi)容和教學(xué)方法，提高教學(xué)質(zhì)量，本書以算法設(shè)計策略為知識單元，系統(tǒng)地介紹計算機(jī)算法的設(shè)計方法與分析技巧，以期為計算機(jī)科學(xué)與技術(shù)學(xué)科的學(xué)生提供廣泛而堅實的計算機(jī)算法基礎(chǔ)知識。另有配套的《算法設(shè)計與分析（第4版）習(xí)題解答》，對本書的全部習(xí)題做了詳盡的解答。
本書內(nèi)容豐富，觀點新穎，理論聯(lián)系實際。不僅可用作高等學(xué)校計算機(jī)專業(yè)本科生和研究生學(xué)習(xí)計算機(jī)算法設(shè)計的教材，而且也適合廣大工程技術(shù)人員和自學(xué)讀者學(xué)習(xí)參考。
本書按照教育部*制定的計算機(jī)科學(xué)與技術(shù)專業(yè)規(guī)范的教學(xué)大綱編寫，努力與國際計算機(jī)學(xué)科的教學(xué)要求接軌。強(qiáng)調(diào)算法與數(shù)據(jù)結(jié)構(gòu)之間密不可分的聯(lián)系，因而強(qiáng)調(diào)融數(shù)據(jù)類型與定義在該類型上的運算于一體的抽象數(shù)據(jù)類型，為面向?qū)ο蟮某绦蛟O(shè)計方法奠定基礎(chǔ)，體現(xiàn)計算機(jī)科學(xué)方法論的理論、抽象和設(shè)計三個過程，知識面較寬，且有一定的深度；反復(fù)再現(xiàn)計算機(jī)科學(xué)中用到的大問題的復(fù)雜性、效率、抽象的層次、重用、折衷等帶有普遍性的概念，讓讀者在更深的層次上掌握算法與數(shù)據(jù)結(jié)構(gòu)這一主科目。
21世紀(jì)大學(xué)本科計算機(jī)專業(yè)系列教材編委會
主任： 李曉明副主任： 蔣宗禮盧先和委員： （按姓氏筆畫為序）
馬華東馬殿富王志英王曉東寧洪
劉辰孫茂松李仁發(fā)李文新楊波
吳朝暉何炎祥宋方敏張莉金海
周興社孟祥旭袁曉潔錢樂秋黃國興
曾明廖明宏秘書： 張瑞慶
本書責(zé)任編委： 宋方敏
前言FOREWORD
以最低的成本、最快的速度、最好的質(zhì)量開發(fā)出適合各種應(yīng)用需求的軟件，必須遵循軟件工程的原則，設(shè)計出高效率的程序。一個高效的程序不僅需要編程技巧，更需要合理的數(shù)據(jù)組織和清晰高效的算法。這正是計算機(jī)科學(xué)領(lǐng)域里數(shù)據(jù)結(jié)構(gòu)與算法設(shè)計所研究的主要內(nèi)容。一些著名的計算機(jī)科學(xué)家在有關(guān)計算機(jī)科學(xué)教育的論述中提出，計算機(jī)科學(xué)是一種創(chuàng)造性思維活動，其教育必須面向設(shè)計。計算機(jī)算法設(shè)計與分析正是一門面向設(shè)計，且處于計算機(jī)科學(xué)與技術(shù)學(xué)科核心地位的教育課程。通過對計算機(jī)算法系統(tǒng)的學(xué)習(xí)與研究，理解和掌握算法設(shè)計的主要方法，培養(yǎng)對算法的計算復(fù)雜性進(jìn)行正確分析的能力，為獨立地設(shè)計算法和對給定算法進(jìn)行復(fù)雜性分析奠定堅實的理論基礎(chǔ)，對從事計算機(jī)系統(tǒng)結(jié)構(gòu)、系統(tǒng)軟件和應(yīng)用軟件研究與開發(fā)的科技工作者是非常重要和必不可少的。為了適應(yīng)我國21世紀(jì)計算機(jī)人才培養(yǎng)的需要，結(jié)合我國高等學(xué)校教育工作的現(xiàn)狀，立足培養(yǎng)學(xué)生能跟上國際計算機(jī)科學(xué)技術(shù)的發(fā)展水平，更新教學(xué)內(nèi)容和教學(xué)方法，本書以算法設(shè)計策略為知識單元，系統(tǒng)地介紹計算機(jī)算法的設(shè)計方法與分析技巧，以期為計算機(jī)科學(xué)與技術(shù)學(xué)科的學(xué)生提供一個廣泛而堅實的計算機(jī)算法基礎(chǔ)知識。
全書共分11章。在第１章中首先介紹算法的基本概念，接著簡要闡述算法的計算復(fù)雜性和算法的描述，然后圍繞設(shè)計算法常用的基本設(shè)計策略組織第２章至第10章的內(nèi)容。第2章介紹遞歸與分治策略，這是設(shè)計有效算法最常用的策略，是必須掌握的方法。第3章是動態(tài)規(guī)劃算法，以具體實例詳述動態(tài)規(guī)劃算法的設(shè)計思想、適用性以及算法的設(shè)計要點。第4章介紹貪心算法，這也是一種重要的算法設(shè)計策略，它與動態(tài)規(guī)劃算法的設(shè)計思想有一定的聯(lián)系，但其效率更高。按貪心算法設(shè)計出的許多算法能導(dǎo)致最優(yōu)解，其中有許多典型問題和典型算法可供學(xué)習(xí)和使用。第５章和第６章分別介紹回溯法和分支限界法，這兩章所介紹的算法適合處理難解問題，其解題的思想各具特色，值得學(xué)習(xí)和掌握。第７章介紹概率算法，對許多難解問題提供高效的解決途徑，是有很高實用價值的算法設(shè)計策略。第８章介紹NP完全性理論和解NP難問題的近似算法。首先介紹計算模型、確定性和非確定性圖靈機(jī)，然后進(jìn)一步深入介紹NP完全性理論，最后介紹解NP難問題的近似算法，這是當(dāng)前計算機(jī)算法領(lǐng)域的熱門研究課題，具有很高的實用價值。第9章介紹有關(guān)串和序列的高效算法。第10章通過實例介紹算法設(shè)計中常用的算法優(yōu)化策略。最后，在第11章介紹算法設(shè)計中較新的研究領(lǐng)域在線算法設(shè)計。
在本書各章的論述中，首先介紹一種算法設(shè)計策略的基本思想，然后從解決計算機(jī)科學(xué)與應(yīng)用中出現(xiàn)的實際問題入手，由簡到繁地描述幾個經(jīng)典的精巧算法，同時對每個算法所需要的時間和空間進(jìn)行分析。這樣使讀者既能學(xué)到一些常用的精巧算法，又能通過對算法設(shè)計策略的反復(fù)應(yīng)用，牢固掌握這些算法設(shè)計的基本策略，以期收到融會貫通之效。在為各種算法設(shè)計策略選擇用于展示其設(shè)計思想與技巧的具體應(yīng)用問題時，本書有意重復(fù)選擇某些經(jīng)典問題，使讀者能深刻地體會到一個問題可以用多種設(shè)計策略求解。同時，通過對解同一問題的不同算法的比較，更容易體會到每一個具體算法的設(shè)計要點。隨著本書內(nèi)容的逐步展開，讀者也將進(jìn)一步感受到綜合應(yīng)用多種設(shè)計策略可以更有效地解決問題。
本書采用面向?qū)ο蟮腏ava語言作為表述手段，在保持Java優(yōu)點的同時，盡量使算法的描述簡明、清晰。
為了便于讀者加深對知識的理解，各章配有難易適當(dāng)?shù)牧?xí)題，以適應(yīng)不同程度讀者練習(xí)的需要。
在本書的編寫過程中，得到教育部高等學(xué)校計算機(jī)類專業(yè)教學(xué)指導(dǎo)委員會的關(guān)心和支持。福州大學(xué)211工程計算機(jī)與信息工程重點學(xué)科實驗室和福建工程學(xué)院為本書的寫作提供了優(yōu)良的設(shè)備與工作環(huán)境。清華大學(xué)出版社負(fù)責(zé)本書編輯出版工作的全體人員為本書的出版付出了大量辛勤勞動，他們認(rèn)真細(xì)致、一絲不茍的工作精神保證了本書的出版質(zhì)量。南京大學(xué)宋方敏教授和福州大學(xué)傅清祥教授在百忙中認(rèn)真審閱了全書，提出了許多寶貴的改進(jìn)意見。在此，謹(jǐn)向每一位曾經(jīng)關(guān)心和支持本書編寫工作的各方面人士表示衷心的謝意！
由于作者的知識和寫作水平有限，書稿雖幾經(jīng)修改，仍難免存在缺點。熱忱歡迎同行專家和讀者惠予批評指正，使本書在使用過程中不斷改進(jìn)，日臻完善。作者2018年6月前言算法設(shè)計與分析(第4版)
王曉東,教授，博士生導(dǎo)師。近年來正式出版學(xué)術(shù)著作11部。近年在國內(nèi)外學(xué)術(shù)刊物上發(fā)表學(xué)術(shù)論文60多篇。參加多項科研項目并獲獎。其中獲國家科技進(jìn)步二等獎一項，水電部科技進(jìn)步一等獎一項，福建省科技進(jìn)步三等獎一項，省水電廳科技進(jìn)步一等獎一項。
目錄CONTENTS
第1章算法引論1
1.1算法與程序1
1.2表達(dá)算法的抽象機(jī)制1
1.3描述算法3
1.4算法復(fù)雜性分析10
小結(jié)13
習(xí)題14
第2章遞歸與分治策略16
2.1遞歸的概念16
2.2分治法的基本思想21
2.3二分搜索技術(shù)23
2.4大整數(shù)的乘法23
2.5Strassen矩陣乘法24
2.6棋盤覆蓋26
2.7合并排序28
2.8快速排序30
2.9線性時間選擇33
2.10最接近點對問題35
2.11循環(huán)賽日程表43
小結(jié)44
習(xí)題44
第3章動態(tài)規(guī)劃50
3.1矩陣連乘問題50
3.2動態(tài)規(guī)劃算法的基本要素55
3.3最長公共子序列58
3.4凸多邊形最優(yōu)三角剖分61
3.5多邊形游戲64
3.6圖像壓縮67
3.7電路布線69
3.8流水作業(yè)調(diào)度72
3.90\|1背包問題75
3.10最優(yōu)二叉搜索樹80
小結(jié)83
習(xí)題83
目錄算法設(shè)計與分析(第4版)第4章貪心算法85
4.1活動安排問題85
4.2貪心算法的基本要素88
4.2.1貪心選擇性質(zhì)88
4.2.2最優(yōu)子結(jié)構(gòu)性質(zhì)89
4.2.3貪心算法與動態(tài)規(guī)劃算法的差異89
4.3最優(yōu)裝載91
4.4哈夫曼編碼92
4.4.1前綴碼93
4.4.2構(gòu)造哈夫曼編碼93
4.4.3哈夫曼算法的正確性95
4.5單源最短路徑96
4.5.1算法基本思想97
4.5.2算法的正確性和計算復(fù)雜性98
4.6最小生成樹99
4.6.1最小生成樹性質(zhì)99
4.6.2Prim算法100
4.6.3Kruskal算法102
4.7多機(jī)調(diào)度問題104
4.8貪心算法的理論基礎(chǔ)106
4.8.1擬陣106
4.8.2帶權(quán)擬陣的貪心算法107
4.8.3任務(wù)時間表問題109
小結(jié)113
習(xí)題113
第5章回溯法115
5.1回溯法的算法框架115
5.1.1問題的解空間115
5.1.2回溯法的基本思想116
5.1.3遞歸回溯117
5.1.4迭代回溯118
5.1.5子集樹與排列樹119
5.2裝載問題120
5.3批處理作業(yè)調(diào)度126
5.4符號三角形問題128
5.5n后問題130
5.601背包問題133
5.7最大團(tuán)問題136
5.8圖的m著色問題138
5.9旅行售貨員問題140
5.10圓排列問題142
5.11電路板排列問題144
5.12連續(xù)郵資問題147
5.13回溯法的效率分析149
小結(jié)152
習(xí)題152
第6章分支限界法153
6.1分支限界法的基本思想153
6.2單源最短路徑問題156
6.3裝載問題158
6.4布線問題166
6.501背包問題170
6.6最大團(tuán)問題175
6.7旅行售貨員問題178
6.8電路板排列問題181
6.9批處理作業(yè)調(diào)度184
小結(jié)189
習(xí)題189
第7章概率算法190
7.1隨機(jī)數(shù)191
7.2數(shù)值概率算法193
7.2.1用隨機(jī)投點法計算值193
7.2.2計算定積分194
7.2.3解非線性方程組195
7.3舍伍德算法197
7.3.1線性時間選擇算法198
7.3.2跳躍表200
7.4拉斯維加斯算法205
7.4.1n后問題206
7.4.2整數(shù)因子分解209
7.5蒙特卡羅算法211
7.5.1蒙特卡羅算法的基本思想211
7.5.2主元素問題213
7.5.3素數(shù)測試214
小結(jié)217
習(xí)題217
第8章NP完全性理論與近似算法221
8.1P類與NP類問題221
8.1.1非確定性圖靈機(jī)222
8.1.2P類與NP類語言222
8.1.3多項式時間驗證224
8.2NP完全問題225
8.2.1多項式時間變換225
8.2.2Cook定理226
8.3一些典型的NP完全問題229
8.3.1合取范式的可滿足性問題230
8.3.23元合取范式的可滿足性問題230
8.3.3團(tuán)問題231
8.3.4頂點覆蓋問題232
8.3.5子集和問題233
8.3.6哈密頓回路問題235
8.3.7旅行售貨員問題238
8.4近似算法的性能238
8.5頂點覆蓋問題的近似算法240
8.6旅行售貨員問題近似算法241
8.6.1具有三角不等式性質(zhì)的旅行售貨員問題242
8.6.2一般的旅行售貨員問題243
8.7集合覆蓋問題的近似算法244
8.8子集和問題的近似算法246
8.8.1子集和問題的指數(shù)時間算法247
8.8.2子集和問題的完全多項式時間近似格式247
小結(jié)250
習(xí)題250
第9章串與序列的算法253
9.1子串搜索算法253
9.1.1串的基本概念253
9.1.2KMP算法255
9.1.3RabinKarp算法258
9.1.4多子串搜索與AC自動機(jī)260
9.2后綴數(shù)組與最長公共子串266
9.2.1后綴數(shù)組的基本概念266
9.2.2構(gòu)造后綴數(shù)組的倍前綴算法267
9.2.3構(gòu)造后綴數(shù)組的DC3分治法270
9.2.4最長公共前綴數(shù)組與最長公共擴(kuò)展算法274
9.2.5最長公共子串算法276
9.3序列比較算法277
9.3.1編輯距離算法277
9.3.2最長公共單調(diào)子序列280
9.3.3有約束最長公共子序列281
小結(jié)284
習(xí)題285
第10章算法優(yōu)化策略288
10.1算法設(shè)計策略的比較與選擇288
10.1.1最大子段和問題的簡單算法288
10.1.2最大子段和問題的分治算法289
10.1.3最大子段和問題的動態(tài)規(guī)劃算法291
10.1.4最大子段和問題與動態(tài)規(guī)劃算法的推廣291
10.2動態(tài)規(guī)劃加速原理294
10.2.1貨物儲運問題294
10.2.2算法及其優(yōu)化295
10.3問題的算法特征298
10.3.1貪心策略298
10.3.2對貪心策略的改進(jìn)299
10.3.3算法三部曲299
10.3.4算法實現(xiàn)300
10.3.5算法復(fù)雜性305
10.4優(yōu)化數(shù)據(jù)結(jié)構(gòu)306
10.4.1帶權(quán)區(qū)間最短路問題306
10.4.2算法設(shè)計思想306
10.4.3算法實現(xiàn)方案308
10.4.4并查集311
10.4.5可并優(yōu)先隊列314
10.5優(yōu)化搜索策略318
小結(jié)324
習(xí)題324
第11章在線算法設(shè)計325
11.1在線算法設(shè)計的基本概念325
11.2頁調(diào)度問題327
11.3勢函數(shù)分析329
11.4k服務(wù)問題330
11.4.1競爭比的下界330
11.4.2平衡算法331
11.4.3對稱移動算法332
11.5Steiner樹問題334
11.6在線任務(wù)調(diào)度336
11.7負(fù)載平衡337
小結(jié)338
習(xí)題338
詞匯索引340
參考文獻(xiàn)345
書單推薦
