算法笔记（第2版）

图书标准信息

• 作者 刁瑞
• 出版社 电子工业出版社
• 出版时间 2023-02
• 版次 1
• ISBN 9787121446306
• 定价 79.00元
• 装帧 其他
• 开本 16开
• 纸张 胶版纸
• 页数 184页

【内容简介】

ChatGPT掀起了现象级的风暴，赶超ChatGPT潮流，算法突破是关键。
  本书介绍了若干常见算法，涉及排序、哈希、动态规划与近似算法、高斯消去法、图论与线性规划、无约束优化、迭代法、插值与拟合等。本书在介绍算法的同时，结合了作者自己对数学背景、应用场景的理解，便于读者把握算法的核心思想。而且，本书不仅指出了哪些算法可以解决问题，还指出了哪些算法可以更好地解决问题，便于读者深入理解算法。本书尽可能地避开了以应试为导向的灌输式讲解，力求引起读者的兴趣并扩大其视野，例如在介绍哈希时，讲解了如何将哈希的算法思想运用于相似性搜索、负载均衡等多个实际问题中；又如在介绍高斯消去法时，讲解了相关的数学理论及编程实现上的具体技巧，并将其运用于对大规模稀疏线性方程组的求解，等等。
  本书面向有一定高等数学、编程语言基础及对算法有初步了解的读者，包括高等院校的学生、程序员、算法分析人员及设计人员等，旨在帮助读者进一步学习算法，理解与算法相关的理论基础和应用实例。

【作者简介】

? 刁瑞，毕业于中国科学院数学与系统科学研究院，博士期间的研究方向为最优化方法。曾获2009年英特尔杯全国计算机多核程序设计大赛第1名，以及2011年KDD Cup第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