算法筆記（第2版）

《算法筆記（第2版）》是電子工業出版社出版圖書，作者是刁瑞和謝妍。

本書涉及排序、哈希、動態規劃與近似算法、高斯消去法、圖論與線性規劃、無約束最佳化、疊代法、插值與擬合等。

基本介紹

• 中文名：算法筆記（第2版）
• 作者：刁瑞、謝妍
• 出版社：電子工業出版社
• 出版時間：2023年3月
• 頁數：184 頁
• 定價：79.00 元
• 開本：16 開
• ISBN：9787121446306

內容簡介

《算法筆記（第2版）》介紹了若干常見算法，涉及排序、哈希、動態規劃與近似算法、高斯消去法、圖論與線性規劃、無約束最佳化、疊代法、插值與擬合等。本書在介紹算法的同時，結合了作者自己對數學背景、套用場景的理解，便於讀者把握算法的核心思想。

圖書目錄

第1章排序 1

1.1 比較排序 ................................................................................................................1

1.1.1 梳排序..........................................................................................................2

1.1.2 堆排序..........................................................................................................4

1.1.3 歸併排序......................................................................................................5

1.1.4 快速排序......................................................................................................8

1.1.5 內省排序......................................................................................................10

1.1.6 Timsort.........................................................................................................11

1.2 非比較排序.............................................................................................................14

1.2.1 桶排序..........................................................................................................14

1.2.2 基數排序 ......................................................................................................15

1.3 總結........................................................................................................................16

第2章哈希 17

2.1 基本概念與實現.....................................................................................................17

2.1.1 哈希函式......................................................................................................17

2.1.2 哈希表..........................................................................................................19

2.2 哈希的套用.............................................................................................................20

2.2.1 相似性搜尋 ..................................................................................................20

2.2.2 信息安全......................................................................................................23

2.2.3 比特幣..........................................................................................................25

2.2.4 負載均衡......................................................................................................26

第3章動態規劃與近似算法 29

3.1 基本概念................................................................................................................29

3.1.1 動態規劃......................................................................................................29

3.1.2 計算複雜性..................................................................................................30

3.2 字元串的編輯距離.................................................................................................30

3.2.1 問題引入......................................................................................................31

3.2.2 動態規划算法...............................................................................................33

3.2.3 滾動數組最佳化...............................................................................................35

3.2.4 上界限制 ......................................................................................................36

3.2.5 解的回溯......................................................................................................37

3.2.6 分治算法 ......................................................................................................38

3.2.7 多個字元串的編輯距離...............................................................................41

3.3 子集和問題.............................................................................................................43

3.3.1 問題引入......................................................................................................43

3.3.2 子集和問題的動態規划算法........................................................................43

3.3.3 最最佳化問題 ..................................................................................................44

3.3.4 滾動數組的技巧...........................................................................................45

3.3.5 貪婪算法 ......................................................................................................46

3.3.6 鬆弛動態規劃...............................................................................................47

3.3.7 相關問題......................................................................................................48

3.4 旅行商問題.............................................................................................................50

3.4.1 問題引入......................................................................................................50

3.4.2 動態規划算法...............................................................................................52

3.4.3 一筆畫問題..................................................................................................52

3.4.4 Christofides 算法..........................................................................................54

3.4.5 Lin-Kernighan 算法......................................................................................55

3.5 總結........................................................................................................................58

第4章高斯消去法 59

4.1 問題引入................................................................................................................59

4.2 矩陣編程基礎.........................................................................................................60

4.3 三角方程組.............................................................................................................62

4.3.1 三角矩陣 ......................................................................................................62

4.3.2 三角矩陣的存儲...........................................................................................63

4.3.3 三角方程組求解...........................................................................................64

4.4 高斯消去法的原理.................................................................................................66

4.4.1 算法概述......................................................................................................66

4.4.2 高斯變換......................................................................................................68

4.4.3 LU 分解........................................................................................................69

