本书是著名计算机科学家Alfred V. Aho、John E. Hopcroft和Jeffrey D. Ullman合著的一部经典著作，着重介绍计算机算法设计领域的统一原则和基本概念。书中深入分析一些计算机模型上的算法，以及一些有效算法常用的数据结构和编程技术，为读者提供了有关递归方法、分治方法和动态规划方面的详细实例和实际应用，并致力于更有效算法的设计和开发。同时，对NP完全等问题能否有效求解进行分析，并探索应用启发式算法解决问题的途径。另外，本书还提供了大量富有指导意义的习题。
　　本书可以作为高等院校计算机专业本科生和研究生算法设计课程的教材，也可以作为计算机算法理论中更高级课程的教材。

　　本书特点：
　　● 介绍若干计算模型，包括图灵机模型、随机存取计算机模型以及它们的变体在算法设计和分析中的作用；
　　● 介绍设计有效算法相关的数据结构，给出递归、分治法、动态规划技术以及相关的算法例子；
　　● 解释排序算法、集合算法、图算法、模式匹配算法、快速傅里叶变换的技术细节和应用技巧；
　　● 讨论矩阵乘法、多项式运算以及整数算法的内在机理；
　　● 探讨一些问题的时间复杂度和空间复杂度，涉及NP完全问题以及一些可以证明不存在有效算法的问题，并将计算难度的概念和向量空间的线性独立性关联在一起;
　　● 本书算法原采用ALGOL实现，译者为配合国内教学实际，在附录中给出了大多数经典算法的C/C++实现。

无

算法研究是计算机科学的核心。近年来，算法领域取得了很多重要的进展。这些进展包括快速算法的开发，如发明了傅里叶变换快速算法，以及不存在有效算法的本质问题的惊人发现。这些结果点燃了计算机学者对算法研究的兴趣。算法设计与分析已成为一个受到广泛注意的领域。本书旨在将这个领域的一些基本成果汇集在一起，使算法设计的基本原则和根本原理的教学变得容易。
　　本书内容
　　分析一个算法的性能需要一种计算机模型。本书首先介绍一些形式模型，使用它们不仅可以进行算法分析，还能确切反映实际计算机的一些显著特性。这些模型包括随机存取计算机RAM、随机存取存储程序计算机RASP以及一些变体。为了证明第10、11章中的一些算法的复杂度下界是指数的，本书还将讨论图灵机模型。由于程序设计趋向于远离机器语言，因此本书将引入一种称为简化ALGOL语言的高级程序语言作为描述算法的主要工具。简化ALGOL语言程序的复杂度和机器模型是相关的。
　　第2章介绍在设计有效的算法中使用的基本数据结构和程序设计技术。涉及列表、下推式存储结构、队列、树和图等。同时给出递归、分治法、动态规划的详细解释以及一些应用实例。
　　第3～9章给出一些不同的应用第2章所介绍的基本技术的领域。这些章节致力于设计已知最有效的渐近算法。由于要考虑渐近性，一些算法可能仅对那些输入规模比目前实际所遇到的问题更大时才有效。特别是第6章中的一些矩阵乘法算法、第7章中的Schnhage-Strassen整数乘法算法以及第8章中的一些多项式和整数算法。
　　另一方面，第3章中的大多数排序算法、第4章中的搜索算法、第5章的图算法、第7章的快速傅里叶算法以及第9章中的串匹配算法都是广泛应用的算法。这些算法对许多实际应用问题的输入规模来说都是有效的。
　　第10～12章讨论计算复杂度的下界。不管对于程序设计者还是希望了解计算本质的人都会对了解一个问题固有的计算难度感兴趣。第10章讨论一类重要的问题，即NP完全问题。该类中所有问题对于计算难度来说是等价的，即，若该类中有一个问题存在有效的算法（多项式时间界），则该类中的所有问题都有有效的算法。由于该问题类包含了许多在现实中非常重要且被广泛研究的问题，如整数规划问题和旅行商问题，有理由怀疑此类问题不存在有效的算法。因此，如果一个程序设计者了解到他欲寻找有效算法的问题属于此类，他就应该尝试寻找启发式的方法。尽管有丰富的经验证据，NP完全问题是否存在有效的算法还是一个有待解决的问题。
　　第11章定义了一些确实可以证明不存在有效算法的问题。第10章和第11章的内容依赖于本书16和17节引入的图灵机的概念。
　　最后一章将计算难度的概念和向量空间的线性独立性关联在一起。该章给出了证明较第10章和第11章简单很多的一些问题的复杂度下界的方法。
　　如何使用本书
　　本书旨在作为涉及算法设计与分析课程的入门教材。强调算法的思想以及如何方便地理解算法而不是算法实现的技巧和细节。因此，常使用内容直观的解释而不是冗长的证明。本书是自包含的，读者无需具有数学和程序设计语言的专业背景。然而，还是希望读者具备一定的处理数学概念的能力，熟悉某种高级程序设计语言如FORTRAN或ALGOL等。要完全理解第6、7、8和12章等内容，读者还需要具备线性代数的知识。
　　本书曾用于算法设计的本科生和研究生课程。一个学期的课程一般涉及第1~5章以及第9和10章的大部分内容，其他章节则可浅尝辄止。在算法的介绍性课程中，可以第1~5章为重点，而16、17、413、511节和定理45一般可不涉及。本书也可用于强调算法理论的高级课程，第6~12章的内容可作为此类课程的基础资料。
　　每章最后都提供有大量的习题，教师可选用作为学生的作业。习题按难度进行分类。没有星号的可用于介绍性的课程，有一个星号（*）的可用于高级课程，有两个星号的可用于研究生高级课程。每章后面的参考文献和注释提供了正文以及习题包含的相应算法和结果的公共资源。
　　致谢
　　本书的材料取自作者在康奈尔大学、普林斯顿大学和史迪温理工学院开设的算法课程的讲义。作者要感谢认真读过本书部分手稿的许多人所提出的批评和建议。作者特别要感谢Kellogg Booth、Stan Brown、Steve Chen、Allen Cypher、Arch Davis、Mike Fischer、Hania Gajewska、Mike Garey、Udai Gupta、Mike Harrison、Matt Hecht、Harry Hunt、Dave Johnson、Marc Kaplan、Don Johnson、Steve Johnson、Brian Kernighan、Don Knuth、Richard Ladner、Anita LaSalle、Doug McIlroy、Albert Meyer、Christos Papadimitriou、Bill Plauger、John Savage、Howard Siegel、Ken Steiglitz、Larry Stockmeyer、Tom Szymanski和Theodore Yen等。
　　特别感谢Gemma Carnevale、Pauline Cameron、Hannah Kresse、Edith Purser和Ruth Suzuki等对手稿所进行的细心和赏心悦目的排版。
　　感谢贝尔实验室、康奈尔大学、普林斯顿大学和加州大学伯克利分校为作者准备本书手稿所提供的设施。

