《算法分析与设计》理论教学大纲.docx

算法分析与设计理论教学大纲(Analysis and Design of Algorithms)课程代码：0610008总学时：48学时(其中：讲课33学时、实验15学时)先修课程：C语言程序设计、Python程序设计、数据结构一、课程的性质、目的与任务算法分析与设计是数据科学与大数据技术专业的一门核心课程。通过对计算机算法 的系统学习与研究，使学生理解和掌握算法设计的主要方法，培养学生对算法复杂性进 行分析的初步能力，为设计问题的求解算法和对给定算法进行复杂性分析奠定基础，对 每一位从事计算机系统结构、系统软件和应用软件设计与开发的科技工作者是非常重要 和必不可少的。二、教学基本内容与基本要求1 .基本内容本课程基本内容是：递归算法，分治算法，贪心算法，动态规划算法，回溯算法， 分支限界算法，概率算法。2 .基本要求要求学生掌握算法的概念、性质，常用算法的设计思路，算法时间复杂性的分析方 法，能用计算机语言熟练地实现常用算法。具有解决实际问题的基本能力。三' 教学内容及学时分配教学内容教学 要求重点 ()难点 ()学时 安排备注第1章 算法及基础知识1.算法的基本概念B2.算法设计的一般过程B33.算法分析B4.基本的数据结构AA第2章 递归与分治算法1.概述B2.递归算法A3.分治算法的基本思想A4.二分搜索技术A65. Strassen矩阵乘法CA6.合并排序A7.快速排序AA8.循环赛日程表BA第3章贪心算法1.概述B2.活动安排问题A3.贪心算法的基本要素A64.哈夫曼编码BA5.单源最短路径AA6.最小生成树AA第4章动态规划算法1.概述B2.动态规划算法的基本要素A3.矩阵连乘问题A64.最长公共子序列AA5.流水线作业调度BA6. 0-1背包问题AA第5章回溯算法1.概述B2.回溯算法的框架A43.装载问题AA4.批处理作业调度BA5. N皇后问题A第6章 分支限界算法1.概述B2.分支限界算法的基本思想A43.单源最短路径问题AA4.装载问题BA（教学要求：A一熟练掌握；B一掌握；C了解）第7章概率算法1 .概述2 .随机数3 .数值概率算法4 .舍伍德算法5 .拉斯维加斯算法BAABB AA4合计33四、建议实验项目及学时分配序 号实验项目名称实验 学时内容提要实验 要求实验 类型1分治算法2熟悉分治算法的设计策略，能熟练运 用分治算法解决信息搜索问题、数据 排序问题、一元方程实根近似值求解 问题等。必做验证2贪心算法2熟悉贪心算法的设计策略，能熟练运 用贪心算法解决背包问题、最小生成 树问题,Huffman编码问题等。必做验证3动态规划算法2熟悉动态规划算法的设计策略，能熟 练运用动态规划算法解决最长公共子 序列问题、矩阵连乘问题、0T背包问 题等。必做验证4回溯算法2熟悉回溯算法的设计策略，能熟练运 用回溯算法解决0T背包问题、旅行 商问题、N皇后问题等。必做验证5分支限界算法2熟悉分支限界算法的设计策略，注意 分支限界算法与回溯算法的区别，能 熟练运用分支限界算法解决0-1背包 问题、旅行商问题、N皇后问题等。必做验证6概率算法2熟悉概率算法的设计策略、线性同余 法产生随机数的方法，能熟练运用概 率算法求圆周率、无理数e和定积分 近似值的计算等。必做验证7（设计性实验）3（另见设计性实验项目教学大纲）必做设计合计15五、教学方法与教学手段1 .教学方法：在课堂教学中，以实际问题为导向，采用启发引导、综合分析，讨 论交流等教学方法，调动学生的学习积极性和学习兴趣，促进教学相长，提高教学质量。2 .教学手段：利用多媒体、CAI课件等现代化教学手段，采取讲练结合、理论联系 实际等方式，提高课堂教学效果。六、建议教材与参考书目1 .建议教材：算法设计与分析，王秋芬、吕聪颖、周春光编著，清华大学出版社，20H年8 月。2 .参考书目：算法设计与分析，屈婉玲、刘田、张立昂、王捍贫编著，清华大学出版社， 2011年5月。计算机算法设计与分析（第4版），王晓东编著，电子工业出版社，2012年2 月。算法设计与分析，张德富编著，国防工业出版社，2009年8月。七、成绩计算方法课程总成绩按百分制计算，其中：平时成绩（作业和考勤）占20%,实验成绩占 20%、期末考试成绩占40%。八、大纲编写的依据与说明本课程教学大纲是依据普通高等学校本科专业目录和专业介绍（2012年）（中华 人民共和国教育部高等教育司编，高等教育出版社）中的教学指导意见，根据数学与 计算机学院制定的数据科学与大数据技术专业应用型人才培养方案，结合本课程的性 质、地位、教学内容和基本要求来编写的。突出了算法和数据结构的关系，注重培养学 生分析和解决实际问题的能力。