算法分析导论

    书籍
    计算机书籍
本书阐述了用于算法数学分析的主要方法，所涉及的材料来自经典数学课题，包括离散数学、初等实分析、组合数学，以及来自经典的计算机科学课题，包括算法和数据结构。本书内容集中覆盖基础、重要和有趣的算法，前面侧重数学，后面集中讨论算法分析的应用，重点是算法分析的数学方法。每章包含大量习题以及参考文献，使读者可以更深入地理解书中的内容。.

本书适合作为高等院校数学、计算机科学以及相关专业的本科生和研究生的教材，也可供相关技术人员参考。...

Philippe Flajolet INRIA的高级研究主任，在EcolePolytechn，que和普林斯顿大学任教，并在斯坦福大学、智利大学和弗吉尼亚技术大学拥有访问席位、他还是法国科学院的通信会员.
Robert Sedgewicd 斯坦福大学博士(导师为Donald E Knuth)，普林斯顿大学计算机科学系教授．Adobe Systems公司董事，曾是XeroxPARC的研究人员，还曾就职于美国国防部防御分析研究所以及INRIA...

出版者的话
专家指导委员会
译者序
序.
前言
记号解释
第1章 算法分析概述
1．1 为什么要对算法进行分析
1．2 计算复杂性
1．3 算法分析的过程
1．4 平均情形分析
1．5 例：快速排序的分析
1．6 渐近逼近
1．7 分布
1．8 概率算法
参考文献
第2章 递归关系
2．1 基本性质
2．2 一阶递归
2．3 非线性一阶递归

　　本书是对算法数学分析中主要方法的综述。所涉及的材料来自经典的数学课题，包括离散数学、初等实分析、组合数学，以及来自经典的计算机科学课题，包括算法和数据结构。重点在于“平均情形”或“概率”分析，不过，也包括“最坏情形”和“复杂性”分析所需要的基本数学工具。.
　　我们假设读者熟悉计算机科学和实分析中的基本概念。概括地说，读者应该既能编写程序，又能够证明定理；在其他方面，本书是自包容的。书中还在文献里捉供了丰富的预备性材料。我们计划中的本书姐妹篇将讨论更为先进的方法。这两部著作总共涵盖那些主要的方法和技巧，并提供通向算法分析日益增长的文献的捷径。
　　本书计划作为算法数学分析初级和高级课程的教科书。它也可以在计算机科学的离散数学课程中使用，因为它包含了离散数学和组合数学中的基本方法以及计算机科学学生所熟悉的重要离散结构的基本性质。传统上，在这些课程中知识范围要广一些，但是许多教师可能发现这里的做法是使学生从事实质性部分学习的有用方式。本书还可以作为数学和应用数学的学生了解与算法和数据结构相关的计算机科学原理的教材。
　　辅以文献中论文的补充，本书可作为研究生算法分析导论性课程的基础来使用，或作为那些想要接近该领域文献的数学或计算机科学研究人员的参考书或自学基础材料。它还可以作为应用和方法的资源为字符组合数学和离散数学的学生和研究人员使用。
　　尽管算法数学分析方面的文献很多，但是关于普遍使用的方法和模型方面的基本信息尚不能很容易地为该领域的学生和研究人员直接使用。本书的目的就是处理这种情况，把想要提供给读者该领域问题的正确评价和学习正在发展以满足这些挑战的高级工具的需求背景的大量材料汇聚在一起。
　　背景要求。假设数学程度为在大学学习一年或两年的水平。组合数学和离散数学的基本课程可以提供有用的背景知识(可能与本书的某些内容重叠)，实分析、数值方法或初等数论中的课程也是如此。我们将涉及所有这些领域，不过在这里只综述必需的材料，那些想要知道更多信息的读者可以参考标准的教科书。
　　假设编程经验为在大学学习过一个或两个学期的水平，包括初等数据结构。我们不在编程和算法实现问题上过多地耗费精力，算法和数据结构则是我们研究的中心课题。从某种意义上讲，我们的处理是完善的：对于基本的信息，我们给出概要的总结，必要时可以参考标准的教科书和一些基本的原始资料。
　　强烈推荐读者在数学计算时使用诸如MAPLE或Mathematica这样的汁算机软件。当验证本书中的材料或求解习题结果时，这些软件系统可以帮助摆脱烦琐的计算。相关的书籍。相关的教科书包括Knuth的The Art of ComputerProgramming；Gonnet和Baeza-Yates的Handbook of AlgorithmsandDataStructure；Sedgewick的Algorithms；Graham、Knuth和Patashnik的Concrefe Mathematics；Cormen、Leiserson和RiveSt的Introduction JdAlgorithms。本书可以看作是对这些著作的增补，下面依次评述。..
　　实质上，本书最接近于Knuth的开创性著作。不过，我们的重点是在分析的数学方法上，而Knuth著作的范围广而全，算法的性质起着主要的作用，而分析的方法则是第二位的。本书可以作为Knuth的著作中所论及的先进结果的基础准备。
　　我们还讨论了自从Knuth的书出版以来始终在发展的算法分析中的方法和结果。Gonnet和Baeza-Yates的著作是这些结果的透彻综述，包括全面的参考文献；它主要介绍源自文献的一些相关结果。本书提供了通向该文献的基本预备内容。
　　我们也努力把重点放在基础、重要和有趣的算法上，像Sedgewick的Algorithms中所描述的一些算法，而Graham、Knuth和Patashnik的ConcreteMathematics则几乎全部侧重在数学方法方面。我们想要使本书成为Graham、Knuth和Patashnik的书中所讨论的基本数学方法和Sedgewick的书所涉及的基本算法的桥梁。
　　Cormen、LeisersOn和Rivest的Introduction to Algorithms是那些提供通向算法的“设计和分析”研究文献著作的代表，一般是基于方法性能的粗略的最坏情形估计的。当需要更精确的结果时(对于大多数重要的方法)，更复杂的模型和数学工具是必不可少的。Cormen、Leiserson和Rivest把重点放在算法的设计(通常带有为最坏情形性能定界的目的)上，而解析结果则用于帮助指导算法的设计。另一方面，我们的书是对他们的书以及类似的书的补充，因为我们侧重于算法的分析，特别是对那些能够用于获取可以预报算法性能的详细结果的方法。在这个过程中，我们也考虑与各种经典数学工具的关系，第1章全部用来描述这种环境。
　　本书还为其姐妹篇AhaJytic Combinatorics奠定了基础，那本书以更广的视野对本书涉及 的材料进行一般的处理，并开发了高级方法和模型，这些方法和模型不仅在算法平均情形的 分析中，而且在组合数学中，均可作为新的研究基础。对于阅读那本姐妹篇，需要更高水平 的数学基础，相当于高年级本科生或低年级研究生所应具备的水平。当然，认真学习本书也 足以具备这些基础。毫无疑问，使得本书充分有趣始终是我们的目的，读者将会惊喜地发现 本书涉及更先进的材料。...