本书介绍了若干常见算法,既包括排序、哈希等基础算法,也包括无约束优化、插值与拟合等数值计算方法。本书在介绍算法的同时,结合了作者自己对数学背景、应用场景的理解,便于读者把握算法的核心思想。本书尽可能地避开了以应试为导向的灌输式讲解,力求引起读者的兴趣并扩大其视野,例如在介绍哈希时,讲解了如何将哈希的算法思想运用于相似性搜索、负载均衡等多个实际问题中;又如在介绍高斯消去法时,讲解了相关的数学理论及编程实现上的具体技巧,并将其运用于对大规模稀疏线性方程组的求解,等等。
本书面向有一定高等数学、编程语言基础及对算法有初步了解的读者,包括高等院校的学生、程序员、算法分析人员及设计人员等,旨在帮助读者进一步学习算法,理解与算法相关的理论基础和应用实例。
注重算法的核心思想及解决实际问题,详细讲解相关数学理论及编程实现技巧。
本书取名“算法笔记”,主要源自作者在中国科学院读书期间学习算法时的体会,可以作为现有算法教科书的补充。本书讨论了计算机算法相关的若干话题,在介绍算法的同时结合了作者自己对数学背景、应用场景的理解,便于读者把握算法的核心思想。阅读本书需要有一定的数学基础和算法基础。
许多经典的算法教科书都详尽地介绍了算法的各个知识点,但在覆盖面广的同时难免会忽略许多细节问题。例如,哪些算法真正值得运用到实际问题中,算法有哪些变种值得我们了解,算法背后有哪些数学理论支撑,等等。
本书共包括8 章。各章中除了讲解基本知识,还回答了许多相关的有趣问题。
? 排序:排序算法有很多种,在比较流行的编程语言中都有提供排序算法的库函数,直接调用这些库函数会非常简单。但它们所使用的算法为何有效,这些算法与一些经典的排序算法又有什么区别?
? 哈希:在讲解哈希算法时一般主要介绍哈希函数的作用及哈希表的不同实现方法。但将哈希函数运用于不同的问题时,最为巧妙的地方在于哈希函数的设计。对于不同领域的问题,哈希函数都有哪些有趣的形式?
? 动态规划与近似算法:通常这两类算法并不会放在一起去探讨。在面对不同复杂性的问题时,它们会有怎样的互补作用?
? 高斯消去法:算法的基本过程是很简单的,但在实际使用中远远没有那么简单。如何保持计算的稳定性?如何解决稀疏矩阵的计算效率问题?
? 图论与线性规划:图论中的许多问题都可以用线性规划去解决。图论中的一些经典结论实质上也可以用线性规划的相关定理去解释。线性规划作为一个更一般的工具,如何用于处理图论问题?
? 无约束优化:无约束优化主要用于求解函数的最大值或最小值的问题。常用的这些方法为何有效?它们之间的差别在哪里?
? 迭代法:常见的迭代算法都有哪些?它们为什么有效?
? 插值与拟合:插值与拟合的思想是什么?有什么异同?如何运用于图像处理?
读者可以发现,本书不仅指出了哪些算法可以解决问题,还指出了哪些算法可以更好地解决问题。这有助于我们对算法的深入理解。
由于作者水平有限,书中难免有错误和不足之处,欢迎读者批评和指正。
刁瑞、谢妍
2016 年7 月