算法概论(注释版)

.

本书源自加州大学伯利分校和加州大学圣迭戈分校本科生的算法课讲义，以独特的视角展现了算法设计的精巧技术及魅力。在表达每一种技术时，强调每个算法背后的简洁数学思想，分析其时间和空间效率，运用与其他技术类比的方法来说明特征，并提供了大量实例。
    本书以人类很古老的算法（算术运算）为起点，将各种算法中优美而有代表性的内容囊括书中，并以很前沿的理论（量子算法）结束，构成了较为完整的算法知识体系。
    本书主要特点
    ●生动的写作风格：作者贯穿一条主线，以讲故事的形式将概念娓娓道来，很好易于理解和消化。
    ●优美地兼顾语言的生动和严谨性：本书中看不到很多数学公式，取而代之的是准确的文字叙述。
    ●合理地挑选主题：用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（递归关系）
  2.3 Mergesort（合并排序）
  2.4 Medians（中位数）
  2.5 Matrix multiplication（矩阵乘法）
  2.6 The fast Fourier transform（快速傅里叶变换）
  Exercises（习题）
3 Decompositions of graphs（图的分解）
  3.1 Why graphs?（图论）
  3.2 Depth-first search in undirected graphs（无向图中的深度优先搜索）
  3.3 Depth-first search in directed graphs（有向图中的深度优先搜索）
  3.4 Strongly connected components（强连通分量）
  Exercises（习题）
4 Paths in graphs（图的路径）
  4.1 Distances（距离）
  4.2 Breadth-first search（广度优先搜索）
  4.3 Lengths on edges（边的长度）
  4.4 Dijkstra’s algorithm（Dijkstra算法）
  4.5 Priority queue implementations（实现优先队列）
  4.6 Shortest paths in the presence of negative edges（带负权的边的图中的最短路径）
  4.7 Shortest paths in dags（有向无环图中的最短路径）
  Exercises（习题）
5 Greedy algorithms（贪婪算法）
  5.1 Minimum spanning trees（最小生成树）
  5.2 Huffman encoding（赫夫曼编码）
  5.3 Horn formulas（Horn公式）
  5.4 Set cover（集合覆盖）
  Exercises（习题）
6 Dynamic programming（动态规划）
  6.1 Shortest paths in dags，revisited（回顾：有向无环图中的最短路径）
  ……
7 Linear programming and reductions（线性规划与归约）
8 NP-complete problems（NP完全问题）
9 Coping with NP-completeness（处理NP完全问题）
10 Quantum algorithms（量子算法）
Historical notes and further reading
（历史注记与扩展阅读）
索引
注释