《算法分析与设计》教学大纲

《算法分析与设计》教学大纲课程编号：13220507英文名称：Design&AnalysisofAlgorithms学分：3学时：总学时64学时，其中理论32学时，实践32学时先修课程：高级语言、数据结构课程类别：专业拓展课授课对象：计算机科学与技术专业学生教学单位：机械与电气工程学院修读学期：第5学期一、课程描述和目标 本课程是一门理论性与实践性兼顾的课程，是计算机科学与技术专业拓展课程,理论性和实践性都很强，既要掌握基本算法设计与实现方法，还要理论分析这些算法的时间与空间复杂度。通过本课程的学习，使学生具备较扎实的算法设计与分析知识和方法；使学生掌握基本的算法分析方法和常见的算法设计方法；理解计算机算法效率分析与设计所涉及的基本概念和基础知识。通过对算法实例的分析，进一步加深对算法设计方法的认识和理解。通过学习本课程，达到以下课程目标：课程目标1：学习算法设计的常见的主要方法，掌握理解算法分析的相关概念和基本方法，培养算法设计和分析的初步能力。课程目标2：能根据实际问题选择合适的数据逻辑结构和存储结构，能运用算法设计与分析的相关知识设计和分析求解实际问题的算法，对复杂工程问题具有一定的算法设计与分析能力，能熟练应用课程介绍的算法设计方法来解决软件开发中的实际问题。课程目标3：能应用算法性能分析方法对算法性能进行分析研究，能有针对性地设计实验，并通过实验数据对算法性能进行分析。二、课程目标对毕业要求的支撑关系毕业要求指标点课程目标权重指标点4-2：能够根据计算机相关领域的复杂工程问题的研究对象及其特征，制定研究方法和技术路线，设计实验方案。课程目标1课程目标2课程目标3H指标点5-3：能够针对具体系统模块，开发或选用满足特定需求的现代工具，模拟、预测计算机软硬件系统在设计与实施等过程中的专业问题，并能够分析其局限性。课程目标1课程目标2课程目标3M

