算法导论(part1)

一、本书的内容 目前，市面上有关计算机算法的书很多，有些叙述严谨但不全面，另外一些则是容量很大但不够严谨。本书将叙述的严谨性以及内容的深度和广度有机地结合了起来。第1版推出后，即在世界范围内受到了广泛的欢迎，被各高等院校用作多种课程的教材和业界的标准参考资料。它深入浅出地介绍了大量的算法及相关的数据结构，以及用于解决一些复杂计算问题的高级策略(如动态规划、贪心算法、平摊分析等)，重点在于算法的分析和设计。对于每一个专题，作者都试图提供目前最新的研究成果及样例解答，并通过清晰的图示来说明算法的执行过程。. 本书是原书的第2版，在第1版的基础之上增加了一些新的内容，涉及算法的作用、概率分析和随机化算法、线性规划，以及对第1版中详尽的、几乎涉及到每一小节的修订。这些修订看似细微，实际上非常重要。书中引入了“循环不变式”，并贯穿始终地用来证明算法的正确性。在不改动数学和分析重点的前提下，作者将第1版中的许多数学基础知识从第一部分移到了附录中。 二、本书的特点 本书在进行算法分析的过程中，保持了很好的数学严谨性。书中的分析和设计可以被具有各种水平的读者所理解。相对来说，每一章都可以作为一个相对独立的单元来教授或学习。书中的算法以英语加伪代码的形式给出，只要有一点程序设计经验的人都能读懂，并可以用任何计算机语言(如C／C++和Java等)方便地实现。在书中，作者将算法的讨论集中在一些比较现代的例子上，它们来自分子生物学(如人类基因项目)、商业和工程等领域。每一小节通常以对相关历史素材的讨论结束，讨论了在每一算法领域的原创研究。 本书的特点可以概括为以下几个方面： 1．概念清晰，广度、深度兼顾。 本书收集了现代计算机常用的数据结构和算法，并作了系统而深入的介绍。对涉及的概念和背景知识都作了清晰的阐述，有关的定理给出了完整的证明。 2．“五个一”的描述方法。 本书以相当的深度介绍了许多常用的数据结构和有效的算法。编写上采用了“五个一”，即一章介绍一个算法、一种设计技术、一个应用领域和一个相关话题。.. 3．图文并茂，可读性强。 书中的算法均以通俗易懂的语言进行说明，并采用了大量插图来说明算法是如何工作的，易于理解。 4．算法的“伪代码”形式简明实用。 书中的算法均以非常简明的“伪代码”形式来设计，可以很容易地把它转化为计算机程序，直接应用。 注重算法设计的效率，对所有的算法进行了仔细、精确的运行时间分析，有利于进一步改进算法。 三、本书的用法 本书对内容进行了精心的设计和安排，尽可能考虑到所有水平的读者。即使是初学计算机算法的人，也可以在本书中找到所需的材料。 每一章都是独立的，读者只需将注意力集中到最感兴趣的章节阅读。 1．适合作为教材或教学参考书。 本书兼顾通用性与系统性，覆盖了许多方面的内容。本书不但阐述通俗、严谨，而且提供了大量练习和思考题。针对每一节的内容，都给出了数量和难度不等的练习题。练习题用于考察对基本内容的掌握程度，思考题有一定的难度，需进行精心的研究，有时还通过思考题介绍一些新的知识。 前言回到顶部↑本书提供了对当代计算机算法研究的一个全面、综合性的介绍。书中给出了多个算法，并对它们进行了较为深入的分析，使得这些算法的设计和分析易于被各个层次的读者所理解。力求在不牺牲分析的深度和数学严密性的前提下，给出深入浅出的说明。. 书中每一章都给出了一个算法、一种算法设计技术、一个应用领域或一个相关的主题。算法是用英语和一种“伪代码”来描述的，任何有一点程序设计经验的人都能看得懂。书中给出了230多幅图，说明各个算法的工作过程。我们强调将算法的效率作为一种设计标准，对书中的所有算法，都给出了关于其运行时间的详细分析。 本书主要供本科生和研究生的算法或数据结构课程使用。因为书中讨论了算法设计中的工程问题及其数学性质，因此，本书也可以供专业技术人员自学之用。 本书是第2版。在这个版本里，我们对全书进行了更新。所做的改动从新增了若干章，到个别语句的改写。 致使用本书的教师 本书的设计目标是全面、适用于多种用途。它可用于若干课程，从本科生的数据结构课程到研究生的算法课程。由于书中给出的内容比较多，只讲一学期一般讲不完，因此，教师们应该将本书看成是一种“缓存区”或“瑞典式自助餐”，从中挑选出能最好地支持自己希望教授的课程的内容。 教师们会发现，要围绕自己所需的各个章节来组织课程是比较容易的。书中的各章都是相对独立的，因此，你不必担心意想不到的或不必要的各章之间的依赖关系。每一章都是以节为单位，内容由易到难。如果将本书用于本科生的课程，可以选用每一章的前面几节内容；在研究生课程中，则可以完整地讲授每一章。 全书包含920多个练习题和140多个思考题。每一节结束时给出练习题，每一章结束时给出一些