《算法分析与设计》课程任务

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