算法設計與分析(屈婉玲、劉田、張立昂、王捍貧編著書籍)

《算法設計與分析》是2011年清華大學出版社出版的圖書，作者是屈婉玲、劉田、張立昂、王捍貧。

基本介紹

• 書名：算法設計與分析
• 作者：屈婉玲、劉田、張立昂、王捍貧
• ISBN：9787302247562
• 定價：25
• 出版社：清華大學出版社
• 出版時間：2011.05.01

內容簡介

本教材為計算機科學技術專業核心課程“算法設計與分析”教材.全書以算法設計技術和分析方法為主線來組織各知識單元，主要內容包括基礎知識、分治策略、動態規劃、貪心法、回溯與分支限界、算法分析與問題的計算複雜度、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 最長公共子序列LCS 64

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.1 P類與NP類155

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

7.1.2 判定問題157

7.1.3 NP類159

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

7.2.1 多項式時間變換160

7.2.2 NP完全性162

7.2.3 Cook-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

參考文獻219

第1章 程式設計概述11.1 學習要點1

1.2 Visual C++ 6.0集成開發環境1

1.2.1 Visual C++ 6.0開發環境介紹1

1.2.2 創建一個C源程式6

1.2.3 C源程式的編譯、連線和運行12

1.2.4 C程式的單步調試命令13

1.2.5 C程式的調試視窗18

1.2.6 創建一個項目檔案(工程)28

1.3 實驗 認識Visual C++ 6.0的開發環境32

1.4 常見錯誤及解決方法33

第2章 C語言基礎知識34

2.1 學習要點34

2.2 實驗內容36

2.2.1 實驗1 變數的使用與賦值運算36

2.2.2 實驗2 格式化輸入輸出函式的套用37

2.2.3 實驗3 宏定義、條件編譯編程39

2.2.4 實驗4 位運算編程39

2.3 常見錯誤及解決方法40

第3章 程式的控制結構46

3.1 學習要點46

3.2 實驗內容48

3.2.1 實驗1 if語句編程48

3.2.2 實驗2 switch語句編程50

3.2.3 實驗3 循環結構編程50

3.3 常見錯誤及解決方法51目 錄 程式設計基礎(C語言)實驗指導第4章 數組58

4.1 學習要點58

4.2 實驗內容62

4.2.1 實驗1 一維數組編程62

4.2.2 實驗2 二維數組編程63

4.2.3 實驗3 字元數組編程64

4.3 常見錯誤及解決方法65

第5章 函式69

5.1 學習要點69

5.2 實驗內容70

5.2.1 實驗1 簡單函式編程70

5.2.2 實驗2 綜合運用一維數組和函式編程71

5.2.3 實驗3 綜合運用二維數組和函式編程73

5.2.4 實驗4 遞歸函式與分治算法編程75

5.2.5 實驗5 變數的存儲類別、內部與外部函式編程75

5.3 常見錯誤及解決方法77

第6章 指針84

6.1 學習要點84

6.2 實驗內容87

6.2.1 實驗1 指向變數的指針變數編程87

6.2.2 實驗2 字元指針編程88

6.2.3 實驗3 指向一維數組的指針變數編程89

6.2.4 實驗4 指向二維數組的指針變數編程90

6.2.5 實驗5 動態數組編程91

6.3 常見錯誤及解決方法92

第7章 結構體與鍊表96

7.1 學習要點96

7.2 實驗內容98

7.2.1 實驗1 結構體變數與結構體數組編程98

7.2.2 實驗2 鍊表基本操作編程99

7.2.3 實驗3 鍊表複雜套用編程101

7.3 常見錯誤及解決方法102

第8章 檔案105

8.1 學習要點105

8.2 實驗內容107

8.2.1 實驗1 檔案順序讀寫編程107

8.2.2 實驗2 檔案隨機讀寫編程108

8.3 常見錯誤及解決方法109

第9章 綜合程式設計112

9.1 學習要點112

9.2 實驗內容112

9.2.1 實驗1 通訊錄管理系統112

9.2.2 實驗2 學生成績管理系統113

9.2.3 實驗3 高校教師人事管理系統113

9.2.4 實驗4 企業職工工資管理系統114

9.2.5 實驗5 倉庫物資管理系統115

9.2.6 實驗6 筆記本電腦銷售管理系統116

9.2.7 實驗7 停車場管理系統117

9.2.8 實驗8 火車訂票管理系統118

附錄A 常見編譯錯誤和警告121

附錄B 常用標準庫函式123B.1 stdio.h中包括的常用函式123

B.2 math.h中包括的常用函式129

B.3 stdlib.h中包括的常用函式132

B.4 string.h中包括的常用函式135

B.5 time.h中包括的常用函式138

B.6 ctype.h中包括的常用函式140

B.7 conio.h中包括的常用函式142

參考文獻144