算法(4th ed)(3):基础——本书框架 2

阅读数:25 2019 年 10 月 26 日 09:58

算法(4th ed)(3):基础——本书框架 2

接下来概述一下全书的主要内容,给出涉及的主题以及本书大致的组织结构。这组主题触及了尽可能多的基础算法,其中的某些领域是计算机科学的核心内容,通过对这些领域的深入研究,我们找出了应用广泛的基本算法,而另一些算法则来自计算机科学和相关领域比较前沿的研究成果。总之,本书讨论的算法都是数十年来研发的重要成果,它们将继续在快速发展的计算机应用中扮演重要角色。

第 1 章 基础

它讲解了在随后的章节中用来实现、分析和比较算法的基本原则和方法,包括 Java 编程模型、数据抽象、基本数据结构、集合类的抽象数据类型、算法性能分析的方法和一个案例分析。

第 2 章 排序

有序地重新排列数组中的元素是非常重要的基础算法。我们会深入研究各种排序算法,包括插入排序、选择排序、希尔排序、快速排序、归并排序和堆排序。同时我们还会讨论另外一些算法,它们用于解决几个与排序相关的问题,例如优先队列、选举以及归并。其中许多算法会成为后续章节中其他算法的基础。

第 3 章 查找

从庞大的数据集中找到指定的条目也是非常重要的。我们将会讨论基本的和高级的查找算法,包括二叉查找树、平衡查找树和散列表。我们会梳理这些方法之间的关系并比较它们的性能。

第 4 章 图

图的主要内容是对象和它们的连接,连接可能有权重和方向。利用图可以为大量重要而困难的问题建模,因此图算法的设计也是本书的一个主要研究领域。我们会研究深度优先搜索、广度优先搜索、连通性问题以及若干其他算法和应用,包括 Kruskal 和 Prim 的最小生成树算法、Dijkstra 和 Bellman-Ford 的最短路径算法。

第 5 章 字符串

字符串是现代应用程序中的重要数据类型。我们将会研究一系列处理字符串的算法,首先是对字符串键的排序和查找的快速算法,然后是子字符串查找、正则表达式模式匹配和数据压缩算法。此外,在分析一些本身就十分重要的基础问题之后,这一章对相关领域的前沿话题也作了介绍。

第 6 章 背景

这一章将讨论与本书内容有关的若干其他前沿研究领域,包括科学计算、运筹学和计算理论。我们会介绍性地讲一下基于事件的模拟、B 树、后缀数组、最大流量问题以及其他高级主题,以帮助读者理解算法在许多有趣的前沿研究领域中所起到的巨大作用。最后,我们会讲一讲搜索问题、问题转化和 NP 完全性等算法研究的支柱理论,以及它们和本书内容的联系。

学习算法是非常有趣和令人激动的,因为这是一个历久弥新的领域(我们学习的绝大多数算法都还不到“五十岁”,有些还是最近才发明的,但也有一些算法已经有数百年的历史)。这个领域不断有新的发现,但研究透彻的算法仍然是少数。本书中既有精巧、复杂和高难度的算法,也有优雅、朴素和简单的算法。在科学和商业应用中,我们的目标是理解前者并熟悉后者,这样才能掌握这些有用的工具并学会算法式思考,以迎接未来计算任务的挑战。

评论

发布