算法技术手册
算法技术手册
George T. Heineman, Gary Pollice, Stanley Selkow
杨晨, 李明 译
出版时间:2010年03月
页数:333
开发健壮的软件需要高效的算法,然而程序员们往往直至问题发生之时,才会去求助于算法。本书讲解了许多现有的算法,可用于解决各种问题。通过阅读它,你可以学会如何选择和实现正确的算法,来达成自己的目标。另外,书中的数学深浅适中,足够使你了解并分析算法的性能。
较之理论而言,本书更专注于应用。本书提供了高效的代码解决方案,使用多种语言进行编写,让你可以轻松地将其应用于特定的工程当中。通过本书,你可以:
· 解决特定代码的问题,或者提升现有解决方案的性能。
· 快速找到与你所解决的问题相关的算法,并决定哪种算法才是最适合的。
· 探索使用C、C++、Java以及Ruby实现的算法解决方案以及开发小贴士。
· 了解算法预期的性能,以及它达到最高性能时所需要的条件。
· 发现不同算法之间相似的设计哲学。
· 学习高级数据结构,来提升算法的性能。
通过本书,你能学到如何提升算法的性能,这将是你的软件应用程序走向成功的关键。
“作者完成了一项了不起的工作,将晦涩的学术加以精炼,完美地在理论和实践之间取得了平衡,从而使本书成为了一本不可或缺的指南。从此,彻底领悟算法就变得十分简单了。”
——Matthew Russell,Digital Reasoning Systems
高级技术总监,《Dojo权威指南》(O’Reilly)的作者
George T. Heineman、Gary Pollice和Stanley Selkow均为伍斯特理工学院计算机科学系的教授。George是《Component-Based Software Engineering: Putting the Pieces Together》(Addison-Wesley)的联合主编。Gary是《Head First Object- Oriented Analysis and Desgin》(O’Reilly)的合著者。
  1. 前言
  2. 第一部分
  3. 第1章 算法真的很重要
  4. 理解问题
  5. 如果需要,尽可能用实践检验
  6. 解决问题的算法
  7. 花絮
  8. 故事的寓意
  9. 参考文献
  10. 第2章 算法的数学原理
  11. 问题样本的规模
  12. 函数的增长率
  13. 最好最坏和平均情况下的性能分析
  14. 性能指标
  15. 混合操作
  16. 基准测试
  17. 最后一点
  18. 参考文献
  19. 第3章 模式和领域
  20. 模式:一种交流语言
  21. 算法模式的格式
  22. 伪代码模式的格式
  23. 设计格式
  24. 基于经验的评价格式
  25. 领域和算法
  26. 浮点计算
  27. 手动内存分配
  28. 选择一门编程语言
  29. 参考文献
  30. 第二部分
  31. 第4章 排序算法
  32. 概述
  33. 插入排序
  34. 中值排序
  35. 快速排序
  36. 选择排序
  37. 堆排序
  38. 计数排序
  39. 选择排序算法的标准
  40. 参考文献
  41. 第5章 查找
  42. 概述
  43. 顺序查找
  44. 二分查找
  45. 基于散列的查找
  46. 二叉查找树
  47. 参考文献
  48. 第6章 图算法
  49. 概述
  50. 深度优先搜索
  51. 广度优先搜索
  52. 单源最短路径
  53. 所有点对最短路径
  54. 最小生成树算法
  55. 参考文献
  56. 第7章 人工智能中的寻路
  57. 概述
  58. 深度优先搜索
  59. 广度优先搜索
  60. A*搜索
  61. 比较
  62. Minimax
  63. NegMax
  64. AlphaBeta
  65. 参考文献
  66. 第8章 网络流算法
  67. 概述
  68. 最大流
  69. 二部图匹配
  70. 在增广路上的深入思考
  71. 最小开销流
  72. 转运问题
  73. 运输问题
  74. 任务分配问题
  75. 线性编程
  76. 参考文献
  77. 第9章 计算几何
  78. 概述
  79. 凸包扫描
  80. 线段扫描
  81. 最近点查询
  82. 范围查询
  83. 参考文献
  84. 第三部分
  85. 第10章 最后的招数
  86. 另类算法
  87. 近似算法
  88. 离线算法
  89. 并行算法
  90. 随机算法
  91. 结果可能出错却可以衰减错误率的算法
  92. 参考文献
  93. 第11章 尾声
  94. 概述
  95. 原则:了解数据
  96. 原则:将问题分解至更小的问题
  97. 原则:选择正确的数据结构
  98. 原则:空间换时间
  99. 原则:如果没有显而易见的解法,使用搜索
  100. 原则:如果没有显而易见的解法,将问题归约为另一个有解的问题
  101. 原则:编写算法难,测试算法更难
  102. 第四部分
  103. 附录 基准测试
书名:算法技术手册
译者:杨晨, 李明 译
国内出版社:机械工业出版社
出版时间:2010年03月
页数:333
书号:978-7-111-28674-5
原版书出版商:O'Reilly Media
George T. Heineman
 
George T. Heineman is an associate professor of computer science at Worcester
Polytechnic Institute. His research interests are in software engineering. He coedited
the 2001 book Component-Based Software Engineering: Putting the Pieces
Together (Addison-Wesley). George was the program chair for the 2005 International
Symposium on Component-Based Software Engineering.
 
 
Gary Pollice
 
