算法基礎

《算法基礎》是2005年7月1日清華大學出版社出版的圖書，作者是布拉薩德。本書適用對象廣泛。對於學習算法設計與分析的本科生和研究生。

基本介紹

• 書名：算法基礎
• 作者：布拉薩德
• ISBN：9787302111559
• 頁數：515
• 定價：35.0
• 出版社：清華大學出版社
• 出版時間：2005年7月1日
• 裝幀：平裝

內容簡介

本書是關於算法導論的經典教材，書中包括大量例題解答與命題證明。本書是按照算法類型而不是按照套用類型對算法進行介紹，以其清晰的概念講解贏得專家們的廣泛讚譽。本書是優選教材。對於從事算法計算研究和工程套用的科研人員和工程技術人員，本書也是一本優秀的基礎性讀物。

圖書目錄

第1章預備知識1

1.1簡介1

1.2什麼是算法1

1.3程式符號4

1.4數學符號5

1.4.1命題演算5

1.4.2集合論6

1.4.3整數、實數和區間7

1.4.4函式和關係7

1.4.5量詞8

1.4.6累加與累積9

1.4.7雜項10

1.5證明技巧1——反證法11

1.6證明技巧2——數學歸納法12

1.6.1數學歸納法的法則15

1.6.2不同顏色的馬18

1.6.3一般化的數學歸納法19

1.6.4構造性歸納22

1.7一些回顧24

1.7.1極限24

1.7.2簡單級數26

1.7.3基本組合30

1.7.4機率基礎32

1.8習題38

1.9參考與深入閱讀43

第2章基本算法45

2.1簡介45

2.2問題和實例45

2.3算法的效率46

2.4平均和最壞情況分析48

2.5什麼是基本運算？50

2.6為什麼尋求效率？52

2.7一些例子53

2.7.1計算行列式的值53

2.7.2排序53

2.7.3大整數的乘法55

2.7.4計算最大公約數55

2.7.5計算斐波納契序列56

2.7.6傅立葉變換57

2.8什麼時候算法是確定的？58

2.9習題58

2.10參考與深入閱讀61

第3章漸近記法62

3.1引言62

3.2同階記法62

3.3其他漸近記法67

3.3.1Ω記法67

3.3.2Θ記法68

3.4條件漸近記法69

3.5具有多個參數的漸近記法71

3.6漸近記法的操作71

3.7習題72

3.8參考與深入閱讀75

第4章算法分析76

4.1引言76

4.2分析控制結構76

4.2.1先後順序76

4.2.2For循環76

4.2.3遞歸調用78

4.2.4while和repeat循環79

4.3使用標稱80

4.4補充例子82

4.4.1選擇排序82

4.4.2插入排序83

4.4.3歐幾里德算法83

4.4.4漢諾塔85

4.4.5計算行列式的值86

4.5平均情況分析86

4.6分期分析87

4.6.1勢函式88

4.6.2賬戶戲法90

4.7求解遞歸式90

4.7.1推測90

4.7.2齊次遞歸式92

4.7.3非齊次遞歸式96

4.7.4變數變換100

4.7.5範圍轉換105

4.7.6漸近遞歸式106

4.8習題107

4.9參考與深入閱讀113

第5章一些數據結構114

5.1數組、棧和佇列114

5.2記錄和指針116

5.3鍊表117

5.4圖118

5.5樹119

5.6關聯表124

5.7堆126

5.8二項堆132

5.9不相交集結構136

5.10習題141

5.11參考與深入閱讀144

第6章貪婪算法146

6.1找零錢(1)146

6.2貪婪算法的一般特性147

6.3圖：最小生成樹148

6.3.1Kruskal算法150

6.3.2Prim算法152

6.4圖：最短路徑154

6.5背包問題(1)157

6.6日程安排160

6.6.1最小化時間160

6.6.2有期限的日程安排162

6.7習題168

6.8參考與深入閱讀170

第7章分治算法171

7.1簡介：大整數乘法171

7.2通用模板174

