算法基礎(chǔ)

第1章預(yù)備知識(shí)1

1.1簡(jiǎn)介1

1.2什么是算法1

1.3程序符號(hào)4

1.4數(shù)學(xué)符號(hào)5

1.4.1命題演算5

1.4.2集合論6

1.4.3整數(shù)、實(shí)數(shù)和區(qū)間7

1.4.4函數(shù)和關(guān)系7

1.4.5量詞8

1.4.6累加與累積9

1.4.7雜項(xiàng)10

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

1.6證明技巧2——數(shù)學(xué)歸納法12

1.6.1數(shù)學(xué)歸納法的法則15

1.6.2不同顏色的馬18

1.6.3一般化的數(shù)學(xué)歸納法19

1.6.4構(gòu)造性歸納22

1.7一些回顧24

1.7.1極限24

1.7.2簡(jiǎn)單級(jí)數(shù)26

1.7.3基本組合30

1.7.4概率基礎(chǔ)32

1.8習(xí)題38

1.9參考與深入閱讀43

第2章基本算法45

2.1簡(jiǎn)介45

2.2問題和實(shí)例45

2.3算法的效率46

2.4平均和最壞情況分析48

2.5什么是基本運(yùn)算？50

2.6為什么尋求效率？52

2.7一些例子53

2.7.1計(jì)算行列式的值53

2.7.2排序53

2.7.3大整數(shù)的乘法55

2.7.4計(jì)算最大公約數(shù)55

2.7.5計(jì)算斐波納契序列56

2.7.6傅立葉變換57

2.8什么時(shí)候算法是確定的？58

2.9習(xí)題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具有多個(gè)參數(shù)的漸近記法71

3.6漸近記法的操作71

3.7習(xí)題72

3.8參考與深入閱讀75

第4章算法分析76

4.1引言76

4.2分析控制結(jié)構(gòu)76

4.2.1先后順序76

4.2.2For循環(huán)76

4.2.3遞歸調(diào)用78

4.2.4while和repeat循環(huán)79

4.3使用標(biāo)稱80

4.4補(bǔ)充例子82

4.4.1選擇排序82

4.4.2插入排序83

4.4.3歐幾里德算法83

4.4.4漢諾塔85

4.4.5計(jì)算行列式的值86

4.5平均情況分析86

4.6分期分析87

4.6.1勢(shì)函數(shù)88

4.6.2賬戶戲法90

4.7求解遞歸式90

4.7.1推測(cè)90

4.7.2齊次遞歸式92

4.7.3非齊次遞歸式96

4.7.4變量變換100

4.7.5范圍轉(zhuǎn)換105

4.7.6漸近遞歸式106

4.8習(xí)題107

4.9參考與深入閱讀113

第5章一些數(shù)據(jù)結(jié)構(gòu)114

5.1數(shù)組、棧和隊(duì)列114

5.2記錄和指針116

5.3鏈表117

5.4圖118

5.5樹119

5.6關(guān)聯(lián)表124

5.7堆126

5.8二項(xiàng)堆132

5.9不相交集結(jié)構(gòu)136

5.10習(xí)題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最小化時(shí)間160

6.6.2有期限的日程安排162

6.7習(xí)題168

6.8參考與深入閱讀170

第7章分治算法171

7.1簡(jiǎn)介：大整數(shù)乘法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綜合：密碼學(xué)簡(jiǎn)介192

7.9習(xí)題194

7.10參考與深入閱讀200

第8章動(dòng)態(tài)規(guī)劃202

8.1兩個(gè)簡(jiǎn)單的例子202

8.1.1計(jì)算二項(xiàng)式系數(shù)202

8.1.2系列賽203

8.2找零錢(2)205

8.3最優(yōu)性原則207

8.4背包問題(2)208

8.5最短路徑209

8.6鏈?zhǔn)骄仃嚦朔?11

8.7使用遞歸214

8.8存儲(chǔ)函數(shù)216

8.9習(xí)題217

8.10參考與深入閱讀221

第9章搜索圖223

9.1圖和游戲：簡(jiǎn)介223

9.2遍歷樹228

9.2.1預(yù)處理228

9.3深度優(yōu)先搜索：無向圖230

9.3.1關(guān)節(jié)點(diǎn)232

9.4深度優(yōu)先搜索：有向圖233

9.4.1無環(huán)圖：拓?fù)渑判?34

9.5廣度優(yōu)先搜索236

9.6回溯法239

9.6.1背包問題(3)240

9.6.2八皇后問題242

9.6.3通用模板244

9.7分支界限244

9.7.1分配任務(wù)問題245

9.7.2背包問題(4)248

