算法设计手册

出版时间：2009-9  出版社：清华大学出版社  作者：斯基恩纳  页数：706  
Tag标签：无  

前言

Most professional programmers that I've encountered are not well prepared to tackle algorithm design problems. This is a pity, because the techniques of algorithm design form one of the core practical technologies of computer science. Designing correct, efficient, and implementable algorithms for real-world problems requires access to two distinct bodies of knowledge:Techniques - Good algorithm designers understand several fundamental al-gorithm design techniques, including data structures, dynamic programming,depth-first search, backtracking, and heuristics. Perhaps the single most im-portant design technique is modeling, the art of abstracting a messy real-worldapplication into a clean problem suitable for algorithmic attack.Resources - Good algorithm designers stand on the shoulders of giants. Rather than laboring from scratch to produce a new algorithm for every task, they can figure out what is known about a particular problem. Rather than re-implementing popular algorithms from scratch, they seek existing imple- mentations to serve as a starting point. They are familiar with many classic algorithmic problems, which provide sufficient source material to model most any application.This book is intended as a manual on algorithm design, providing access tocombinatorial algorithm technology for both students and computer professionals.It is divided into two parts: Techniques and Resources, The former is a generalguide to techniques for the design and analysis of computer algorithms. The Re-sources section is intended for browsing and reference, and comprises the catalogof algorithmic resources, implementations, and an extensive bibliography.

内容概要

本书是算法设计畅销书的最新版本，是设计实用且高效算法的最全面指导书。本书揭密了算法的设计与分析，以简单易懂的写作风格，介绍了各种算法技术，着重强调了算法分析，全书包括两大部分，“技术”部分介绍了设计和分析计算机算法的各种方法，“资源”部分给出了大量的参考资源，以及算法实现的各种资源，此外，在作者的个人网址http：／／www．CS．sunysb．edu／～algorith／I-还提供了各种教学资源和参考材料，这些资源对读者很有参考价值。    本书可以作为算法设计课程的主教材，也是程序人员、研究人员和学生的常备参考书。

作者简介

作者：(德国)斯基恩纳(Steven S.Skiena)

书籍目录

I  Practical Algorithm Design　1　Introduction to Algorithm Design　　1.1 Robot Tour Optimization　　1.2  Selecting the Right Jobs　　1.3   Reasoning about Correctness　　1.4  Modeling the Problem　　1.5  About the War Stories　　1.6  War Story: Psychic Modeling　　1.7  Exercises　2  Algorithm Analysis　　2.1   The RAM Model of Computation　　2.2  The Big Oh Notation　　2.3  Growth Rates and Dominance Relations　　2.4  Working with the Big Oh　　2.5  Reasoning About Efficiency　　2.6   Logarithms and Their Applications 　　2.7  Properties of Logarithms　　2.8  War Story: Mystery of the Pyramids 　　2.9   Advanced Analysis (*)　　2.10 Exercises　3  Data Structures　　3.1   Contiguous vs. Linked Data Structures.　　3.2   Stacks and Queues　　3.3  Dictionaries　　3.4  Binary Search Trees　　3.5  Priority Queues　　3.6 War Story: Stripping Triangulations　　3.7　Hashing and Strings　　3.8  Specialized Data Structures　　3.9   War Story: String 'em Up　　3.10 Exercises　4 Sorting and Searching　　4.1   Applications of Sorting　　4.2   Pragmatics of Sorting　　4.3  Heapsort: Fast Sorting via Data Structures　　4.4  War Story: Give me a Ticket on an Airplane　　4.5   Mergesort: Sorting by Divide-and-Conquer　　4.6   Quicksort: Sorting by Randomization　　4.7  Distribution Sort: Sorting via Bucketing　　4.8  War Story: Skiena for the Defense　　4.9   Binary Search and Related Algorithms　　4.10 Divide-and-Conquer　　4.11 Exercises  　5  Graph Traversal　　5.1 Flavors of Graphs　　5.2   Data Structures for Graphs　　5.3   War Story: I was a Victim of Moore's Law　　5.4  War Story: Getting the Graph　　5.5  Traversing a Graph　　5.6  Breadth-First Search　　5.7  Applications of Breadth-First Search　　5.8  Depth-First Search　　5.9  Applications of Depth-First Search　　5.10 Depth-First Search on Directed Graphs　　5.11 Exercises　6  Weighted Graph Algorithms　　6.1   Minimum Spanning Trees　　6.2   War Story: Nothing but Nets　　6.3  Shortest Paths　　6.4   Wax Story: Dialing for Documents　　6.5   Network Flows and Bipartite Matching　　6.6  Design Graphs, Not Algorithms　　6.7   Exercises……

章节摘录

插图：3.7.2 Efficient String Matching via HashingStrings are sequences of characters where the order of the characters matters, sinceALGORITHM is different than LOGARITHM. Text strings are fundamental to ahost of computing applications, from programming language parsing/compilation,to web search engines, to biological sequence analysis.The primary data structure for representing strings is an array of characters.This allows us constant-time access to the ith character of the string. Some auxiliaryinformation must be maintained to mark the end of the string　either a specialend-of-string character or （perhaps more usefully） a count of the n characters inthe string.The most fundamental operation on text strings is substring search, namely:Problem: Substring Pattern MatchingInput: A text string t and a pattern string p.Output: Does t contain the pattern p as a substring, and if so where？

编辑推荐

《算法设计手册(第2版)》：大学计算机教育国外著名教材系列(影印版)

用户评论 (总计25条)

