《《算法设计与分析》考核要求》由会员分享,可在线阅读,更多相关《《算法设计与分析》考核要求(2页珍藏版)》请在金锄头文库上搜索。
1、算法设计与分析课程考核要求 本课程在教学计划中为考查课。考核形式采用大作业形式,以打印文档形式验收并提交。 一考核内容1 分治法题目(1)编程实现归并排序算法和快速排序算法,输出排序结果。输入10组相同的数据,验证排序结果和完成排序的比较次数。(2)求方程f(x) = x3 + x2 - 1 = 0在0,1上的近似解,精确度为0.01。2 动态规划题目(1)对于以下5 个矩阵:M1: 23, M2: 36, M3: 64, M4: 42, M5: 27 ,找出这5个矩阵相乘需要的最小数量乘法的次数,并给出一个括号化表达式,使在这种次序下达到乘法的次数最少。(2)假如我们有两个字符串:X=0,1
2、,2.n Y=0,1,2.m。我们定义L(i, j)为X0.i与Y0.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)的权为cvw。如果G的子图G是一棵包含G的所有顶点的树,则称G为G的生成树。生成树上各边权的总和称为生成树的耗费。在
3、G的所有生成树中,耗费最小的生成树称为G的最小生成树。实现构造最小生成树算法(Prim算法或者Kruskal算法)。二具体要求1每个学生从以上3组题目中分别选择一个题目,即一共要完成3个题目,分别用分治法、动态规划和贪心法来求解。2提交每一个题目的完整的完成报告,报告包括:(1)分治法( 动态规划、贪心法)的基本思想;(2)要完成题目的算法思想(可以用流程图、自然语言或伪代码来描述);(3)算法实现的源程序代码完成题目的要求;(4)通过截图的方式给出程序运行的结果;(5)对题目的算法作一定的分析(可以从算法复杂度、优缺点或改进方法等角度来分析)。3每一个报告题目为“分治法(动态规划/贪心法)大
4、作业报告”。正文中的大标题分别为:问题陈述(即题目),分治法(动态规划/贪心法)基本思想、算法描述、程序代码、运行结果、结论分析。4大作业报告必须提交打印稿。封面标题用算法设计与分析大作业报告,并附上班级,学号和姓名。正文部分一律用五号宋体字(各级标题字体可以自行调整)。注意排版尽量做到规范美观。5可以参考任何资料,但杜绝抄袭。源程序代码必须通过验收(即在验收时要能够说明各行代码的作用)。6提交和验收时间:5月3日(周四下午7-8节课),地点:222机房。三成绩评定1平时成绩占30%,大作业成绩占70%。2大作业评分标准如下: 格式规范(10分) 基本思想和算法描述(20分) 程序代码(20分) 运行结果和分析(20分) 验收(30分)3如果发现学生的大作业有雷同现象,被认定为雷同的作业,最终考试成绩一律作不及格处理。任课教师:王云华 2012.4.15