算法概论

出版者:清华大学出版社

作者:Sanjoy Dasgupta

页数:345

译者:王沛

出版时间:2008-7

价格:39.99元

装帧:平装

isbn号码:9787302179399

丛书系列:国外经典教材·计算机科学与技术

具体描述

《国外经典教材·算法概论》涵盖了绝大多数算法设计中的常用技术。在表达每一种技术时，阐述它的应用背景，强调每个算法运转背后的简洁数学思想，注意运用与其他技术类比的方法来说明它的特征，并提供了大量相应实际问题的例子。《国外经典教材·算法概论》同时也注重了对每一种算法的复杂性分析。全书共10章，从基本的数字算法人手，先后介绍了分治、图的遍历、贪心算法、动态规划、线性规划等技术，对NP完全问题进行厂基本而清晰的阐述，对随机算法、近似算法和量子算法这些近年来发展迅猛的领域也花费了一定的笔墨。书中每章后面都附有大量的习题，有利于读者对书中内容的理解和应用。

作者简介

王沛，男，国防科学技术大学管理科学与工程专业博士，自攻读硕士起一直从事智能优化算法领域的研究，已在该领域发表论文6篇，其中英文论文3篇。

Sanjoy Dasgupta于2002年在加州大学伯克利分校获得计算机科学专业的博士学位。他是AT&T实验室的高级技术人员。他的工作重点是研究数据挖掘的算法，对业务数据的语音识别和分析的应用。他在多维数据的统计分析的开发算法领域获得很重要的研究成果。

目录信息

第0章 序言
0.1 书籍和算法
0.2 从Fibonacci数列开始
0.3 大O符号
习题
第1章 数字的算法
1.1 基本算术
1.1.1 加法
1.1.2 乘法和除法
1.2 模运算
1.2.1 模的加法和乘法
1.2.2 模的指数运算
1.2.3 Euclid的最大公因数算法
1.2.4 Euclid算法的一种扩展
1.2.5 模的除法
1.3 素性测试
1.4 密码学
1.4.1 密钥机制：一次一密乱码本和AES
1.4.2 RSA
1.5 通用散列表
1.5.1 散列表
1.5.2 散列函数族
习题
第2章 分治算法
2.1 乘法
2.2 递推式
2.3 合并排序
2.4 寻找中项
2.5 矩阵乘法
2.6 快速Fourier变换
2.6.1 多项式的另一种表示法
2.6.2 计算步骤的分治实现
2.6.3 插值
2.6.4 快速Fourier变换的细节
习题
第3章 图的分解
3.1 为什么是图
3.2 无向图的深度优先搜索
3.2.1 迷宫探索
3.2.2 深度优先搜索
3.2.3 无向图的连通性
3.2.4 前序和后序
3.3 有向图的深度优先搜索
3.3.1 边的类型
3.3.2 有向无环图
3.4 强连通部件
3.4.1 定义有向图的连通性
3.4.2 一个有效的算法
习题
第4章 图中的路径
4.1 距离
4.2 广度优先搜索
4.3 边的长度
4.4 Dijkstra算法
4.4.1 广度优先搜索的一个改进
4.4.2 另一种解释
4.4.3 运行时间
4.5 优先队列的实现
4.5.1 数组
4.5.2 二分堆
4.5.3 d堆
4.6 含有负边的图的最短路径
4.6.1 负边
4.6.2 负环
4.7 有向无环图中的最短路径
习题
第5章 贪心算法
5.1 最小生成树
5.1.1 一个贪心方法
5.1.2 分割性质
5.1.3 Kruskal算法
5.1.4 一种用于分离集的数据结构
5.1.5 Prim算法
5.2 Huffman编码
5.3 Horn公式
5.4 集合覆盖
习题
第6章 动态规划
6.1 重新审视有向无环图的最短路径问题
6.2 最长递增子序列
6.3 编辑距离
6.4 背包问题
6.5 矩阵链式相乘
6.6 最短路径问题
6.7 树中的独立集
习题
第7章 线性规划与归约
7.1 线性规划简介
7.1.1 示例：利润最大化
7.1.2 示例：生产计划
7.1.3 示例：最优带宽分配
7.1.4 线性规划的变体
7.2 网络流
7.2.1 石油运输
7.2.2 最大流
7.2.3 对算法的深入观察
7.2.4 最优性的保证
7.2.5 算法的效率
7.3 二部图的匹配
7.4 对偶
7.5 零和博弈(游戏)
7.6 单纯形算法
7.6.1 n维空间中的顶点和邻居
7.6.2 算法
7.6.3 补遗
7.6.4 单纯形法的运行时间
7.7 后记：电路值1
习题
第8章 NP-完全问题
8.1 搜索问题
8.2 NP-完全问题
8.3 所有的归约
习题
第9章 NP-完全问题的处理
9.1 智能穷举搜索
9.1.1 回溯
9.1.2 分支定界
9.2 近似算法
9.2.1 顶点覆盖
9.2.2 聚类
9.2.3 TSP
9.2.4 背包问题
9.2.5 逼近的层次
9.3 局部搜索中的启发方法
9.3.1 重新审视旅行商问题
9.3.2 图划分
9.3.3 处理局部最优
习题
第10章 量子算法
10.1 量子位元、叠加状态和度量
10.2 算法设计
10.3 量子傅立叶变换
10.4 周期性
10.5 量子电路
10.5.1 基本量子门
10.5.2 量子电路的两种基本类型
10.5.3 量子傅立叶变换电路
10.6 将因子分解问题转化为周期求解问题
10.7 因子分解的量子算法
习题
历史背景及深入阅读的资料
· · · · · · (收起)

