计算机算法（C++语言描述）（第2版）

前言 如果我们预挑出计算机科学中那些影响长久的贡献，算法（algorithm）一定位列其中。自从人类发明了可以执行基本数学运算的机器，什么是可以计算的以及如何计算就成为人们一直研究的课题。伴随此项研究，人们发现了大量的重要算法以及设计方法。算法成为计算机科学领域中的一项重要组成部分。本书的目的就是对有关算法的内容精心地组织，从而使得使用本书的同学以及实践者可以设计和分析全新的算法。 一本包含所有已发明的算法的书将会异常冗长。传统的算法书通常只对很少的几个问题领域有深入的阐述。对于每个问题，通常会给出并分析效率最高的算法。这样的做法有一个主要缺点。尽管同学们了解了很多很快的算法并且也掌握了分析算法的工具，但还是对如何设计一个好的算法信心不足。 这里所欠缺的就是没有强调设计（design）技术。设计方面的知识一定可以帮助创造好的算法，没有分析工具则无法判断算法的优劣。这样设计为主分析为辅的关系就自然地延伸为有效的讲授之道：我们将围绕基本的算法设计策略来组织本书。基本的设计策略是相对比较少的。并且大部分读者想要学习的算法可以划分到这些分类中；例如归并排序和快速排序是分治策略的例子，而Kruskal的最小生成树算法和Dijkstra的单源最短路径算法是贪心策略的例子。理解这些策略是掌握设计技能的重要的第一步。 尽管我们深切地认为强调设计以及分析是组织算法学习的正确之路，这里还是要给出一些注意事项。首先，我们并没有包括所有的设计原理。例如线性规划是最成功的技术之一，由于它往往由单独的课程所讲述从而没有包含到本书中。其次，读者不应该死板地学习算法设计，认为每个算法都是由一种技术得到的。事实并不是如此。 本书的主要篇幅，第3～9章，描述了不同的设计策略。每种策略首先描述一个大概。通常给出一个“程序抽象”来描述采用该策略所形成的计算模式的大纲。接着给出一系列的例子来讲述该策略的复杂以及变化。这些例子往往是按照由易到难的次序安排。其复杂的程度可以在不同的方面升高。我们通常先给出一个非常容易理解的例子，所使用的数据结构也仅仅为一维的数组。对这个例子，所用设计策略显而易见可以得到正确的解法。后面的例子可能需要证明基于该设计技术的算法是正确的。也可能是需要更加复杂的数据结构（例如树或者图），并且分析更加复杂。这样组织的主要目的是强调组成和分析算法的艺术。另外还希望能让读者体会好的程序结构以及算法正确性的证明。 第1～12章中的算法都是用C++或者伪C++代码给出。很多是可以直接运行并且已经经过测试的。选择C++是因为它是面向对象的程序语言。C++在计算机业界被广泛接受还有其他的很多理由。选择这种程序语言并不是说不熟悉C++的读者就不能用这本书。因为本书中大部分的算法都是比较短的，用来描述这些算法的代码也足够简单可以被广大读者所理解。第13～15章讲述并行计算。并行计算是一个飞速发展的领域，没有一个被广泛接受的模型或者程序语言。因此，我们选择用伪代码来描述这些算法。第1～12章中也有些简单的算法是用伪代码描述的。这是因为我们认为这些算法的核心思想用伪代码描述更加清晰。如何将这些伪代码转换为C++代码将作为练习留给读者。 另外本书的一大特色是广泛地讨论了随机算法。第13～15章中的很多算法是随机的。其他章节中也包含了一些随机算法。一门学季制的并行算法导论课程可以包含第13～15章，以及其他少量的补充内容。 我们也标出了一些内容（用*号）是适用于高级课程的。这本书的内容可以作为本科高年级学生或者研究生的一门学期制课程，或者两门学季制的课程。它需要学生具备高级语言的编程能力，其余的内容都自完备的。实践上，一门数据结构课也是有帮助的，这样学生具备更成熟的编程能力。如果是学季制的学校，第一个学季可以讲授一些基本的设计技术，例如第3章～第9章中的分治、贪心、动态规划、搜索和遍历、回溯、分治定界以及代数方法（见表Ⅰ）。第二个学季可以讲授第10～15章：下界定理、 D_Dd__________ǒe??_____________ 如果课程是一个学期的，并且学生之前没有接触过数据结构和大O表示，那么第1～7章、第11章以及第13章的内容比较合适（见表Ⅲ）。 如果进度更加紧凑一些可以包含第1～7章、第11章、第13章以及第14章的内容（见表Ⅳ）。 如果学生已经掌握了数据结构和大O表示，可以由第3～11章，以及第13～15章构成一门高级课程（见表Ⅴ）。 表Ⅰ 第一学季 周次 内容 阅读 1 引言 1.1-1.3 2 引言 数据结构 1.4 2.1、2.2 3 数据结构 2.3-2.6 4 分治 第3章 第一次作业 5 贪心算法 第4章 期中考试 6 动态规划 第5章 7 搜索与遍历 第6章 第二次作业 8 回溯 第7章 9 分支定界 第8章 10 代数方法 第9章 第三次作业