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

算法设计与分析实验教学大纲一、制定本大纲的依据 根据2006级信息与计算科学专业培养计划和算法设计与分析课程教学大纲制定本实验教学大纲。二、本实验课程的具体安排实验项目的设置及学时分配序号实验项目名称内容简介（50字左右）实验学时实验要求实验类型实验类别每组人数1分治策略掌握分治策略的基本思想以及用分治法解决问题的一般技巧2必修验证基础602动态规划掌握动态规划解决问题的一般过程，学会使用动态规划解决实际问题。2必修验证基础603贪心算法掌握贪心法解决问题的一般步骤，学会使用贪心法解决实际2必修验证基础604回溯法掌握回溯法解决问题的一般步骤，学会使用回溯法解决实际问题。2必修验证基础605分支限界法掌握分支限界法解决问题的基本思想，学会使用分支限界法解决实际问题。2必修验证基础60三、本实验课在该课程体系中的地位与作用本课程的主要目的是研究计算机领域及其它有关领域中的主要算法设计方法及一些常用算法， 使学生掌握算法设计的常用方法，以便运用这些方法来设计解决一些常用的或较为复杂的实际问题的算法，并力争做到快捷、有效，从而提高程序设计的质量。同时，还要使学生学会分析算法、估计算法的复杂性，以便理解并科学评估有一个算法的好坏。 它属于技术基础课，是进行软件设计的核心内容，是一门实践性很强的课程。学生应具有C或C+、数据结构的基础知识。四、学生应达到的实验能力与标准掌握递归算法、分治算法、贪心算法、动态规划算法、回溯算法和分支定界算法，并能灵活运用这些算法解决实际问题。通过实验使学生加深对基本算法设计方法的理解，增强学生对解决问题的不同算法运行时间不同的感性认识，使学生在算法设计方法和编程技能等方面得到系统的训练，使学生养成设计良好算法的习惯， 为今后从事软件开发和软件理论研究打下良好的实验基础 。五、讲授实验的基本理论与实验技术知识实验一 分治策略1.实验的基本内容选择完成下列程序中的一个：递归概念，分治法基本思想，二分搜索技术，大整数乘法，矩阵乘法，棋盘覆盖，合并排序，快速排序，线性时间选择，最接近点对问题，循环赛日程表。2.实验的基本要求掌握分治策略的基本思想以及用分治法解决问题的一般技巧3.实验的基本仪器设备和耗材PC机一台。实验二 动态规划1.实验的基本内容用动态规划算法实现下列程序中的一个：矩阵连乘，最长公共子序列，最大子段和，凸多边形最优三角剖分，多边形游戏，图像压缩，电路布线，流水作业调度，01背包问题，最优二叉搜索树。2.实验的基本要求（掌握动态规划解决问题的一般过程，学会使用动态规划解决实际问题。3.实验的基本仪器设备和耗材PC机一台。实验三 贪心算法1.实验的基本内容用贪心算法实现下列程序中的一个：活动安排问题，最优装载，哈夫曼编码，单源最短路径，最小生成树，多机调度。2.实验的基本要求掌握贪心法解决问题的一般步骤，学会使用贪心法解决实际3.实验的基本仪器设备和耗材PC机一台。实验四 回溯法1.实验的基本内容用回溯法实现下列程序中的一个：n个皇后问题，最大团问题，图的m着色问题，旅行售货员问题，圆排列问题，连续邮资问题，电路板排列问题。2.实验的基本要求掌握回溯法解决问题的一般步骤，学会使用回溯法解决实际问题。3.实验的基本仪器设备和耗材PC机一台。实验五 分支限界法1.实验的基本内容用分支限界法实现下列程序中的一个：单源最短路径，布线问题，01背包问题，批处理作业调度问题。2.实验的基本要求掌握分支限界法解决问题的基本思想，学会使用分支限界法解决实际问题。3.实验的基本仪器设备和耗材PC机一台。六、实验的考核与成绩评定以实际操作能力为主，参考提问和出勤情况等，综合评定给出成绩。七、主要参考书推荐使用由电子工业出版社出版，王晓东主编的21世纪高等学校计算机学科系列教材的计算机算法设计与分析教材。主要参考书目：张铭、刘晓丹译电子工业出版社出版的数据结构