7.3二分搜尋176

7.4排序178

7.4.1歸併排序178

7.4.2快速排序180

7.5查找中值184

7.6矩陣乘法188

7.7求冪189

7.8綜合：密碼學簡介192

7.9習題194

7.10參考與深入閱讀200

第8章動態規劃202

8.1兩個簡單的例子202

8.1.1計算二項式係數202

8.1.2系列賽203

8.2找零錢(2)205

8.3最優性原則207

8.4背包問題(2)208

8.5最短路徑209

8.6鏈式矩陣乘法211

8.7使用遞歸214

8.8存儲函式216

8.9習題217

8.10參考與深入閱讀221

第9章搜尋圖223

9.1圖和遊戲：簡介223

9.2遍歷樹228

9.2.1預處理228

9.3深度優先搜尋：無向圖230

9.3.1關節點232

9.4深度優先搜尋：有向圖233

9.4.1無環圖：拓撲排序234

9.5廣度優先搜尋236

9.6回溯法239

9.6.1背包問題(3)240

9.6.2八皇后問題242

9.6.3通用模板244

9.7分支界限244

9.7.1分配任務問題245

9.7.2背包問題(4)248

9.7.3一般考慮248

9.8極小化原則248

9.9習題251

9.10參考與深入閱讀256

第10章機率算法257

10.1簡介257

10.2機率不意味著不確定258

10.3預期與平均時間259

10.4生成偽隨機數259

10.5數值機率算法261

10.5.1Buffon的針261

10.5.2數值積分264

10.5.3機率計數265

10.6Monte Carlo算法267

10.6.1驗證矩陣乘法267

10.6.2素數性測試269

10.6.3一個數可能是素數嗎？272

10.6.4隨機優勢的擴大274

10.7Las Vegas算法276

10.7.1重訪八皇后問題278

10.7.2機率選擇與排序281

10.7.3通用散列282

10.7.4大整數分解因數284

10.8習題287

10.9參考與深入閱讀293

第11章並行算法295

11.1並行計算的模型295

11.2一些基本的技術297

11.2.1計算完全二叉樹297

11.2.2指針倍增298

11.3工作量與效率301

11.4圖論的兩個例子303

11.4.1最短路徑303

11.4.2連通分量304

11.5表達式的並行求值308

11.6並行排序網路312

11.6.101原理313

11.6.2並行合併網路314

11.6.3改進的排序網路315

11.7並行排序316

11.7.1預備工作316

11.7.2核心思想317

11.7.3算法317

11.7.4細節概述318

11.8EREW和CRCW pram的一些注意點319

11.9分散式計算320

11.10習題321

11.11參考與深入閱讀323

第12章計算複雜性324

12.1引言：一個簡單的例子324

12.2信息理論論證325

12.2.1排序的複雜性327

12.2.2複雜性對算法設計的幫助330

12.3對手論證331

12.3.1查找數組的最大項332

12.3.2測試圖的連通性333

12.3.3中值再考察333

12.4線性歸約335

12.4.1形式定義337

12.4.2矩陣問題中的歸約338

12.4.3最短路徑問題中的歸約342

12.5NP完全性介紹344

12.5.1P和NP類345

12.5.2多項式歸約348

12.5.3NP完全性問題351

12.5.4一些NP完全性證明353

12.5.5NP難問題356

12.5.6非確定性算法357

12.6複雜性類縱覽359

12.7習題362

12.8參考與深入閱讀366

第13章啟發式和近似算法369

13.1啟發式算法369

13.1.1圖著色369

13.1.2旅行商371

13.2近似算法372

13.2.1度量旅行商372

13.2.2背包問題（5）374

13.2.3裝箱問題375

13.3NP難近似問題377

13.3.1絕對難近似問題378

13.3.2相對難近似問題379

13.4相同，惟一不同380

13.5近似模式383

13.5.1重訪裝箱問題383

13.5.2背包問題（6）384

13.6習題386

13.7參考與深入閱讀389

參考文獻390