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

《算法分析与设计》课程教学大纲（理论课程）一、课程基本信息课程号3023D06014开课单位国际学院课程名称（中文）算法分析与设计（英文）AnalysisandDesignofAlgorithms课程性质选修考核类型考试课程学分3课程学时51课程类别专业拓展课（学科基础课程）先修课程高等数学、离散数学、数据结构、程序设计基础、python程序设计或c++程序设计适用专业（类）软件工程二、课程描述及目标（一）课程简介《算法分析与设计》是软件工程、计算机科学与技术及相关专业的基础课程。该课程的学习将为专业课程学习打下良好基础。本课程主要是讲授算法设计的基本原理、方法和算法分析技术。学生通过对算法设计策略的系统学习与研究，理解和掌握算法设计的主要方法，锻炼独立分析问题和解决问题的能力，为开发高效的软件系统奠定坚实的基础。《算法分析与设计》是一门理论性与实践性兼顾的课程，通过本课程的学习，要求学生理解计算机算法效率分析与设计所涉及的基本概念和基础知识，掌握基本的算法分析的方法和常见的算法设计方法，通过大量对算法实例的分析，加深对算法设计方法的认识和理解，并通过不同的算法设计技术在同一问题中的应用进行比较，牢固掌握算法设计技术的基本策略，深刻体会算法设计技术的思想方法，培养学生综合利用多种算法设计技术更有效地解决问题的能力。（二）教学目标通过本课程的学习，要求学生理解计算机算法效率分析与设计所涉及的基本概念和基础知识，掌握基本的算法分析的方法和常见的算法设计方法，深刻体会算法设计技术的思想方法，培养学生综合利用多种算法设计技术更有效地解决问题的能力。课程目标1：掌握算法复杂度分析的基本理论以及算法的计算复杂性分析方法，以及算法分析相关的数学基础，能够对所现有的或者设计出的算法从理论上进行复杂度分析；课程目标2：理解、掌握常见的算法设计方法，能够综合利用多种算法设计技术更有效地解决实际问题；课程目标3：培养学生算法分析的时空意识、离散的计算思维、以及在有限的计算资源上为实际问题选择或设计合适算法的能力。三、课程目标对毕业要求的支撑关系毕业要求指标点课程目标权重1-2：掌握计算机科学与软件开发的基本理论和基础专业知识，具备常用软件及数据分析软件使用的相关知识，掌握常用软件开发语言，具备大数据环境下数据分析算法与软件系统的设计、开发与分析等相关知识。课程目标10.42-2：具有较强的创新意识和批判意识，善于发现、提出问题，有意识涉猎相关学科的基本知识，并尝试将数据科学与大数据技术的理论和方法应用到具体问题分析、建模及求解中。课程目标20.33-4：具有科学情怀，具备数学思维和数据思维素养，能胜任数据建模、数据分析与挖掘算法等问题的研究和大数据系统的开发工作，即可在科研机构或高校继续深造，从事数据科学相关的科研工作，也可在经济、管理、生物、交通、医疗等领域或业界从事大数据的采集、管理、分析与处理方面的工作。课程目标30.3四、教学方式与方法由于本课程具有很强的理论和实践集合的特点，因此本课程采用教授式教学和探讨式教学、启发式教学、案例教学相结合的方式。在教学过程中，采用任务驱动模式，通过分析展示问题解决的过程，培养学生自主分析问题和解决问题的能力。五、教学重点与难点（一）教学重点教学重点：求解问题的基本步骤、算法的概念、程序与算法的区别、算法效率的分析；分治策略的基本原理与应用、递归算法的效率分析；动态规划算法的基本思想、动态规划算法的设计策略；贪心策略的基本思想、适用条件及其应用、适用条件及其应用；图的基本算法；最小生成树；单源最短路径问题和所有节点对最短路径问题。（二）教学难点算法时间复杂性和空间复杂性的度量、算法运行时间的估计；分治策略的基本原理与应用、递归算法的效率分析；动态规划典型问题的应用；贪心算法典型问题的解决方法及时间复杂性的分析；所有节点对最短路径问题。六、教学内容、基本要求与学时分配序号教学内容基本要求学时教学方式对应课程目标1第1章算法在计算中的作用理解算法的概念、算法的时间复杂性和空间复杂性；掌握求解问题的基本步骤；掌握算法运行时间的估计。2讲授课程目标1-22第2章算法基础掌握算法时间复杂度分析方法。4讲授+探讨课程目标13第3章函数的增长理解函数的渐进分析。3讲授+案例课程目标2-34第4章分治策略掌握递归的概念与的基本原理；理解分治策略的基本原理和效率分析，掌握设计有效算法的分治策略。掌握主方法。6讲授+探讨课程目标2-35第7章快速排序掌握快速排序和随机快速排序算法。3讲授+案例课程目标2-36第8章线性时间排序掌握计数排序、基数排序和桶排序相关算法。3讲授+案例课程目标2-37第9章中位数和顺序统计量掌握期望线性时间选择算法。3讲授+演示课程目标2-38第15章动态规划理解动态规划算法的概念；掌握动态规划算法的基本要素；掌握设计动态规划算法的步骤以及典型问题的应用与分析。9讲授+案例课程目标1-39第16章贪心算法理解贪心算法的基本思想、适用条件；掌握贪心算法的设计策略，掌握贪心算法典型问题的应用与分析6讲授+案例课程目标1-310第23章最小生成树掌握Kruskal和Prim算法。3讲授+案例课程目标1-311第24章单源最短路径掌握Bellman-Ford和Dijkstra算法，了解算法适用的条件。3讲授+案例课程目标1-312第25章

所有结点对的最短路径问题掌握Floyd-Warshall算法。3讲授+案例课程目标1-313分组讨论对算法相关问题进行阐述并讨论。3讨论课程目标2-3合计51八、学业评价和课程考核（一）考核类型：eq\o\ac(□,√)考试考查（二）考核方式：开卷考试eq\o\ac(□,√)闭卷考试课程论文课程报告其它：（三）成绩评定：考核依据建议分值（百分比）考核/评价细则对应课程目标过程考核50%诚信20%平时考核中是否诚实完成课程目标1课堂练习20%按照正确率考评课程目标1-3课堂表现30%积极思考、回答问题正确满分，否则酌情减分课程目标1-2分组项目20%项目完成情况和团队配合综合考评课程目标2-3期中测试10%按照期中测试正确率考评课程目标2-3期末考核50%参照考题答案评分标准考评课程目标1-3八、课程目标达成评价课程目标的实际达成效果计算方式如下，达成值越高，教学效果越好。课程目标达成度毕业要求指标点达成度九、教材与教学参考书（一）教材《算法导论》（原书第3版），ThomasH.Cormen，机械工业出版社，2018年8月。（二）教学参考书《算法设计与分析》，吕国英，清华大学出版社，2006，第一版；《计算机算法设计与分析》，王晓东，电子工业出版社，2007，第三版；《算法分析与设计基础》，（美）AnanyLevition,清华大学出版社，2013，第三版（影印版）；（三）参考资料《IntroductiontoAlgorithms》,