9.7.3一般考慮248

9.8極小化原則248

9.9習(xí)題251

9.10參考與深入閱讀256

第10章概率算法257

10.1簡(jiǎn)介257

10.2概率不意味著不確定258

10.3預(yù)期與平均時(shí)間259

10.4生成偽隨機(jī)數(shù)259

10.5數(shù)值概率算法261

10.5.1Buffon的針261

10.5.2數(shù)值積分264

10.5.3概率計(jì)數(shù)265

10.6Monte Carlo算法267

10.6.1驗(yàn)證矩陣乘法267

10.6.2素?cái)?shù)性測(cè)試269

10.6.3一個(gè)數(shù)可能是素?cái)?shù)嗎？272

10.6.4隨機(jī)優(yōu)勢(shì)的擴(kuò)大274

10.7Las Vegas算法276

10.7.1重訪八皇后問題278

10.7.2概率選擇與排序281

10.7.3通用散列282

10.7.4大整數(shù)分解因數(shù)284

10.8習(xí)題287

10.9參考與深入閱讀293

第11章并行算法295

11.1并行計(jì)算的模型295

11.2一些基本的技術(shù)297

11.2.1計(jì)算完全二叉樹297

11.2.2指針倍增298

11.3工作量與效率301

11.4圖論的兩個(gè)例子303

11.4.1最短路徑303

11.4.2連通分量304

11.5表達(dá)式的并行求值308

11.6并行排序網(wǎng)絡(luò)312

11.6.101原理313

11.6.2并行合并網(wǎng)絡(luò)314

11.6.3改進(jìn)的排序網(wǎng)絡(luò)315

11.7并行排序316

11.7.1預(yù)備工作316

11.7.2核心思想317

11.7.3算法317

11.7.4細(xì)節(jié)概述318

11.8EREW和CRCW pram的一些注意點(diǎn)319

11.9分布式計(jì)算320

11.10習(xí)題321

11.11參考與深入閱讀323

第12章計(jì)算復(fù)雜性324

12.1引言：一個(gè)簡(jiǎn)單的例子324

12.2信息理論論證325

12.2.1排序的復(fù)雜性327

12.2.2復(fù)雜性對(duì)算法設(shè)計(jì)的幫助330

12.3對(duì)手論證331

12.3.1查找數(shù)組的最大項(xiàng)332

12.3.2測(cè)試圖的連通性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多項(xiàng)式歸約348

12.5.3NP完全性問題351

12.5.4一些NP完全性證明353

12.5.5NP難問題356

12.5.6非確定性算法357

12.6復(fù)雜性類縱覽359

12.7習(xí)題362

12.8參考與深入閱讀366

第13章啟發(fā)式和近似算法369

13.1啟發(fā)式算法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絕對(duì)難近似問題378

13.3.2相對(duì)難近似問題379

13.4相同，惟一不同380

13.5近似模式383

13.5.1重訪裝箱問題383

13.5.2背包問題（6）384

13.6習(xí)題386

13.7參考與深入閱讀389

參考文獻(xiàn)390 2100433B

本書是關(guān)于算法導(dǎo)論的經(jīng)典教材，書中包括大量例題解答與命題證明。本書是按照算法類型而不是按照應(yīng)用類型對(duì)算法進(jìn)行介紹，以其清晰的概念講解贏得專家們的廣泛贊譽(yù)。本書是優(yōu)選教材。對(duì)于從事算法計(jì)算研究和工程應(yīng)用的科研人員和工程技術(shù)人員，本書也是一本優(yōu)秀的基礎(chǔ)性讀物。

CADCS基礎(chǔ)算法(CADCS basic algorithm) 被控制理論算法引用的通用性計(jì)算方法.控制理論算法中，常常用到一些已知的算法，這些算法有獨(dú)立意義，常常被不同的控制理論算法所引用，其本身絕大部分在CADCS中不具有控制理論算法的意義，這些算法被稱之為CADCS基礎(chǔ)算法.例如，矩陣運(yùn)算、優(yōu)化算法、多項(xiàng)式陣運(yùn)算、統(tǒng)計(jì)算法等.這些算法的好壞直接影響控制理論算法的CADCS中的時(shí)間復(fù)雜性與空間復(fù)雜性，以及精度等數(shù)值質(zhì)量，這些基礎(chǔ)算法的研究都是計(jì)算數(shù)學(xué)的主要研究方向，計(jì)算數(shù)學(xué)可為控制理論提供好的基礎(chǔ)算法.反過來，控制理論算法的研究也可給計(jì)算數(shù)學(xué)提出富有啟發(fā)性的基礎(chǔ)算法問題.類似控制理論算法，一個(gè)基礎(chǔ)算法在什么條件下是好的，同樣也是一個(gè)極富挑戰(zhàn)性的問題.2100433B