4.4.4 Cholesky 分解...............................................................................................70

4.5 主元選擇................................................................................................................71

4.5.1 列選主元 ......................................................................................................71

4.5.2 全選主元......................................................................................................73

4.5.3 主元與計算量...............................................................................................74

4.6 稀疏矩陣的編程基礎.............................................................................................75

4.6.1 稀疏向量......................................................................................................76

4.6.2 稀疏矩陣......................................................................................................79

4.7 稀疏 LU 分解..........................................................................................................82

4.7.1 Markowitz 算法............................................................................................82

4.7.2 最小度算法..................................................................................................83

第5章圖論與線性規劃 86

5.1 線性規劃基礎.........................................................................................................86

5.1.1 Fourier Motzkin 消去法...............................................................................89

5.1.2 基..................................................................................................................91

5.1.3 單純形方法..................................................................................................93

5.1.4 對偶..............................................................................................................95

5.2 全單模矩陣詳解.....................................................................................................98

5.2.1 關聯矩陣 ......................................................................................................98

5.2.2 全單模矩陣..................................................................................................99

5.2.3 全單模矩陣與圖論.......................................................................................100

5.2.4 全單模矩陣與線性規劃...............................................................................103

5.3 圖論中的經典問題.................................................................................................104

5.3.1 單源最短路問題...........................................................................................104

5.3.2 二分圖的最大匹配與最小覆蓋問題 ............................................................ 106

5.3.3 最大流與最小割問題 ...................................................................................108

5.4 延伸閱讀................................................................................................................109

5.4.1 逐步線性規劃...............................................................................................109

5.4.2 半正定規劃..................................................................................................111

第6章無約束最佳化 113

6.1 單峰函式的最值.....................................................................................................114

6.1.1 三分法..........................................................................................................115

6.1.2 對分法..........................................................................................................115

6.1.3 黃金分割法 ..................................................................................................116

6.1.4 小結..............................................................................................................117

6.2 無導數最佳化方法.....................................................................................................118

6.2.1 模式搜尋法..................................................................................................118

6.2.2 坐標下降法 ..................................................................................................119

6.2.3 代理模型法..................................................................................................120

6.3 導數最佳化方法.........................................................................................................121

6.3.1 線搜尋..........................................................................................................122

6.3.2 梯度下降法..................................................................................................123

6.3.3 共軛梯度法..................................................................................................124

6.3.4 牛頓法..........................................................................................................127

6.3.5 擬牛頓法 ......................................................................................................128

6.4 最小二乘................................................................................................................132

6.4.1 線性最小二乘...............................................................................................133

6.4.2 非線性最小二乘...........................................................................................133

第7章疊代法 136

7.1 線性方程組的疊代法 .............................................................................................136

7.1.1 一階定常格式疊代法...................................................................................136

7.1.2 Krylov 子空間算法.......................................................................................142

7.1.3 無約束最佳化方法...........................................................................................147

7.2 非線性方程組的疊代法..........................................................................................147

7.2.1 不動點疊代 ..................................................................................................148

7.2.2 Newton-Raphson 疊代..................................................................................149

7.2.3 無約束最佳化方法...........................................................................................152

第8章插值與擬合 153

8.1 插值........................................................................................................................153

8.1.1 常見的插值算法...........................................................................................154

8.1.2 插值的套用..................................................................................................158

8.2 擬合........................................................................................................................163

8.2.1 常見的擬合算法...........................................................................................164

8.2.2 擬合的套用..................................................................................................166

參考文獻 169

作者簡介

刁瑞，畢業於中國科學院數學與系統科學研究院，博士期間的研究方向為最最佳化方法。曾獲2009年英特爾杯全國計算機多核程式設計大賽第1名，以及2011年KDD Cup第2名等。

謝妍，畢業於中國科學院數學與系統科學研究院，博士期間的研究方向為並行有限元計算。曾在微軟網際網路工程院從事搜尋研發相關工作。