算法設計與分析檢視原始碼討論檢視歷史

來自 孔夫子網 的圖片

《算法設計與分析》，王紅梅 著，出版社： 清華大學出版社。

清華大學出版社成立於1980年6月，是教育部主管、清華大學主辦的綜合性大學出版社。清華社現年出版圖書、音像製品、電子出版物等近3000種，銷售規模和綜合實力以及在高等教育教材市場、科技圖書市場、館配圖書市場占有率均名列前茅。

目錄

篇基 礎 知 識

章算法設計基礎3

1.1什麼是算法3

1.1.1算法的定義3

1.1.2算法的描述方法4

1.1.3算法在問題求解中的地位6

1.2什麼是好算法6

1.2.1如何評價算法6

1.2.2效率——算法的核心和靈魂7

1.3為什麼要學習和研究算法8

1.3.1算法研究是推動計算機技術發展的關鍵8

1.3.2算法訓練能夠提高計算思維能力8

1.3.3程序員要學習算法9

1.4如何設計算法9

1.4.1基本的數據結構9

1.4.2重要的問題類型11

1.4.3算法設計的一般過程13

1.5拓展與演練14

1.5.1算法研究與圖靈獎14

1.5.2代碼優化技巧15

實驗1公約數17

習題118第2章算法分析基礎19

2.1算法的時間複雜度分析19

2.1.1輸入規模與基本語句192.1.2算法的漸近分析21

2.1.3、最壞和平均情況22

2.1.4非遞歸算法的時間複雜度分析22

2.1.5遞歸算法的時間複雜度分析23

2.2算法的空間複雜度分析24

2.3算法的實驗分析25

2.4拓展與演練26

2.4.1算法26

2.4.2角谷猜想27

實驗2排序算法的實驗比較28

習題229

算法設計與分析（第3版）目錄第二篇基本的算法設計技術

第3章模擬法33

3.1概述33

3.1.1模擬法的設計思想33

3.1.2一個簡單的例子: 雞兔同籠問題33

3.2數學問題中的模擬法34

3.2.1約瑟夫環問題34

3.2.2埃拉托色尼篩法35

3.3排序問題中的模擬法37

3.3.1計數排序37

3.3.2顏色排序38

3.4拓展與演練39

3.4.1裝箱問題39

3.4.2數字迴轉方陣41

實驗3埃氏篩法的優化42

習題342第4章遞推法45

4.1概述45

4.1.1遞推法的設計思想45

4.1.2一個簡單的例子: 猴子吃桃45

4.2數學問題中的遞推法46

4.2.1Fibonacci數列46

4.2.2Catalan數列46

4.3組合問題中的遞推法48

4.3.1伯努利錯裝信封問題48

4.3.2旋轉的萬花筒49

4.4拓展與演練49

4.4.1整數劃分49

4.4.2捕魚知多少50

實驗4楊輝三角形51

習題451第5章蠻力法53

5.1概述53

5.1.1蠻力法的設計思想53

5.1.2一個簡單的例子: 百元買百雞問題54

5.2查找問題中的蠻力法54

5.2.1順序查找54

5.2.2串匹配問題56

5.3排序問題中的蠻力法61

5.3.1選擇排序61

5.3.2起泡排序62

5.4圖問題中的蠻力法63

5.4.1哈密頓迴路問題63

5.4.2TSP問題64

5.5幾何問題中的蠻力法65

5.5.1最近對問題65

5.5.2凸包問題66

5.6拓展與演練68

5.6.1KMP算法中next值的計算68

5.6.20/1背包問題69

實驗5任務分配問題70

習題571第6章分治法73

6.1概述73

6.1.1分治法的設計思想73

6.1.2分治與遞歸74

6.1.3一個簡單的例子: 漢諾塔問題74

6.2排序問題中的分治法75

6.2.1歸併排序75

6.2.2快速排序77

6.3組合問題中的分治法80

6.3.1子段和問題80

6.3.2棋盤覆蓋問題82

6.4幾何問題中的分治法84

6.4.1最近對問題84

6.4.2凸包問題86

6.5拓展與演練88

6.5.1擴展歐幾里得算法88

6.5.2中國剩餘定理89

實驗6Karatsuba乘法90

習題691第7章減治法93

7.1概述93

7.1.1減治法的設計思想93

7.1.2一個簡單的例子: 俄式乘法94

7.2查找問題中的減治法94

7.2.1折半查找94

7.2.2選擇問題96

7.3排序問題中的減治法98

7.3.1插入排序98

7.3.2堆排序99

7.4組合問題中的減治法101

7.4.1淘汰賽問題101

7.4.2問題102

7.5拓展與演練104

7.5.1兩個序列的中位數104

7.5.2topK問題106

實驗7問題的複雜版本107

習題7109第8章貪心法111

8.1概述111

8.1.1貪心法的設計思想111