旋轉(zhuǎn)門算法除了平行四邊形算法之外，還能用三角形算法來表示。

圖遍歷算法

圖遍歷算法是最基本的圖算法之一，由指定節(jié)點(diǎn)開始，按照一定規(guī)則遍歷圖結(jié)構(gòu)中所有的連通節(jié)點(diǎn)，包括寬度優(yōu)先搜索(Breadth First Search,BFS)和深度優(yōu)先搜索(Depth First Search, DFS)等核心算法。

作為最基本的圖遍歷算法，寬度優(yōu)先搜索算法代表了圖遍歷算法的計(jì)算特性，具有非常重要的研究意義。一方面，BFS算法是最短路徑、鄰接查詢、可達(dá)性查詢等算法的實(shí)現(xiàn)基礎(chǔ)，廣泛應(yīng)用于圖分割、信念傳播統(tǒng)計(jì)以及網(wǎng)絡(luò)社區(qū)結(jié)構(gòu)發(fā)現(xiàn)等領(lǐng)域;另一方面，BFS算法作為典型的數(shù)據(jù)密集型算法，體現(xiàn)了數(shù)據(jù)密集型應(yīng)用對(duì)高性能計(jì)算系統(tǒng)的需求，廣泛應(yīng)用于大規(guī)模并行計(jì)算系統(tǒng)的數(shù)據(jù)處理能力評(píng)測(cè)，已經(jīng)成為Parboil, Rodinia和Graph500等基準(zhǔn)測(cè)試程序的核心算法。

在實(shí)際應(yīng)用中，圖的規(guī)模在不斷增大，相應(yīng)的，對(duì)圖的存儲(chǔ)和處理開銷不斷增加，有效地實(shí)現(xiàn)大規(guī)模并行BFS算法具有十分重要的意義。

稀疏線性方程組求解法

稀疏線性方程組的求解是對(duì)自然科學(xué)和社會(huì)科學(xué)中許多實(shí)際問題進(jìn)行數(shù)值模擬時(shí)的關(guān)鍵技術(shù)之一。在高層建筑、橋梁、水壩、防洪堤的結(jié)構(gòu)設(shè)計(jì)中，需對(duì)變形與應(yīng)力情況進(jìn)行模擬；在油氣資源探測(cè)與分析、數(shù)值天氣預(yù)報(bào)、飛行器的動(dòng)力學(xué)分析中，需利用流體力學(xué)方程組進(jìn)行模擬;在進(jìn)行恒星大氣分析與核爆實(shí)驗(yàn)時(shí)，常需利用輻射流體力學(xué)與粒子統(tǒng)計(jì)平衡等規(guī)律進(jìn)行模擬。在對(duì)這些問題進(jìn)行分析模擬時(shí)，通常利用偏微分方程建立數(shù)學(xué)模型。在對(duì)偏微分方程的離散求解過程中，稀疏線性方程組求解算法扮演著十分重要的角色。在許多不以偏微分方程建模的問題中，稀疏線性方程組求解同樣發(fā)揮了重要的作用。在空中交通控制、電力線路中的最優(yōu)電流問題中，需利用數(shù)學(xué)規(guī)劃求解;在對(duì)采納某項(xiàng)政策時(shí)在某給定條件下對(duì)國(guó)內(nèi)、國(guó)際多個(gè)區(qū)域的相應(yīng)經(jīng)濟(jì)指標(biāo)進(jìn)行預(yù)測(cè)時(shí)，需利用CGE模型進(jìn)行分析；在可靠性分析、排隊(duì)網(wǎng)絡(luò)分析與計(jì)算機(jī)系統(tǒng)性能評(píng)估中，常利用具有大量狀態(tài)的離散Markov鏈進(jìn)行模擬。在這些問題的求解中，稀疏線性方程組的求解都占有重要位置，并且往往是整個(gè)計(jì)算過程中的性能瓶頸，稀疏線性方程組的高效求解是計(jì)算數(shù)學(xué)和工程應(yīng)用中十分重要的課題之一。