读后感

刚开始看了一点，还不好评论，但是没答案实在太痛苦了！作为一本典型的教材，还有很多内容放在了习题部分，但是习题答案在网上流传只有一个网友做出来的版本，自己想的话好多题想不明白。google 百度都没找到正式答案。还有这本书比较简练，初学者还是看厚重一点的书比较好。 ...  

Chapter 7 中很多 Figure 中都出先了很低级的印刷错误。 举个例子： Figure 7.13 中，max 2x_1 + 5x_2 在影印版中变成了 a x2 x_1 + 5x_2 （下划线表示下标）。其他好几处都出现了类似的错误。 这种错误让人看的很莫名。。。 另外注释里也有些错误，如果看的时候觉得奇怪就...  

我手头上有一本英文版，读了几章，感觉读到的并不是我这样一个急需在自己的大脑中填塞进一些东西的人，书中可能是借一些算法作为例子来阐述算法思想，但是我始终认为一些思想思路的东西不是看会的，是要完全从自己脑子里搭建起来的才会有用，每个人都有不同的思维习惯和思维模...  

第一次写书评献给算法了，也不亏。 这本书用于美国CS专业大二/大三学生的算法课，必修课，跟数据结构啊操统啊一起。研究生算法课有时候不用教材了，老师带着讨论一下那么上课。 Dasgupta在课上说他当年算法学得很差，没想到后来当了教授。 对，这本书就是没答案，因为习题在课...  

前印度卡塔邦政府信息技术部部长也叫Sanjoy Dasgupta，看来搞IT名字很重要！爹妈给取个像Sanjoy Dasgupta这样的好名字，是搞学术有学术，搞经济有经济啊！

用户评价

这本《算法概论》绝对是计算机科学领域的一本“镇山之宝”，光是看到厚度就让人心里踏实了不少。我刚开始接触算法设计的时候，感觉就像在迷宫里乱撞，各种复杂的数学公式和抽象的概念把我绕得七荤八素。但是，这本书的叙述方式却有一种奇特的魔力，它不像某些教科书那样干巴巴地堆砌定义，而是非常注重“为什么”和“怎么做”。比如，在讲解图论算法时，作者并没有直接抛出Kruskal或Prim的伪代码，而是先用一个非常贴近现实的例子——比如规划城市的光纤网络铺设——将问题背景铺陈开来，让你真切地感受到为什么需要高效的最小生成树算法。然后，它才优雅地引入算法的构建过程，每一步的逻辑推导都像是在雕刻一件艺术品，清晰、有力，且充满美感。更让我赞叹的是，它对时间复杂度和空间复杂度的分析极其到位，不是简单地给出一个$O(n^2)$就算完事，而是会详细剖析在不同输入规模下，算法性能会发生怎样的质变，这对于我们这些需要将理论付诸实践的工程师来说，简直是救命稻草。翻阅这本书的过程，与其说是学习，不如说是一次与顶尖思想的深度对话，它培养的不仅仅是解题的能力，更是那种对问题进行结构化思考的底层逻辑。我把它放在书架最显眼的位置，时不时翻开某一章，总能发现一些新的领悟。

