演演算法設計與分析

本教材為計算機科學技術專業核心課程“演演算法設計與分析”教材。全書以演演算法設計技術和分析方法為主線來組織各知識單元，主要內容包括基礎知識、分治策略、動態規劃、貪心法、回溯與分支限界、演演算法分析與問題的計算複雜度、NP完全性、近似演演算法、隨機演演算法、處理難解問題的策略等。書中突出對問題本身的分析和求解方法的闡述，從問題建模、演演算法設計與分析、改進措施等方面給出適當的建議，同時也簡要介紹了計算複雜性理論的核心內容和處理難解問題的一些新技術。本書有配套的學習指導與習題解析用書以及PPT電子教案。本書可作為大學計算機科學與技術、軟體工程、信息安全、信息與計算機科學等專業本科生和研究生教學用書，也可以作為從事實際問題求解的演演算法設計與分析工作的參考書。

目錄CONTENTS第1章基礎知識1

1.1有關演演算法的基本概念1

1.2演演算法的偽碼描述5

1.3演演算法的數學基礎6

1.3.1函數的漸近的界6

1.3.2求和的方法10

1.3.3遞推方程求解方法12

習題121

第2章分治策略25

2.1分治策略的基本思想25

2.1.1兩個熟悉的例子25

2.1.2分治演演算法的一般性描述26

2.2分治演演算法的分析技術26

2.3改進分治演演算法的途徑30

2.3.1通過代數變換減少子問題個數30

2.3.2利用預處理減少遞歸內部的計算量33

2.4典型實例36

2.4.1快速排序演演算法36

2.4.2選擇問題39

2.4.3n-1次多項式在全體2n次方根上的求值43

習題246

第3章動態規劃51

3.1動態規劃的設計思想51

3.1.1多起點、多終點的最短路徑問題51

3.1.2使用動態規劃技術的必要條件53

3.2動態規劃演演算法的設計要素54

3.2.1子問題的劃分和遞推方程55

3.2.2動態規劃演演算法的遞歸實現56

3.2.3動態規劃演演算法的迭代實現57

3.2.4一個簡單實例的計算過程58

3.3動態規劃演演算法的典型應用59

3.3.1投資問題59

3.3.2背包問題61

3.3.3最長公共子序列LCS64

3.3.4圖像壓縮67

3.3.5最大子段和71

3.3.6最優二分檢索樹74

3.3.7生物信息學中的動態規劃演演算法78

習題381

目錄演演算法設計與分析第4章貪心法85

4.1貪心法的設計思想85

4.2關於貪心法的正確性證明88

4.3對貪心法得不到最優解情況的處理92

4.4貪心法的典型應用96

4.4.1最優前綴碼96

4.4.2最小生成樹101

4.4.3單源最短路徑106

習題4108

第5章回溯與分支限界112

5.1回溯演演算法的基本思想和適用條件112

5.1.1幾個典型的例子112

5.1.2回溯演演算法的適用條件116

5.2回溯演演算法的設計步驟117

5.2.1回溯演演算法的遞歸實現和迭代實現117

5.2.2幾個典型的例子118

5.3回溯演演算法的平均效率和改進途徑120

5.4分支限界122

5.4.1背包問題123

5.4.2最大團問題125

5.4.3貨郎問題125

5.4.4圓排列問題127

5.4.5連續郵資問題129

習題5130

第6章演演算法分析與問題的計算複雜度132

6.1平凡下界133

6.2直接計數求解該問題所需要的最少運算134

6.3決策樹135

6.4檢索演演算法的時間複雜度分析136

6.5排序演演算法的時間複雜度分析138

6.5.1冒泡排序演演算法138

6.5.2堆排序演演算法139

6.5.3排序演演算法的決策樹與演演算法類時間複雜度的下界144

6.6選擇演演算法的時間複雜度分析146

6.6.1找最大和最小問題147

6.6.2找第二大問題148

6.6.3找中位數的問題150

6.7通過歸約確認問題計算複雜度的下界152

習題6153

第7章NP完全性155

7.1P類與NP類155

7.1.1易解的問題與難解的問題155

7.1.2判定問題157

7.1.3NP類159

7.2多項式時間變換與NP完全性160

7.2.1多項式時間變換160

7.2.2NP完全性162

7.2.3Cook-Levin定理--第一個NP完全問題163

7.3幾個NP完全問題163

7.3.1最大可滿足性與三元可滿足性163

7.3.2頂點覆蓋、團與獨立集165

