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

PAGE 1 PAGE 3 《算法设计与分析》实验课程教学大纲 课程编号 课程名称：算法设计与分析 / The Design and Analysis of Computer Algorithms 课程属性：必修 实验属性：非独立设课 开课学期：6 学 时：16 适用专业：计算机科学与技术 　　　　 学 分：3.5 开课部门：数计学院 考核要求：考查 课程简介： 《算法设计与分析》课程主要学习和掌握几种基本的算法：分治算法、动态规划、贪心算法、回溯法、分支限界法，掌握算法设计的基本思想和策略、算法优化的技巧、算法性能分析的方法。本课程着重于培养学生的算法设计与分析能力，程序设计和实现能力，培养学生分析问题和解决问题的能力，使学生掌握算法设计的基本方法，熟悉算法分析的基本技术，并能熟练运用一些常用算法，为学生进一步学习奠定良好的基础。 一、实验项目设置及学时分配 项目编号 实验项目名称 实验 类型 开出 要求 学时 分配 1 蛮力法程序设计 验证型 必做 2 2 分治法程序设计 验证型 必做 4 3 动态规划程序设计 验证型 必做 4 4 贪婪法程序设计 验证型 必做 2 5 回溯法程序设计 验证型 必做 4 学时总计 16 二、实验内容及教学要求 实验项目1：蛮力法程序设计 1、教学内容 用蛮力法编程，解决字符串匹配问题 用蛮力法打印1、2、3、4的全排列 2、教学目标 （1）掌握蛮力法的编程方法 （2）学会用蛮力法进行程序设计 实验项目2：分治法程序设计 1、教学内容 用分治法编程，解决找最大值和最小值问题 用分治法编程，对数组元素进行快速排序、归并排序 用分治法思想进行编程，解决找第K大数的问题 用分治法对棋盘覆盖问题进行编程 2、教学目标 （1）掌握分治法的基本思想和方法 （2）学会用分治法进行程序设计 实验项目3：动态规划程序设计 1、教学内容 用动态规划解决0-1背包问题 用动态规划解决矩阵连乘问题 用动态规划解决找零钱问题 用动态规划解决最长公共子序列问题 2、教学目标 （1）掌握动态规划算法的基本思想和方法 （2）掌握设计动态规划算法的步骤 实验项目4：贪心法程序设计 1、教学内容 用贪心算法解决找零钱问题 用贪心算法解决部分背包问题 用贪心算法解决活动选择问题 2、教学目标 （1）掌握贪心算法的基本思想和编程方法 （2）学会用贪心算法来编程解决问题 实验项目5：回溯法程序设计 1、教学内容 用回溯法解决八皇后问题 用回溯法解决0-1背包问题 用回溯法解决走迷宫问题 用回溯法解决骑士巡游问题 用回溯法解决数字全排列问题 2、教学目标 （1）掌握回溯法的基本思想和方法 （2）学会用回溯法进行程序设计 三、考核方式及要求 和理论课一起算成绩，实验占总成绩的20%。 四、主要仪器设备及实验材料 项目编号 实验项目名称 主要仪器设备 及台（套）数 实验材料 备注 1 蛮力法程序设计 电脑一台 2 分治法程序设计 电脑一台 3 动态规划程序设计 电脑一台 4 贪婪法程序设计 电脑一台 5 回溯法程序设计 电脑一台 五、教材及参考书 王红梅编，《算法设计与分析（第2版）》，清华大学出版社，2013年 王晓东主编，《计算机算法设计与分析（第4版）》，电子工业出版社，2012年