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

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

内容包括以下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完全性