说实话，我拿到这本《算法概论》时，内心是抱着一种“试试看”的心态的。我之前读过好几本号称“入门”的算法书籍，结果往往是开头几章还算友好，一到动态规划或者高级排序算法就开始云里雾里，最终只能放弃。然而，这本书的编排结构简直是为我这种“半吊子”学习者量身定做的。它的梯度设计非常平缓，每一章都会在前一章知识的基础上进行延伸和深化，绝不会出现知识点上的突然断层。举个例子，它在讲解分治策略时，会先用经典的二分查找进行铺垫，然后自然而然地过渡到快速排序，最后再引入归并排序。这种循序渐进的方式，让那些原本令人望而生畏的概念，变得触手可及。作者的文字风格极其平易近人，他似乎非常理解初学者在面对复杂算法时那种焦躁不安的心情，因此在关键的转折点，总会用一些非常生活化的比喻来类比抽象的数学概念，仿佛你身边就坐着一位耐心的导师在为你拨开迷雾。读完一遍基础部分后，我发现我对那些曾经困扰我的“黑箱”算法，都有了一种清晰的、可复现的认知框架，这极大地提升了我在实际项目中使用算法的信心。

这本书的精髓，我个人认为在于它对“算法思维”的培养，而非仅仅是知识点的罗列。很多书籍会告诉你“A算法解决B问题”，但这本书更关注的是“面对一个优化问题时，我们应该从哪些角度去思考最优解的可能性”。它花了相当大的篇幅去探讨那些经典算法背后的设计哲学，比如贪心选择的有效性边界在哪里，动态规划的状态定义和最优子结构是如何确定的。我尤其喜欢它在每一章节末尾设置的“思考题集”，这些题目往往不是简单的套用公式，而是需要你对所学知识进行灵活的组合和创新。我花了整整一个周末的时间去攻克其中一个关于网络流最大匹配的变种问题，虽然过程异常艰辛，但在最终找到那个巧妙的对偶解法时，那种醍醐灌顶的成就感是无与伦比的。这感觉就像是学会了一套新的“武功秘籍”，它赋予了你一套看待和解决问题的全新工具箱。对于希望深入研究算法理论，甚至未来打算从事相关研究工作的读者来说，这本书提供的理论深度和广度，是市面上大多数速成读物无法比拟的。

如果要用一个词来概括我对这本《算法概论》的感受，那一定是“结构化”。很多算法书给人的感觉是零散的知识点堆砌，学完这个章节，下一章又好像是全新的开始。但在这本书里，你会清晰地感受到作者构建了一个宏大的知识体系。他从基础的计算模型入手，逐步引入了数据结构作为算法的载体，然后聚焦于几大类核心问题（排序、搜索、图、动态规划），并始终强调算法的效率分析和正确性证明。这种自顶向下的组织方式，使得学习过程充满了逻辑上的连贯性。我特别欣赏它对“证明”这一环节的重视，它不只是告诉你“这个算法是对的”，而是带着你一步步去验证它的正确性，这在很大程度上提升了我对程序逻辑健壮性的要求。读完这本书，我发现自己写出的代码更少出现边界错误，对算法的适用范围也有了更清晰的界定。它教会我的不仅仅是如何写出能跑的代码，而是如何写出结构合理、理论可靠、能够在任何复杂场景下稳定运行的程序。这本书的价值，在于它为你打下了坚实的理论地基，让你未来的技术探索不再是空中楼阁。

从装帧和排版来看，《算法概论》也展现出一种严谨的学术风范。纸张的质量很好，长时间阅读下来眼睛的疲劳感明显减轻。更重要的是，书中的图示和伪代码部分，设计得异常清晰。在涉及到数据结构的可视化呈现时，比如AVL树的旋转操作，或者B树的节点分裂与合并过程，那些插图往往能瞬间将文字描述的晦涩复杂性转化为直观的几何变化，这对于理解那些涉及大量指针操作和递归过程的算法至关重要。我发现自己过去常常因为看不懂复杂的流程图而放弃，但这本书的插图似乎融入了作者对教学逻辑的深刻理解，它们不仅仅是辅助材料，更是帮助理解算法执行流程的核心线索。此外，作者在引用参考文献和后续拓展阅读方面的推荐也做得非常专业，为那些希望在特定子领域（比如计算几何或概率算法）进行深耕的读者指明了方向。这是一本可以伴随你度过本科、研究生乃至初入职场，并不断从中汲取营养的工具书，它的价值是时间沉淀下来的。

入门级,长进不小.

考试用书，考完可以挖个坑活埋了。有志在算法界有所建树的人，还是看算法导论。没错，就是那本厚的可以当枕头的书。

入门级,长进不小.

考试用书，考完可以挖个坑活埋了。有志在算法界有所建树的人，还是看算法导论。没错，就是那本厚的可以当枕头的书。

语言简炼、思维清晰、论述方式独特而又引人入胜。本书是一本值得细细品味思考的书，不厚的书却有着大量的练习，一定要认真对待习题，本书的习题是延伸你思考的灯塔。对于本书，我个人的评价是这是我看过最好的算法书。