《算法分析与设计》课程任务
《算法分析与设计》课程任务 内容包括以下8个部分，建议将任务按以下方式分解： 其中1-6的每个部分的简介、适用条件、基本思想、基本步骤、复杂度分析等由1人讲解，实例分析由1人讲解（注：至少一个实例），实例实现代码（注：至少一个实例）由1人讲解，找一篇使用了该算法设计策略的论文（最好是英文）讲解； 另外，1人讲解随机算法基本知识、1人将随机算法实例，1人讲NP完全性知识，1人讲 NP完全问题实例 。 具体分工由龙虎负责完成，时间从国庆后的第2周或第3周开始。 1 递归技术 2 分治法 2.1 简介（定义与发展） 2.2 分治法的基本思想 2.3 分治法的适用条件 2.4 分治法的基本步骤 2.5 分治法的复杂性分析 2.6 分治法的实例分析 2.6.1 例1：二分查找 2.6.2 例2：快速排序 2.6.3 例3：大整数乘法 2.6.4 例4：Strassen矩阵乘法 2.6.5 例5：最接近点对问题 2.6.6 例6：导线和开关 3 动态规划 3.1 简介（定义与发展） 3.2 动态规划的适用条件 3.3 动态规划的基本思想 3.4 动态规划的基本步骤 3.5 动态规划的复杂性分析 3.6 动态规划的实例分析 3.6.1 例1：最短路径问题 3.6.2 例2：生产计划问题 3.6.3 例3：Bitonic旅行路线问题 3.6.4 例4：计算矩阵连乘积 3.6.5 例5：最长公共子序列 3.6.6 例6：凸多边形的最优三角剖分问题 3.6.7 例7：多边形计算 3.6.8 例8：字符识别 4 贪心算法 4.1 简介（定义与发展） 4.2 贪心算法的适用条件 4.3 贪心算法的基本思想 4.4 贪心算法的基本步骤 4.5 贪心算法的复杂性分析 4.6 贪心算法的实例分析 4.6.1 例1：活动安排问题； 4.6.2 例2：最优装载问题； 4.6.3 例3：哈夫曼编码； 4.6.4 例4：单源最短路径； 4.6.5 例5：最小生成树； 4.6.6 例6：多机调度问题。 5 回溯法 5.1 简介 5.2 回溯法的适用条件 5.3 回溯法的基本思想 5.4 回溯法的基本步骤 5.5 回溯法的复杂度分析 5.6 回溯法的实例分析 5.6.1 例1：装载问题； 5.6.2 例2：批处理作业调度； 5.6.3 例3：符号三角形问题 5.6.4 例4：n后问题； 5.6.5 例5：0-1背包问题； 5.6.6 例6：最大团问题； 5.6.7 例7：图的m着色问题 5.6.8 例8：旅行售货员问题 5.6.9 例9：圆排列问题 5.6.10 例10：电路板排列问题 5.6.11 例11：连续邮资问题 6 分支界限法 6.1 简介 6.2 分支界限法的适用条件 6.3 分支界限法的基本思想 6.4 分支界限法的基本步骤 6.5 分支界限法的复杂度分析 6.5.1 例1：单源最短路径问题 6.5.2 例2：装载问题； 6.5.3 例3：布线问题 6.5.4 例4：0-1背包问题； 6.5.5 例5：最大团问题； 6.5.6 例6：旅行售货员问题 6.5.7 例7：电路板排列问题 6.5.8 例8：批处理作业调度问题 7 随机算法 8 NP完全性 |
https://blog.sciencenet.cn/blog-944416-1391270.html《算法分析与设计》课程任务
内容包括以下8个部分，建议将任务按以下方式分解：
其中1-6的每个部分的简介、适用条件、基本思想、基本步骤、复杂度分析等由1人讲解，实例分析由1人讲解（注：至少一个实例），实例实现代码（注：至少一个实例）由1人讲解，找一篇使用了该算法设计策略的论文（最好是英文）讲解；
另外，1人讲解随机算法基本知识、1人将随机算法实例，1人讲NP完全性知识，1人讲NP完全问题实例。
具体分工由龙虎负责完成，时间从国庆后的第2周或第3周开始。
1 递归技术
2 分治法
2.1 简介（定义与发展）
2.2 分治法的基本思想
2.3 分治法的适用条件
2.4 分治法的基本步骤
2.5 分治法的复杂性分析
2.6 分治法的实例分析
2.6.1 例1：二分查找
2.6.2 例2：快速排序
2.6.3 例3：大整数乘法
2.6.4 例4：Strassen矩阵乘法
2.6.5 例5：最接近点对问题
2.6.6 例6：导线和开关
3 动态规划
3.1 简介（定义与发展）
3.2 动态规划的适用条件
3.3 动态规划的基本思想
3.4 动态规划的基本步骤
3.5 动态规划的复杂性分析
3.6 动态规划的实例分析
3.6.1 例1：最短路径问题
3.6.2 例2：生产计划问题
3.6.3 例3：Bitonic旅行路线问题
3.6.4 例4：计算矩阵连乘积
3.6.5 例5：最长公共子序列
3.6.6 例6：凸多边形的最优三角剖分问题
3.6.7 例7：多边形计算
3.6.8 例8：字符识别
4 贪心算法
4.1 简介（定义与发展）
4.2 贪心算法的适用条件
4.3 贪心算法的基本思想
4.4 贪心算法的基本步骤
4.5 贪心算法的复杂性分析
4.6 贪心算法的实例分析
4.6.1 例1：活动安排问题；
4.6.2 例2：最优装载问题；
4.6.3 例3：哈夫曼编码；
4.6.4 例4：单源最短路径；
4.6.5 例5：最小生成树；
4.6.6 例6：多机调度问题。
5 回溯法
5.1 简介
5.2 回溯法的适用条件
5.3 回溯法的基本思想
5.4 回溯法的基本步骤
5.5 回溯法的复杂度分析
5.6 回溯法的实例分析
5.6.1 例1：装载问题；
5.6.2 例2：批处理作业调度；
5.6.3 例3：符号三角形问题
5.6.4 例4：n后问题；
5.6.5 例5：0-1背包问题；
5.6.6 例6：最大团问题；
5.6.7 例7：图的m着色问题
5.6.8 例8：旅行售货员问题
5.6.9 例9：圆排列问题
5.6.10 例10：电路板排列问题
5.6.11 例11：连续邮资问题
6 分支界限法
6.1 简介
6.2 分支界限法的适用条件
6.3 分支界限法的基本思想
6.4 分支界限法的基本步骤
6.5 分支界限法的复杂度分析
6.5.1 例1：单源最短路径问题
6.5.2 例2：装载问题；
6.5.3 例3：布线问题
6.5.4 例4：0-1背包问题；
6.5.5 例5：最大团问题；
6.5.6 例6：旅行售货员问题
6.5.7 例7：电路板排列问题
6.5.8 例8：批处理作业调度问题
7 随机算法
8 NP完全性
转载本文请联系原作者获取授权，同时请注明本文来自王闯科学网博客。
链接地址：https://blog.sciencenet.cn/blog-944416-1391270.html