编辑推荐
（1）由算法领域的知名专家Steven Skiena教授编写。
（2）“设计”是本书的核心，作者不但以生动有趣的语言讲授了算法设计中的常用技术与思想，还着重教导我们应从已有经典设计和实现中汲取力量来完成问题求解，而这正是一个优秀算法工作者所必备的素养。
（3）为了更全面真实地展现作者的算法设计观，本书每章都给出了若干取自现实案例的精彩War Story，读者可以从中深刻体验到优秀算法设计的曲折历程。
（4）本书配套网站包含大量算法设计资源以及作者本人的授课视频，为算法设计者提供了极大的便利。
（5）本书英文版长期占据算法设计领域畅销书的销售前列，是一本不可多得的“算法设计指南”，它不仅能作为计算机相关专业算法课程的教材，对于相关领域从业人员亦是极具价值的参考书。
作者简介
作者：（德国）斯蒂文·斯金纳（Steven S.Skiena） 译者：谢勰
目录
卷Ⅰ实用算法设计
第1章算法设计导引
1.1机器人巡游优化
1.2合理挑选工作
1.3关于正确性的推理
1.4建立问题的模型
1.5关于War Story
1.6War Story：通灵者的模型建立
1.7习题
第2章算法分析
2.1RAM计算模型
2.2大O记号
2.3增长量级与强弱关系
2.4以大O来推演公式
2.5关于效率的推理
2.6对数及其应用
2.7对数的特性
2.8War Story：锥体之秘
2.9高等分析（*）
2.10习题
第3章数据结构
3.1紧接数据结构与链接数据结构
3.2栈与队列
3.3字典
3.4二叉查找树
3.5优先级队列
3.6War Story：剥离三角剖分
3.7散列与字符串
3.8专用数据结构
3.9War Story：把它们串起来
3.10习题
第4章排序与查找
4.1排序的应用
4.2排序的范式，
4.3堆排序：借助数据结构而得的最优排序
4.4War Story：给我一张机票
4.5归并排序：通过分治来排序
4.6快速排序：通过随机化来排序
4.7分配排序：通过装桶来排序
4.8War Story：为被告辩护的Skiena
4.9二分查找及相关算法
4.10分治
4.11习题
第5章图的遍历
5.1图的风格
5.2用于图的数据结构
5.3War Story：我曾是摩尔定律的受害者
5.4War Story：图的获取
5.5遍历图
5.6广度优先搜索
5.7广度优先搜索的应用
5，8深度优先搜索
5.9深度优先搜索的应用
5.10有向图的深度优先搜索
5.11习题
第6章加权图算法
6.1最小生成树
6.2War Story：网络之外别无他求
6.3最短路径
6.4War Story：拨出文档
6.5网络流和二部匹配
6.6去设计图，而非算法
6.7习题
第7章组合搜索与启发式方法
7.1回溯
7.2搜索剪枝法
7.3数独
7.4War Story：覆盖棋盘
7.5启发式搜索方法
7.6只不过它不是收音机而已
7.7对阵列退火
7.8其他启发式搜索方法
7.9并行算法
7.10War Story：毫无进展
7.11习题
第8章动态规划
8.1缓存与计算
8.2字符串近似匹配
8.3最长递增子序列
8.4War Story：龙虾的进化
8.5划分问题
8.6对上下文无关的语言做语法分析
8.7动态规划的局限性：TSP
8.8War Story：过去所发生的事就是Prolog
8.9War Story：条码的文本压缩
8.10习题
第9章难解问题和近似算法
9.1问题和归约
9.2算法的归约
9.3基础性的难解性归约
9.4可满足性
9.5创造性的归约
9.6难解性证明的艺术
9.7War Story：争分夺秒亦难
9.8War Story：后来我失败了
9.9P与NP
9.10NP完全问题的处理
9.11习题
第10章如何设计算法
参考文献
序言
我遇到的大多数专业程序员都不太愿意去解决算法设计问题. 这点很遗憾, 因为算法
设计已成长为计算机科学的核心实用技术之一. 若想设计出正确、高效和易于实现的算法
去求解真实世界的问题, 需要了解两种不同的知识体系:
? 技术——优秀的算法设计师懂好几种基本算法设计技术, 包括数据结构、动态规
划、深度优先搜索、回溯以及启发式方法. 也许最最重要的设计技术应该就是建模
了, 它能将杂乱现实世界中的应用问题提炼精化以便于用算法攻破, 这可称得上是
门艺术.
? 资源——优秀的算法设计师都站在巨人的肩膀上. 他们不是每次都从一张白纸开始
费尽心思最后创造出新算法来解决问题, 他们会先弄清楚这个问题目前的研究现
状. 他们不是从零开始重新实现那些广为流传的算法, 他们会去寻找现有的程序实
现并以此作为起点. 他们对许多经典算法问题都非常熟悉, 这些问题为大多数应用
问题的建模提供了充足的素材.
本书意在作为算法设计的一本指南, 从而让学生和计算机从业人员能走进组合算法技
术的殿堂. 全书分为两卷: 技术和资源. 前者是对计算机算法设计和分析技术的一般性指引.
后者则可让你进行查阅和参考, 它是由多条简介构成的算法问题便览,1 其中每一条都包含
了算法资料、程序实现以及大量的参考书目.
文摘
第1章
算法设计导引
何谓算法? 算法是完成某项特定任务的具体步骤. 算法更是藏于程序背后的思想, 当然
这个程序本身至少要过得去才能谈及思想.
一个算法想要让人关注, 它一定要能解决一个有着清楚而且准确叙述的一般性问
题(problem). 要想精确地表述清楚一个算法问题, 我们得描述该算法问题所要处理算
例(instance)1的完备集合, 以及处理完任意一个算例之后所想要得到的输出. 分清一个问题
和问题的一个算例, 这点极其重要. 例如排序这个算法问题2可按如下方式来定义:
问题: 排序
输入: 一个由n个键(key)组成的序列a1, . . . , an.
输出: 输入序列的置换(即重新安排)a′
1, . . . , a′
n, 它满足a′
1 6 a′
2 6 · · · 6 a′
n.
排序的算例可以是存储姓名的一个数组, 例如{Mike, Bob, Sally, Jill, Jan}, 也可以是
存储数字的一个列表, 例如{154, 245, 568, 324, 654, 324}. 先搞清楚你是不是在处理一个一
般性的问题, 这才是你通向最终解决它的第一步.
接收满足问题要求的输入算例, 再将其转换成我们想要的输出, 算法(algorithm)就是
完成上述任务的具体步骤. 有许多不同的算法能求解排序问题. 例如插入排序(insertion
sorting)就是一种排序的方法, 它一开始会从序列中取出一个元素(从而形成一个平凡的有
序列表), 然后再将序列中余下元素按输入次序逐个插入到列表中, 并保证插入后列表仍然
有序. 以C实现的插入排序算法描述如下:
void insertion_sort(item s[], int n)
{
int i, j; /* 计数器*/
for (i = 1; i0) && (s[j] < s[j - 1])){
swap(&s[j], &s[j - 1]);
j = j - 1;
}
}
}
（1）由算法领域的知名专家Steven Skiena教授编写。
（2）“设计”是本书的核心，作者不但以生动有趣的语言讲授了算法设计中的常用技术与思想，还着重教导我们应从已有经典设计和实现中汲取力量来完成问题求解，而这正是一个优秀算法工作者所必备的素养。
（3）为了更全面真实地展现作者的算法设计观，本书每章都给出了若干取自现实案例的精彩War Story，读者可以从中深刻体验到优秀算法设计的曲折历程。
（4）本书配套网站包含大量算法设计资源以及作者本人的授课视频，为算法设计者提供了极大的便利。
（5）本书英文版长期占据算法设计领域畅销书的销售前列，是一本不可多得的“算法设计指南”，它不仅能作为计算机相关专业算法课程的教材，对于相关领域从业人员亦是极具价值的参考书。
作者简介
作者：（德国）斯蒂文·斯金纳（Steven S.Skiena） 译者：谢勰
目录
卷Ⅰ实用算法设计
第1章算法设计导引
1.1机器人巡游优化
1.2合理挑选工作
1.3关于正确性的推理
1.4建立问题的模型
1.5关于War Story
1.6War Story：通灵者的模型建立
1.7习题
第2章算法分析
2.1RAM计算模型
2.2大O记号
2.3增长量级与强弱关系
2.4以大O来推演公式
2.5关于效率的推理
2.6对数及其应用
2.7对数的特性
2.8War Story：锥体之秘
2.9高等分析（*）
2.10习题
第3章数据结构
3.1紧接数据结构与链接数据结构
3.2栈与队列
3.3字典
3.4二叉查找树
3.5优先级队列
3.6War Story：剥离三角剖分
3.7散列与字符串
3.8专用数据结构
3.9War Story：把它们串起来
3.10习题
第4章排序与查找
4.1排序的应用
4.2排序的范式，
4.3堆排序：借助数据结构而得的最优排序
4.4War Story：给我一张机票
4.5归并排序：通过分治来排序
4.6快速排序：通过随机化来排序
4.7分配排序：通过装桶来排序
4.8War Story：为被告辩护的Skiena
4.9二分查找及相关算法
4.10分治
4.11习题
第5章图的遍历
5.1图的风格
5.2用于图的数据结构
5.3War Story：我曾是摩尔定律的受害者
5.4War Story：图的获取
5.5遍历图
5.6广度优先搜索
5.7广度优先搜索的应用
5，8深度优先搜索
5.9深度优先搜索的应用
5.10有向图的深度优先搜索
5.11习题
第6章加权图算法
6.1最小生成树
6.2War Story：网络之外别无他求
6.3最短路径
6.4War Story：拨出文档
6.5网络流和二部匹配
6.6去设计图，而非算法
6.7习题
第7章组合搜索与启发式方法
7.1回溯
7.2搜索剪枝法
7.3数独
7.4War Story：覆盖棋盘
7.5启发式搜索方法
7.6只不过它不是收音机而已
7.7对阵列退火
7.8其他启发式搜索方法
7.9并行算法
7.10War Story：毫无进展
7.11习题
第8章动态规划
8.1缓存与计算
8.2字符串近似匹配
8.3最长递增子序列
8.4War Story：龙虾的进化
8.5划分问题
8.6对上下文无关的语言做语法分析
8.7动态规划的局限性：TSP
8.8War Story：过去所发生的事就是Prolog
8.9War Story：条码的文本压缩
8.10习题
第9章难解问题和近似算法
9.1问题和归约
9.2算法的归约
9.3基础性的难解性归约
9.4可满足性
9.5创造性的归约
9.6难解性证明的艺术
9.7War Story：争分夺秒亦难
9.8War Story：后来我失败了
9.9P与NP
9.10NP完全问题的处理
9.11习题
第10章如何设计算法
参考文献
序言
我遇到的大多数专业程序员都不太愿意去解决算法设计问题. 这点很遗憾, 因为算法
设计已成长为计算机科学的核心实用技术之一. 若想设计出正确、高效和易于实现的算法
去求解真实世界的问题, 需要了解两种不同的知识体系:
? 技术——优秀的算法设计师懂好几种基本算法设计技术, 包括数据结构、动态规
划、深度优先搜索、回溯以及启发式方法. 也许最最重要的设计技术应该就是建模
了, 它能将杂乱现实世界中的应用问题提炼精化以便于用算法攻破, 这可称得上是
门艺术.
? 资源——优秀的算法设计师都站在巨人的肩膀上. 他们不是每次都从一张白纸开始
费尽心思最后创造出新算法来解决问题, 他们会先弄清楚这个问题目前的研究现
状. 他们不是从零开始重新实现那些广为流传的算法, 他们会去寻找现有的程序实
现并以此作为起点. 他们对许多经典算法问题都非常熟悉, 这些问题为大多数应用
问题的建模提供了充足的素材.
本书意在作为算法设计的一本指南, 从而让学生和计算机从业人员能走进组合算法技
术的殿堂. 全书分为两卷: 技术和资源. 前者是对计算机算法设计和分析技术的一般性指引.
后者则可让你进行查阅和参考, 它是由多条简介构成的算法问题便览,1 其中每一条都包含
了算法资料、程序实现以及大量的参考书目.
文摘
第1章
算法设计导引
何谓算法? 算法是完成某项特定任务的具体步骤. 算法更是藏于程序背后的思想, 当然
这个程序本身至少要过得去才能谈及思想.
一个算法想要让人关注, 它一定要能解决一个有着清楚而且准确叙述的一般性问
题(problem). 要想精确地表述清楚一个算法问题, 我们得描述该算法问题所要处理算
例(instance)1的完备集合, 以及处理完任意一个算例之后所想要得到的输出. 分清一个问题
和问题的一个算例, 这点极其重要. 例如排序这个算法问题2可按如下方式来定义:
问题: 排序
输入: 一个由n个键(key)组成的序列a1, . . . , an.
输出: 输入序列的置换(即重新安排)a′
1, . . . , a′
n, 它满足a′
1 6 a′
2 6 · · · 6 a′
n.
排序的算例可以是存储姓名的一个数组, 例如{Mike, Bob, Sally, Jill, Jan}, 也可以是
存储数字的一个列表, 例如{154, 245, 568, 324, 654, 324}. 先搞清楚你是不是在处理一个一
般性的问题, 这才是你通向最终解决它的第一步.
接收满足问题要求的输入算例, 再将其转换成我们想要的输出, 算法(algorithm)就是
完成上述任务的具体步骤. 有许多不同的算法能求解排序问题. 例如插入排序(insertion
sorting)就是一种排序的方法, 它一开始会从序列中取出一个元素(从而形成一个平凡的有
序列表), 然后再将序列中余下元素按输入次序逐个插入到列表中, 并保证插入后列表仍然
有序. 以C实现的插入排序算法描述如下:
void insertion_sort(item s[], int n)
{
int i, j; /* 计数器*/
for (i = 1; i0) && (s[j] < s[j - 1])){
swap(&s[j], &s[j - 1]);
j = j - 1;
}
}
}
| ISBN | 9787302457343 |
|---|---|
| 出版社 | 清华大学出版社 |
| 作者 | 斯蒂文·斯金纳 (Steven S.Skiena) |
| 尺寸 | 16 |