•   相当有水准的一套书，英文也不难。不过还是喜欢看中文
•   案头必备
•   这本书适合做大学教材
•   很实际,特别是第二章,基本每页都有实战价值
•   确实是一本好书 经典的书就是不一样 值得推荐
•   此书作者精于recursive codding,除了Backtracking和Depth-First Search这种本来就recursive的算法不说，一些很小的subroutine也用了recursive式的编写，其实没有必要，普通的code个人感觉很容易被理解和控制，总的来说，本书还是很不错的。 前期Sorting里的例子给出了一些典型，但没有细数家珍，以实用性很强的Quick Sorting结尾。 Graph部分略显晦涩，主要问题是作者在给完源码后，仅作了少量的文字描述和分析，对于初学者，这样的称述理解起来是很困难的，不过通过解答Graph的习题，可以加深理解，但得有足够的钻研精神。Graph的算法还是比较全的，基础的一些都有涉及，但就是过于言简意赅了，关于Graph，推荐阅读George T.Heineman的那本算法书，介绍的比较细腻，但是覆盖面小很多。 接着就是Backtracking，Heuristic Methods，这里情况比Graph好一些，给出了例子和运行结果，便于读者自行分析。 Heuristic Methods里着重强调了Simulated Annealling，也是出于实用性的目的，前面的例子可以不必细看，基本是拿来反衬Simulated Annea...lling的。Backtracking这一部分比较难，需要一定时间和基础才能理解。 Dynamic Programming的难度在Backtracking之上，基本上可以粗略地理解为对recursive coding的顺序化，这要求对recursive coding本身具有非常娴熟的掌握，也侧面解释了为什么作者如此自觉或下意识地在方方面面使用recursive coding，这是极具技巧性和挑战性的一章，一般的读者可以略去此章。 关于War Story，推荐一读，但不要深究。 后半部分基本上把常见问题的算法介绍给全了，这一块的Visualization做的相当不错，基本都有可视化的图形用于加深记忆和理解，Head First在这方面可以说是走向了一个极端，当然是比较好的极端，在我看来。算法介绍和实际的算法完整度是差别很大的，但至少它告诉你手头问题的学名是什么，也给了几个链接，也算是领进门了吧，剩下的修行就只能靠自己了。 总结，该书适用于偏好实践的读者，所罗列的算法不一定很复杂，但基本很实用，而且书中比较注意Visualization，并一直坚持用C给出源代码，这在一定程度上方便了读者进行理解，但Graph的部分过于言简意赅，读者需要一定的分析能力，或者要进行一些补充阅读。Hint：C和现在的Java，C#有着本质的区别，尤其是像C#这种具有Garbage Collection的现代编程语言，pointer基本被弃用了，相对的补偿则是简化了内存管理和编程过程，当然还有一个超棒的IDE：Visual Studio，与C相比，孰优孰劣，只能仁者见仁，智者见智了。我是偏好C#的，原因主要有2点，1是不碰硬件编程，2是这个IDE实在是太棒了，彻底把我征服，由此可见MicroSoft还是很老道的。 阅读更多 ›
•   如果你要参加acm或icpc建议你选购这本书并再购买一本此作者的编程挑战。
•   此书让我受益匪浅。全书分为两部分1. 和其他算法书一样，对各类算法（比如排序）给出难度适中的介绍。War Stories是作者遇到的实际问题，让你知道这些算法是如何应用于实际问题的。2. 作为一本手册，对各类问题给出了菜单式指导。这是此书的独特之处。比如找子串，不同情况下该用哪些不同算法。它给出的文献将各个问题研究到极致。这是一本很好的手册，也可以最为准备程序员面试的材料。
•   例子很好。讲解精炼!!
•   比那个什么算法导论要简单明了一些
•   书的质量还是很好的,书也很好.
•   纸张太薄但是可以忍受，内容很好，有实际问题做引导，算法也是一步步提升难度的，简单的集中在前几章，不会让人看不懂望而却步
•   没有算法导论那么晦涩，接近实际情况而且有作者很多的经验，重点推荐动态规划，深入浅出。
•   该书封面和装订都没有任何问题，但是纸张确让人无法忍受，非常之薄，每一页都透着反面的内容，导致阅读非常吃力，真的是“瞎了我的狗眼”。。。
•   看上不去，锻炼一下鸟语
•   有代码实现，具体书评可以到豆瓣或者亚马逊美国网站了解，挺好的一本书，偏实践，部分算法有时候与算法导论的思想不一样。还有一本好像叫《algorithms in a nutshell》也挺不错的，也是注重实践的，比较各个算法的运行时间
•   　　看着看着时而就觉得不明白了
  　　看到amazon上有人说
  　　This book isn't always the easiest to understand..
  　　. Consider the explanation of Djikstra's Algorithm on p. 206 of the 2nd ed:
  　　
  　　...
  　　我才放下心来.
  　　他就是没讲明白么,真是的!
  　　
  　　
•   　　第一部分讨论实用算法思路；第二部分实例分析极其讨喜。
  　　解释直观易懂，并提供了大量的参考信息，相当适合自己学习和额外研究用。
  　　每晚看一两个章节或例子相当愉快。
  　　不过印刷纸质颇为低劣……=_=
  　　
  　　居家旅行，闲时翻阅，面试备战的最佳选择……
  　　
  　　http://www.cs.sunysb.edu/~algorith/video-lectures/
  　　内有1997和2007的视音频和slides
•   个人觉得CLRS对算法的介绍太形式化了。。。自己中文版的CLRS丢了去书店本来想寻一本CLRS的英文版，结果只买到这本。。。可读性相当不错的说
•   嗯，这书还不错
•   雲妹,那么方便搞本原版啊..
•   好贵的啊..每次都同学回国都得求他们带影印版啊=.=
•   我去,朋友每次出国我都要求带原版..
•   我记得貌似这本书影印版被阉割过了..
•   内容的话我不确定(其实一直没读完Orz), 但是影印版是没有index了, 出版社脑子被驴踢了....=_=###