　　AVA
　　JEH
　　JDU
　　1974年6月

Alfred V. Aho;John E.Hopcroft;Jeffrey D. Ullman：Alfred V. Aho: Alfred V. Aho 于普林斯顿大学获得博士学位，现任贝尔实验室基础科学研究院副院长、计算机科学研究中心主任、ACM自动控制与可计算性理论特别兴趣组副主席以及美国国家科学基金会计算机与信息技术顾问委员会主席。
John E.Hopcroft: John E. Hopcroft 于斯坦福大学获得博士学位，美国康奈尔大学计算机科学系教授、美国国家工程院院士，曾担任贝尔实验室的顾问。
Jeffrey D. Ullman: 斯坦福大学计算机科学系Stanford W. Ascherman教授，数据库技术专家。他独立或合作出版了15本著作，发表了170多篇技术论文。他的研究兴趣包括数据库理论，数据库集成，数据挖掘和利用信息基础设施进行教育。他获得了Guggenheim Fellowship等多种奖励，并被推选进入美国国家工程院。他还被授予1996年度Sigmod贡献奖和1998年度Karl V.Karstrom杰出教育家奖。 他先后在Prentice Hall出版了A First Course in Database Systems, Database Systems Implementation, Elements of ML Porgramming等著作。

黄林鹏 王德俊 张仕：暂无简介

本书是算法设计与分析领域的经典之作。
　　该书第1卷第1册和第4卷第2、3和4册的双语版已由机械工业出版社出版。——编辑注
　　该书的第2版已由机械工业出版社翻译出版。——编辑注本书和Knuth所著的《计算机程序设计艺术》、Cormen、Leiserson和Rivest等著的《算法导论》合称为算法设计领域的3大名著。和《算法导论》力求浅显易懂及颇具全面性相比，本书更倾向于数学和形式化描述，特别对图灵机模型和空间复杂度等有更深入的讨论。本书的另一个特点是简洁，直指问题核心，并给出严谨的分析及解决方案和改进措施。
　　不管从内容上还是形式上，目前市场上所有算法设计的书籍都深受本书的影响（截至本书中文版出版之前，据Amazon统计，已有271本书籍引用了本书），可以说，不论是计算机理论研究人员、计算机算法设计者还是研究生、本科生，都可以通过阅读本书受到启发。
　　本书的特点
 介绍了若干计算模型，包括图灵机模型、随机存取计算机模型以及它们的变体在算法设计和分析中的作用。
 介绍了和设计有效算法相关的数据结构，给出递归、分治法、动态规划技术以及相关的算法例子。
 解释了排序算法、集合算法、图算法、模式匹配算法、快速傅里叶变换的技术细节和应用技巧。
 讨论了矩阵乘法、多项式运算以及整数算法的内在机理。
 探讨了一些问题的时间复杂度和空间复杂度，涉及NP完全问题以及一些可以证明是不存在有效算法的问题，并将计算难度的概念和向量空间的线性独立性关联在一起。
