算法设计与分析(第3版·微课视频·题库版)

扫一扫 源码下载
第1章绪论/ 1．1算法概述/ 1．1．1什么是算法/ 1．1．2算法描述/ 1．1．3算法设计的基本步骤/ 1.2算法分析/ 1．2．1算法时间复杂度分析/ 1．2．2算法空间复杂度分析/ 1.3算法设计工具——STL/ 1．3．1STL概述/ 1．3．2vector(向量容器)/ 1．3．3string(字符串容器)/ 1．3．4deque(双端队列容器)/ 1．3．5list(链表容器)/ 1．3．6stack(栈容器)/ 1．3．7queue(队列容器)/ 1．3．8priority_queue(优先队列容器)/ 1．3．9set(集合容器)/multiset(多重集合容器)/ 1．3．10map(映射容器)/multimap(多重映射容器)/ 1．3．11unordered_set(哈希集合容器)/ 1．3．12unordered_map(哈希映射容器)/ 1.4练习题/ 1.5在线编程实验题/ 第2章递归算法设计技术/ 2.1递归概述/ 2．1．1什么是递归/ 2．1．2何时使用递归/ 2．1．3递归模型/ 2．1．4递归算法的执行过程/ 2．1．5递归算法的时间复杂度和空间复杂度分析/ 2.2递归算法的设计方法/ 2．2．1递归与数学归纳法/ 2．2．2递归算法设计的一般步骤/ 2．2．3基于递归数据结构的递归算法设计/ 2．2．4基于归纳思想的递归算法设计/ 2.3直接插入排序/ 2.40/1背包问题/ 2.5求表达式的值/ 2.6计算递推式/ 2．6．1直接展开法/ 2．6．2递归树方法/ 2．6．3主方法/ 2．6．4*特征方程方法/ 2.7练习题/ 2.8在线编程实验题/ 第3章穷举法/ 3.1穷举法概述/ 3．1．1什么是穷举法/ 3．1．2穷举算法的框架/ 3.2算法优化中常用的数据结构/ 3．2．1前缀和数组/ 3．2．2并查集/ 3.3求回文串的个数/ 3.4求*大连续子序列和/ 3.5求幂集/ 3.60/1背包问题/ 3.7求全排列/ 3.8n皇后问题/ 3.9任务分配问题/ 3.10旅行商问题/ 3.11练习题/ 3.12在线编程实验题/ 第4章分治法/ 4.1分治法概述/ 4．1．1什么是分治法/ 4．1．2分治法的求解过程/ 4．1．3分治算法分析/ 4.2快速排序/ 4.3二路归并排序/ 4.4二分查找/ 4．4．1基本二分查找/ 4．4．2二分查找的扩展/ 4.5求*大连续子序列和/ 4.6棋盘覆盖问题/ 4.7循环日程安排问题/ 4.8旅行商问题/ 4.9练习题/ 4.10在线编程实验题/ 第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图的m着色问题/ 5.6子集和问题/ 5.7简单装载问题/ 5.80/1背包问题/ 5.9*完全背包问题/ 5.10基于排列树的回溯算法框架/ 5．10．1求全排列/ 5．10．2排列树回溯算法框架/ 5.11n皇后问题/ 5.12任务分配问题/ 5.13旅行商问题/ 5.14练习题/ 5.15在线编程实验题/ 第6章分支限界法/ 6.1分支限界法概述/ 6．1．1什么是分支限界法/ 6．1．2分支限界法的设计要点/ 6．1．3分支限界法的时间性能/ 6.2广度优先搜索/ 6．2．1图的广度优先搜索/ 6．2．2广度优先搜索的应用/ 6.3队列式分支限界法的框架/ 6.4图的单源*短路径/ 6.50/1背包问题(1)/ 6.6优先队列式分支限界法的框架/ 6.70/1背包问题(2)/ 6.8任务分配问题/ 6.9旅行商问题/ 6.10*A*算法及其应用/ 6．10．1A*算法概述/ 6．10．2启发式函数/ 6.11练习题/ 6.12在线编程实验题/ 第7章动态规划/ 7.1动态规划概述/ 7．1．1从一个简单的示例入门/ 7．1．2动态规划的原理/ 7．1．3动态规划求解问题的类型、性质和步骤/ 7．1．4动态规划与其他方法的比较/ 7.2求*大连续子序列和/ 7.3*长递增子序列/ 7.4三角形的*小路径和/ 7.5*长公共子序列/ 7.6编辑距离/ 7.70/1背包问题/ 7.8*完全背包问题和多重背包问题/ 7．8．1完全背包问题/ 7．8．2多重背包问题/ 7.9扔鸡蛋问题/ 7.10资源分配问题/ 7.11旅行商问题/ 7.12*少士兵数问题/ 7.13矩阵连乘问题/ 7.14练习题/ 7.15在线编程实验题/ 第8章贪心法/ 8.1贪心法概述/ 8．1．1什么是贪心法/ 8．1．2用贪心法求解的问题具有的性质/ 8．1．3用贪心法求解问题的一般过程/ 8.2区间问题/ 8．2．1*大兼容区间个数/ 8．2．2区间合并/ 8．2．3**少资源问题/ 8.3背包问题/ 8.4田忌赛马问题/ 8.5零钱兑换问题/ 8.6哈夫曼编码/ 8.7*拟阵/ 8．7．1拟阵概述/ 8．7．2求加权拟阵*优子集的贪心算法/ 8．7．3带期限和惩罚的任务调度问题/ 8.8练习题/ 8.9在线编程实验题/ 第9章图算法/ 9.1图的*小生成树/ 9．1．1什么是*小生成树/ 9．1．2Prim算法/ 9．1．3Kruskal算法/ 9.2图的*短路径/ 9．2．1Dijkstra算法/ 9．2．2BellmanFord算法/ 9．2．3SPFA算法/ 9．2．4Floyd算法/ 9.3网络流/ 9．3．1问题的引入/ 9．3．2FordFulkerson算法/ 9．3．3EdmondsKrap算法/ 9．3．4Dinic算法/ 9.4练习题/ 9.5在线编程实验题/ 第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在线编程实验题/ 第11章计算复杂性/ 11.1P类和NP类/ 11．1．1易解问题和难解问题/ 11．1．2判定问题和优化问题/ 11．1．3计算模型/ 11．1．4P类问题/ 11．1．5NP类问题/ 11.2多项式时间变换和问题归约/ 11.3NP完全问题/ 11．3．1什么是NP完全问题和NP难问题/ 11．3．2**个NP完全问题/ 11．3．3其他NP完全问题/ 11.4练习题/ 第12章概率算法和近似算法/ 12.1概率算法/ 12．1．1什么是概率算法/ 12．1．2数值概率算法/ 12．1．3蒙特卡洛算法/ 12．1．4拉斯维加斯算法/ 12．1．5舍伍德算法/ 12.2近似算法/ 12．2．1什么是近似算法/ 12．2．2多机调度问题的近似算法/ 12．2．30/1背包问题的近似算法/ 12．2．4旅行商问题的近似算法/ 12.3练习题/ 参考文献/