編輯推薦
內容詳細，涉及排序、哈希、動態規劃與近似算法、高斯消去法、圖論與線性規劃、無約束最佳化、疊代法、插值與擬合等。
重點講解算法的核心思想。
注重用算法解決實際問題，如相似性搜尋、負載均衡等。
詳細講解算法涉及的數學理論及編程實現上的具體技巧。
避開了以應試為導向的灌輸式講解。
語言精練，無廢話；視點獨到，不複製。
內容提要
《算法筆記》介紹了若干常見算法，既包括排序、哈希等基礎算法，也包括無約束最佳化、插值與擬合等數值計算方法。《算法筆記》在介紹算法的同時，結合了作者自己對數學背景、套用場景的理解，便於讀者把握算法的核心思想。《算法筆記》儘可能地避開了以應試為導向的灌輸式講解，力求引起讀者的興趣並擴大其視野，例如在介紹哈希時，講解了如何將哈希的算法思想運用於相似性搜尋、負載均衡等多個實際問題中；又如在介紹高斯消去法時，講解了相關的數學理論及編程實現上的具體技巧，並將其運用於對大規模稀疏線性方程組的求解，等等。
《算法筆記》面向有一定高等數學、程式語言基礎及對算法有初步了解的讀者，包括高等院校的學生、程式設計師、算法分析人員及設計人員等，旨在幫助讀者進一步學習算法，理解與算法相關的理論基礎和套用實例。
目錄
第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名等。
謝妍，畢業於中國科學院數學與系統科學研究院，博士期間的研究方向為並行有限元計算。曾在微軟網際網路工程院從事搜尋研發相關工作。
前言
本書取名“算法筆記”，主要源自作者在中國科學院讀書期間學習算法時的體會，可以作為現有算法教科書的補充。本書討論了計算機算法相關的若干話題，在介紹算法的同時結合了作者自己對數學背景、套用場景的理解，便於讀者把握算法的核心思想。閱讀本書需要有一定的數學基礎和算法基礎。
許多經典的算法教科書都詳盡地介紹了算法的各個知識點，但在覆蓋面廣的同時難免會忽略許多細節問題。例如，哪些算法真正值得運用到實際問題中，算法有哪些變種值得我們了解，算法背後有哪些數學理論支撐，等等。
本書共包括8 章。各章中除了講解基本知識，還回答了許多相關的有趣問題。
排序：排序算法有很多種，在比較流行的程式語言中都有提供排序算法的庫函式，直接調用這些庫函式會非常簡單。但它們所使用的算法為何有效，這些算法與一些經典的排序算法又有什麼區別？
哈希：在講解哈希算法時一般主要介紹哈希函式的作用及哈希表的不同實現方法。但將哈希函式運用於不同的問題時，最為巧妙的地方在於哈希函式的設計。對於不同領域的問題，哈希函式都有哪些有趣的形式？
動態規劃與近似算法：通常這兩類算法並不會放在一起去探討。在面對不同複雜性的問題時，它們會有怎樣的互補作用？
高斯消去法：算法的基本過程是很簡單的，但在實際使用中遠遠沒有那么簡單。如何保持計算的穩定性？如何解決稀疏矩陣的計算效率問題？
圖論與線性規劃：圖論中的許多問題都可以用線性規划去解決。圖論中的一些經典結論實質上也可以用線性規劃的相關定理去解釋。線性規劃作為一個更一般的工具，如何用於處理圖論問題？
無約束最佳化：無約束最佳化主要用於求解函式的最大值或最小值的問題。常用的這些方法為何有效？它們之間的差別在哪裡？
疊代法：常見的疊代算法都有哪些？它們為什麼有效？
插值與擬合：插值與擬合的思想是什麼？有什麼異同？如何運用於圖像處理？
讀者可以發現，本書不僅指出了哪些算法可以解決問題，還指出了哪些算法可以更好地解決問題。這有助於我們對算法的深入理解。
由於作者水平有限，書中難免有錯誤和不足之處，歡迎讀者批評和指正。
刁瑞、謝妍
2016 年7 月
