算法概论

前    言

　　本书是在加州大学Berkeley分校和San Diego分校本科生算法课程讲义的基础上，历经十年，逐渐整理、日益完善而成的。我们教授此门课程的方法在过去几年间经历了巨大变革，它一方面照顾到了学生的背景(学生们除编程之外并不具备正式而完善的应用技巧)，一方面反映了算法领域总体上走向成熟的趋势，正如过去数十年我们已经见证了的。随着当初的教学讲义被逐渐提炼成娓娓道来的文字，我们也逐渐调整着课程的结构，以突出教学材料编排中蕴含的“故事情节”。因此，本书的内容经过仔细选择后才得以结集成篇。我们不求把此书编成一本算法百科全书，这使我们可以自由地把大多数传统算法书籍未曾强调或忽略的主题包含进来。

　　我们根据学生的特点(这些特点也是当今计算机科学专业的大多数本科生所共有的)，提炼出能使每个算法运转下去的简洁数学思想，而不是沉湎于正式而冗长的理论证明。换言之，我们在活力和刻板之间，更强调前者。我们发现，学生更能接受这种形式带来的数学的生命力。正是在这些简洁有力的数学思想的推动下，我们才得以展开我们的阐述。

　　一旦按照这种方式来理解算法，那么从它的历史本源开始研究就显得很有意义，并且，对于今天的我们来说，一方面，历史的主题看似那样的熟悉，另一方面，其与今天的对比却又是那样的显著：数论、素性测试和因子分解。这就是本书部分的主题，此外它还包括RSA密码系统、整数乘法的分治算法、排序与寻找中项以及快速Fourier变换。本书还包含其他三个部分：其中第二部分堪称本书内容传统的章节，主要围绕数据结构和图论展开。这一部分中，错综复杂的问题结构和用于解决问题的简洁明快的伪代码形成了鲜明对比。如果希望以传统的方式进行讲授，可以直接从本书的第二部分开始，这部分自成体系(在序言之后)，如有需要，可再跳回部分。在本书的和第二部分，我们介绍了某些用于解决特定问题的技术(例如贪心算法和分治技术)；第三部分介绍一些强有力的算法设计技术，它们被广泛地用于解决实际问题：如动态规划技术(一种新颖的可用于清除学生的传统学习障碍的方法)和线性规划技术(一种简洁而直观地处理单纯形法、对偶问题以及原问题的简化问题的技术)。本书后的第四部分介绍了对付困难问题的方法：NP完全性、各种启发式算法以及量子算法，后者或许是当今前沿的课题。碰巧的是，我们关于算法的讲述在本书的末尾又回到了初讨论的问题：针对因子分解问题的Shor量子算法。

　　本书包含了三个附加的脉络。为了保持全书的可读性(兼顾学生的不同需求和兴趣)和逻辑的完整性，它们以三组自成系列的“灰色方框”形式出现，分别对应于一些算法技术的历史背景、对所介绍算法如何在实际中应用(突出了互联网应用)的描述，以及对相关数学知识的简要阐释。

我们的很多同事为此书的出版做出了重要贡献。在此对Dimitris Achlioptas、Dorit Aharanov、Mike Clancy、Jim Demmel、Monika Henzinger、Mike Jordan、Milena Mihail、Gene Myers、Dana Randall、Satish Rao、Tim Roughgarden、Jonathan Shewchuk、Martha Sideri、Alistair Sinclair，以及David Wagner表示由衷的感谢，他们均对本书提出了宝贵意见，并对本书的初稿作了校对。Satish Rao、Leonard Schulman和Vijay Vazirani对本书几个核心章节的内容给出了重要建议。Gene Myers、Satish Rao、Luca Trevisan、Vijay Vazirani和Lofti Zadeh提供了本书的习题。后，向加州大学Berkeley分校和San Diego分校的同学们表示感谢，是他们推动了本书的出版工作，并参与审阅本书的手稿。