描述
开 本: 16开纸 张: 胶版纸包 装: 平装是否套装: 否国际标准书号ISBN: 9787302311850
算法是思维的艺术，是数学之美的完美体现，是计算机和信息科学的灵魂，更是优秀程序员的安身立命之本。本书将算法视为解决问题的工具，通过作者独创的、具有里程碑意义的新型分类法弥补了传统算法设计技术分类法的缺陷，用深入浅出的语言和新颖的实例与谜题，诠释了何为算法、算法的分类、算法幕后的思想、算法的效率，抽丝剥茧、条分缕析地探索了算法设计与分析过程。
本书，本书起到了很好的作用用全新的方式通过谜题和游戏来开拓算法思维，既适合本科生和研究生教学，又适合程序员参考，是帮助他们享受算法的乐趣，领悟思维训练之美，提升编程能力的理想读物。
（1)从科学性和专业性来讲，作者将原来不受重视的一些算法设计策略（如蛮力法、减治法、变治法、时空权衡和迭代改进）等纳入其中，覆盖了更多传统方法无法分类的经典算法（如欧几里得算法、堆排序、查找树、散列法、拓扑排序、高斯消去法、霍钠法则等），甚至还纳入了一些重要算法设计方法的变种。
（2)从系统性来讲，有趣的是，本书采用的正是算法的经典模式，首先说明什么是算法，然后经过思维训练和实践，解决如何分析与设计算法。这一点而言，对学生的真正意义在于，学会用思维能力和创新能力来解决问题，为日后的职业生涯打下坚实的基础。
（3)从适用性来讲，本书跳出了传统教材的框架，用一种新颖的方式来呈现主题，既照顾了本科学生课堂教学的需求，也兼顾了让他们课后拓展学习，进一步探索算法奥秘的愿望，具有广泛的普适性。
（4)从创新性来讲，本书的分类框架条理清晰，符合计算机教育的原理，非常适合算法教学，大量的流行谜题和游戏，让人流连忘返，手不释卷。
经过近5年的教学实践，本书第1版和第2版被证明是算法课程中具有较高价值的经典教材，据不完全统计，选用本书的学校包括清华大学、复旦大学、中国矿业大学、上海交通大学、解放军理工大学、广西大学、华南理工大学、安徽工业大学、广东工业大学、西安建筑科技大学，广东理工大学，齐齐哈尔大学、南昌航空工业学院软件学院、解放军炮兵学院、绵阳师范学院、湘潭大学、徐州工程学院、广东工业大学、广东工业大学、沈阳工业大学、西南科技大学、上海工程技术大学、湖南商学院、炮兵学院基础部、江西财经大学、华北科技学院、中南民族大学、沈阳建筑大学、北京第二外国语学院教育技术中心、潍坊学院、西华大学、武汉理工大学、河南师范大学、无锡科技职业学院、安徽理工大学、浙江工商大学、肇庆学院等。
本书在讲述算法设计技术时采用了新的分类方法，在讨论分析方法时条分缕析，形成了连贯有序、耳目一新的风格。为便于学生掌握，本书涵盖算法入门课程的全部内容，更注重对概念(而非形式)的理解。书中通过一些流行的谜题来激发学生的兴趣，帮助他们加强和提高解决算法问题的能力。每章小结、习题提示和详细解答，形成了非常鲜明的教学特色。
本书特色：
独辟蹊径，采用一种更全面的算法设计技术分类方法
涵盖递归与非递归算法的数学分析，也涉及经验分析和算法可视化
探讨算法的局限性及解决方法
将算法视为解决问题的工具，通过谜题和游戏来开拓算法思维
为学生提供600多道习题(含提示)，为教师提供有详细解答的教师手册
本书适用于以下课程：
算法(计算机科学)
C++算法(计算机科学)
Java—算法(计算机科学)
C算法(计算机科学)
C算法/数据结构高级课程(计算机科学)
Java-算法/数据结构高级课程(计算机科学)
C++–算法/数据结构高级课程(计算机科学)
Previous Editions
Levitin
ISBN-10: 0321358287 ? ISBN-13:9780321358288
©2007 ? Paper, 592 pp ? Out ofPrint
More info
……
“一个人接受科技教育时所能获得的最珍贵的收获，是那些能够受用终身的通用智能工具[1]。”
——George Forsythe，What to do till thecomputer scientist comes，1968
无论是计算科学还是计算实践，算法都在其中扮演着重要角色。因此，这门学科中出现了大量的教材。它们在介绍算法的时候，基本上都选择了以下两种方案中的一种。第一种方案是按照问题的类型对算法分类。这类教材安排了不同的章节分别讨论排序、查找、图等算法。这种做法的优点是，对于解决同一问题的不同算法，它能够立即比较这些算法的效率。其缺点在于，由于过于强调问题的类型，它忽略了对算法设计技术的讨论。
第二种方案围绕着算法设计技术来组织章节。在这种结构中，即使算法来自于不同的计算领域，如果它们采用了相同的设计技术，就会被编成一组。从各方(例如[BaY95])获得的信心使我相信，这种结构更适合于算法设计与分析的基础课程。强调算法设计技术有三个主要原因。第一，学生们在解决新问题时，可以运用这些技术设计出新的算法。从实用的角度看，这使得学习算法设计技术颇有价值。第二，学生们会试图按照算法的内在设计方法对已知的众多算法进行分类。计算机科学教育的一个主要目的，就是让学生们知道如何发掘不同应用领域的算法间的共性。毕竟，每门学科都会倾向于把它的重要主题归纳为几个甚至一个规则。第三，依我看来，算法设计技术作为问题求解的一般性策略，在解决计算机领域以外的问题时，也能发挥相当大的作用。
遗憾的是，无论是从理论还是从教学的角度，传统的算法设计技术分类法都存在一些严重的缺陷。其中最显著的缺陷就是无法对许多重要的算法进行分类。由于这种局限性，这些书的作者不得不在按照设计技术进行分类的同时，另外增加一些章节来讨论特殊的问题类型。但这种改变将导致课程缺乏一致性，而且很可能会使学生感到迷惑。
算法设计技术的新分类法
传统算法设计技术分类法的缺陷令我感到失望，它激发我开发一套新的分类法[Lev99]，这套分类法就是本书的基础。以下是这套新分类法的几个主要优势。
新分类法比传统分类法更容易理解。它包含的某些设计策略，例如蛮力法、减治法、变治法、时空权衡和迭代改进，几乎从不曾被看作重要的设计范例。
新分类法很自然地覆盖了许多传统方法无法分类的经典算法(欧几里得算法、堆排序、查找树、散列法、拓扑排序、高斯消去法、霍纳法则等，不胜枚举)。所以，新分类法能够以一种连贯的、一致的方式表达这些经典算法的标准内容。
新分类法很自然地容纳了某些设计技术的重要变种(例如，它能涵盖减治法的3个变种和变治法的3个变种)。
在分析算法效率时，新分类法与分析方法结合得更好(参见附录B)。
设计技术作为问题求解的一般性策略
在本书中，主要将设计技术应用于计算机科学中的经典问题(这里唯一的创新是引入了一些数值算法的内容，我们也是用同样的通用框架来表述这些算法的)。但把这些设计技术看作问题求解的一般性工具时，它们的应用就不仅限于传统的计算问题和数学问题了。有两个因素令这一点变得尤其重要。第一，越来越多的计算类应用超越了它们的传统领域，并且有足够的理由使人相信，这种趋势会愈演愈烈。第二，人们渐渐认识到，提高学生们的问题求解能力是高等教育的一个主要目标。为了满足这个目标，在计算机科学课程体系中安排一门算法设计和分析课程是非常合适的，因为它会告诉学生如何应用一些特定的策略来解决问题。
虽然我并不建议将算法设计和分析课程变成一门教授一般性问题求解方法的课程，但我的确认为，我们不应错过算法设计和分析课程提供的这样一个独一无二的机会。为了这个目标，本书包含了一些和谜题相关的应用。虽然利用谜题来教授算法课程绝不是我的创新，但本书打算通过引进一些全新的谜题来系统地实现这个思路。
如何使用本书
我的目标是写一本既不泛泛而谈，又可供学生们独立阅读的教材。为了实现这个目标，本书做了如下努力。
根据GeorgeForsythe的观点(参见引言)，我试图着重强调那些隐藏在算法设计和分析背后的主要思想。在选择特定的算法来阐述这些思想的时候，我并不倾向于涉及大量的算法，而是选择那些最能揭示其内在设计技术或分析方法的算法。幸运的是，大多数经典算法满足了这个要求。
第2章主要分析算法的效率，该章将分析非递归算法的方法和分析递归算法的典型方法区别开来。这一章还花了一些篇幅介绍算法经验分析和算法可视化。
书中系统地穿插着一些面向读者的提问。其中有些问题是经过精心设计的，而且答案紧随其后，目的是引起读者的注意或引发疑问。其余问题的用意是防止读者走马观花，不能充分理解本书的内容。
每一章结束时都会对本章最重要的概念和结论做一个总结。
本书包含600多道习题。有些习题是为了给大家练习，另外一些则是为了指出书中正文部分所涉及内容的重要意义，或是为了介绍一些书中没有涉及的算法。有一些习题利用了因特网上的资源。较难的习题数量不多，会在教师用书中用一种特殊的记号标注出来(因为有些学生可能没有勇气做那些标有难度的习题，所以本书没有对习题标注难度)。谜题类的习题用一种特殊的图标做标注。
本书所有的习题都附有提示。除了编程练习，习题的详细解法都能够在教师用书中找到，符合条件的教师可以填写书后的教师证明表，发传真到010-62791865或者发邮件到[email protected]，以获得教学资源的访问权限，也可联系培生公司的当地销售代表，或者访问www.pearsonhighered.com/irc。本书的任何读者都可以在CS支持网站http://cssupport.pearsoncmg.com上找到PowerPoint格式的幻灯片文件。
第3版的变化
第3版有若干变化。其中最重要的变化是介绍减治法和分治法的先后顺序。第3版会先介绍减治法，后介绍分治法，这样做有以下几个优点。
较之分治法，减治法更简单。
在求解问题方面，减治法应用更广。
这样的编排顺序便于先介绍插入排序，后介绍合并排序和快速排序。
数组划分的概念通过选择性问题引入，这次利用Lomuto算法的单向扫描来实现，而将Hoare划分方法的双向扫描留至后文与快速排序一并介绍。
折半查找归入介绍减常量算法的章节。
另一重要变化是重新编排第8章关于动态规划的内容，具体如下所述。
导述部分的内容是全新的。在前两版中用计算二项式系数的例子来引入动态规划这一重要技术，但在第3版中会介绍3个基础性示例，这样介绍的效果更好。
8.1节的习题是全新的，包括一些在前两版中没有涉及的流行的应用。
第8章其他小节的顺序也做了调整，以便达到由浅入深、循序渐进的效果。
此外，还有其他一些变化。增加了不少与本书所述算法相关的应用。遍历图算法不再随减治法介绍，而是纳入蛮力算法和穷举查找的范畴，我认为这样更合理。在介绍生成组合对象的算法时，会新增格雷码算法。对求解最近对问题的分治法会有更深入的探讨。改进的内容包括算法可视化和求解旅行商问题的近似算法，当然参考文献也相应更新。
第3版新增约70道习题，其中涉及算法谜题和面试问题。
读者所需的知识背景
本书假定读者已经学习了离散数学的标准课程和一门基础性的编程课程。有了这样的知识背景，读者应该能够掌握本书的内容而不会遇到太大的困难。尽管如此，1.4节、附录A和附录B仍然对基本的数据结构，必须用到的求和公式和递推关系分别进行了复习和回顾。只有3个小节(2.2节、11.4节和12.4节)会用到一些简单的微积分知识，如果读者缺少必要的微积分知识，完全可以跳过这3个涉及微积分的小节，这并不会妨碍对本书其余部分的理解。
进度安排
如果打算开设一门围绕算法设计技术来讲解算法设计和分析理论的基础课程，可以采用本书作为教材。但要想在一个学期内完成该课程，本书涵盖的内容可能过于丰富了。大体上来说，跳过第3～12章的部分内容不会影响读者对后面部分的理解。本书的任何一个部分都可以安排学生自学。尤其是2.6节和2.7节，它们分别介绍了经验分析和算法可视化，这两小节的内容可以结合练习[2]布置给学生。
下面给出了一种针对一个学期课程的教学计划，这是按照40课时的集中教学来设计的。
……
评论
还没有评论。