8.1.2一個簡單的例子: 付款問題111

8.2圖問題中的貪心法112

8.2.1TSP問題112

8.2.2圖着色問題114

8.2.3最小生成樹116

8.3組合問題中的貪心法119

8.3.1背包問題119

8.3.2活動安排問題121

8.3.3埃及分數123

8.4拓展與演練124

8.4.1貪心法的正確性證明124

8.4.2田忌賽馬126

實驗8合併字符串127

習題8127第9章動態規劃法129

9.1概述129

9.1.1多階段決策過程129

9.1.2動態規劃法的設計思想130

9.1.3一個簡單的例子: 網格上的最短路徑131

9.2組合問題中的動態規劃法133

9.2.1公共子序列133

9.2.20/1背包問題135

9.3圖問題中的動態規劃法137

9.3.1多段圖的最短路徑137

9.3.2TSP問題140

9.4查找問題中的動態規劃法141

9.4.1近似串匹配141

9.4.2二叉查找樹144

9.5拓展與演練146

9.5.1性原理146

9.5.2數塔問題147

實驗9子段和150

習題9150

第三篇基於搜索的算法設計技術

0章深度優先搜索155

10.1深度優先搜索概述155

10.1.1深度優先搜索的設計思想155

10.1.2山洞尋寶圖156

10.1.3城堡問題157

10.2回溯法158

10.2.1問題的解空間樹158

10.2.2回溯法的設計思想159

10.2.3回溯法的時間性能160

10.2.4素數環問題160

10.2.5八皇后問題162

10.2.6圖着色問題164

10.3拓展與演練167

10.3.1批處理作業調度167

10.3.2哈密頓迴路170

實驗100/1背包問題172

習題101731章廣度優先搜索175

11.1廣度優先搜索概述175

11.1.1廣度優先搜索的設計思想175

11.1.2農夫抓牛176

11.1.3騎士旅行177

11.2A算法179

11.2.1A算法的設計思想179

11.2.2八數碼問題180

11.2.3多段圖的最短路徑問題181

11.2.4任務分配問題183

11.3限界剪枝法184

11.3.1限界剪枝法的設計思想184

11.3.20/1背包問題185

11.3.3TSP問題187

11.3.4圓排列問題189

11.4拓展與演練191

11.4.1限界剪枝法的關鍵問題191

11.4.2批處理作業調度問題192

實驗11電路布線問題194

習題11195

第四篇NP問題的算法設計技術

2章問題的複雜性199

12.1問題的複雜性分類199

12.1.1什麼是計算199

12.1.2可計算問題與不可計算問題201

12.1.3易解問題與難解問題202

12.2P類問題與NP類問題204

12.2.1判定問題204

12.2.2確定性算法與P類問題205

12.2.3非確定性算法與NP類問題205

12.3NP問題206

12.3.1問題變換206

12.3.2NP問題的定義207

12.3.3基本的NP問題207

12.4拓展與演練208

12.4.1k帶圖靈機208

12.4.2NP類問題的計算機處理209

實驗12SAT問題210

習題122103章近似算法213

13.1概述213

13.1.1近似算法的設計思想213

13.1.2一個簡單的例子: 求π的近似值214

13.2圖問題中的近似算法215

13.2.1頂點覆蓋問題215

13.2.2TSP問題216

13.3組合問題中的近似算法217

13.3.1裝箱問題217

13.3.2多機調度問題219

13.4拓展與演練222

13.4.1帶權頂點覆蓋問題222

13.4.2子集和問題223

實驗13TSP問題的近似算法226

習題132274章概率算法229

14.1概述229

14.1.1概率算法的設計思想229

14.1.2數生成器230

14.2舍伍德型概率算法231

14.2.1舍伍德型概率算法的設計思想231

14.2.2快速排序231

14.2.3二叉查找樹232

14.3拉斯維加斯型概率算法234

14.3.1拉斯維加斯型概率算法的設計思想234

14.3.2八皇后問題234

14.3.3整數因子劃分問題235

14.4蒙特卡羅型概率算法236

14.4.1蒙特卡羅型概率算法的設計思想236

14.4.2主元素問題237

14.4.3素數測試238

14.5拓展與演練239

14.5.1數與數生成器239

14.5.2蒙特卡羅型算法計算定積分240

實驗14數生成器241

習題142415章群智能算法243

15.1遺傳算法243

15.1.1遺傳算法的基本思想243

15.1.2遺傳算法的關鍵問題244

15.1.3應用舉例245

15.2蟻群算法246

15.2.1蟻群算法的基本原理246

15.2.2蟻群算法的參數設定247

15.2.3應用舉例248

15.3粒子群算法249

15.3.1粒子群算法的基本思想249

15.3.2粒子群算法的參數分析250

15.3.3應用舉例250

實驗15函數的值251

習題15251名詞索引253參考文獻257