算法设计与分析(第2版微课版高等学校数据结构课程系列教材)
全新正版 极速发货
￥ 46.8 7.9折 ￥ 59.5 全新
库存6件
浙江嘉兴
认证卖家担保交易快速发货售后保障
作者李春葆
出版社清华大学出版社
ISBN9787302500988
出版时间2018-08
装帧其他
开本16开
定价59.5元
货号30249126
上书时间2024-11-15
商品详情
- 品相描述：全新
- 商品描述
-
作者简介
李春葆，武汉大学计算机学院教授。主要研究方向为数据挖掘和算法设计，先后主持和参加多个大型研究项目。主要为本科生讲授数据结构(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算法设计工具——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书中部分算法清单/
参考文献/
内容摘要
\\\\\\\"内容简 介本书系统地介绍了各种常用的算法设计策略，包括递归、分治法、蛮力法、回溯法、分枝限界法、贪心法、动态规划、概率算法和近似算法等，并详细讨论了各种图算法和计算几何设计算法。
全书既注重原理又注重实践，配有大量图表、练习题、上机实验题和在线编程题，内容丰富，概念讲解清楚，表达严谨，逻辑性强，语言精练，可读性好。
本书既便于教师课堂讲授，又便于自学者阅读，适合作为高等院校“算法设计与分析”课程的教材，也可供ACM和各类程序设计竞赛者参考。\\\\\\\"
精彩内容
第3章分治法分治法是使用最广泛的算法设计方法之一。其基本策略是采用递归思想把大问题分解成一些小问题，然后由小问题的解方便地构造出大问题的解。本章介绍分治法求解问题的一般方法，并给出一些用分治法求解的经典示例。
3.1分治法概述3.1.1分治法的设计思想对于一个规模为n的问题，若该问题可以容易地解决(例如规模n较小)则直接解决，否则将其分解为k个规模较小的子问题，这些子问题互相独立且与原问题形式相同，递归地解这些子问题，然后将各子问题的解合并得到原问题的解，这种算法设计策略叫分治法。
如果原问题可分割成k(1
(2)该问题可以分解为若干个规模较小的相似问题。
(3)利用该问题分解出的子问题的解可以合并为该问题的解。
(4)该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子问题。
上述特征(1)是绝大多数问题都可以满足的，因为问题的计算复杂性一般是随着问题规模的增加而增加；特征(2)是应用分治法的前提，它也是大多数问题可以满足的，此特征反映了递归思想的应用；特征(3)是关键，能否利用分治法完全取决于问题是否具有该特征，如果具备了特征(1)和(2)，而不具备特征(3)，则可以考虑用贪心法或动态规划法；特征(4)涉及分治法的效率，如果各子问题是不独立的则分治法要做许多不必要的工作，重复地解公共的子问题，此时虽然可用分治法，但一般用动态规划法较好。
从上看到，分治是一种解题的策略，它的基本思想是“如果整个问题比较复杂，可以将问题分化，各个击破”。分治包含“分”和“治”两层含义，如何分，分后如何治成为解决问题的关键所在。不是所有的问题都可以采用分治，只有那些能将问题分成与原问题类似的子问题并且归并后符合原问题的性质的问题才能进行分治。分治可进行二分、三分等，具体怎么分，需看问题的性质和分治后的效果。只有深刻地领会分治的思想，认真分析分治后可能产生的预期效率，才能灵活地运用分治思想解决实际问题。
3.1.2分治法的求解过程递归特别适合解决结构自相似的问题，所谓结构自相似，是指构成原问题的子问题与原问题在结构上相似，可以采用类似的方法解决。所以分治法通常采用递归算法设计技术，在每一层递归上都有3个步骤。
(1)分解成若干个子问题：将原问题分解为若干个规模较小、相互独立、与原问题形式相同的子问题。
(2)求解子问题：若子问题规模较小，容易被解决，则直接求解，否则递归地求解各个子问题。
(3)合并子问题：将各个子问题的解合并为原问题的解。 分治法的一般算法设计模式如下：divideandconquer(P){if|P|≤n0returnadhoc(P);将P分解为较小的子问题P1、P2、…、Pk;for(i=1;i<=k;i++)//循环处理k次yi=divideandconquer(Pi); //递归解决Pireturnmerge(y1,y2,…,yk); //合并子问题}其中，|P|表示问题P的规模；n0为一阈值，表示当问题P的规模不超过n0时(即P问题规模足够小时)已容易直接解出，不必再继续分解。adhoc(P)是该分治法中的基本子算法，用于直接解小规模的问题P。算法merge(y1，y2，…，yk)是该分治法中的合并子算法，用于将P的子问题P1、P2、…、Pk的相应解y1、y2、…、yk合并为P的解。
根据分治法的分解原则，原问题应该分解为多少个子问题才较适合？各个子问题的规模应该怎样才为适当？这些问题很难给予肯定的回答。但人们从大量图3.1二分法的基本策略的实践中发现，在用分治法设计算法时最好使子问题的规模大致相同。换句话说，将一个问题分成大小相等的k个子问题的处理方法是行之有效的。当k=1时称为减治法。许多问题可以取k=2，称为二分法，如图3.1所示，这种使子问题规模大致相等的做法出自一种平衡子问题的思想，它几乎总是比子问题规模不等的做法要好。
分治法的合并步骤是算法的关键所在。有些问题的合并方法比较明显，有些问题的合并方法比较复杂，或者是有多种合并方案；或者是合并方案不明显。究竟应该怎样合并没有统一的模式，需要具体问题具体分析。
尽管许多分治法算法都是采用递归实现的，但要注意分治法和递归是有区别的，分治法是一种求解问题的策略，而递归是一种实现求解算法的技术。分治法算法也可以采用非递归方法实现。就像二分查找，作为一种典型的分治法算法，既可以采用递归实现，也可以采用非递归实现。
3.2求解排序问题对于给定的含有n个元素的数组a，对其按元素值递增排序。快速排序和归并排序是典型的采用分治法进行排序的方法。
3.2.1快速排序快速排序的基本思想是在待排序的n个元素中任取一个元素(通常取第一个元素)作为基准，把该元素放入最终位置后，整个数据序列被基准分割成两个子序列，所有小于基准的元素放置在前子序列中，所有大于基准的元素放置在后子序列中，并把基准排在这两个子序列的中间，这个过程称为划分，如图3.2所示。然后对两个子序列分别重复上述过程，直到每个子序列内只有一个元素或空为止。
图3.2快速排序的一趟排序过程这是一种二分法思想，每次将整个无序序列一分为二，归位一个元素，对两个子序列采用同样的方式进行排序，直到子序列的长度为1或0为止。
快速排序的分治策略如下。
(1)分解：将原序列a［s..t］分解成两个子序列a［s..i-1］和a［i+1..t］，其中i为划分的基准位置，即将整个问题分解为两个子问题。
(2)求解子问题：若子序列的长度为0或1，则它是有序的，直接返回；否则递归地求解各个子问题。
(3)合并：由于整个序列存放在数组a中，排序过程是就地进行的，合并步骤不需要执行任何操作。 例如，对于(2，5，1，7，10，6，9，4，3，8)序列，其快速排序过程如图3.3所示，图中虚线表示一次划分，虚线旁的数字表示执行次序，圆圈表示归位的基准。
图3.3(2，5，1，7，10，6，9，4，3，8)序列的快速排序过程实现快速排序的完整程序如下：#includevoiddisp(inta［］,intn)//输出a中的所有元素{inti;for(i=0;i
3.2.2归并排序归并排序的基本思想是首先将a［0..n-1］看成n个长度为1的有序表，将相邻的k(k≥2)个有序子表成对归并，得到n/k个长度为k的有序子表；然后再将这些有序子表继续归并，得到n/k2个长度为k2的有序子表，如此反复进行下去，最后得到一个长度为n的有序表。由于整个排序结果放在一个数组中，所以不需要特别地进行合并操作。
若k=2，即归并是在相邻的两个有序子表中进行的，称为二路归并排序。若k>2，即归并操作在相邻的多个有序子表中进行，则叫多路归并排序。这里仅讨论二路归并排序算法，二路归并排序算法主要有两种，下面一一讨论。
相关推荐
— 没有更多了 —
以下为对购买帮助不大的评价