算法概论(注释版)

    书籍
    计算机书籍
本书源自加州大学伯克利分校和加州大学圣迭戈分校本科生的算法课讲义，以独特的视角展现了算法设计的精巧技术及魅力。在表达每一种技术时，强调每个算法背后的简洁数学思想，分析其时间和空间效率，运用与其他技术类比的方法来说明特征，并提供了大量实例。
本书以人类最古老的算法（算术运算）为起点，将各种算法中优美而有代表性的内容囊括书中，并以最前沿的理论（量子算法）结束，构成了较为完整的算法知识体系。
本书主要特点
●生动的写作风格：作者贯穿一条主线，以讲故事的形式将概念娓娓道来，非常易于理解和消化。
●优美地兼顾语言的生动和严谨性：本书中看不到很多数学公式，取而代之的是精确的文字叙述。
●合理地挑选主题：用300多页的篇幅使读者对这门博大精深的科学有深刻的认识。
●穿插注解框：内容包括人文历史背景、对复杂概念的进一步阐述、算法的扩展与重要应用等，对正文的叙述进行补充。

Sanjoy Dasgupta，拥有加州大学伯克利分校计算机科学博士学位，现为加州大学圣迭戈分校教授，主要研究领域是多维数据的统计分析。他曾是AT&T实验室的高级技术人员。

出版者的话
序言
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（递归关系）

　　This book evolved over the past ten years from a set of lecture notes developed while teaching the undergraduate Algorithms course at Berkeley and U.C. San Diego. Our way of teaching this course evolved tremendously over these years in a number of directions, partly to address our students' background (undeveloped formal skills outside of programming), and partly to reflect the maturing of the field in general, as we have come to see it. The notes increasingly crystallized into a narrative, and we progressively structured the course to emphasize the "story line" implicit in the progression of the material. As a result, the topics were carefully selected and clustered. No attempt was made to be encyclopedic, and this freed us to include topics traditionally de-emphasized or omitted from most Algorithms books. .
　　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. ...