本课程在教学计划中为考查课。考核形式采用大作业形式，以打印文档形式验收并提交。 

一．考核内容

1．分治法题目

（1）编程实现归并排序算法和快速排序算法，输出排序结果。输入10组相同的数据，验证排序结果和完成排序的比较次数。

（2）求方程f(x) = x^3 + x^2 - 1 = 0在[0,1]上的近似解，精确度为0.01。

2．动态规划题目

（1）对于以下5 个矩阵：M1: 23, M2: 36, M3: , M4: 42, M5: 27 ,

找出这5个矩阵相乘需要的最小数量乘法的次数，并给出一个括号化表达式，使在这种次序下达到乘法的次数最少。

（2）假如我们有两个字符串：X=[0,1,2....n]  Y=[0,1,2...m]。我们定义L(i, j)为X[0...i]与Y[0...j]之间的最长公共子序列的长度。

（3）定义0-1背包问题为：。条件为：，且。p和w为物品的价值和容量，c为背包容量。

3．贪心法题目

（1）给定n种物品和一个背包.物品i的重量是Wi,其价值为Vi,背包的容量为C。在选择物品i装入背包时，可以选择物品i的一部分，1<= i <=n。问应如何选择装入背包中的物品，使得装入背包中物品的总价值最大。

（2）设G = (V,E)是无向连通带权图，即一个网络。E中的每一条边（v,w）的权为c[v][w]。如果G的子图G’是一棵包含G的所有顶点的树，则称G’为G的生成树。生成树上各边权的总和称为生成树的耗费。在G的所有生成树中，耗费最小的生成树称为G的最小生成树。实现构造最小生成树算法（Prim算法或者Kruskal算法）。

二．具体要求

1．每个学生从以上3组题目中分别选择一个题目，即一共要完成3个题目，分别用分治法、动态规划和贪心法来求解。

2．提交每一个题目的完整的完成报告，报告包括：

（1）分治法（ 动态规划、贪心法）的基本思想；

（2）要完成题目的算法思想（可以用流程图、自然语言或伪代码来描述）；

（3）算法实现的源程序代码完成题目的要求；

（4）通过截图的方式给出程序运行的结果；

（5）对题目的算法作一定的分析（可以从算法复杂度、优缺点或改进方法等角度来分析）。

3．每一个报告题目为“分治法（动态规划/贪心法）大作业报告”。正文中的大标题分别为：问题陈述（即题目），分治法（动态规划/贪心法）基本思想、算法描述、程序代码、运行结果、结论分析。

4．大作业报告必须提交打印稿。封面标题用《算法设计与分析大作业报告》，并附上班级，学号和姓名。正文部分一律用五号宋体字（各级标题字体可以自行调整）。注意排版尽量做到规范美观。

5．可以参考任何资料，但杜绝抄袭。源程序代码必须通过验收（即在验收时要能够说明各行代码的作用）。

6．提交和验收时间：5月3日（周四下午7-8节课），地点：222机房。

三．成绩评定

1．平时成绩占30%，大作业成绩占70%。

2．大作业评分标准如下：

     格式规范（10分）

     基本思想和算法描述（20分）

     程序代码（20分）

     运行结果和分析（20分）

     验收（30分）

3．如果发现学生的大作业有雷同现象，被认定为雷同的作业，最终考试成绩一律作不及格处理。

任课教师：王云华 

2012.4.15下载本文