算法设计与分析

图书标准信息

• 作者 李春葆 编
• 出版社 清华大学出版社
• 出版时间 2015-05
• 版次 1
• ISBN 9787302381136
• 定价 39.50元
• 装帧 平装
• 开本 16开
• 纸张 胶版纸
• 页数 321页
• 字数 508千字
• 正文语种 简体中文
• 丛书 高等学校数据结构课程系列教材

【内容简介】

　　《算法设计与分析》系统地介绍了各种常用的算法设计策略，包括穷举法、分治法、贪心法、动态规划法、回溯法、分枝限界法等，并详细讨论了各种图搜索算法和计算几何设计算法。
　　全书既注重原理又注重实践，配有大量图表、上机实验题和练习题，内容丰富，概念讲解清楚，表达严谨，逻辑性强，语言精练，可读性好。
　　《算法设计与分析》既便于教师课堂讲授，又便于自学者阅读。《算法设计与分析》可作为高等院校算法设计与分析课程的教材，也可供ACM和各类程序设计竞赛者参考。

【作者简介】

　　李春葆，武汉大学计算机学院教授，主要研究方向为数据挖掘和算法设计，先后主持和参加多个大型研究项目。主要为本科生讲授数据结构（15年以上）和软件工程等课程，为研究生讲授软件开发新技术、数据仓库与数据挖掘等课程，并出版十多部精品著作。

【目录】

第1章概论
1.1算法的概念
1.1.1什么是算法
1.1.2算法描述
1.1.3算法和数据结构
1.1.4算法设计的基本步骤
1.2算法分析
1.2.1算法时间复杂度分析
1.2.2算法空间复杂度分析
1.3计算复杂性理论简介
1.3.1图灵机模型
1.3.2P类和NP类问题
1.3.3NPC问题
上机实验题1——统计求最大、最小元素的平均比较次数
练习题1

第2章递归算法设计技术
2.1什么是递归
2.1.1递归的定义
2.1.2何时使用递归
2.1.3递归模型
2.1.4递归算法的执行过程
2.2递推式的计算
2.2.1用特征方程求解递归方程
2.2.2用递归树方法求解递归方程
2.3递归算法设计
2.3.1递归与数学归纳法
2.3.2递归算法设计的一般步骤
2.3.3基于递归数据结构的递归算法设计
2.3.4基于归纳思想的递归算法设计
2.4递归算法设计示例
2.4.1简单选择排序和冒泡排序
2.4.2求解n皇后问题
2.4.3求解简单装载问题
2.5递归算法转化为非递归算法
2.5.1用循环结构替代递归过程
2.5.2用栈消除递归过程
上机实验题2——删除二叉树的子树
练习题2

第3章穷举法
3.1穷举法概述
3.2穷举法的基本应用
3.2.1直接采用穷举法的一般格式
3.2.2简单选择排序和冒泡排序
3.2.3求解幂集问题
3.2.4求解0/1背包问题
3.2.5求解全排列问题
3.2.6求解最大连续子序列和问题
3.3递归在穷举法中的应用
3.3.1用递归方法求解幂集问题
3.3.2用递归方法求解全排列问题
3.3.3用递归方法求解组合问题
上机实验题3——钱币兑换问题
练习题3

第4章分治法
4.1分治法概述
4.1.1分治法的设计思想
4.1.2分治法的求解过程
4.2求解排序问题
4.2.1快速排序
4.2.2归并排序
4.3求解查找问题
4.3.1折半查找
4.3.2寻找一个序列中第k小元素
4.3.3寻找两个等长有序序列的中位数
4.4求解最大连续子序列和问题
4.5求解大整数乘法问题
4.6求解矩阵乘法问题
4.7并行计算简介
4.7.1并行计算概述
4.7.2并行计算模型
4.7.3快速排序的并行算法
上机实验题4——求序列的最大元素和次大元素
练习题4

