描述
开 本: 16开纸 张: 胶版纸包 装: 平装-胶订是否套装: 否国际标准书号ISBN: 9787121446306
- 平替ChatGPT亟需夯实算法基础，本书简洁高效归纳了排序、哈希、动态规划与近似算法、高斯消去法、图论与线性规划、无约束优化、迭代法、插值与拟合等算法的核心原理及应用案例。
- 非常注重用算法解决实际问题，比如信息安全、比特币、相似性搜索、负载均衡、二分图的最大匹配与最小覆盖问题等。
- 注重数学理论及编程实现上的具体技巧讲解。
- 语言精练，无废话；视点独到，不复制。
ChatGPT掀起了现象级的风暴，赶超ChatGPT潮流，算法突破是关键。
本书介绍了若干常见算法，涉及排序、哈希、动态规划与近似算法、高斯消去法、图论与线性规划、无约束优化、迭代法、插值与拟合等。本书在介绍算法的同时，结合了作者自己对数学背景、应用场景的理解，便于读者把握算法的核心思想。而且，本书不仅指出了哪些算法可以解决问题，还指出了哪些算法可以更好地解决问题，便于读者深入理解算法。本书尽可能地避开了以应试为导向的灌输式讲解，力求引起读者的兴趣并扩大其视野，例如在介绍哈希时，讲解了如何将哈希的算法思想运用于相似性搜索、负载均衡等多个实际问题中；又如在介绍高斯消去法时，讲解了相关的数学理论及编程实现上的具体技巧，并将其运用于对大规模稀疏线性方程组的求解，等等。
本书面向有一定高等数学、编程语言基础及对算法有初步了解的读者，包括高等院校的学生、程序员、算法分析人员及设计人员等，旨在帮助读者进一步学习算法，理解与算法相关的理论基础和应用实例。
第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
ChatGPT掀起了现象级的风暴，赶超ChatGPT潮流，算法突破是关键。
许多经典的算法教科书都详尽地介绍了算法的各个知识点，但在覆盖面广的同时难免会忽略许多细节问题。例如，哪些算法真正值得运用到实际问题中，算法有哪些变种值得我们了解，算法背后有哪些数学理论支撑，等等。
本书讨论了计算机算法相关的若干话题，在介绍算法的同时结合了作者自己对数学背景、应用场景的理解，便于读者把握算法的核心思想。而且，本书不仅指出了哪些算法可以解决问题，还指出了哪些算法可以更好地解决问题，这有助于我们对算法的深入理解。
本书总计 8 章，除了讲解基本知识，还回答了许多相关的有趣问题。
- 排序：排序算法有很多种，在比较流行的编程语言中都有提供排序算法的库函数，直接调用这些库函数会非常简单。但它们所使用的算法为何有效，这些算法与一些经典的排序算法又有什么区别？
- 哈希：在讲解哈希算法时一般主要介绍哈希函数的作用及哈希表的不同实现方法。但将哈希函数运用于不同的问题时，最为巧妙的地方在于哈希函数的设计。对于不同领域的问题，哈希函数都有哪些有趣的形式？
- 动态规划与近似算法：通常这两类算法并不会放在一起去探讨。在面对不同复杂性的问题时，它们会有怎样的互补作用？
- 高斯消去法：算法的基本过程是很简单的，但在实际使用中远远没有那么简单。如何保持计算的稳定性？如何解决稀疏矩阵的计算效率问题？
- 图论与线性规划：图论中的许多问题都可以用线性规划去解决。图论中的一些经典结论实质上也可以用线性规划的相关定理去解释。线性规划作为一个更一般的工具，如何用于处理图论问题？• 无约束优化：无约束优化主要用于求解函数的最大值或最小值的问题。常用的这些方法为何有效？它们之间的差别在哪里？
- 迭代法：常见的迭代算法都有哪些？它们为什么有效？
- 插值与拟合：插值与拟合的思想是什么？有什么异同？如何运用于图像处理？
本书已建立读者交流群，欢迎加入该群，与更多同道中人互动。具体加群方式，请参见本书封底的“读者服务”。
由于作者水平有限，书中难免有错误和不足之处，欢迎读者批评和指正。
刁瑞、谢妍
本书既包含常见算法，又包含相关数学理论和编程技巧，详细讲解了如何将各种算法应用于实际问题中。本书作者有深厚的数学背景，对应用场景理解透彻。通过本书，读者不仅能学到算法的核心思想和相关数学理论，还能提升编程技巧，提升核心竞争力。
——《算法训练营：海量图解 竞赛刷题》作者 陈小玉
介绍算法的书很多，这些书大多很厚而且抽象。而本书是由作者将其在中科院学习算法期间的笔记总结、提炼和沉淀而成的，是实实在在的干货，能够用简练的语言讲解复杂、抽象的算法，不但对算法研究人员很有帮助，对学生也很有帮助。
——《看漫画学Python》作者 关东升
本书是作者对自己学习、应用算法的经验总结，实用性很强。本书在介绍具体算法时先介绍算法的背景和思想，然后介绍算法的核心原理和使用场景，条理清晰，引人入胜，是一本非常值得阅读的算法书。
——《Offer来了：Java面试核心知识点精讲》作者 王磊
虽然算法的入门有一定门槛，但是本书通俗易懂地讲解了各种算法的原理，并结合实际应用来加深读者对算法的认知。通过本书，读者不仅能学习和查阅相关算法的原理，还能拓展知识的广度，更能增加知识的深度。
——《架构演变实战：从单体到微服务再到中台》作者 潘志伟
评论
还没有评论。