高等学校数据结构课程系列教材算法设计与分析(第2版)/李春葆等 内容简介

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

高等学校数据结构课程系列教材算法设计与分析(第2版)/李春葆等 本书特色

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

高等学校数据结构课程系列教材算法设计与分析(第2版)/李春葆等 目录

目录 第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算法设计工具——STL/ 1.3.1STL概述/ 1.3.2常用的STL容器/ 1.3.3STL在算法设计中的应用/ 1.4练习题/ 1.5上机实验题/ 1.6在线编程题/ 第2章递归算法设计技术/ 2.1什么是递归/ 2.1.1递归的定义/ 2.1.2何时使用递归/ 2.1.3递归模型/ 2.1.4递归算法的执行过程/ 2.2递归算法设计/ 2.2.1递归与数学归纳法/ 2.2.2递归算法设计的一般步骤/ 2.2.3递归数据结构及其递归算法设计/ 2.2.4基于归纳思想的递归算法设计/ 2.3递归算法设计示例/ 2.3.1简单选择排序和冒泡排序/ 2.3.2求解n皇后问题/ 2.4*递归算法转化为非递归算法/ 2.4.1用循环结构替代递归过程/ 2.4.2用栈消除递归过程/ 2.5递推式的计算/ 2.5.1用特征方程求解递归方程/ 2.5.2用递归树求解递归方程/ 2.5.3用主方法求解递归方程/ 2.6练习题/ 2.7上机实验题/ 2.8在线编程题/ 第3章分治法/ 3.1分治法概述/ 3.1.1分治法的设计思想/ 3.1.2分治法的求解过程/ 3.2求解排序问题/ 3.2.1快速排序/ 3.2.2归并排序/ 3.3求解查找问题/ 3.3.1查找*大和次大元素/ 3.3.2折半查找/ 3.3.3寻找一个序列中第k小的元素/ 3.3.4寻找两个等长有序序列的中位数/ 3.4求解组合问题/ 3.4.1求解*大连续子序列和问题/ 3.4.2求解棋盘覆盖问题/ 3.4.3求解循环日程安排问题/ 3.5求解大整数乘法和矩阵乘法问题/ 3.5.1求解大整数乘法问题/ 3.5.2求解矩阵乘法问题/ 3.6并行计算简介/ 3.6.1并行计算概述/ 3.6.2并行计算模型/ 3.6.3快速排序的并行算法/ 3.7练习题/ 3.8上机实验题/ 3.9在线编程题/ 第4章蛮力法/ 4.1蛮力法概述/ 4.2蛮力法的基本应用/ 4.2.1采用直接穷举思路的一般格式/ 4.2.2简单选择排序和冒泡排序/ 4.2.3字符串匹配/ 4.2.4求解*大连续子序列和问题/ 4.2.5求解幂集问题/ 4.2.6求解简单0/1背包问题/ 4.2.7求解全排列问题/ 4.2.8求解任务分配问题/ 4.3递归在蛮力法中的应用/ 4.3.1用递归方法求解幂集问题/ 4.3.2用递归方法求解全排列问题/ 4.3.3用递归方法求解组合问题/ 4.4图的深度优先和广度优先遍历/ 4.4.1图的存储结构/ 4.4.2深度优先遍历/ 4.4.3广度优先遍历/ 4.4.4求解迷宫问题/ 4.5练习题/ 4.6上机实验题/ 4.7在线编程题/ 第5章回溯法/ 5.1回溯法概述/ 5.1.1问题的解空间/ 5.1.2什么是回溯法/ 5.1.3回溯法的算法框架及其应用/ 5.1.4回溯法与深度优先遍历的异同/ 5.1.5回溯法的时间分析/ 5.2求解0/1背包问题/ 5.3求解装载问题/ 5.3.1求解简单装载问题/ 5.3.2求解复杂装载问题/ 5.4求解子集和问题/ 5.4.1求子集和问题的解/ 5.4.2判断子集和问题是否存在解/ 5.5求解n皇后问题/ 5.6求解图的m着色问题/ 5.7求解任务分配问题/ 5.8求解活动安排问题/ 5.9求解流水作业调度问题/ 5.10练习题/ 5.11上机实验题/ 5.12在线编程题/ 第6章分枝限界法/ 6.1分枝限界法概述/ 6.1.1什么是分枝限界法/ 6.1.2分枝限界法的设计思想/ 6.1.3分枝限界法的时间性能/ 6.2求解0/1背包问题/ 6.2.1采用队列式分枝限界法求解/ 6.2.2采用优先队列式分枝限界法求解/ 6.3求解图的单源*短路径/ 6.3.1采用队列式分枝限界法求解/ 6.3.2采用优先队列式分枝限界法求解/ 6.4求解任务分配问题/ 6.5求解流水作业调度问题/ 6.6练习题/ 6.7上机实验题/ 6.8在线编程题/ 第7章贪心法/ 7.1贪心法概述/ 7.1.1什么是贪心法/ 7.1.2用贪心法求解的问题应具有的性质/ 7.1.3贪心法的一般求解过程/ 7.2求解活动安排问题/ 7.3求解背包问题/ 7.4求解*优装载问题/ 7.5求解田忌赛马问题/ 7.6求解多机调度问题/ 7.7哈夫曼编码/ 7.8求解流水作业调度问题/ 7.9练习题/ 7.10上机实验题/ 7.11在线编程题/ 第8章动态规划/ 8.1动态规划概述/ 8.1.1从求解斐波那契数列看动态规划法/ 8.1.2动态规划的原理/ 8.1.3动态规划求解的基本步骤/ 8.1.4动态规划与其他方法的比较/ 8.2求解整数拆分问题/ 8.3求解*大连续子序列和问题/ 8.4求解三角形*小路径问题/ 8.5求解*长公共子序列问题/ 8.6求解*长递增子序列问题/ 8.7求解编辑距离问题/ 8.8求解0/1背包问题/ 8.9求解完全背包问题/ 8.10求解资源分配问题/ 8.11求解会议安排问题/ 8.12滚动数组/ 8.12.1什么是滚动数组/ 8.12.2用滚动数组求解0/1背包问题/ 8.13练习题/ 8.14上机实验题/ 8.15在线编程题/ 第9章图算法设计/ 9.1求图的*小生成树/ 9.1.1*小生成树的概念/ 9.1.2用普里姆算法构造*小生成树/ 9.1.3克鲁斯卡尔算法/ 9.2求图的*短路径/ 9.2.1狄克斯特拉算法/ 9.2.2贝尔曼福特算法/ 9.2.3SPFA算法/ 9.2.4弗洛伊德算法/ 9.3求解旅行商问题/ 9.3.1旅行商问题描述/ 9.3.2采用蛮力法求解TSP问题/ 9.3.3采用动态规划求解TSP问题/ 9.3.4采用回溯法求解TSP问题/ 9.3.5采用分枝限界法求解TSP问题/ 9.3.6采用贪心法求解TSP问题/ 9.4网络流/ 9.4.1相关概念/ 9.4.2求*大流/ 9.4.3割集与割量/ 9.4.4求*小费用*大流/ 9.5练习题/ 9.6上机实验题/ 9.7在线编程题/ 第10章计算几何/ 10.1向量运算/ 10.1.1向量的基本运算/ 10.1.2判断一个点是否在一个矩形内/ 10.1.3判断一个点是否在一条线段上/ 10.1.4判断两条线段是否平行/ 10.1.5判断两条线段是否相交/ 10.1.6判断一个点是否在多边形内/ 10.1.7求3个点构成的三角形的面积/ 10.1.8求一个多边形的面积/ 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.5练习题/ 10.6上机实验题/ 10.7在线编程题/ 第11章计算复杂性理论简介/ 11.1计算模型/ 11.1.1求解问题的分类/ 11.1.2图灵机模型/ 11.2P类和NP类问题/ 11.3NPC问题/ 11.4练习题/ 第12章概率算法和近似算法/ 12.1概率算法/ 12.1.1什么是概率算法/ 12.1.2蒙特卡罗类型概率算法/ 12.1.3拉斯维加斯类型概率算法/ 12.1.4舍伍德类型概率算法/ 12.2近似算法/ 12.2.1什么是近似算法/ 12.2.2求解旅行商问题的近似算法/ 12.3练习题/ 12.4上机实验题/ 12.5在线编程题/ 附录A书中部分算法清单/ 参考文献/

高等学校数据结构课程系列教材算法设计与分析(第2版)/李春葆等 作者简介

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