计算机 类型
可以朗读 语音朗读
112千字 字数
2023-06-01 发行日期
展开全部

主编推荐语

一本囊括基本算法知识的详解指南，详细讲解算法理念，展现算法本质。

内容简介

本书是《算法详解》系列第三卷——贪心算法和动态规划。其中贪心算法主要包括调度、最小生成树、聚类、哈夫曼编码等，动态规划主要包括背包、序列对齐、最短路径、最佳搜索树等。

本书的每一章均有小测验和章末习题，这将为读者的自我检查以及进一步学习提供方便。本书作者提供丰富而实用的资源，能够帮助读者提升算法思维能力。

目录

  • 版权信息
  • 内容提要
  • 前言
  • 服务与支持
  • 第1章 贪心算法概述
  • 1.1 贪心算法设计范例
  • 1.1.1 算法设计范例
  • 1.1.2 贪心算法设计范例的特性
  • 1.2 一个调度问题
  • 1.2.1 问题的设定
  • 1.2.2 竞争时间
  • 1.2.3 目标函数
  • 1.2.4 小测验1.1的答案
  • 1.3 开发一种贪心算法
  • 1.3.1 两种特殊情况
  • 1.3.2 贪心算法之间的竞争
  • 1.3.3 小测验1.2～1.3的答案
  • 1.4 正确性证明
  • 1.4.1 没有平局时的情况：高层计划
  • 1.4.2 在相邻逆序对中交换作业
  • 1.4.3 成本收益分析
  • 1.4.4 处理平局的情况
  • 1.4.5 小测验1.4～1.5的答案
  • 1.5 本章要点
  • 1.6 章末习题
  • 编程题
  • 第2章 哈夫曼编码
  • 2.1 编码
  • 2.1.1 固定长度的二进制编码
  • 2.1.2 可变长度的编码
  • 2.1.3 非前缀编码
  • 2.1.4 非前缀编码的优点
  • 2.1.5 问题定义
  • 2.1.6 小测验2.1～2.2的答案
  • 2.2 编码和树
  • 2.2.1 3个例子
  • 2.2.2 什么样的树表示非前缀编码
  • 2.2.3 问题定义（精练版）
  • 2.3 哈夫曼的贪心算法
  • 2.3.1 通过连续的归并创建树
  • 2.3.2 哈夫曼的贪心准则
  • 2.3.3 伪码
  • 2.3.4 例子
  • 2.3.5 一个更复杂的例子
  • 2.3.6 运行时间
  • 2.3.7 小测验2.3的答案
  • *2.4 正确性证明
  • 2.4.1 高层计划
  • 2.4.2 细节
  • 2.5 本章要点
  • 2.6 章末习题
  • 挑战题
  • 编程题
  • 第3章 最小生成树
  • 3.1 问题定义
  • 3.1.1 图
  • 3.1.2 生成树
  • 3.1.3 小测验3.1的答案
  • 3.2 Prim算法
  • 3.2.1 例子
  • 3.2.2 伪码
  • 3.2.3 简单的实现
  • *3.3 通过堆提升Prim算法的速度
  • 3.3.1 探求接近线性的运行时间
  • 3.3.2 堆数据结构
  • 3.3.3 如何在Prim算法中使用堆
  • 3.3.4 基于堆的实现的伪码
  • 3.3.5 运行时间分析
  • 3.3.6 小测验3.3的答案
  • *3.4 Prim算法：正确性证明
  • 3.4.1 最小瓶颈属性
  • 3.4.2 生成树的一些有趣结论
  • 3.4.3 定理3.4（MBP意味着MST）的证明
  • 3.4.4 综合运用
  • 3.5 Kruskal算法
  • 3.5.1 例子
  • 3.5.2 Kruskal算法的伪码
  • 3.5.3 Kruskal算法的简单实现
  • *3.6 通过合并查找对Kruskal算法进行加速
  • 3.6.1 合并查找数据结构
  • 3.6.2 基于合并查找的实现的伪码
  • 3.6.3 基于合并查找的实现的运行时间分析
  • 3.6.4 合并查找的快速有余而严谨不足的实现：父图
  • 3.6.5 小测验3.5～3.7的答案
  • *3.7 Kruskal算法的正确性证明
  • 3.8 应用：单链集群
  • 3.8.1 集群
  • 3.8.2 自底向上的集群
  • 3.9 本章要点
  • 3.10 章末习题
  • 挑战题
  • 编程题
  • 第4章 动态规划概述
  • 4.1 加权独立集合问题
  • 4.1.1 问题定义
  • 4.1.2 自然的贪心算法失败了
  • 4.1.3 分治算法可行吗
  • 4.1.4 小测验4.1～4.2的答案
  • 4.2 路径图的WIS问题的线性时间算法
  • 4.2.1 最优子结构和推导公式
  • 4.2.2 一种不成熟的递归方法
  • 4.2.3 使用缓存的递归算法
  • 4.2.4 一种迭代式的自底向上的实现
  • 4.2.5 小测验4.3～4.4的答案
  • 4.3 一种重建算法
  • 4.4 动态规划的原则
  • 4.4.1 3个步骤的配方
  • 4.4.2 子问题的期望属性
  • 4.4.3 一个可重复的思维过程
  • 4.4.4 动态规划和分治算法的区别
  • 4.4.5 为什么叫“动态规划”
  • 4.5 背包问题
  • 4.5.1 问题定义
  • 4.5.2 最优子结构和推导公式
  • 4.5.3 子问题
  • 4.5.4 一种动态规划算法
  • 4.5.5 例子
  • 4.5.6 重建
  • 4.5.7 小测验4.5～4.6的答案
  • 4.6 本章要点
  • 4.7 章末习题
  • 挑战题
  • 编程题
  • 第5章 高级动态规划
  • 5.1 序列对齐
  • 5.1.1 驱动力
  • 5.1.2 问题定义
  • 5.1.3 最优子结构
  • 5.1.4 推导公式
  • 5.1.5 子问题
  • 5.1.6 一种动态规划算法
  • 5.1.7 重新构建
  • 5.1.8 小测验5.1～5.3的答案
  • *5.2 最优二叉搜索树
  • 5.2.1 二叉搜索树回顾
  • 5.2.2 平均搜索时间
  • 5.2.3 问题定义
  • 5.2.4 最优子结构
  • 5.2.5 推导公式
  • 5.2.6 子问题
  • 5.2.7 一种动态规划算法
  • 5.2.8 改善运行时间
  • 5.2.9 小测验5.4～5.5的答案
  • 5.3 本章要点
  • 5.4 章末习题
  • 挑战题
  • 编程题
  • 第6章 再论最短路径算法
  • 6.1 边长可能为负的最短路径
  • 6.1.1 单源最短路径问题
  • 6.1.2 负环
  • 6.1.3 小测验6.1的答案
  • 6.2 Bellman-Ford算法
  • 6.2.1 子问题
  • 6.2.2 最优子结构
  • 6.2.3 推导公式
  • 6.2.4 什么时候应该停止
  • 6.2.5 伪码
  • 6.2.6 Bellman-Ford算法的例子
  • 6.2.7 Bellman-Ford算法的运行时间
  • 6.2.8 Internet路由
  • 6.2.9 小测验6.2～6.3的答案
  • 6.3 所有顶点对的最短路径问题
  • 6.3.1 问题定义
  • 6.3.2 简化为单源最短路径
  • 6.3.3 小测验6.4的答案
  • 6.4 Floyd-Warshall算法
  • 6.4.1 子问题
  • 6.4.2 最优子结构
  • 6.4.3 伪码
  • 6.4.4 检测负环
  • 6.4.5 Floyd-Warshall算法的总结和开放性问题
  • 6.4.6 小测验6.5～6.6的答案
  • 6.5 本章要点
  • 6.6 章末习题
  • 挑战题
  • 编程题
  • 附录 章末习题答案节选
  • 后记 算法设计工作指南
展开全部

评分及书评

尚无评分
目前还没人评分

出版方

人民邮电出版社

人民邮电出版社是工业和信息化部主管的大型专业出版社，成立于1953年10月1日。人民邮电出版社坚持“立足信息产业、面向现代社会、传播科学知识、服务科教兴国”，致力于通信、计算机、电子技术、教材、少儿、经管、摄影、集邮、旅游、心理学等领域的专业图书出版。