[
-
内容大纲
本书主要介绍经典的算法设计技术，包括递归与分治策略、动态规划法、贪心算法、回溯法、分支限界法、概率算法等。在算法分析方面，介绍了二分搜索技术、大整数的乘法、Strassen矩阵乘法、棋盘覆盖、合并排序、快速排序、循环赛日程表、矩阵连乘问题、最长公共子序列、凸多边形最优三角剖分、多边形游戏、图像压缩、活动安排问题、最优装载、哈夫曼编码、最小生成树问题、套利问题、n皇后问题、图的m着色问题、15谜问题、单源最短路径问题、旅行商问题等，并对有的问题进行算法优化设计。书中主要突出对问题本身的分析和求解方法，并进行了问题的计算复杂性分析。本书每章均精选了一些基础的算法习题，针对各章节不同的算法设计技术设计了多个上机实验，并提供多套自测试卷，有助于学生了解自己对学习内容的掌握程度，自测学习效果。
本书可作为大学计算机科学与技术、软件工程等专业本科生的教学用书，也可作为从事实际问题求解的算法设计与分析工作人员的参考书。 -
作者介绍
-
目录
第1章 算法概述
1.1 什么是算法
1.2 算法复杂性
1.3 算法复杂性计量
1.4 算法复杂性的表示
1.4.1 算法复杂性的渐近性态
1.4.2 复杂性渐近阶
1.4.3 5个渐近意义下的记号
1.4.4 常见的算法时间复杂度
1.5 算法复杂性的重要性
习题1
第2章 递归与分治策略
2.1 递归的概念
2.2 分治法的基本思想
2.3 二分搜索技术
2.3.1 线性查找
2.3.2 二分搜索法
2.3.3 二分搜索算法复杂性最坏情形分析
2.3.4 二分搜索算法复杂性平均情形分析
2.4 大整数的乘法
2.4.1 大整数乘积的分治算法描述
2.4.2 大整数乘积的时间复杂度递推方程
2.5 Strassen矩阵乘法
2.5.1 Strassen矩阵分治乘法
2.5.2 时间复杂度递推方程
2.6 棋盘覆盖问题
2.6.1 问题描述
2.6.2 算法复杂性分析
2.7 合并排序
2.7.1 基于比较的排序时间复杂度下界
2.7.2 用递归树解递归关系式
2.7.3 合并排序
2.8 快速排序
2.8.1 算法描述
2.8.2 时间复杂度分析
2.9 循环赛日程表安排
2.9.1 问题描述
2.9.2 问题的分治法设计思想
2.9.3 分治算法实现
习题2
第3章 动态规划法
3.1 动态规划法概述
3.1.1 最优性原理
3.1.2 动态规划法的基本步骤
3.2 矩阵连乘问题
3.2.1 问题描述
3.2.2 分析最优解的结构
3.2.3 建立递归关系
3.2.4 计算最优值
3.2.5 构造最优解
3.3 动态规划算法的基本要素
3.3.1 最优子结构
3.3.2 重叠子问题
3.3.3 备忘录方法
3.4 最长公共子序列问题
3.4.1 问题描述
3.4.2 最长公共子序列的结构
3.4.3 子问题的递归结构
3.4.4 计算最优值
3.4.5 构造最长公共子序列
3.4.6 算法的改进
3.5 凸多边形的最优三角剖分问题
3.5.1 问题描述
3.5.2 三角剖分的结构及其相关问题
3.5.3 最优子结构性质
3.5.4 最优三角剖分对应的权的递归结构
3.5.5 计算最优值
3.5.6 构造最优三角剖分
3.6 多边形游戏
3.6.1 问题描述
3.6.2 最优子结构性质
3.6.3 递归求解
3.6.4 算法描述
3.7 图像压缩
3.7.1 图像压缩实例
3.7.2 最优子结构性质
3.7.3 递归计算最优值
3.7.4 算法实现
习题3
第4章 贪心算法
4.1 活动安排问题
4.1.1 贪心算法设计的特点
4.1.2 问题描述
4.1.3 活动安排问题的贪心算法
4.2 贪心算法的基本要素
4.2.1 贪心选择性质
4.2.2 最优子结构性质
4.2.3 贪心算法的求解过程
4.2.4 贪心算法与动态规划法的差异
4.3 最优装载
4.3.1 问题描述
4.3.2 贪心选择性质
4.3.3 最优子结构性质
4.3.4 算法描述
4.4 最短路径问题
4.4.1 问题描述
4.4.2 算法基本思想
4.4.3 算法实现
4.5 哈夫曼编码
4.5.1 哈夫曼树
4.5.2 构造一棵哈夫曼树
4.5.3 哈夫曼编码
4.5.4 算法分析与设计
4.5.5 哈夫曼算法的正确性
4.6 TSP问题
4.6.1 TSP问题研究进展
4.6.2 最近邻点贪心策略
4.6.3 最短链接贪心策略
4.7 最小生成树
4.7.1 Prim算法（最近顶点策略）
4.7.2 Kruskal算法（最短边策略）
4.8 套利问题
4.8.1 套利问题描述
4.8.2 问题的贪心选择性质
4.8.3 问题的最优子结构性质
4.8.4 算法实例
习题4
第5章 回溯法
5.1 回溯法的算法框架
5.1.1 明确定义问题的解空间
5.1.2 运用回溯法解题的步骤
5.1.3 回溯法的算法框架
5.2 n皇后问题
5.2.1 问题描述
5.2.2 算法设计
5.2.3 算法实现
5.2.4 8皇后问题的不等效解分析与实现
5.3 图的m着色问题
5.3.1 问题描述
5.3.2 算法实现
5.4 回溯法的效率分析
5.4.1 重排原理
5.4.2 估算结点数
5.4.3 回溯法的效率
习题5
第6章 分支限界法
6.1 分支限界法的基本思想
6.2 分支限界法的算法实例
6.2.1 分支限界法解0-1背包问题
6.2.2 分支限界法解旅行商问题
6.2.3 分支限界法解15谜问题
6.3 单源最短路径问题
6.3.1 问题描述
6.3.2 算法分析
6.3.3 分支限界算法实现
6.4 装载问题
6.4.1 队列式分支限界法
6.4.2 算法的改进
6.4.3 构造最优解
6.4.4 最大收益分支限界（优先队列式）
习题6
第7章 概率算法
7.1 随机数
7.2 数值概率算法
7.2.1 用随机投点法计算n值
7.2.2 计算定积分
7.2.3 解非线性方程
7.2.4 解非线性方程组
7.3 蒙特卡罗算法
7.3.1 蒙特卡罗算法的基本思想
7.3.2 蒙特卡罗算法的简单应用
7.3.3 主元素问题
7.3.4 素数测试
7.4 拉斯维加斯算法
7.4.1 n皇后问题
7.4.2 整数因子分解
7.5 舍伍德算法
7.5.1 线性时间选择算法
7.5.2 跳跃表
习题7
第8章 实验指导
实验1 分治法上机实验
实验1-1 棋盘覆盖问题的分治法设计
实验1-2 利用分治法实现合并排序
实验1-3 用分治法实现快速排序算法
实验1-4 循环赛日程表安排问题的分治法设计
实验1-5 最大子段和问题的分治法设计
实验2 动态规划法上机实验
实验2-1 矩阵连乘问题的动态规划法设计
实验2-2 最长公共子序列的动态规划法设计
实验2-3 图像压缩问题的动态规划法设计
实验3 贪心算法上机实验
实验3-1 找硬币问题的贪心算法设计
实验3-2 活动安排问题的贪心算法
实验3-3 单源最短路径问题的贪心算法设计
实验4 回溯法上机实验
实验4-1 8皇后问题的回溯法设计
实验4-2 图的着色问题的回溯法设计
第9章 算法自测卷
9.1 算法自测卷1
9.2 算法自测卷2
9.3 算法自测卷3
附录 习题参考答案
习题1参考答案
习题2参考答案
习题3参考答案
习题4参考答案
习题5参考答案
习题6参考答案
习题7参考答案
算法自测卷1参考答案
算法自测卷2参考答案
算法自测卷3参考答案
同类热销排行榜
- C语言与程序设计教程(高等学校计算机类十二五规划教材)16
- 电机与拖动基础(教育部高等学校自动化专业教学指导分委员会规划工程应用型自动化专业系列教材)13.48
- 传感器与检测技术(第2版高职高专电子信息类系列教材)13.6
- ASP.NET项目开发实战(高职高专计算机项目任务驱动模式教材)15.2
- Access数据库实用教程(第2版十二五职业教育国家规划教材)14.72
- 信号与系统(第3版下普通高等教育九五国家级重点教材)15.08
- 电气控制与PLC(普通高等教育十二五电气信息类规划教材)17.2
- 数字电子技术基础(第2版)17.36
- VB程序设计及应用(第3版十二五职业教育国家规划教材)14.32
- Java Web从入门到精通(附光盘)/软件开发视频大讲堂27.92
推荐书目
-
孩子你慢慢来/人生三书 华人世界率性犀利的一枝笔，龙应台独家授权《孩子你慢慢来》20周年经典新版。她的《...
-
时间简史(插图版) 相对论、黑洞、弯曲空间……这些词给我们的感觉是艰深、晦涩、难以理解而且与我们的...
-
本质(精) 改革开放40年，恰如一部四部曲的年代大戏。技术突变、产品迭代、产业升级、资本对接...