GaryPPollice将自己归类为臭脾气的老古董,他在业界花了35年的时间,试图成为其成长过程中想要成为的人。即使他尚未成熟,在2003年,他还是毅然决然地进入学术殿堂。在那里,他一直在摧残下一代软件开发者的心智,以近乎激进的观念,如“软件是为客户开发的;学习如何扮演团队的一分子;设计和程序的品质、优雅性及正确性都很重要;只要你是一个伟大的程序员,就算是一个程序狂也无妨。”
Gary是伍斯特理工学院(Worcester Polytechnic Institute,WPI)的实训教授(Professor of Practice,这是指成为教授之前具有实际工作的经验),他与妻子 Vikki以及两只狗 Aloysius 与 Ignatius住在马萨诸塞州中部。你可访问他在 WPI 的主页,http://web.cs.wpi.edu/~gpollice/。别客气,有关于本书的抱怨或鼓励,请尽管留言给他。
Gary Pollice is a self-labeled curmudgeon (that's a crusty, ill-tempered,
usually old man) who spent over 35 years in industry trying to fi gure out
what he wanted to be when he grew up. Even though he hasn't grown up yet,
he did make the move in 2003 to the hallowed halls of academia where he
has been corrupting the minds of the next generation of software developers
with radical ideas like, "develop software for your customer, learn how to
work as part of a team, design and code quality and elegance and correctness
counts, and it's okay to be a nerd as long as you are a great one."
Gary is a Professor of Practice (meaning he had a real job before becoming a
professor) at Worcester Polytechnic Institute. He lives in central Massachusetts
with his wife, Vikki, and their two dogs, Aloysius and Ignatius. You can visit
his WPI home page at http://web.cs.wpi.edu/~gpollice/. Feel free
to drop him a note and complain or cheer about the book.


Gary Pollice is a self-labeled curmudgeon (that’s a crusty, ill-tempered, usually
old man) who spent more than 35 years in industry trying to figure out what he
wanted to be when he grew up. Even though he hasn’t grown up yet, he did make
the move in 2003 to the hallowed halls of academia, where he has been corrupting
the minds of the next generation of software developers with radical ideas like,
“develop software for your customer,” “learn how to work as part of a team,”
“design and code quality and elegance and correctness counts,” and “it’s OK to be
a nerd as long as you are a great one.”
Gary is a professor of practice (meaning he had a real job before becoming a
professor) at Worcester Polytechnic Institute. He went to WPI because he was so
impressed with the WPI graduates that he’s worked with over the years. He lives
in central Massachusetts with his wife, Vikki, and their two dogs, Aloysius and
Ignatius. When not working on geeky things he...well he’s always working on
geeky things. You can see what he’s up to by visiting his WPI home page,
http://web.cs.wpi.edu/~gpollice/. Feel free to drop him a note and complain or
cheer about the book.
 
 
Stanley Selkow
 
Stanley Selkow, a professor of computer science at Worcester Polytechnic Institute,
received a B.S. in electrical engineering from Carnegie Institute of Technology
in 1965, and a Ph.D. in the same area from the University of Pennsylvania in 1970.
From 1968 to 1970 he was in the public health service at the National Institutes of
Health at Bethesda, Maryland. Since 1970 he has been on the faculty at universities
in Knoxville, Tennessee and Worcester, Massachusetts, as well as Montreal,
Chonqing, Lausanne, and Paris. His major research has been in graph theory and
algorithm design.
 
 
本书封面的动物是一只寄居蟹(Pagurus bernhardus)。在世界各地有超过500种寄居蟹。它们大多为水生,生活在珊瑚礁和潮池的盐水中。一些寄居蟹,尤其是在热带地区的,是陆生的。例如一种名为盗蟹的寄居蟹,它能够长到椰子那么大。陆生寄居蟹在它们的壳里面存放着少量的水,用来帮助呼吸以及保持腹部湿润。
寄居蟹和其他螃蟹不一样,它们不需要一个坚硬的属于自己的外壳,它们寻找食肉动物不能食用的腹足动物(例如蜗牛)的外壳作为庇护所。它们特别偏好玉黍螺和海螺的壳。随着身体的长大,它们需要寻找更大的壳寄居。如果他们将身体的任何部分暴露出来,那么会非常容易受到食肉动物的攻击;此外,如果没有一个合适的外壳,就会阻碍它们的成长,因为昆虫腹足动物的壳是有限的,所以竞争也是一个问题。
寄居蟹是十足(也就是说十只脚)甲壳动物。在它们的五对足中,第一对是钳子,或者是螯,较大的那个是它们用来防御和撕碎食物用的,而较小的是用来辅助进食的。第二对和第三对足帮助它们走路,最后两对足用于将它们固定在壳中。
寄居蟹具有明显的甲壳动物的特征:它们没有内骨架,而是有一个钙质的外骨骼。它们也有两只复眼,两对触角(它们用来感知味道和振动)并拥有三对口器。在触角的底部是一对触角腺,用来排出废物。
可以经常看见海葵附在寄居蟹的壳上。海葵以这种方式移动并食用寄居蟹的食物残渣,不过作为交换,海葵能够伪装寄居蟹以逃过海洋食肉动物的捕食,例如鱼和章鱼。其他的食肉动物也包括:鸟和其他的螃蟹,以及一些哺乳动物(例如人)。
寄居蟹号称“海洋的垃圾收集器”,它能够吃掉几乎所有的东西,例如海岸上腐烂的物质,因此它们在海岸清洁中扮演着一个非常重要的角色。作为杂食动物,它们的食物是极其多样化的,从虫子到有机废品(例如草和叶子)无所不有。
封面的图片来自于Johnson的《Library of Natural History》卷2。