基本信息
- 原书名:Algorithms
- 原出版社: McGraw-Hill Companies
- 作者: (美)Sanjoy Dasgupta Christos Papadimitriou Umesh Vazirani
- 译者: 钱枫 邹恒明(注释)
- 丛书名: 经典原版书库
- 出版社:机械工业出版社
- ISBN:9787111253617
- 上架时间:2009-1-14
- 出版日期:2009 年1月
- 开本:16开
- 页码:376
- 版次:1-1
- 所属分类:计算机 > 计算机科学理论与基础知识 > 计算理论 > 算法
教材

内容简介
计算机书籍
本书源自加州大学伯克利分校和加州大学圣迭戈分校本科生的算法课讲义,以独特的视角展现了算法设计的精巧技术及魅力。在表达每一种技术时,强调每个算法背后的简洁数学思想,分析其时间和空间效率,运用与其他技术类比的方法来说明特征,并提供了大量实例。
本书以人类最古老的算法(算术运算)为起点,将各种算法中优美而有代表性的内容囊括书中,并以最前沿的理论(量子算法)结束,构成了较为完整的算法知识体系。
本书主要特点
●生动的写作风格:作者贯穿一条主线,以讲故事的形式将概念娓娓道来,非常易于理解和消化。
●优美地兼顾语言的生动和严谨性:本书中看不到很多数学公式,取而代之的是精确的文字叙述。
●合理地挑选主题:用300多页的篇幅使读者对这门博大精深的科学有深刻的认识。
●穿插注解框:内容包括人文历史背景、对复杂概念的进一步阐述、算法的扩展与重要应用等,对正文的叙述进行补充。
作译者
目录
序言
Preface
方框目录
0 Prologue(序论)
0.1 Books and algorithms(书和算法)
0.2 Enter Fibonacci(斐波那契数列)
0.3 Big-O notation(大O记号)
Exercises(习题)
1 Algorithms with numbers(数的算法)
1.1 Basic arithmetic(基本算术)
1.2 Modular arithmetic(模运算)
1.3 Primality testing(素性测试)
1.4 Cryptography(密码学)
1.5 Universal hashing(全域散列)
Exercises(习题)
Randomized algorithms:a virtual chapter(虚拟章:随机化算法)
2 Divide-and-conquer algorithms(分而治之算法)
2.1 Multiplication(乘法)
2.2 Recurrence relations(递归关系)
前言
Playing on the strengths of our students (shared by most of today's undergraduates in Computer Science), instead of dwelling on formal proofs we distilled in each case the crisp mathematical idea that makes the algorithm work. In other words, we emphasized rigor over formalism. We found that our students were much more receptive to mathematical rigor of this form. It is this progression of crisp ideas that helps weave the story.
Once you think about Algorithms in this way, it makes sense to start at the historical beginning of it all, where, in addition, the characters are familiar and the contrasts dramatic: numbers, primality, and factoring. This is the subject of Part I of the book, which also includes the RSA cryptosystem, and divide-and-conquer algorithms for integer multiplication, sorting and median finding, as well as the fast Fourier transform. There are three other parts: Part II, the most traditional section of the book, concentrates on data structures and graphs; the contrast here is between the intricate structure of the underlying problems and the short and crisp pieces of pseudocode that solve them. Instructors wishing to teach a more traditional course can simply start with Part II, which is self-contained (following the prologue), and then.cover Part I as required. In Parts I and II .we introduced certain techniques (such as greedy and divide-and-conquer) which work for special kinds of problems; Part III deals :with the "sledgehammers" of the trade, techniques that are powerful and general: dynamic programming (a novel approach helps clarify this traditional stumbling block for students) and linear programming (a clean and intuitive treatment of the simplex algorithm, duality, and reductions to the basic problem). The final Part IV is about ways of dealing with hard problems: NP-completeness, various heuristics, as well as quantum algorithms, perhaps the most advanced and modern topic. As it happens, we end the story exactly where we started it, with Shor's quantum algorithm for factoring. ..
The book includes three additional undercurrents, in the form of three series of separate "boxes," strengthening the narrative (and addressing variations in the needs and interests of the students) while keeping the flow intact, pieces that provide historical context; descriptions of how the explained algorithms are used in practice (with emphasis on internet applications); and excursions for the mathematically sophisticated.
Many of our colleagues have made crucial contributions to this book. We are grateful for feedback from 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, and David Wagner, all of whom beta tested early drafts. Satish Rao, Leonard Schulman, and Vijay Vazirani shaped the exposition of several key sections. Gene Myers, Satish Rao, Luca Trevisan, Vijay Vazirani, and Lofti Zadeh provided exercises. And finally, there are the students of UC Berkeley and, later, UC San Diego, who inspired this project, and who have seen it through its many incarnations. ...
序言
算法是计算机科学的灵魂,其复杂与抽象让许多学生望而却步。这本书最显著的特点是生动的写作风格:作者贯穿一条主线,以讲故事的形式将概念娓娓道来,非常易于理解和消化。例如,在全书的开头,作者以计数法的更迭为背景(从复杂的罗马数字到简洁的阿拉伯数字),给算法下了这样生动的定义(这样的例子在书中比比皆是):
“……十进制计数法是由印度人在公元600年左右发明的,它对数学推理简直是一场革命:仅仅需要10个符号,就能很容易地把非常大的数写下来,而且数的运算也能用非常简单的步骤完成。这个绝妙的主意在漫长的时间中克服了语言、距离和人们的无知这些传统因素的重重阻碍而传播到世界各地。推动此传播的是一本9世纪的阿拉伯文的教科书,该书由一个生活在巴格达的叫Al Khwarizmi的人写成。书中不仅列举了加、减、乘、除这些基本运算规则,还包括了求平方根和计算圆周率数值的方法。这些步骤的特点是:简单、没有歧义、机械、有效和正确——这就是算法。几百年后,当十进制计数法在欧洲被广泛使用时,算法(algorithm)这个单词被人们创造出来以纪念这位聪明的Al Khwarizmi先生……”
当然,这本书没有走另一个极端:过分强调语言的生动而忽视了严谨性。恰恰相反,这本书完美地兼顾了两者。在书中我们看不到很多数学式子,取而代之的是精确的文字叙述。作者认为,这种用严谨的语言代替数学形式化的方法更容易被学生接受,因为读者需要知道的往往是蕴涵在数学公式或者程序代码背后的思想,而正是这些思想促成了精巧的算法。
这本书不是一本字典式的百科全书,而是一本教科书。因此,作者合理地挑选了讲授的内容,用300多页的篇幅使学生对这门博大精深的科学有了深刻的认识。本书共分为四个部分。其中,第一部分是引论和算术运算(这是算法的起源),包括复杂度分析、算术运算、最大公约数、素性测试、散列函数、快速乘法、递归、合并排序、矩阵乘法,还有在一般算法书中不多见的RSA公钥体制和快速傅里叶变换等内容。第二部分是“传统”的算法和数据结构(树和图):图的搜索、连通性、最短路径、最小生成树、堆、赫夫曼编码等。在第三部分里,作者用新颖的方式介绍了两种强大的运筹学算法——动态规划和线性规划,以及它们的应用。利用这两种运筹学算法,能够优美地解决一大批实际问题。最后一部分是关于如何解决困难的问题,包括NP完全、优化搜索(回溯、分支限界)、近似算法等。值得一提的是本书的最后一章——量子算法。作者首次将理论研究中最前沿的内容以通俗易懂的形式写入算法教科书中,给人耳目一新的感觉。作者以人类最古老的算法(算术运算)为起点,将各种算法中优美而有代表性的内容囊括书中,并以最前沿的理论结束本书,构成了完整的知识体系。..
此外,作者以穿插注解框的形式,对正文的叙述作进一步的解释。这些注解框的内容包括:人文历史背景、对复杂概念的进一步阐述、算法的扩展与重要应用等。书中还包括了近300道习题、补充阅读文献列表和术语索引。
在算法类书籍中,《算法导论》的地位是不可动摇的。但是对大多数读者而言,上千页的篇幅和形式化的叙述决定了《算法导论》只能是工具书而非教科书,最多只能作为研究生算法课程的教材,而不太适合本科生。在剩下的为数不多的算法类书籍中,《算法概论》一书在出版两年的时间内,就获得了读者的青睐。它新颖生动、简洁清新,向每个读者展示着算法的魅力,可以作为大学本科生一学期或两学期的教科书,又可以作为算法学习的参考书和补充读物。
我国大学计算机系的算法课一般开设在低年级,引进这本书是十分有必要的,相信它将对国内的算法教学起到推动作用。
本书的第0、3、4、8、9、10章由钱枫注释,第1、2、5、6、7章由邹恒明注释。
另外,在本书注释过程中,得到了以下人士的帮助:康奈尔大学(Cornell University)的范鸿敏,密歇根大学(University of Michigan-Ann Arbor)的方禄俊、李翼、钱志云、许密靖,以及上海交通大学的张漳、梁伟明、刘渊杰、孙涵、张华君,在此表示感谢。...
钱枫 邹恒明
2008年9月于美国密歇根安娜堡和上海莘庄