第5章贪心法
5.1贪心法概述
5.1.1什么是贪心法
5.1.2贪心法求解的问题应具有的性质
5.1.3贪心法的一般求解过程
5.2求解区间问题
5.2.1求解区间覆盖问题
5.2.2求解最大不相交区间问题
5.2.3求解活动安排问题
5.3求解背包问题
5.4求解多机调度问题
5.5哈夫曼编码
5.6求解磁盘排序问题
上机实验题5——求解删数问题
练习题5

第6章动态规划
6.1动态规划概述
6.1.1动态规划的原理
6.1.2动态规划求解的基本步骤
6.1.3动态规划与其他方法的比较
6.2求解整数拆分问题
6.3求解最长公共子序列问题
6.4求解0/1背包问题
6.5求解完全背包问题
6.6求解最大连续子序列和问题
6.7求解资源分配问题
上机实验题6——求最长单调递增子序列
练习题6

第7章回溯法
7.1回溯法概述
7.1.1问题的解空间
7.1.2什么是回溯法
7.1.3回溯法的算法框架
7.1.4回溯法算法的时间分析
7.2求解0/1背包问题
7.3求解子集和问题
7.4求解排列和组合问题
7.4.1求解全排列问题
7.4.2求解组合问题
7.5求解迷宫问题
7.5.1采用回溯法递归框架求解迷宫问题
7.5.2采用回溯法非递归框架求解迷宫问题
7.6求解n皇后问题
7.6.1不采用栈求解n皇后问题
7.6.2采用栈求解n皇后问题
上机实验题7——求解装载问题
练习题7

第8章分枝限界法
8.1分枝限界法概述
8.1.1什么是分枝限界法
8.1.2分枝限界法的设计思想
8.1.3分枝限界法的时间性能
8.2求解0/1背包问题
8.2.1采用队列式分枝限界法求解
8.2.2采用优先队列式分枝限界法求解
上机实验题8——求解最优装载问题
练习题8

第9章图搜索算法设计
9.1图的表示
9.1.1图的定义
9.1.2图的存储结构
9.2图的搜索方法
9.2.1图搜索的概念
9.2.2深度优先搜索
9.2.3广度优先搜索
9.3最小生成树
9.3.1最小生成树的概念
9.3.2普里姆算法构造最小生成树
9.3.3克鲁斯卡尔算法
9.4最短路径
9.4.1狄克斯特拉算法
9.4.2贝尔曼·福特算法
9.4.3弗洛伊德算法
9.5利用STL设计算法
9.5.1什么是容器
9.5.2什么是算法
9.5.3什么是迭代器
9.5.4常用STL容器的使用
9.6求解TSP问题
9.6.1TSP问题描述
9.6.2采用穷举法求解TSP问题
9.6.3采用动态规划求解TSP问题
9.6.4采用回溯法求解TSP问题
9.6.5采用分枝限界法求解TSP问题
9.6.6采用贪心法求解TSP问题
9.7求多段图的关键路径
9.8网络流
9.8.1相关概念
9.8.2求最大流
9.8.3割集与割量
9.8.4求最小费用最大流
上机实验题9——求图着色问题
练习题9

第10章计算几何
10.1矢量运算
10.1.1矢量的基本运算
10.1.2判断一个点是否在一个矩形内
10.1.3判断一个点是否在一条线段上
10.1.4判断两条线段是否平行
10.1.5判断两线段是否相交
10.1.6判断一个点是否在多边形内
10.2求解凸包问题
10.2.1礼品包裹算法
10.2.2Graham扫描算法
10.3求解最近点对问题
10.3.1用穷举法求最近点对
10.3.2用分治法求最近点对
10.4求解最远点对问题
10.4.1用穷举法求最远点对
10.4.2用旋转卡壳法求最远点对
上机实验题10——求凸多边形的直径
练习题10

附录A部分练习题参考答案
附录B上机实验题参考程序
附录C书中部分算法清单
参考文献