算法分析与设计(2014教学大纲).doc

《》课程教学大纲（学时） （理论课程） 一 课程说明 （一）课程概况 课程中文名称： 课程英文名称：Design and Analysis of Algorithms 课程编码：3810432112 开课学院： 适用专业/开课学期： 学分/周学时： 本课程是计算机科学与技术专业主干必修课程。通过对计算机算法系统的学习与研究，理解和掌握算法设计的主要方法，培养对算法的计算复杂性进行正确分析的能力，为独立地设计算法和对给定算法进行复杂性分析奠定坚实的理论基础。这些对以后从事计算机系统结构、系统软件和应用软件研究与开发的工作都是非常重要和必不可少的。 要求学生先修：高级语言程序设计，高等数学，离散数学，数据结构等课程；后修课程程序设计技巧与实践，人工智能。 （二）目 章（专题） 主要内容 理论学时 实验实践学时 1 6 0 2 分治法 10 4 3 贪心方法 8 8 4 动态规划 8 4 合计 32 16 （三）分配 二 教学方法和手段 三 教学内容 第?部分 导引与基本数据结构?（学时） 一、教学二、教学重、难点 三、主要内容 四、实践要求 第????分治法（学时） 一、教学二、教学重、难点 三、主要内容 四、实践要求 五、练习作业 四、实践要求 实验三：贪心法求解背包问题 1、 实验项目名称：贪心法求解背包问题 2、 实验类型：设计性 3、 学时分配：4学时 4、 每组人数：1人 5、 实验内容及要求：有一个背包容量为M ，输入N个物品，每个物品有重量W ，以及物品放入背包中所得的收益。问选择放入的物品，不超过背包的容量，且得到的收益最好。 实验四：贪心法求最短路径 1、 实验项目名称：贪心法求最短路径 2、 实验类型：设计性 3、 学时分配：4学时 4、 每组人数：1人 5、 实验内容及要求：已知图G(V,E) ，边的权值矩阵C，求某点到其他各点的路径最短。 五、练习作业 完成课后练习 第四部分 动态规划 （12学时） 一、教学目标 通过本部份的学习，使学生理解并掌握动态规划的一般方法，理解用动态规划解决多段图、每对结点之间的最短路径、最优二分检索树等问题的算法。 二、教学重、难点 教学重点是动态规划的一般方法、最优二分检索树、0/1背包问题、可靠性设计。教学难点是多段图、最优二分检索树、流水线调度问题。 三、主要内容 一般方法、多段图、每对结点之间的最短路径、最优二分检索树、0/1背包问题、可靠性设计、货郎担问题、流水线调度问题。 四、实践要求 实验五：使用动态规划算法求解0/1背包问题 1、 实验项目名称：使用动态规划算法求解0/1背包问题 2、 实验类型：设计性 3、 学时分配：4学时 4、 每组人数：1人 5、 实验内容及要求：有一个背包容量为M，输入个物品N，每个物品有重量W，以及物品放入背包中所得的收益。问选择放入的物品，要么全部放入，要么不放，不超过背包的容量，且得到的收益最好。 五、练习作业 完成课后练习 四 考核办法 考核方式闭卷 评分办法平时成绩占%，考占%。 五 教材及主要参考书教材参考书目执笔： 参与：*** 审核：*** ：*** 制定日期：201年月 1