算法分析教学大纲

算法设计与分析DesignandAnalysisofAlgorithms适用范围：2018本科人才培养方案课程编号：0604808150学分：3学分学时：52学时（其中：讲课学时：40；实验学时：12）开课学期：5先修课程：程序设计基础、离散数学、数据结构适用专业：计算机科学与技术建议教材：《算法设计与分析》，王秋芬等主编，清华大学出版社，2011开课单位：计算机与信息工程学院大纲版本：1一、课程性质、任务课程性质：算法的设计与分析属于专业平台必修课，是计算机科学的核心问题之一。算法涉及的范围十分广泛，不论是从事计算机硬件设计，还是从事计算机软件设计，都需要认真研究算法。该课程系统地介绍计算机算法的设计方法与分析技巧，通过课程学习，为独立地设计算法和对算法进行分析奠定坚实的知识基础，对从事计算机软件和计算机应用的研究者来说是非常重要和必不可少的。课程任务：通过学习该课程，使学生在知识方面要求：掌握算法的定义及基本概念、计算模型和复杂度的衡量；为分析算法的复杂性做准备，要了解相应的数学知识；掌握算法设计的过程和方法；掌握算法的时间复杂度、空间复杂度和稳定性的分析；具有问题抽象和建模的初步能力。在能力方面要求：通过本课程的学习，学生要掌握几种常用的算法设计策略，包括递归与分治策略、动态规划算法、贪心算法、回溯法、分支限界法概率算法、线性规划和网络流法和NP完全性理论与近似算法等，并会分析算法的效率，能够用所学方法解决实际问题。算法设计与分析能够有效锻炼学生的逻辑思维能力和想象力，更重要的是培养学生的创造性思维能力；培养学生在理论的指导下，分析、解决实际问题的能力。这正是计算机科学与技术专业培养目标的核心所在。二、课程目标（一）课程具体目标目标1：掌握算法设计与分析的专业知识，具有应用数学、算法及计算机的基本原理，能将其用于计算机复杂工程问题模型的实现。目标2：能基于算法设计与分析的专业知识，具备针对计算机应用领域复杂工程问题的关键环节进行分析、设计及优化等工程实践活动的能力；目标3：针对计算机复杂工程问题，能够基于算法设计与分析方法，通过调研和分析，设计合适的研究方案。（二）课程目标与专业毕业要求的关系本课程对专业毕业要求及其指标点的支撑课程目标支撑的毕业要求支撑的毕业要求指标点目标1毕业要求1：能够将数学、自然科学、工程基础和计算机科学与技术专业知识用于解决计算机工程领域内的复杂工程问题。指标点1-2：掌握算法分析与程序设计等计算机科学与技术专业知识，能将其用于计算机复杂工程问题模型的实现。目标2毕业要求2：能够应用数学、自然科学和工程科学的基本原理，识别、表达、并通过文献研究分析计算机工程领域的复杂工程问题，以获得有效结论。指标点2-3：能够基于数学、自然科学和计算机科学与技术的基本原理，对计算机复杂工程问题进行提炼、定义、建模、分析和评价。目标3毕业要求4：能够基于计算机学科相关的原理并采用科学方法对计算机工程领域的复杂工程问题进行研究，包括设计实验、分析与解释数据，并通过信息综合得到合理有效的结论。指标点4-1：针对计算机复杂工程问题，能够基于计算机学科原理，通过调研和分析，设计合适的研究方案。（三）课程对解决复杂工程问题能力的培养在课程理论知识讲授环节，不但注重培养学生对算法设计与分析的深入理解，使学生掌握解决计算机应用领域复杂工程问题所需的基本理论以及了解相关技术对社会等的影响，而且跟踪行业发展前沿，探讨当前热点问题激发学生的学习兴趣。并通过适当的课后作业锻炼和检验学生解决复杂工程问题的能力。在实验教学环节，以培养学生解决复杂工程问题的能力为目标，围绕课程支撑的课程目标安排实验项目，设计实验内容，明确实验要求，指导实验实施，严格实验成果考核。在课程考核环节，根据课程支撑的课程目标选择合适的考核方式，考题设置完全覆盖课程目标，考题设计应充分考虑学生解决复杂工程问题所需知识和能力。总之，本课程的教学通过在理论讲授、课后作业、课内实验、课程考核等环节充分贯彻培养学生解决复杂工程问题能力的理念和要求，实现本课程支撑课程目标的达成。三、课程教学内容及基本要求（一）理论教学第1章算法概述（4学时）1．教学内容（1）算法的基本概念。（2）算法设计的一般过程。（3）算法分析的概念及渐进意义下的记号。（4）时间复杂度和空间复杂度建立的依据。（5）递推方程求解方法。2．基本要求（1）理解算法的基本概念、复杂度的衡量。（2）掌握渐进复杂的概念及渐进意义下的记号。（3）掌握时间复杂度建立的依据和递推方程求解的方法。3．支撑的课程目标本章各知识点的讲授和学习，可以支撑“课程目标1：掌握算法设计与分析的专业知识，具有应用数学、算法及计算机的基本原理，能将其用于计算机复杂工程问题模型的实现”，使学生了解算法的基本概念、复杂度的衡量，掌握渐进复杂的概念及渐进意义下的记号，掌握时间复杂度建立的依据和递推方程求解的方法，为解决实际工程问题奠定基础。替代式教学策略和案例教学法，让学生理解算法的基本概念及算法复杂度的分析方法，掌握渐进复杂度表示及递推方程求解方法。第2章贪心算法（6学时）1．教学内容（1）贪心法的基本思想及基本要素。（2）会场安排问题、最优装载问题。（3）单源最短路径问题。（4）哈夫曼编码。（5）最小生成树。（6）背包问题2．基本要求（1）了解贪心法的应用范围，理解贪心法的基本思想、特点。（2）掌握典型问题的精巧贪心算法（如会场安排问题、最短路径问题的Dijkstra算法、求最小生成树的Kruskal算法和Prim算法等）的基本思想，能利用贪心算法解决实际工程中遇到的问题。通过这些应用，掌握使用贪心策略设计算法的关键步骤、熟悉算法的分析方法及算法正确性的证明方法。3．支撑的课程目标本章各知识点的讲授和学习，可以支撑“课程目标1：掌握算法设计与分析的专业知识，具有应用数学、算法及计算机的基本原理，能将其用于计算机复杂工程问题模型的实现”、“课程目标2：能基于算法设计与分析的专业知识，具备针对计算机应用领域复杂工程问题的关键环节进行分析、设计及优化等工程实践活动的能力”、“课程目标3：针对计算机复杂工程问题，能够基于算法设计与分析方法，通过调研和分析，设计合适的研究方案”。使学生了解贪心算法的基本思想，掌握典型问题的精巧贪心算法，能利用贪心算法解决实际工程中遇到的问题。启发式和任务驱动相结合，让学生算法设计的过程及算法复杂度的分析方法，掌握贪心法的基本要素，如何使用贪心法解决实际问题。采用任务驱动，充分调动学生的积极性。第3章分治算法（6学时）1．教学内容（1）分治法基本思想。（2）分治法的求解步骤。（3）二分查找。（4）选第二大元素。（5）循环赛日程表。（6）合并排序。（7）快速排序。（8）线性时间选择。2．基本要求（1）了解分治法的适用范围，理解其基本思想、特点。（2）掌握设计分治算法的基本步骤；掌握使用分治策略设计的典型问题的精巧算法（如二分搜索算法、排序算法、选择问题算法等）。（3）理解算法的设计思想、分析方法及复杂度结论，能在给定问题实例上模拟算法的执行。3．支撑的课程目标本章各知识点的讲授和学习，可以支撑“课程目标1：掌握算法设计与分析的专业知识，具有应用数学、算法及计算机的基本原理，能将其用于计算机复杂工程问题模型的实现”、“课程目标2：能基于算法设计与分析的专业知识，具备针对计算机应用领域复杂工程问题的关键环节进行分析、设计及优化等工程实践活动的能力”、“课程目标3：针对计算机复杂工程问题，能够基于算法设计与分析方法，通过调研和分析，设计合适的研究方案”。”。使学生了解分治法的适用范围，理解其基本思想，掌握使用分治策略设计的典型问题的精巧算法，能够利用分治算法解决实际工程问题。分组讨论和启发式教学，让学生理解分治算法的基本思想，掌握分治法分与治两个要点。启发学生回顾以前的哪些算法使用了分治策略，生活中哪些事情也是分治。第4章动态规划（10学时）1．教学内容（1）动态规划的基本思想及要素。（2）矩阵连乘问题。（3）最优凸多边形三角剖分。（4）最长公共子序列问题。（5）加工顺序问题。（6）0-1背包问题。（7）最优二叉查找树。2．基本要求（1）了解动态规划法的适用范围，理解其基本思想、特点，设计算法的基本步骤。（2）掌握典型问题（如最长公共子序列问题、矩阵连乘、加工顺序、0/1背包及最优二叉查找树等问题）的动态规划算法，能在给定问题实例上模拟算法的执行。（3）能通过这些典型应用，熟练地掌握使用态规划法设计算法的关键步骤。3．支撑的课程目标本章各知识点的讲授和学习，可以支撑“课程目标1：掌握算法设计与分析的专业知识，具有应用数学、算法及计算机的基本原理，能将其用于计算机复杂工程问题模型的实现”、“课程目标2：能基于算法设计与分析的专业知识，具备针对计算机应用领域复杂工程问题的关键环节进行分析、设计及优化等工程实践活动的能力”、“课程目标3：针对计算机复杂工程问题，能够基于算法设计与分析方法，通过调研和分析，设计合适的研究方案”。使学生了解动态规划法的适用范围，理解其基本思想、特点，设计算法的步骤，掌握典型问题的动态规划算法求解方法，能够熟练应用动态规划算法为解决计算机应用的工程项目问题。案例教学法，让学生了解为什么要使用动态规划，理解动态规划算法的基本要素，掌握动态规划最优子结构分析及递归式的设计方法。任务驱动教学法，让学生动手进行算法实现和分析。第5章回溯法（6学时）1．教学内容（1）回溯法的算法框架及思想。（2）子集树。（3）排列树。（4）满m叉树。2．基本要求（1）了解回溯法，理解其基本思想、特点。（2）掌握针对具体问题设计回溯算法的基本步骤和方法。（3）通过在典型问题（如旅行商问题、0-1背包问题等）上的应用，较熟练掌握使用回溯法求解问题的基本步骤和方法，并能熟练编程序实现算法。（4）了解回溯算法估计方法。3．支撑的课程目标本章各知识点的讲授和学习，可以支撑“课程目标1：掌握算法设计与分析的专业知识，具有应用数学、算法及计算机的基本原理，能将其用于计算机复杂工程问题模型的实现”、“课程目标2：能基于算法设计与分析的专业知识，具备针对计算机应用领域复杂工程问题的关键环节进行分析、设计及优化等工程实践活动的能力”、“课程目标3：针对计算机复杂工程问题，能够基于算法设计与分析方法，通过调研和分析，设计合适的研究方案”。使学生了解回溯法、分支限界法的应用范围，掌握针对具体问题设计回溯算法的基本步骤和方法，并能熟练编程序实现算法，为解决实际工程问题奠定基础。分组讨论和案例教学法，让学生掌握回溯法及算法框架；回溯法的算法设计模式；回溯法及分支限界法的效率分析。布置任务，提高学生动手实践能力。第6章分支限界法（4学时）1．教学内容（1）分支限界法的基本思想。（3）0/1背包问题。（3）旅行商问题。（4）图的m着色问题。（5）分支限界法与回溯法的比较。2．基本要求（1）了解分支限界法的应用范围，理解其基本思想、特点。（2）掌握针对具体问题设计分枝限界算法的基本步骤和方法。（3）通过在典型问题（如m着色问题、旅行商问题、0-1背包问题等）上的应用，较熟练掌握使用分枝限界法求解问题的基本步骤和方法，并能熟练编程序实现算法。（4）了解分枝限界算法的效率估计方法。3．支撑的课程目标本章各知识点的讲授和学习，可以支撑“课程目标1：掌握算法设计与分析的专业知识，具有应用数学、算法及计算机的基本原理，能将其用于计算机复杂工程问题模型的实现”、“课程目标2：能基于算法设计与分析的专业知识，具备针对计算机应用领域复杂工程问题的关键环节进行分析、设计及优化等工程实践活动的能力”、“课程目标3：针对计算机复杂工程问题，能够基于算法设计与分析方法，通过调研和分析，设计合适的研究方案”。使学生了解回溯法、分支限界法的应用范围，掌握针对具体问题设计分枝限界算法的基本步骤和方法，并能熟练编程序实现算法，为解决实际工程问题奠定基础。分组讨论和案例教学法，让学生掌握分支限界法算法框架；分支限界法的算法设计模式；分支限界法的效率分析。布置任务，提高学生动手实践能力。第7章线性规划问题与网络流（8学时）1．教学内容（1）线性规划的基本概念、定理及单纯形算法。（2）最大网络流问题的解法。（3）最小费用流问题的解法。2．基本要求（1）了解线性规划模型的特点、线性规划问题的标准型及退化处理。（2）掌握线性规划问题解的概念、有关解的基本定理。（3）掌握单纯形法的原理和求解方法。（4）掌握最大网络流问题的求解方法和最小费用流问题的求解方法。3．支撑的课程目标本章各知识点的讲授和学习，可以支撑“课程目标1：掌握算法设计与分析的专业知识，具有应用数学、算法及计算机的基本原理，能将其用于计算机复杂工程问题模型的实现”、“课程目标2：能基于算法设计与分析的专业知识，具备针对计算机应用领域复杂工程问题的关键环节进行分析、设计及优化等工程实践活动的能力”、“课程目标3：针对计算机复杂工程问题，能够基于算法设计与分析方法，通过调研和分析，设计合适的研究方案”。使学生解线性规划模型的特点、线性规划问题的标准型及退化处理，掌握单纯形法的原理和求解方法，掌握最大网络流问题的求解方法和最小费用流问题的求解方法，能够利用最大流算法解决实际工程问题。案例教学和启发式教学法，让学生理解线性规划和网络流的基本思想，掌握单纯形算法；最大网络流问题；最小费用流问题的求解方法。启发学生动手动脑，解决布置的任务。第8章随机化算法（6学时）1．教学内容（1）随机化算法的类型及特点。（2）随机数发生器。（3）数值随机化算法。（4）蒙特卡罗算法。（5）拉斯维加斯算法。（6）舍伍德算法。2．基本要求（1）了解随机化算法的基本特征。（2）理解数值随机算法、舍伍德算法、拉斯维加斯算法、蒙特卡洛算法的特点和适用范围。（3）掌握素数测试、整数的因子分解等随机化算法。3．支撑的课程目标本章各知识点的讲授和学习，可以支撑“课程目标1：掌握算法设计与分析的专业知识，具有应用数学、算法及计算机的基本原理，能将其用于计算机复杂工程问题模型的实现”、“课程目标2：能基于算法设计与分析的专业知识，具备针对计算机应用领域复杂工程问题的关键环节进行分析、设计及优化等工程实践活动的能力”，使学生了解随机化算法的基本特征，掌握素数测试、整数的因子分解等随机化算法，体会随机化算法在工程项目中的应用，为解决实际工程问题奠定基础。启发式教学法，让学生理解什么是随机化算法，掌握四种随机化算法的特点和适用范围，启发学生思考生活中的随机化例子，鼓励学生动手实现。第9章NP完全理论（2学时）1．教学内容（1）P类和NP类问题。（2）NP完全问题。（3）NP完全问题的近似算法。2．基本要求（1）了解P类和NP类问题。（2）理解NP完全问题及近似算法。3．支撑的课程目标本章各知识点的讲授和学习，可以支撑“课程目标1：掌握算法设计与分析的专业知识，具有应用数学、算法及计算机的基本原理，能将其用于计算机复杂工程问题模型的实现”，使学生了解P类和NP类问题，理解NP完全问题及近似算法，为解决实际工程问题奠定基础。分组讨论和启发式教学法，让学生理解P类和NP类问题、NP完全问题，及近似算法的设计与可靠性分析。启发学生思考以前学过的算法属于什么问题类型。（二）实验教学实验项目1．贪心算法应用（2学时）1．实验内容（1）给出背包问题的贪心算法。（2）给出会议安排问题的贪心算法。（3）给出算法复杂度分析。2．基本要求（1）理解和掌握贪心算法的基本思想和步骤。（2）掌握贪心算法的复杂性分析方法。（3）能够利用贪心算法解决实际工程问题。3．支撑的课程目标本实验项目可以支撑“课程目标1：掌握算法设计与分析的专业知识，具有应用数学、算法及计算机的基本原理，能将其用于计算机复杂工程问题模型的实现”、“课程目标2：能基于算法设计与分析的专业知识，具备针对计算机应用领域复杂工程问题的关键环节进行分析、设计及优化等工程实践活动的能力”、“课程目标3：针对计算机复杂工程问题，能够基于算法设计与分析方法，通过调研和分析，设计合适的研究方案”。本实验通过问题启发式引导学生依据所掌握的相关知识点，熟悉某一具体问题的贪心算法求解方法，加深对贪心算法的理解，达到课程目标的要求。实验项目2．分治算法应用（2学时）1．实验内容（1）给出合并排序算法和程序。（2）给出快速排序算法和程序。（3）给出算法复杂度分析。2．基本要求（1）熟悉分治算法的分解与治理方法。（2）掌握分治法的应用场景和递归求解的方法。（3）锻炼利用分治法解决实际问题的能力。3．支撑的课程目标本实验项目可以支撑“课程目标1：掌握算法设计与分析的专业知识，具有应用数学、算法及计算机的基本原理，能将其用于计算机复杂工程问题模型的实现”、“课程目标2：能基于算法设计与分析的专业知识，具备针对计算机应用领域复杂工程问题的关键环节进行分析、设计及优化等工程实践活动的能力”、“课程目标3：针对计算机复杂工程问题，能够基于算法设计与分析方法，通过调研和分析，设计合适的研究方案”。本实验通过问题启发式引导学生依据所掌握的相关知识点，熟悉某一具体问题的分治算法求解方法，加深对分治算法的理解，达到课程目标的要求。实验项目3．动态规划算法应用（2学时）1．实验内容（1）给出最优三角剖分的动态规划算法和程序。（2）给出最优二叉树的动态规划算法和程序。（3）给出算法复杂度分析。2．基本要求（1）理解动态规划算法的适用场景。（2）掌握动态规划问题的算法设计与实现方法。（3）掌握动态规划算法的复杂度分析方法。3．支撑的课程目标本实验项目可以支撑“课程目标1：掌握算法设计与分析的专业知识，具有应用数学、算法及计算机的基本原理，能将其用于计算机复杂工程问题模型的实现”、“课程目标2：能基于算法设计与分析的专业知识，具备针对计算机应用领域复杂工程问题的关键环节进行分析、设计及优化等工程实践活动的能力”、“课程目标3：针对计算机复杂工程问题，能够基于算法设计与分析方法，通过调研和分析，设计合适的研究方案”。本实验通过启发式方式引导学生依据所掌握的相关知识点，根据具体问题设计动态规划算法并分析优化，达到课程目标的要求。实验项目4．搜索算法应用（2学时）1．实验内容（1）给出最大团问题的回溯算法和程序。（2）给出旅行商问题的分支限界算法和程序。（3）掌握搜索算法的复杂度分析方法。2．基本要求（1）理解和掌握搜索算法的算法设计框架。（2）理解和掌握搜索算法解决实际问题的过程和算法设计优化方法。3．支撑的课程目标本实验项目可以支撑“课程目标1：掌握算法设计与分析的专业知识，具有应用数学、算法及计算机的基本原理，能将其用于计算机复杂工程问题模型的实现”、“课程目标2：能基于算法设计与分析的专业知识，具备针对计算机应用领域复杂工程问题的关键环节进行分析、设计及优化等工程实践活动的能力”、“课程目标3：针对计算机复杂工程问题，能够基于算法设计与分析方法，通过调研和分析，设计合适的研究方案”。本实验通过启发式方式引导学生依据所掌握的相关知识点，根据具体工程项目设计搜索算法并分析优化，达到课程目标的要求。实验项目5．随机化算法应用（2学时）1．实验内容（1）给出n皇后问题的随机化算法和程序。（2）给出随机快速排序的算法和程序。（3）掌握随机化算法的复杂度分析方法。2．基本要求（1）熟悉随机化算法的类型和特点。（2）根据具体问题设计随机化算法。3．支撑的课程目标本实验项目可以支撑“课程目标1：掌握算法设计与分析的专业知识，具有应用数学、算法及计算机的基本原理，能将其用于计算机复杂工程问题模型的实现”、“课程目标2：能基于算法设计与分析的专业知识，具备针对计算机应用领域复杂工程问题的关键环节进行分析、设计及优化等工程实践活动的能力”。本实验通过启发式方式，引导学生掌握在计算机应用项目中设计随机化算法解决实际问题，达到课程目标的要求。实验项目6．网络流算法应用（2学时）1．实验内容（1）给出飞行员配对问题的算法和程序。（2）给出太空实验室计划的算法和程序。（3）掌握网络流算法的复杂度分析方法。2．基本要求（1）理解并体会具体问题分析抽象的过程。（2）运用网络流算法解决实际问题。（3）培养学生的系统思维，提升解决复杂工程问题所需的问题分析和系统设计能力。3．支撑的课程目标本实验项目可以支撑“课程目标1：掌握算法设计与分析的专业知识，具有应用数学、算法及计算机的基本原理，能将其用于计算机复杂工程问题模型的实现”、“课程目标2：能基于算法设计与分析的专业知识，具备针对计算机应用领域复杂工程问题的关键环节进行分析、设计及优化等工程实践活动的能力”、“课程目标3：针对计算机复杂工程问题，能够基于算法设计与分析方法，通过调研和分析，设计合适的研究方案”。本实验通过启发式方式，引导学生依据所掌握的相关知识点，培养具备学生根据具体工程项目问题进行网络流算法设计的能力，达到课程目标的要求。四、教学方式、教学方法及课时安排（一）教学方式课程目标与教学环节序号课程目标教学环节讲授作业实验1掌握算法设计与分析的专业知识，具有应用数学、算法及计算机的基本原理，能将其用于计算机复杂工程问题模型的实现2目标2：能基于算法设计与分析的专业知识，具备针对计算机应用领域复杂工程问题的关键环节进行分析、设计及优化等工程实践活动的能力3目标3：针对计算机复杂工程问题，能够基于算法设计与分析方法，通过调研和分析，设计合适的研究方案。以课堂讲授为主，结合课堂讲授内容安排课内实验及课后作业，加深对理论教学内容的理解和认识，培养工程实践能力。（二）教学方法本课程贯彻“以学生为主体，以教师为主导”的教学思想，采用“互动、开放”的课堂形式，具体以课堂教学为主，结合自学、课后作业和实验教学，采用启发式、问题式的教学方法，基于项目的实际问题，提高学生解决复杂计算机算法应用问题的能力，达到课程目标的要求。相关课程目标支撑如下：课堂教学主要讲解与算法设计与分析有关的基本概念、基本理论以及基本分析方法，并将日常生活中所遇到的算法问题、智能应用系统案例融入基本理论的讲解，使同学们更好地熟悉或掌握算法的基本原理，提高学生对算法的兴趣、熟悉算法设计分析及优化、思维方式和研究方法。课堂教学尽量引入互动环节，通过问题导入教学，引导学生寻找解决方案，提高教学效果，达到“课程目标1：掌握算法设计与分析的专业知识，具有应用数学、算法及计算机的基本原理，能将其用于计算机复杂工程问题模型的实现”、“课程目标2：能基于算法设计与分析的专业知识，具备针对计算机应用领域复杂工程问题的关键环节进行分析、设计及优化等工程实践活动的能力”、“课程目标3：针对计算机复杂工程问题，能够基于算法设计与分析方法，通过调研和分析，设计合适的研究方案”的要求。通过实验教学增强学生理解理论知识，动手寻找答案，以培养学生解决数据库应用问题的能力，达到“课程目标1：掌握算法设计与分析的专业知识，具有应用数学、算法及计算机的基本原理，能将其用于计算机复杂工程问题模型的实现”、“课程目标2：能基于算法设计与分析的专业知识，具备针对计算机应用领域复杂工程问题的关键环节进行分析、设计及优化等工程实践活动的能力”、“课程目标3：针对计算机复杂工程问题，能够基于算法设计与分析方法，通过调研和分析，设计合适的研究方案”。课堂讨论以及课后作业，能培养同学们的综合能力，熟悉运用所学知识的能力，锻炼表达能力，并通过合作客观评价相关工程对社会、经济等影响，发表自己的见解。达到“课程目标1：掌握算法设计与分析的专业知识，具有应用数学、算法及计算机的基本原理，能将其用于计算机复杂工程问题模型的实现”、“课程目标2：能基于算法设计与分析的专业知识，具备针对计算机应用领域复杂工程问题的关键环节进行分析、设计及优化等工程实践活动的能力”、“课程目标3：针对计算机复杂工程问题，能够基于算法设计与分析方法，通过调研和分析，设计合适的研究方案”的要求。（三）课时安排本课程总学时52学时，其中：讲授40学时，实验（或上机或综合练习）12学时，具体教学安排如下表。学时分配与教学方法序号教学内容学时分配教学方法1算法概述4讲授2贪心算法6讲授3分治算法6讲授4动态规划10讲授5回溯法6讲授6分支限界法4讲授7线性规划和网络流8讲授8随机化算法6讲授9NP完全理论2讲授10实验一：贪心算法应用2实验11实验二：分治算法应用2实验12实验三：动态规划算法应用2实验13实验四：搜索算法应用2实验14实验五：随机化算法应用2实验15实验六：网络流算法应用2实验合计64五、考核方式与成绩评定办法（一）考核方式及具体要求最终成绩由平时作业成绩、上机与实验成绩和期末成绩等组合而成，各部分所占比例如下：平时作业成绩（占30%）：包括章节测试、作业。其中，作业：教师评判作业并根据作业内容的正确性、完成认真度及规范性给出评定成绩。上机与实验（占20%）：主要考核根据常见的问题进行算法设计能力、算法分析的能力、算法优化的能力，学生可根据任课教师布置的实验题目与目标，通过结合算法的理论知识，进行设计、代码编写、测试与分析，给出一定形式的实验结果及分析说明。上机与实验考核：根据实验结果正确性的完成情况及实验报告的规范性给出评定成绩。期末考试成绩（占50%）：在考核算法基础知识掌握程度的基础上，重点考核理论知识的应用能力，以及解决计算机应用工程项目中相关复杂工程问题的能力。期末考试采用书面闭卷形式，主要题型可以是选择题、填空题、简答题、算法设计题、综合应用题等。课程考核能够针对学生对专业核心知识的掌握情况、运用理论知识解决计算机应用的能力、客观评价算法优化及智能算法领域对社会、文化等影响的能力和能及时跟踪相关行业发展状况，就当前的热点问题发表自己见解的能力等方面进行考核，支持“课程目标1：掌握算法设计与分析的专业知识，具有应用数学、算法及计算机的基本原理，能将其用于计算机复杂工程问题模型的实现”、“课程目标2：能基于算法设计与分析的专业知识，具备针对计算机应用领域复杂工程问题的关键环节进行分析、设计及优化等工程实践活动的能力”、“课程目标3：针对计算机复杂工程问题，能够基于算法设计与分析方法，通过调研和分析，设计合适的研究方案”。（二）成绩评定办法及依据1.平时成绩章节测试成绩由网络教学平台自动批阅评定。平时成绩评分标准（作业）分值观测点90-100分70-89分60-69分0-59分得分作业完成程度（权重10%）按时全部完成延时全部完成按时部分完成延时部分完成算法基础知识掌握及复杂算法问题应用系统解决方案的分析（权重45%）概念清晰，分析得当主要概念清晰，但部分分析有误部分概念清晰，分析中有明显错误基本概念不清，分析错误应用