算法设计与分析 课程大纲 许瑾晨

算法设计与分析教学大纲课程代码：课程名称（中/英）：算法设计与分析/DesignandAnalysisofAlgorithms学分：2总学时：40理论学时：30实验学时：10课程类别：必修开课学期：3或4适用专业：计算机科学与技术、网络安全、网络工程等相关专业课程性质：专业核心类先修课程：C语言程序设计、离散数学、数据结构开课单位：信息工程大学网络空间安全学院大纲版本：制定（修订）人：审核人：大纲批准人：制定（修订）时间：审核时间：批准时间：一、课程简介本课程是计算机相关专业的专业核心课程。二、课程目标（一）课程具体目标1.知识目标：通过本课程的学习，使学生了解评价和分析算法优劣的方法，2.能力目标：提高学生评价算法优劣的能力，对算法时间复杂度进行正确的3.素质目标：通过本课程学习，增强学生科技报国的爱国情怀，培养学生攻坚克难、追求卓越的科研精神，拓展学生缜密辩证、崇尚科学的思维方法。（二）教学内容安排总体思路本课程的教学内容，以课程具体目标为总体指导进行制定。NPPNPNPCNPC三、教学内容及基本要求（一）算法概述（4）主要内容：（1）算法相关的基本概念（2）算法时间复杂度的分析方法（3）算法的数学基础1.基本要求（1）掌握算法、时间复杂度的基本概念及时间复杂度的分析方法。（2）掌握算法中常用的求和方法，递推方程的求解方法。2.重点、难点重点：算法的定义和特征，评价算法的准则，算法时间复杂度的分析方法，渐进时间复杂度，递推方程的求解方法。难点：算法时间复杂度的分析。3．作业及课外学习要求作业：根据具体问题或求解代码，分析算法的时间复杂度。（二）分治策略（642）主要内容：（1）分治策略的基本思想、求解步骤和代码框架（2）分治法的时间复杂度分析方法1.基本要求（1）熟练掌握递归与分治策略的基本思想和时间复杂度分析方法。（2）熟练掌握递归与分治算法的典型应用的求解。（3）能够利用分治法解决实际问题并会对算法的时间复杂度进行分析。2.重点、难点重点：分治策略的基本思想，典型应用的求解，分治法的时间复杂度分析。难点：大整数乘法，Strassen矩阵乘法，分治法的优化。3．作业及课外学习要求课外学习要求：查阅快速傅里叶变换的相关知识。4．实践课内容实践名称：递归与分治（2学时）实践内容：通过重要逆序对、最大次大项等问题考察学生利用递归和分治方法解决实际问题的能力。（三）动态规划（862）主要内容：（1）动态规划的设计思想（2）动态规划的两个重要性质0-11.基本要求（最优子结构和重叠子问题）和解题步骤。（2）熟练掌握动态规划的两种求解方法：备忘录和自底向上。（3）熟练掌握动态规划的典型应用的求解。（4）掌握动态规划空间优化的方法。（5）能够利用动态规划解决实际问题。2.重点、难点重点：动态规划的设计思想、两个重要性质和解题步骤，动态规划与分治的区别，典型应用的求解，空间优化的方法。难点：针对具体应用，给出问题的合适定义，确定问题和子问题最优值的关系。3．作业及课外学习要求4．实践课内容实践名称：动态规划（2学时）实践内容：通过编辑距离、线性石子合并和环形石子合并等问题考察学生利用动态规划方法解决实际问题的能力。（四）贪心算法（642）主要内容：（1）贪心法的设计思想和两个重要性质（2）贪心法的正确性证明1.基本要求（1）熟练掌握贪心法的设计思想和两个重要性质。（2）了解贪心法的正确性证明方法。（3）熟练掌握贪心法的典型应用的求解。（4）能够利用贪心法解决实际问题。2.重点、难点重点：贪心法的设计思想，贪心选择性质，贪心与动态规划的区别，典型应用的求解。难点：贪心法的正确性证明。3．作业及课外学习要求4．实践课内容实践名称：贪心算法（2学时）实践内容：通过田忌赛马、最优分解等问题考察学生利用贪心算法解决实际问题的能力。（五）回溯法（642）主要内容：（1）回溯法的基本思想和适用条件（2）两种典型的解空间树：排列树和子集树（3）回溯法的典型应用：0-1N1.基本要求（1）熟练掌握回溯法的基本思想。（2）熟练掌握排列树和子集树的代码框架。（3）熟练掌握回溯法的典型应用。（4）能够利用回溯法解决实际问题。2.重点、难点重点：回溯法的基本思想，排列树和子集树的代码框架，剪枝函数，典型应用的求解。难点：根据具体问题设计合适的剪枝函数。3．作业及课外学习要求4．实践课内容实践名称：回溯法（2学时）实践内容：24（六）分支限界法（2学时）主要内容：（1）分支限界法的基本思想（2）限界函数的设计（3）分支限界法的典型应用：0-1背包问题、旅行售货员等问题。1.基本要求（1）熟练掌握分支限界法的基本思想。（2）了解分支限界的典型应用的求解方法。2.重点、难点重点：分支限界法的基本思想，限界函数的设计，典型应用的求解。难点：根据具体问题设计合适的剪枝函数。3．作业及课外学习要求（七）NP（862）主要内容：（1）P类与NP类问题的概念（2）多项式时间变换与NP完全性（3）几个典型的NP完全问题（4）概率算法（5）综合应用：最大子段和问题、资源分配问题、最短路径问题等1.基本要求PNPNPNP（2）了解常见的NP完全问题。（3）了解概率算法。2.重点、难点重点：NP完全理论的相关概念，概率算法，综合应用的多种求解方法。难点：NP完全问题的证明。3．作业及课外学习要求4．实践课内容实践名称：综合应用（2学时）实践内容：通过选择一个典型应用，考察学生分析问题、用多种算法求解以及分析算法优劣的能力。四、教学安排及教学方式总学时40学时，其中，讲授30学时，实践（上机）10学时。序号课程内容讲授学时上机学时教学方式序号课程内容讲授学时上机学时教学方式1算法概述4讲授2分治4讲授3实验一：递归与分治实践2上机4动态规划6讲授5实验二：动态规划实践2上机6贪心法4讲授7实验三：贪心法实践2上机8回溯法4讲授9实验四：回溯法实践2上机10分支限界法2讲授11NP完全理论、概率算法、综合应用6讲授12实验五：综合应用实践2上机合计301040五、考核方式与成绩评定办法10%3~5实验成绩：10%。主要考核学生在实践课堂上的题目完成情况，根据课堂完（和解题报25期末考试成绩：70%。主要考核对算法基础知识、算法的时间复杂度分析方六、教材及其他教学资源（一）课程教材（python（二）推荐参考资料1（5，王晓东编著，电子工业出版社，20182（320233