基本信息
- 原书名：Algorithm Design and Applications
- 作者： （美）迈克尔T.古德里奇（Michael T. Goodrich） （美）罗伯托·塔马西亚（Roberto Tamassia）
- 译者： 乔海燕 李悫炜 王烁程
- 丛书名： 计算机科学丛书
- 出版社：机械工业出版社
- ISBN：9787111582779
- 上架时间：2017-11-16
- 出版日期：2018 年1月
- 开本：16开
- 版次：1-1
- 所属分类：计算机 > 计算机科学理论与基础知识 > 计算理论 > 算法
教材
内容简介
目录
出版者的话
译者序
前言
第1章算法分析
1.1分析算法
1.1.1伪代码
1.1.2随机存取机模型
1.1.3基本操作数目的计算
1.1.4递归算法的分析
1.1.5渐近表示法
1.1.6渐近表示法的重要性
1.2相关数学知识复习
1.2.1求和
1.2.2对数和幂
1.2.3简单的证明技术
1.2.4概率基础
1.3算法分析案例
1.3.1最大子数组问题的第一个解
1.3.2一种改进的求最大子数组算法
1.3.3线性时间的最大子数组算法
译者序
前言
第1章算法分析
1.1分析算法
1.1.1伪代码
1.1.2随机存取机模型
1.1.3基本操作数目的计算
1.1.4递归算法的分析
1.1.5渐近表示法
1.1.6渐近表示法的重要性
1.2相关数学知识复习
1.2.1求和
1.2.2对数和幂
1.2.3简单的证明技术
1.2.4概率基础
1.3算法分析案例
1.3.1最大子数组问题的第一个解
1.3.2一种改进的求最大子数组算法
1.3.3线性时间的最大子数组算法
译者序
本书全面系统地介绍数据结构、算法设计、算法分析和算法应用。全书内容丰富，讲解由浅入深，既包含经典数据结构和算法、算法设计方法和分析方法以及算法应用，又包含众多高级主题，包括多维搜索、计算几何、密码算法、傅里叶变换和线性规划等。
本书采用应用驱动的方式组织各章内容。书中算法均给出伪代码描述，附带图文并茂的运行过程例子，以及严谨的复杂度分析。每章都附有大量的练习，并分为巩固练习、创新练习和应用练习三种类型，其中应用练习是将刚刚学习的知识应用到实际生活的具体场景中，能极好地加深读者对知识的理解。这种内容和练习的安排，为读者全面深刻地掌握有关内容提供了很好的素材和途径。
全书分六个部分。第一部分系统地讲解基础数据结构与算法，包括栈、队列、二叉搜索树、平衡二叉搜索树、优先队列和堆、哈希表和并查集结构等。通过学习这些章节，读者能由浅入深地掌握常见的数据结构，并为学习后续内容打下坚实的基础。
第二部分讲解排序和选择，包括归并排序和快速排序算法，以及如何进行快速的排序和选择。排序算法是极为重要的一类算法，本部分首先讲解了基于比较的归并排序和快速排序算法，然后讲解了桶排序和基数排序等算法，还讲解了选择和加权中位数算法。
第三部分讲解算法设计常用的技术，包括贪心法、分治法、动态规划、图的遍历。这些均为算法设计中常用的方法，本书用很多具体的算法和实例来讲解如何运用这些方法来设计算法，使得读者能够举一反三，根据实际问题利用这些方法来设计算法。
第四部分讲解图的算法，包括最短路径算法、最小生成树算法，以及网络流和匹配。通过学习这些章节，读者能掌握多种求解最短路径、最小生成树的算法，通过学习网络流和匹配的相关概念和算法，对图有更深入的理解。
第五部分讲解计算困难问题，包括NP完全问题，以及近似算法。本部分主要讨论NP难的问题，为解决这些计算困难问题，讨论了一些近似算法。
第六部分讲解高级主题，包括随机算法、B树和外部存储器、多维搜索、计算几何、字符串算法、密码学、快速傅里叶变换和线性规划。这一部分覆盖面较广，涉及计算机科学的各个领域，读者可以借此了解更多有趣的主题。
本书作者Michael T Goodrich和Roberto Tamassia均为知名大学教授，算法研究领域知名学者。他们不仅对算法理论和应用有深刻见解，而且对算法教学有实际经验。如作者在前言中所讲，本书涵盖内容丰富，既可作为数据结构和算法核心课程的教材，也可作为高年级本科生和研究生的高级算法课程的教材。
本书在翻译过程中得到了许多同行和编辑的大力支持。特别是，任利明对有关棒球的规则和术语做了说明，黄森中对图题的德文做了翻译。在此一并对给予我们帮助的同行和编辑表示感谢！
另外，为了便于读者的阅读，我们对算法伪代码也做了必要的翻译。限于译者水平，译文中难免出现疏漏和错误，欢迎大家批评指正！
译者
2017年4月于广州大学城
本书采用应用驱动的方式组织各章内容。书中算法均给出伪代码描述，附带图文并茂的运行过程例子，以及严谨的复杂度分析。每章都附有大量的练习，并分为巩固练习、创新练习和应用练习三种类型，其中应用练习是将刚刚学习的知识应用到实际生活的具体场景中，能极好地加深读者对知识的理解。这种内容和练习的安排，为读者全面深刻地掌握有关内容提供了很好的素材和途径。
全书分六个部分。第一部分系统地讲解基础数据结构与算法，包括栈、队列、二叉搜索树、平衡二叉搜索树、优先队列和堆、哈希表和并查集结构等。通过学习这些章节，读者能由浅入深地掌握常见的数据结构，并为学习后续内容打下坚实的基础。
第二部分讲解排序和选择，包括归并排序和快速排序算法，以及如何进行快速的排序和选择。排序算法是极为重要的一类算法，本部分首先讲解了基于比较的归并排序和快速排序算法，然后讲解了桶排序和基数排序等算法，还讲解了选择和加权中位数算法。
第三部分讲解算法设计常用的技术，包括贪心法、分治法、动态规划、图的遍历。这些均为算法设计中常用的方法，本书用很多具体的算法和实例来讲解如何运用这些方法来设计算法，使得读者能够举一反三，根据实际问题利用这些方法来设计算法。
第四部分讲解图的算法，包括最短路径算法、最小生成树算法，以及网络流和匹配。通过学习这些章节，读者能掌握多种求解最短路径、最小生成树的算法，通过学习网络流和匹配的相关概念和算法，对图有更深入的理解。
第五部分讲解计算困难问题，包括NP完全问题，以及近似算法。本部分主要讨论NP难的问题，为解决这些计算困难问题，讨论了一些近似算法。
第六部分讲解高级主题，包括随机算法、B树和外部存储器、多维搜索、计算几何、字符串算法、密码学、快速傅里叶变换和线性规划。这一部分覆盖面较广，涉及计算机科学的各个领域，读者可以借此了解更多有趣的主题。
本书作者Michael T Goodrich和Roberto Tamassia均为知名大学教授，算法研究领域知名学者。他们不仅对算法理论和应用有深刻见解，而且对算法教学有实际经验。如作者在前言中所讲，本书涵盖内容丰富，既可作为数据结构和算法核心课程的教材，也可作为高年级本科生和研究生的高级算法课程的教材。
本书在翻译过程中得到了许多同行和编辑的大力支持。特别是，任利明对有关棒球的规则和术语做了说明，黄森中对图题的德文做了翻译。在此一并对给予我们帮助的同行和编辑表示感谢！
另外，为了便于读者的阅读，我们对算法伪代码也做了必要的翻译。限于译者水平，译文中难免出现疏漏和错误，欢迎大家批评指正！
译者
2017年4月于广州大学城
前言
本书全面地介绍了计算机算法和数据结构的设计和分析。书中各章相对独立，所以教师和读者可以自由选择感兴趣的章节。此外，本书内容广泛，既包含了经典的算法，也包含了新兴的算法，具体如下：
渐近分析数学，包括平摊和随机化。
通用算法设计技术，包括贪心法、分治法和动态规划。
数据结构，包括列表、树、堆、搜索树、B树、哈希表、跳跃表、并查集结构和多维树。
算法框架，包括NP完全性、近似算法和外存算法。
基本算法，包括排序、图算法、计算几何、数值算法、密码、快速傅里叶变换（FFT）和线性规划。
应用驱动方法
计算机科学已经进入一个令人兴奋的时代。计算机已经从早期的计算引擎发展到现在的信息处理器，其应用遍布各个领域。此外，互联网的扩展推动了计算机在社会和商业中的新范式和新模式。例如，计算机可以用来存储和检索大规模数据，并且用于许多其他的应用领域，如运动、视频游戏、生物、制药、社交网络、工程和科学。因此，我们认为算法的讲授既要强调其数学分析，也要突出其实际应用。
为了达到这个目的，每章开篇都有该章主题应用的一个简短讨论。这些应用有的来自于主题的实际应用，有的是设想该章主题在实践中的可能应用。这些讨论的意图是为读者阅读各章时提供一定的背景和实际应用动机。除了这些应用的动机外，我们还给出算法的详细伪代码描述和完整的数学分析。事实上，我们认为数学的严谨性有其实际的意义。
写给教师
本书的结构便于教师自由地选择和讲授内容。各章节之间的依存度已经降至很低，以便教师可以按照自己喜欢的顺序授课。此外，依据内容的深度，每章的讲授时间在1～3节课。
课程样例
本书可作为多个课程的教材。例如，可用于算法核心课程的教材，即经典CS7。另外，本书也可以用于高年级本科生或者研究生的数据结构课程、算法课程，或者两学期连续教授这两个课程的教材。为了突出这些选择，下面为这些可能的课程给出教学大纲样例。
算法核心课程（CS7）大纲样例
第1章算法分析
（跳读、略读或复习第2～4章的基本数据结构）
这些内容以及第5章和第6章是数据结构课程的基本内容，也是本课程的先行课。
第5章优先队列和堆
第6章散列表
第7章并查集结构
渐近分析数学，包括平摊和随机化。
通用算法设计技术，包括贪心法、分治法和动态规划。
数据结构，包括列表、树、堆、搜索树、B树、哈希表、跳跃表、并查集结构和多维树。
算法框架，包括NP完全性、近似算法和外存算法。
基本算法，包括排序、图算法、计算几何、数值算法、密码、快速傅里叶变换（FFT）和线性规划。
应用驱动方法
计算机科学已经进入一个令人兴奋的时代。计算机已经从早期的计算引擎发展到现在的信息处理器，其应用遍布各个领域。此外，互联网的扩展推动了计算机在社会和商业中的新范式和新模式。例如，计算机可以用来存储和检索大规模数据，并且用于许多其他的应用领域，如运动、视频游戏、生物、制药、社交网络、工程和科学。因此，我们认为算法的讲授既要强调其数学分析，也要突出其实际应用。
为了达到这个目的，每章开篇都有该章主题应用的一个简短讨论。这些应用有的来自于主题的实际应用，有的是设想该章主题在实践中的可能应用。这些讨论的意图是为读者阅读各章时提供一定的背景和实际应用动机。除了这些应用的动机外，我们还给出算法的详细伪代码描述和完整的数学分析。事实上，我们认为数学的严谨性有其实际的意义。
写给教师
本书的结构便于教师自由地选择和讲授内容。各章节之间的依存度已经降至很低，以便教师可以按照自己喜欢的顺序授课。此外，依据内容的深度，每章的讲授时间在1～3节课。
课程样例
本书可作为多个课程的教材。例如，可用于算法核心课程的教材，即经典CS7。另外，本书也可以用于高年级本科生或者研究生的数据结构课程、算法课程，或者两学期连续教授这两个课程的教材。为了突出这些选择，下面为这些可能的课程给出教学大纲样例。
算法核心课程（CS7）大纲样例
第1章算法分析
（跳读、略读或复习第2～4章的基本数据结构）
这些内容以及第5章和第6章是数据结构课程的基本内容，也是本课程的先行课。
第5章优先队列和堆
第6章散列表
第7章并查集结构