7.3.3哈密頓迴路與貨郎問題167

7.3.4恰好覆蓋169

7.3.5子集和、背包、裝箱與雙機調度171

習題7174

第8章近似演演算法176

8.1近似演演算法及其近似比176

8.2多機調度問題177

8.2.1貪心的近似演演算法177

8.2.2改進的貪心近似演演算法178

8.3貨郎問題179

8.3.1最鄰近法179

8.3.2最小生成樹法180

8.3.3最小權匹配法181

8.4背包問題182

8.4.1一個簡單的貪心演演算法182

8.4.2多項式時間近似方案182

8.4.3偽多項式時間演演算法與完全多項式時間近似方案183

習題8185

第9章隨機演演算法187

9.1概率論預備知識187

9.2對隨機快速排序演演算法的分析189

9.3隨機演演算法的分類及其局限性191

9.3.1拉斯維加斯型隨機演演算法191

9.3.2蒙特卡洛型隨機演演算法191

9.3.3隨機演演算法的局限性192

9.4素數檢驗和多項式恆等檢驗193

9.4.1素數檢驗193

9.4.2多項式恆等檢驗194

9.5隨機遊動演演算法195

9.5.1有限馬氏鏈及其表示195

9.5.2求解二元布爾可滿足性問題的隨機遊動演演算法196

習題9197

第10章處理難解問題的策略198

10.1對問題施加限制198

10.1.1二元可滿足性問題199

10.1.2霍恩公式可滿足性問題200

10.2固定參數演演算法201

10.3改進指數時間演演算法203

10.4啟髮式方法205

10.5平均情形的複雜性206

10.6難解算例生成208

10.6.1相變現象與難解性208

10.6.2隱藏解的難解算例210

10.7基於統計物理的消息傳遞演演算法211

10.7.1消息傳遞演演算法與回溯法、局部搜索演演算法的比較211

10.7.2基於統計物理的消息傳遞演演算法212

10.8量子演演算法簡介213

10.8.1量子比特213

10.8.2正交測量214

10.8.3量子門215

10.8.4一個量子演演算法216

習題10218

該教材是作者在多年從事演演算法設計分析及計算複雜性理論的教學和研究的基礎上編寫而成。

該教材的第1~4章由屈婉玲完成，第5~6章由王捍貧完成，第7~8章由張立昂完成，第9~10章由劉田完成。

在編寫過程中，作者參考了中國國內外多種版本的演演算法設計與分析以及計算複雜性方面的教材、論文和專著，從中吸取了一些好的思路和素材；李曉明教授審閱了初稿並提出了修改意見。

2011年5月1日，該教材由清華大學出版社出版。

● 配套教材

該教材有配套的學習指導與習題解析用書——《演演算法設計與分析習題解答與學習指導》。

● 課程資源

該教材提供PPT電子教案。

該教材的主要特點是：

● ● 該教材沒有過多地關注實現細節，演演算法描述採用偽碼，突出對問題本身的分析和求解方法的闡述，從問題建模、演演算法設計與分析、改進措施等方面給出了建議，為從事實際問題的演演算法設計與分析工作在理論上提供思路和方法；

● ● 該教材介紹了一些關於問題複雜度的分析方法；

● ● 該教材對計算複雜性理論的核心內容和針對難解問題的處理策略加以簡單的介紹；

● ● 該教材的素材來自多年的教學積澱，先引入基本概念和數學基礎知識，然後進入演演算法設計與分析的核心內容。

屈婉玲，北京大學信息科學技術學院教授、博士生導師，長期從事離散數學、演演算法分析和計算複雜性等方向的教學和研究工作。曾獲得北京市教學成果獎一等獎，被評為北京大學十佳教師和北京市優秀教師。

劉田，博士，北京大學信息科學技術學院副教授、中國電子學會電路與系統分會圖論與系統優化專委會副理事長、中國計算機學會理論計算機科學專委會委員，主要從事演演算法分析與計算複雜度方面的研究和教學工作。

張立昂，北京大學信息科學技術學院教授、博士生導師，一直從事數學和理論計算機科學的教學與研究工作，主要研究方向是計算複雜性理論和演演算法設計與分析，曾獲得北京市教學成果獎一等獎和教育部科技進步二等獎。

王捍貧，博士，北京大學信息科學技術學院教授、博士生導師、軟體研究所副所長、中國人工智慧學會離散智能計算專委會主任，長期從事離散數學、形式化方法及演演算法設計與分析的教學和研究工作，曾獲得北京市教學成果獎一等獎。