三、教学内容、基本要求与学时分配序号教学内容基本要求及重、难点（含德育要求）学时教学方式对应课程目标1算法概述：算法和程序；算法复杂性；算法效率；NP完全性理论。理解算法的概念、算法的时间复杂性和空间复杂性；掌握求解问题的基本步骤；掌握算法运行时间的估计；NP完全理论。德育要求：培养勇于探索的科学精神。2讲授式讨论式课程目标1课程目标22递归与分治策略：递归的概念；分治法的基本思想；二分搜索技术；大整数的乘法；strassen矩阵乘法；棋盘覆盖；合并排序；快速排序；线性时间选择；最接近点对问题；循环赛日程表。理解掌握递归的概念与的基本原理；理解分治策略的基本原理和效率分析，掌握设计有效算法的分治策略。德育要求：培养严谨踏实的科学态度。6讲授式启发式探究式讨论式练习式课程目标1课程目标2课程目标33动态规划：矩阵连乘问题；动态规划算法的基本要素；最长公共子序列；最大子段和；凸多边形最优三角剖分；多边形游戏；图像压缩；电路布线；流水作业调度；0-1背包问题；最优二叉搜索树。理解动态规划算法的概念；掌握动态规划算法的基本要素；掌握设计动态规划算法的步骤以及典型问题的应用与分析。德育要求：培养刻苦钻研的科学精神。4讲授式启发式探究式讨论式练习式课程目标1课程目标2课程目标34贪心算法：活动安排问题；贪心算法的基本要素；最优装载；哈夫曼编码；单源最短路径；最小生成树；多机调度问题。理解贪心算法的基本思想、适用条件；掌握贪心算法的设计策略，掌握贪心算法典型问题的应用与分析。德育要求：养成脚踏实地、精益求真的习惯；获取奋发向上、探索创新的精神动力。4讲授式讨论式练习式课程目标1课程目标2课程目标35回溯法：回溯法的算法框架；装载问题；批处理作业调度；符号三角形问题；n后问题；0-1背包问题；最大团问题；图的m着色问题；旅行售货员问题；圆排列问题；电路板排列问题；连续邮资问题；回溯法的效率分析。理解回溯法的基本思想及效率估计，限界函数；掌握回溯法在典型问题的应用及分析。德育要求：树立爱国情怀、文化自信；获取奋发向上、探索创新的精神动力。4讲授式启发式探究式讨论式练习式课程目标1课程目标2课程目标36分支限界法：分支限界法的基本思想；单源最短路径问题；装载问题；布线问题；0-1背包问题；最大团问题；旅行售货员问题；电路板排列问题；批处理作业调度。理解分支限界法的基本思想及效率估计；掌握分支限界法的算法框架；掌握分支限界法在典型问题的应用。德育要求：体会勤奋学习、洞察研究的价值；获取奋发向上、探索创新的精神动力。4讲授式启发式探究式讨论式练习式课程目标1课程目标2课程目标37随机化算法：随机数；数值随机化算法；舍伍德(Sherwood)算法；拉斯维加斯(LasVegas)算法；蒙特卡罗(MonteCarlo)算法。理解产生伪随机数的算法；掌握数值概率算法的设计思想；掌握蒙特卡罗算法、拉斯维加斯算法和舍伍德算法的设计思想。德育要求：坚定家国情怀和助力中国梦的信念；获取奋发向上、探索创新的精神动力。4讲授式启发式探究式讨论式练习式课程目标1课程目标2课程目标38线性规划与网络流：线性规划问题和单纯形算法；最大网络流问题；最小费用流问题。理解线性规划算法的模型，理解网络与网络流的基本概念；掌握线性规划问题的单纯形算法；掌握网络最大流的增广路算法与预流推进算法；掌握网络最小费用流的消圈算法、最小费用路算法与单纯形算法。德育要求：树立正确的世界观、价值观、人生观；获取奋发向上、探索创新的精神动力。4讲授式启发式探究式讨论式练习式课程目标1课程目标2课程目标3合计32序号实验项目实验内容与要求学时类型对应课程目标1递归与分治策略实验内容：（1）递归算法；（2）分治算法；（3）用递归和分治算法求解问题。实验要求：必修。6设计课程目标1课程目标2课程目标32动态规划法实验内容：（1）动态规划基本要素；（2）设计动态规划算法的步骤；（3）用动态规划算法求解问题。实验要求：必修。4设计课程目标1课程目标2课程目标33贪心算法实验内容：（1）贪心算法基本要素；（2）贪心设计策略；（3）用贪心算法求解问题。实验要求：必修。4设计课程目标1课程目标2课程目标34回溯法实验内容：（1）回溯法基本框架；（2）回溯法设计策略；（3）用回溯法求解问题。实验要求：必修。4设计课程目标1课程目标2课程目标35分支限界法实验内容：（1）分支限界法的基本思想；（2）剪枝搜索策略；（3）分支限界法基本框架。（4）用分支限界法求解问题。实验要求：必修。4设计课程目标1课程目标2课程目标36随机化算法实验内容：（1）伪随机数生成算法；（2）随机算法的设计思想；（3）用蒙特卡罗算法求解问题。实验要求：必修。4设计课程目标1课程目标2课程目标37线性规划与网络流实验内容：（1）线性规划问题与单纯形算法；（2）最大网络流问题求解算法；（3）最小费用流问题求解算法。实验要求：必修。6综合课程目标1课程目标2课程目标3合计32四、课程教学方法课堂讲授与小组讨论相结合；集中讲授与探究式教学及翻转课堂相结合；采用讲授式、启发式、探究式、讨论式和练习式等教学方式。五、学业评价和课程考核（一）考核方式及具体要求序号考核方式课程目标1（分值）课程目标2（分值）课程目标3（分值）合计1平时作业244102课程实验253103课堂表现253104期末考试15352070课程目标对应分值214930100（二）考核与评价标准1.平时作业考核与评价标准分值观测点90-100分70-89分60-69分0-59分作业按时完成，90%以上的作业内容齐全，基本知识点理解、掌握到位。能够利用理论知识设计算法求解具体问题并分析算法复杂度。按时完成，70%以上的作业内容齐全，基本知识点理解、掌握得较为到位。能够较好地利用理论知识设计算法求解具体问题并分析算法复杂度。延时完成，60%以上作业内容齐全，基本知识点理解、掌握得基本到位。基本能够利用理论知识设计算法求解具体问题并分析算法复杂度。不交和补交，50%以下作业内容齐全，基本知识点理解、掌握有偏差。基本不能利用理论知识设计算法求解具体问题并分析算法复杂度。2.课程实验考核与评价标准分值观测点90-100分70-89分60-69分0-59分课程实验能根据实验要求自主设计实验方案，有自己的设计理念，实验完成度高，效果好。算法复杂度分析正确。实验报告内容完整。能根据实验要求自主设计实验方案，有自己的设计理念，实验完成度较高，效果较好。算法复杂度分析比较正确。实验报告比较完整。能根据实验要求自主设计实验方案，实验完成度一般，效果一般。算法复杂度分析基本正确。实验报告基本完整。基本能根据实验要求自主设计实验方案，实验完成度较差，效果较差。算法复杂度分析不正确。实验报告不完整。3.线下表现与评价标准根据回答问题、课堂表现及团队合作等情况及评分标准评分（百分制）。4.期末考试与评价标准根据期末考试及评分标准评分（百分制）。六、教材与参考书（一）推荐教材《计算机算法设计与分析（第5版）》，王晓东主编，电子工业出版社，2018年8月版。（二