解稀疏線性方程組的方法包括直接法(direct method)與迭代(iterative method)兩類。直接法指在不考慮計(jì)算舍入誤差的情況下，通過包括矩陣分解和三角方程組求解等有限步的操作求得方程組的精確解，因此又稱精確法;迭代法指給定一個(gè)初始解向量，通過一定的計(jì)算構(gòu)造一個(gè)向量列(一般通過逐次迭代得到一系列逼近精確值的近似解)，向量列的極限為方程組理論上的精確解。迭代法對(duì)存儲(chǔ)空間的需求低，在求解高階非病態(tài)稀疏線性方程組方面具有一定優(yōu)勢(shì)。然而，迭代法不適合求解病態(tài)問題，性能因問題而異，并且面臨精度控制、收斂速度慢或不收斂等問題。與迭代法相比，直接法的通用性好，求解結(jié)果精度高，性能穩(wěn)定。當(dāng)矩陣分解結(jié)果能夠被多次后續(xù)計(jì)算重用以及多右端項(xiàng)時(shí)，直接法的優(yōu)勢(shì)尤其明顯。在有限元分析、模擬電路瞬態(tài)仿真等應(yīng)用領(lǐng)域的商用軟件均采用直接法求解器作為標(biāo)準(zhǔn)的稀疏線性方程組求解器。但直接法的缺點(diǎn)在于對(duì)存儲(chǔ)資源要求較高，無法處理高階稀疏矩陣。

一般來說，迭代法的求解速度高于直接法。但是，如果使用直接法時(shí)矩陣分解過程能夠被很多后續(xù)計(jì)算重復(fù)使用，則后續(xù)的三角陣求解可以非常快速實(shí)現(xiàn)，此時(shí)直接法在性能上具有優(yōu)勢(shì)。典型例子是模擬電路瞬態(tài)仿真，這時(shí)需要多次以Newton-Raphson方法求解非線性方程，每一次求解均會(huì)在工作點(diǎn)附近展開為線性方程，而且所有線性方程的矩陣分解方式都是固定的，因此求解該類問題最好的方法是直接法。稀疏矩陣的矩陣分解在GPU上的實(shí)現(xiàn)是很困難的，主要難點(diǎn)在于現(xiàn)有算法的數(shù)據(jù)依賴性導(dǎo)致可利用的并行性不足。此外，矩陣元素的排列順序?qū)τ?jì)算過程中間結(jié)果矩陣的非零元素個(gè)數(shù)有很大影響，同時(shí)矩陣分解后的非零元素的分布與原來矩陣可能很不相同。

迭代法的理論基礎(chǔ)相對(duì)復(fù)雜，并且具有多種不同的具體算法，但其基本形式均為從一個(gè)猜測(cè)解出發(fā)，通過多次迭代逐漸收斂，當(dāng)誤差滿足一定條件時(shí)迭代中止。共扼梯度法(CG)是迭代法的主流方法之一，特別適合于特征值為良態(tài)分布的對(duì)稱正定方程組；其它迭代法包括Jacobi、逐次超松弛(SOR)、廣義極小剩余(GMRES)、預(yù)條件共扼梯度(PCG)等。迭代法的核心算法是稀疏矩陣向量乘(SpMV)，因此實(shí)現(xiàn)SpMV的高效并行結(jié)構(gòu)也是實(shí)現(xiàn)迭代法的基礎(chǔ)。

直接法由高斯消元法發(fā)展向來，求解過程包括矩陣排序(matrix ordering)符號(hào)分解(symbolic factorization)、數(shù)值分解(numerical factorization)、三角方程組求解((triangular solves)四個(gè)步驟。其中，矩陣排序和符號(hào)分解屬于預(yù)處理部分。矩陣排序通過啟發(fā)算法置換稀疏矩陣的行列，試圖在后續(xù)計(jì)算中維持矩陣的稀疏性或數(shù)值穩(wěn)定性。符號(hào)分解則是預(yù)先對(duì)矩陣分解后的稀疏結(jié)構(gòu)進(jìn)行預(yù)測(cè)，預(yù)先分配存儲(chǔ)空間并記錄數(shù)據(jù)相關(guān)性。直接法的計(jì)算瓶頸在于數(shù)值分解部分和三角方程組求解部分，高效的直接法求解依賴于二者的高效實(shí)現(xiàn)。

對(duì)于一個(gè)稀疏線性方程組是選擇直接法還是迭代法求解，一般有如下原則：對(duì)于低階矩陣或大型帶狀矩陣所對(duì)應(yīng)的線性方程組，用直接法求解；而對(duì)于大型(非帶形)矩陣所對(duì)應(yīng)的線性方程組，用迭代方法求解。實(shí)際上，選用何種方法還要看具體的應(yīng)用背景，比如，對(duì)于線性規(guī)劃和一些結(jié)構(gòu)工程應(yīng)用，只有直接法是切實(shí)可行的。對(duì)于精度要求很高的問題，還可以采用由直接法得到初始解再用迭代法進(jìn)行迭代的方法求解，這種方法稱為迭代精化法。