算法概论

出版时间：2008-7  出版社：清华大学出版社  作者：Sanjoy Dasgupta,Christos Papadimitriou,Umesh Vazirani  页数：345  译者：王沛,唐扬斌,刘齐军  
Tag标签：无  

内容概要

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

作者简介

　　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 密钥机制：一次一密乱码本和AES1.4.2 RSA1.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 TSP9.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 因子分解的量子算法习题历史背景及深入阅读的资

章节摘录

　　序言　　如果你环视左右，就会发现电脑与网络在生活中无处不在，它们织就了一张复杂的网，人类的各种活动都蕴含其中：教育、商业、娱乐、研究、制造、医疗管理、人际交往，甚至包括战争。如今有两项技术可以用日新月异这个词来形容，其中之一就是硬件速度的飞速提升，这得益于微电子业和芯片制造业惊人的发展速度。

编辑推荐

　　作为一本介绍算法技术和思想的书籍，本书不仅是面各信息学科大学生的优秀教材（或参考书），更是将任何具有初等数学基础的人引入算法应用与研究殿堂的一块引路石。本书循序渐进、深入浅出地展示了算法研究与应用领域中，从模型分析、算法构造到复杂性分析和算法优化的方方面面。涉及内容从古老的算术算法、排序算法、简单算法、线性规划、动态规划、随机算法以及NP复杂理论，甚至是尚未完全显现全貌的量子计算，覆盖了经典、现代和未来算法发展的众多代表性成果。　　本书选材新颖，内容丰富，适用于作为计算机学科以及相关学科算法课程的教材和参考书，同时也可作从事算法研究的入门书籍。　　本书主要内容　　分治算法，图的分解与图中的路径，贪心算法，线性规划归约，NP—完全问题，量子算法。　　实践指南清晰，内容深入广泛，实例学以致用。

用户评论 (总计6条)

•   帮同事买的，很好，到货快
•   质量好 发货快 书不错
•   读书的教材
•   哈哈，上课要买的=
•   给参加信息学奥赛的孩子买的书他很喜欢
•   和英文版做比对