　　关于本书附录
　　本书使用一种称为Pidgin ALGOL的语言来描述算法，Pidgin意思是“由两种或多种语言混合而成的一种简化的说话方式，语法和词汇较初等，用于不同语言者进行交流”。算法的开发可分为设计、分析和实现3个环节。该过程可能不断重复，直到需求满足为止。一般说来，算法的描述只要清晰明了就可以了。书中所用的Pidgin ALGOL语言，对于算法的描述是充分的。但ALGOL是一个比较古老的语言，如果读者想测试书中给出的例子，那么找到一个ALGOL语言的编译器可是一件不容易的事（译者推荐使用PLT Scheme附带的ALGOL语言解释器，读者可参阅本书译者的另一本译作《程序设计方法》，人民邮电出版社 2003年出版）。因此，在翻译本书的时候，经和机械工业出版社讨论协商，本书的代码保持原貌，另将书中的算法用C/C++实现并作为译本的附录。本书附录中的代码由译者的研究生王慧芳实现，并经杨欢、彭冲、许赵云等同学测试，以保证其准确性。
　　本书的翻译工作由黄林鹏负责并与其博士生共同完成。其中第9章和第10章由王德俊翻译，第7章和第8章由张仕翻译，参加翻译的还有王欣、徐小辉、伍建焜等，全书由黄林鹏统稿和审校。
　　本书的英文版，曾学习过两次。一次是1980年，当时我在浙江大学读计算机本科，另一次是1986年，那时我已经在上海交通大学攻读硕士学位了。这本教材给我的印象很深，但没有想到在20多年后我有机会翻译这本书，感谢机械工业出版社华章分社给我重温巨著并用中文表述的机会。在此，我要向所有为本书的翻译提供帮助的人表示感谢。由于我们水平有限，翻译中难免出现不妥和错误之处，敬请读者谅解，并请将意见寄至lphuang@sjtueducn，我们将不胜感激。

　　黄林鹏
　　于上海交通大学
　　2007年5月

出版者的话
译者序
前言
第1章计算模型1
11 算法和复杂度1
12 随机存取计算机3
13RAM程序的计算复杂度7
14 存储程序模型8
15RAM的抽象11
16 一种基本的计算模型：图灵机15
17 图灵机模型和RAM模型的关系19
18 简化ALGOL——一种高级语言20
第2章有效算法的设计26
21数据结构：表、队列和堆栈26
22集合的表示28
23图29
24树30
25递归33
26分治法35
27平衡38
28动态规划39
29后记41
第3章排序和顺序统计46
31排序问题46
32基数排序47
33比较排序52
34堆排序——O(n log n)的比较排序
算法52
35快速排序——期望时间为O(n log n)
的排序算法55
36顺序统计学58
37顺序统计的期望时间60
第4章集合操作问题的数据结构65
41集合的基本操作65
42散列法67
43二分搜索68
44二叉查找树69
45最优二叉查找树71
46简单的不相交集合合并算法74
47UNIONFIND问题的树结构77
48UNIONFIND算法的应用和扩展83
49平衡树方案87
410字典和优先队列88
411可合并堆91
412可连接队列93
413划分94
414本章小结98
第5章图算法103
51最小代价生成树103
52深度优先搜索105
53双连通性107
54有向图的深度优先搜索112
55强连通性113
56路径查找问题117
57传递闭包算法119
58最短路径算法120
59路径问题与矩阵乘法121
510单源问题124
511有向无环图的支配集：概念
整合126
第6章矩阵乘法及相关操作135
61基础知识135
62Strassen 矩阵乘法算法137
63矩阵求逆139
64矩阵的LUP分解140
65LUP分解的应用145
66布尔矩阵的乘法146
第7章快速傅里叶变换及其应用153
71离散傅里叶变换及其逆变换153
72快速傅里叶变换算法156
73使用位操作的FFT161
74多项式乘积164
75SchnhageStrassen整数相乘
算法165
第8章整数与多项式计算170
81整数和多项式的相似性170
82整数的乘法和除法171
83多项式的乘法和除法175
84模算术177
85多项式模算术和多项式计值179
86中国余数180
87中国余数和多项式的插值183
88最大公因子和欧几里得算法184
89多项式GCD的渐近快速算法186
810整数的GCD190
811再论中国余数191
812稀疏多项式192
第9章模式匹配算法196
91有穷自动机和正则表达式196
92正则表达式的模式识别201
93子串识别203
94双向确定型下推自动机207
95位置树和子串标识符215
第10章NP完全问题226
101非确定型图灵机问题226
102P类和NP类231
103语言和问题233
104可满足性问题的NP完全性234
105其他NP完全问题239
106多项式空间界问题245
第11章 一些可证难的问题252
111复杂度层次252
112确定型图灵机的空间层次252
113一个需要指数时间和空间的
问题254
114一个非基本的问题260
第12章算术运算的下界265
121域265
122再论直线状代码266
123问题的矩阵表述267
124面向行的矩阵乘法的下界267
125面向列的矩阵乘法的下界269
126面向行和列的矩阵乘法的下界272
127预处理273
附录算法的C/C++代码280
参考文献407