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

算法分析与设计课程教学大纲（48学时）（理论课程）一 课程说明（一）课程概况课程中文名称：算法分析与设计课程英文名称：Design and Analysis of Algorithms课程编码：3810432112开课学院：信息工程学院适用专业/开课学期：计算机科学与技术学分/周学时：3/3本课程是计算机科学与技术专业主干必修课程。通过对计算机算法系统的学习与研究，理解和掌握算法设计的主要方法，培养对算法的计算复杂性进行正确分析的能力，为独立地设计算法和对给定算法进行复杂性分析奠定坚实的理论基础。这些对以后从事计算机系统结构、系统软件和应用软件研究与开发的工作都是非常重要和必不可少的。要求学生先修：高级语言程序设计，高等数学，离散数学，数据结构等课程；后修课程程序设计技巧与实践，人工智能。（二）课程目标通过本课程的学习，使学生理解和掌握算法设计的主要方法，培养学生对算法复杂性进行正确分析的基本能力，为独立地设计求解问题的最优算法和对给定算法进行复杂性分析奠定坚实的基础。章（专题）主要内容理论学时实验实践学时1导引与基本数据结构602分治法1043贪心方法884动态规划84合计3216（三）学时分配二 教学方法和手段教学手段为传统教学方式和课后作业相结合的方法。在课堂教学中，多采用黑板粉笔讲述算法描述和存储描述，反映出算法的思维过程。用任务驱动模式，通过问题解决的过程，培养学生自主分析问题和解决问题的能力。注重采用启发式教学，运用课堂提问和课堂讨论的方式。 三 教学内容第一部分 导引与基本数据结构（6学时）一、教学目标通过本部分的学习，使学生理解算法的概念及其特性，学会分析算法的一般方法，掌握计算机科学中常用的数据结构，了解相关描述算法所用的语言。二、教学重、难点教学重点是算法及分析算法，教学难点是递归和消去递归。三、主要内容算法的定义、分析算法、用SPARKS语言写算法、基本数据结构、递归和消去递归。四、实践要求无五、练习作业完成课后练习第二部分分治法（14学时） 一、教学目标通过本部分的学习，使学生理解分治法的内涵，然后从解决计算机科学和应用中出现的几个实际问题入手，用二分法的基本思想描述了几个经典的精巧的算法，包括二分检索算法、分类算法、选择算法等，同时对每个算法给出了数量级的分析，以使学生理解本部分介绍的算法，并能用于解决实际问题。二、教学重、难点教学重点是分治法的一般方法、归并分类和快速分类算法。，教学难点是快速分类算法、选择问题算法。三、主要内容分治法的一般方法、分治检索、找最大和最小元素、归并分类、快速分类、选择问题、斯特拉森矩阵乘法。四、实践要求实验一：分治法1、实验项目名称：分治法2、实验类型：设计性3、学时分配：2学时4、每组人数：1人5、实验内容及要求：用分治法查找数组元素的最大值和最小值实验二：分治与递归1、实验项目名称：分治与递归2、实验类型：设计性3、学时分配：2学时4、每组人数：1人5、实验内容及要求：用分治法实现归并排序算法五、练习作业完成课后练习第三部分 贪心方法（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，以及物品放入背包中所得的收益。问选择放入的物品，要么全部放入，要么不放，不超过背包的容量，且得到的收益最好。五、练习作业完成课后练习四 考核办法（一）考核方式：闭卷（二）评分办法：平时成绩占50%，期末考核占50%。期末总评成绩由以下三个方面构成：1）期末考试成绩，占总评成绩的50%。2）平时表现，占总评成绩的30%。根据随堂提问，作业抽查中的学生表现给分。3）期中成绩，占总评成绩的20%。 五 教材及