本書為計算機類專業(yè)核心課程“算法設(shè)計與分析”教材. 全書以算法設(shè)計技術(shù)和分析方法為主線來組織各知識單元. 主要內(nèi)容包括基礎(chǔ)知識、分治策略、動態(tài)規(guī)劃、貪心法、回溯與分支限界、線性規(guī)劃、網(wǎng)絡(luò)流算法、算法分析與問題的計算復(fù)雜度、NP完全性、近似算法、隨機算法、處理難解問題的策略等. 力求突出對問題本身的分析和求解方法的闡述，從問題建模、算法設(shè)計與分析、改進措施等方面給出適當?shù)慕ㄗh，同時也簡要介紹了計算復(fù)雜性理論的核心內(nèi)容和處理難解問題的一些新技術(shù).
與本書配套有學(xué)習(xí)指導(dǎo)與習(xí)題解析用書、PPT電子教案，MOOC視頻教學(xué)資源也將近期完成.
本書適合作為大學(xué)計算機科學(xué)與技術(shù)、軟件工程、信息安全、信息與計算科學(xué)等專業(yè)本科生和研究生的教學(xué)用書，也可以作為從事實際問題求解的算法設(shè)計與分析工作的科技人員的參考書.
作為問題求解和程序設(shè)計的重要基礎(chǔ)，“算法設(shè)計與分析”在計算機科學(xué)與技術(shù)專業(yè)的課程體系中是一門重要的必修課。通過該課程的學(xué)習(xí)，不但為學(xué)習(xí)其他專業(yè)課程奠定了扎實的基礎(chǔ)，也對培養(yǎng)學(xué)生的邏輯思維和創(chuàng)造性有著不可替代的作用.ACM IEEE Computing Curricula 2004與我國教育部高等學(xué)校計算機科學(xué)與技術(shù)專業(yè)教學(xué)指導(dǎo)委員會提出的《計算機科學(xué)與技術(shù)專業(yè)規(guī)范》都把該課程列入本專業(yè)的核心課程之一.縱觀計算機學(xué)科數(shù)十年發(fā)展的歷史，算法與計算復(fù)雜性理論一直是計算機科學(xué)研究的熱點和活躍領(lǐng)域，也是獲得圖靈獎最多的研究領(lǐng)域之一.面對計算機應(yīng)用領(lǐng)域的大量問題，最重要的是根據(jù)問題的性質(zhì)選擇正確的求解思路，即找到一個好的算法.特別在復(fù)雜的、海量信息的處理中，一個好的算法往往起著決定性的作用.
目前已經(jīng)出版了許多算法教材，各有特色.作為國家高等教育“十一五”規(guī)劃教材，我們在多年從事算法設(shè)計分析及計算復(fù)雜性理論的教學(xué)和研究的基礎(chǔ)上，精心選材，完成了本書的寫作.本書的主要特點是：
(1) 以算法設(shè)計技術(shù)為主線來組織素材，深入分析各種設(shè)計技術(shù)的適用范圍、設(shè)計步驟、算法的正確性證明與復(fù)雜度的分析方法、改進算法的途徑、局限性等.與通常的算法與數(shù)據(jù)結(jié)構(gòu)教材有所不同，本書不過多地關(guān)注實現(xiàn)細節(jié)，算法描述采用偽碼，力求突出對問題本身的分析和求解方法的闡述，從問題建模、算法設(shè)計與分析、改進措施等方面給出適當?shù)慕ㄗh，為從事實際問題的算法設(shè)計與分析工作在理論上提供清晰的、整體的思路和方法.
(2) 從對具體算法的設(shè)計技術(shù)與分析方法，自然過渡到對問題難度的分析和界定.這里處理的不是一個具體的算法，而是對求解該問題的一大類算法的評價和分析，是對問題本身計算復(fù)雜度的估計.基于這種分析，就能回答“求解該問題的最好算法是什么”，“它能好到什么程度”等問題，從而為選擇最好的算法給出依據(jù).一般的算法教材涉及這方面的知識比較少，本書比較系統(tǒng)地介紹了一些關(guān)于問題復(fù)雜度的分析方法.
(3) NP完全理論是計算復(fù)雜性理論的核心內(nèi)容，其中“P≠NP”的問題是21世紀最重要的數(shù)學(xué)難題之一. 計算復(fù)雜性理論關(guān)注的不僅僅是某個具體問題，而是希望了解每一個問題在計算難度的層次結(jié)構(gòu)中到底處于什么位置，不同問題的難度之間有什么關(guān)系.本書力求用清晰易懂的語言，對計算復(fù)雜性理論的核心內(nèi)容和針對難解問題的處理策略加以簡單的介紹，希望為那些從事復(fù)雜問題求解的讀者提供一點幫助.
(4) 本書的素材來自多年的教學(xué)積淀，選材適當，組織合理，先引入基本概念和數(shù)學(xué)基礎(chǔ)知識，然后進入算法設(shè)計與分析的核心內(nèi)容.在敘述中不但注意理論的嚴謹，也精選了大量生動有趣的例子. 每章都配有難度適當?shù)木毩?xí)，適合教學(xué)使用.
全書共10章，第1章是基礎(chǔ)知識，介紹和算法設(shè)計與分析有關(guān)的基本概念、符號和數(shù)學(xué)知識；第2~5章分別闡述分治策略、動態(tài)規(guī)劃、貪心法、回溯與分支限界等算法設(shè)計技術(shù)；第6章介紹算法分析與問題的計算復(fù)雜度；第7章是NP完全性理論；第8章是近似算法；第9章是隨機算法；第10章介紹處理難解問題的策略.
本書既可以作為本科生教材，也可以作為研究生教材.對于本科生教學(xué)，建議講授第1~6章的全部內(nèi)容，第7~10章可根據(jù)情況選擇部分內(nèi)容做一些概括性的介紹.研究生教學(xué)可以選擇第1~9章的全部內(nèi)容，第10章可根據(jù)情況選講.此外，對于從事實際問題求解的研究工作者，本書也可以作為一本算法設(shè)計與分析的入門參考書.
為了更好地為使用本教材的讀者服務(wù)，作者正在撰寫和開發(fā)與本教材配套的教學(xué)輔導(dǎo)書和PPT電子教案.
本書的第1~4章由屈婉玲完成，第5~6章由王捍貧完成，第7~8章由張立昂完成，第9~10章由劉田完成.
在編寫過程中，作者參考了國內(nèi)外多種版本的算法設(shè)計與分析以及計算復(fù)雜性方面的教材、論文和專著，從中吸取了一些好的思路和素材，在此一并向有關(guān)作者致謝.特別感謝李曉明教授審閱了初稿并提出了寶貴意見，感謝清華大學(xué)出版社對本書出版的大力支持.我們期待著廣大讀者，特別是使用本書的教師和學(xué)生對本書的批評、指正和建議.
作者2010年11月寫于北京大學(xué)
第1章基礎(chǔ)知識1
1.1有關(guān)算法的基本概念1
1.2算法的偽碼描述5
1.3算法的數(shù)學(xué)基礎(chǔ)6
1.3.1函數(shù)的漸近的界6
1.3.2求和的方法10
1.3.3遞推方程求解方法12
習(xí)題121
第2章分治策略26
2.1分治策略的基本思想26
2.1.1兩個熟悉的例子26
2.1.2分治算法的一般性描述27
2.2分治算法的分析技術(shù)27
2.3改進分治算法的途徑31
2.3.1通過代數(shù)變換減少子問題個數(shù)31
2.3.2利用預(yù)處理減少遞歸內(nèi)部的計算量34
2.4典型實例37
2.4.1快速排序算法37
2.4.2選擇問題40
2.4.3n-1次多項式在全體2n次方根上的求值44
習(xí)題247
第3章動態(tài)規(guī)劃52
3.1動態(tài)規(guī)劃的設(shè)計思想52
3.1.1多起點、多終點的最短路徑問題52
3.1.2使用動態(tài)規(guī)劃技術(shù)的必要條件54
3.2動態(tài)規(guī)劃算法的設(shè)計要素55目錄算法設(shè)計與分析(第2版)3.2.1子問題的劃分和遞推方程56
3.2.2動態(tài)規(guī)劃算法的遞歸實現(xiàn)57
3.2.3動態(tài)規(guī)劃算法的迭代實現(xiàn)58
3.2.4一個簡單實例的計算過程59
3.3動態(tài)規(guī)劃算法的典型應(yīng)用60
3.3.1投資問題60
3.3.2背包問題63
3.3.3最長公共子序列LCS65
3.3.4圖像壓縮68
3.3.5最大子段和72
3.3.6最優(yōu)二分檢索樹75
3.3.7生物信息學(xué)中的動態(tài)規(guī)劃算法79
習(xí)題382
第4章貪心法87
4.1貪心法的設(shè)計思想87
4.2關(guān)于貪心法的正確性證明90
4.3對貪心法得不到最優(yōu)解情況的處理94
4.4貪心法的典型應(yīng)用98
4.4.1最優(yōu)前綴碼98
4.4.2最小生成樹103
4.4.3單源最短路徑108
習(xí)題4110
第5章回溯與分支限界114
5.1回溯算法的基本思想和適用條件114
5.1.1幾個典型的例子114
5.1.2回溯算法的適用條件118
5.2回溯算法的設(shè)計步驟119
5.2.1回溯算法的遞歸實現(xiàn)和迭代實現(xiàn)119
5.2.2幾個典型的例子120
5.3回溯算法的效率估計和改進途徑122
5.4分支限界124
5.4.1背包問題125
5.4.2最大團問題127
5.4.3貨郎問題127
5.4.4圓排列問題129
5.4.5連續(xù)郵資問題131
習(xí)題5132
第6章線性規(guī)劃134
6.1線性規(guī)劃模型134
6.1.1模型134
6.1.2二維線性規(guī)劃的圖解法137
6.2標準形138
6.2.1標準形基本概念138
6.2.2標準形的可行解的性質(zhì)140
6.3單純形法142
6.3.1確定初始基本可行解143
6.3.2最優(yōu)性檢驗143
6.3.3基變換144
6.3.4單純形表146
6.3.5人工變量和兩階段法148
6.3.6單純形法的有限終止154
6.4對偶性155
6.4.1對偶線性規(guī)劃155
6.4.2對偶單純形法159
6.5整數(shù)線性規(guī)劃的分支限界算法160
習(xí)題6165
第7章網(wǎng)絡(luò)流算法171
7.1最大流問題171
7.1.1網(wǎng)絡(luò)流及其性質(zhì)171
7.1.2FordFulkerson算法173
7.1.3Dinic有效算法176
7.2最小費用流184
7.2.1Floyd算法184
7.2.2最小費用流的負回路算法186
7.2.3最小費用流的最短路徑算法188
7.3運輸問題189
7.3.1確定初始調(diào)運方案191
7.3.2改進調(diào)運方案191
7.3.3表上作業(yè)法193
7.4二部圖匹配194
7.4.1二部圖的最大匹配194
7.4.2賦權(quán)二部圖的匹配197
習(xí)題7203
第8章算法分析與問題的計算復(fù)雜度208
8.1平凡下界209
8.2直接計數(shù)求解該問題所需要的最少運算210
8.3決策樹211
8.4檢索算法的時間復(fù)雜度分析212
8.5排序算法的時間復(fù)雜度分析214
8.5.1冒泡排序算法214
8.5.2堆排序算法215
8.5.3排序算法的決策樹與算法類時間復(fù)雜度的下界220
8.6選擇算法的時間復(fù)雜度分析222
8.6.1找最大和最小問題223
8.6.2找第二大問題224
8.6.3找中位數(shù)的問題226
8.7通過歸約確認問題計算復(fù)雜度的下界228
習(xí)題8229
第9章NP完全性231
9.1P類與NP類231
9.1.1易解的問題與難解的問題231
9.1.2判定問題233
9.1.3NP類235
9.2多項式時間變換與NP完全性236
9.2.1多項式時間變換236
9.2.2NP完全性及其性質(zhì)238
9.2.3CookLevin定理——第一個NP完全問題239
9.3幾個NP完全問題239
9.3.1最大可滿足性與三元可滿足性240
9.3.2頂點覆蓋、團與獨立集241
9.3.3哈密頓回路與貨郎問題243
9.3.4恰好覆蓋245
9.3.5子集和、背包、裝箱與雙機調(diào)度247
9.3.6整數(shù)線性規(guī)劃249
習(xí)題9252
第10章近似算法255
10.1近似算法及其近似比255
10.2多機調(diào)度問題256
10.2.1貪心的近似算法256
10.2.2改進的貪心近似算法257
10.3貨郎問題258
10.3.1最鄰近法258
10.3.2最小生成樹法259
10.3.3最小權(quán)匹配法260
10.4背包問題261
10.4.1一個簡單的貪心算法261
10.4.2多項式時間近似方案261
10.4.3偽多項式時間算法與完全多項式時間近似方案262
習(xí)題10264
第11章隨機算法266
11.1概率論預(yù)備知識266
11.2對隨機快速排序算法的分析268
11.3隨機算法的分類及其局限性270
11.3.1拉斯維加斯型隨機算法270
11.3.2蒙特卡洛型隨機算法270
11.3.3隨機算法的局限性271
11.4素數(shù)檢驗和多項式恒等檢驗271
11.4.1素數(shù)檢驗271
11.4.2多項式恒等檢驗272
11.5隨機游動算法274
11.5.1有限馬氏鏈及其表示274
11.5.2求解二元布爾可滿足性問題的隨機游動算法275
習(xí)題11276
第12章處理難解問題的策略277
12.1對問題施加限制277
12.1.1二元可滿足性問題278
12.1.2霍恩公式可滿足性問題279
12.2固定參數(shù)算法280
12.3改進指數(shù)時間算法282
12.4啟發(fā)式方法284
12.5平均情形的復(fù)雜性285
12.6難解算例生成287
12.6.1相變現(xiàn)象與難解性287
12.6.2隱藏解的難解算例289
12.7基于統(tǒng)計物理的消息傳遞算法290
12.7.1消息傳遞算法與回溯法、局部搜索算法的比較290
12.7.2用消息傳遞算法求解3SAT問題291
12.8量子算法簡介292
12.8.1量子比特292
12.8.2正交測量293
12.8.3量子門294
12.8.4一個量子算法295
習(xí)題12297
參考文獻298
新書資訊