《算法分析与设计》实验教学大纲.doc

《算法分析与设计》实验教学大纲课程编号:课程名称:算法分析与设计英文名称:AlgorithmAnalysisandDesign适应专业:软件工程执笔人:刘淑英实验教材(指导书):王晓东,计算机算法设计与分析,电子工业出版社,2007主要参考书目:①张铭、刘晓丹译电子工业出版社出版的《数据结构与算法分析》②徐士良主编清华大学出版社出版的《计算机常用算法》第二版③卢开澄主编清华大学出版社出版的《计算机指导引论-设计与分析》                            一、实验学时总学时:48 总学分:3 实验学时:10 二、实验课的任务、性质与目的《算法设计与分析》是计算机专业的专业核心课程,其先修课程有数据结构和至少一门高级语言。算法设计与分析课程将覆盖计算机软件实现中的大部分算法,并具有一定的深度和广度,使学生对计算机常用算法有一个全盘的了解;通过此课的学****学生应该具有针对所给的问题设计和实现高效算法的能力。通过上机实验,将使学生熟悉、掌握课堂教学中所学的大部分算法。同时,上机实****是对学生在软件设计方面的综合训练,包括问题分析,总体结构设计,用户界面设计,程序设计基本技能和技巧等,以培养良好的编程风格和科学作风。通过理论联系实际,以最终提高学生动手操作的能力以及分析问题的能力。本课程的主要目的是研究计算机领域及其它有关领域中的主要算法设计方法及一些常用算法,使学生掌握算法设计的常用方法,以便运用这些方法来设计解决一些常用的或较为复杂的实际问题的算法,并力争做到快捷、有效,从而提高程序设计的质量。同时,还要使学生学会分析算法、估计算法的复杂性,以便理解并科学评估有一个算法的好坏。它属于技术基础课,是进行软件设计的核心内容,是一门实践性很强的课程。学生应具有C或C++、数据结构的基础知识。三、实验内容(1)分治策略算法(4学时)实验内容:用分治法实现快速排序、归并分类算法;编写程序实现循环赛日程表。设有n=2k个运动员要进行网球循环赛。现要设计一个满足以下要求的比赛日程表:(1)每个选手必须与其它n-1个选手各赛一次(2)每个选手一天只能赛一场(3)循环赛进行n-1天。实验要求:掌握递归算法实现的过程;了解快速排序算法的思想,掌握用算法设计思想解题的思路。(2)贪心算法(2学时)实验内容:编写一个简单的程序,实现单源最短路径问题;编写一段程序,实现找零;编写程序实现多机调度问题。实验要求:掌握贪心算法的基本设计思路,并用其解决实际问题。(3)动态规划算法(2学时)实验内容:编写一个简单的程序,解决0-1背包问题;编程解决合唱队形安排。实验要求:掌握动态规划算法设计的基本策略。(4)回溯算法(2学时)实验内容:用回溯法解8皇后问题;批处理作业调度。实验要求:掌握回溯法的算法框架和算法的基本思想。 四、实验要求(1)学生在完成预****报告、熟悉实验内容后才能进入实验室进行上机实验。实验1人一组,由学生独立操作完成实验。(2)学生分析问题,熟悉解决问题的算法描述。要求记录上机实验过程,且得到指导教师认可后,学生方可离开实验室。(3)实验完成后提交实验报告。(4)实验过程由指导老师监督,听从老师安排和督导。 五、实验项目的设置与内容提要 本课程主要通过综合设计性实验,完成一个问题的算法分析设计过程,培养学生解决设计问题的能力,提高学生综合设计能力。要求学生通过查阅文献、小组讨论完成实验任务。 序号实验项目名称实验学时实验类型实验要求内容提要1分治策略算法4综合设计性必做用分治策略解决排序等问题。2贪心算法2综合设计性必做掌握贪心算法的基本设计思路,并用其解决实际问题。3动态规划算法2综合设计性必做掌握动态规划算法设计的基本策略。4回溯算法2综合设计性必做掌握回溯算法的基本思想。 六、考核方式(1)每次任务完成后由指导老师逐个的检查实验内容、结果并评分,占实验成绩60%。(2)上机考勤评分,占实验成绩10%。(3)实验报告占实验成绩30%。实验一排序问题求解实验目的1)以排序(分类)问题为例,掌握分治法的基本设计策略。2)熟练掌握一般插入排序算法的实现;3)熟练掌握快速排序算法的实现;Forpersonaluseonlyinstudyandresearch;mercialuse4)理解常见的算法经验分析方法;实验环境计算机、C语言程序设计环境Forpersonaluseonlyinstudyandresearch;mercialuse实验学时4学时,必做实验。:are,生成2000个在区间[1,10000]上的随机整数,。这些数作为后面算法的实验数据。:实现insertionsort算法。;输出记录为文件: