《算法分析与设计》李少芳 理论教学大纲.docx
算法分析与设计课程教学大纲一、课程说明课程名称算法分析与设计课程编号英文译名Algorithm analysis and design总学时48先修课程程序设计基础、数据结构学分3适用专业软件工程、大数据等计算机相关专业课程类型专业选修课二、学时分配表早P教学内容讲授学时实践学时第1章算法概述20第2章递归与分治策略84第3章动态规划法64第4章贪心算法64第5章回溯法44第6章分支限界法40第7章概率算法20合计3216三、教学目的与要求开设本课程的目的是培养学生分析问题和解决问题的能力，使学生掌握算法设计的基本技巧和 方法，熟悉算法分析的基本技术和常用算法，并能够熟练运用多种算法设计技术更有效地解决问题。通过课堂讲授、课堂练习和讨论互动、课后作业等教学手段，系统介绍计算机算法的有关概念 和算法设计的基本技巧，使学生掌握计算机算法的基本概念和特性，了解计算机相关学科中算法分 析与设计技巧的重要性，掌握算法时间复杂性的分析方法和基本的算法设计策略，结合具体问题实 例，使学生重点掌握递归算法、分治法、动态规划法、贪心算法、回溯法、分支限界法等常见的算 法设计策略，了解计算复杂性基本理论，具备灵活运用所学解决实际应用问题的能力。本课程各章的教学要求和知识考核点如下：第1章算法概述通过本章教学使学生掌握算法的概念、性质；掌握算法时间复杂度分析，掌握最坏情况分析， 熟练掌握渐进分析工具，掌握渐进符号0,q或0, O, 3的定义，能判断一个较复杂的函数 属于哪个渐近增长阶；了解算法复杂性的重要性。本章主要知识点是：算法概念，算法的性质，最坏情况时间复杂度函数，0,。或o, 3的定义，算法复杂性的重要性。难点是：最坏情况时间复杂度函数，0, Q,。或e, O, 3的定义。第2章递归与分治策略通过本章教学使学生掌握递归与分治法的基本策略和求解过程；掌握运用分治法求解大整数乘 法问题、矩阵乘法问题、排序问题、查找问题、棋盘覆盖问题和循环赛日程表问题等；掌握递归算 法时间复杂度函数的计算方法：迭代法、递归树法等。本章主要知识点是：分治法基本策略；分治法的设计步骤；时间复杂度函数的递推方程求解； 分治法的典型实例。难点是：递推方程的求解；分治法的典型实例。第3章动态规划通过本章教学使学生掌握动态规划的原理和求解步骤；掌握动态规划的适用条件(最优子结构、 重复子问题)及其设计步骤(递推关系和边界条件，自底向上计算，通过标记函数追踪最优解)； 掌握运用动态规划法求解数塔问题、最小代价子母树问题、最长公共子序列问题、凸多边形最优三 角剖分问题、多边形游戏和图像压缩问题等。本章主要知识点是：动态规划适用条件；动态规划设计步骤；递推关系建立；自底向上计算； 最优解追踪；动态规划法的典型实例。难点是：递推关系建立；自底向上计算；最优解追踪；动态规划法的典型实例。第4章贪心算法通过本章教学使学生掌握贪心算法的策略、求解过程和贪心算法求解问题应具有的性质；掌握 贪心算法正确性的证明方法；掌握运用贪心算法求解活动安排问题、背包问题、最优装载问题、最 短路径问题、哈夫曼编码、TSP问题、最小生成树问题和套利问题等；通过不同的算法设计技术在 同一问题中的应用，了解算法优化策略。本章主要知识点是：贪心算法思想，贪心算法适用条件，贪心算法设计步骤，贪心算法证明方 法，贪心算法的典型实例，算法优化策略实例。难点是：贪心算法证明方法，贪心算法的典型实例。第5章回溯法通过本章教学使学生掌握解空间的概念和回溯法的算法框架，掌握采用回溯法求解n皇后问 题、图的m着色问题等。本章主要知识点是：解空间的概念、回溯法算法框架、回溯法的典型实例、回溯法的效率分析。难点是：递归回溯、迭代回溯、回溯法的典型实例。第6章分支限界法通过本章教学使学生掌握分支限界法的基本思想，掌握常见的队列式(FIFO)和优先队列式两种 分支限界法，掌握采用分支限界法求解0-1背包问题、旅行售货员问题、求解单源最短路径问题、 15谜问题和装载问题等。本章主要知识点是：解空间树的搜索方式、分支限界法的基本思想、分支限界法的典型实例。难点是：分支限界法的典型实例。第7章概率算法通过本章教学使学生了解概率算法的基本特征，理解产生伪随机数的算法，掌握数值概率算法 的设计思想、蒙特卡罗(Monte Carlo)算法的设计思想、拉斯维加斯(Las Vegas)算法的设计思想和舍伍 德(Sherwood)算法的设计思想。本章主要知识点是：数值概率算法的设计思想、蒙特卡罗(Monte Carlo)算法的设计思想、拉斯 维加斯(Las Vegas)算法的设计思想和舍伍德(Sherwood)算法的设计思想。难点是：不同概率算法的应用场合。四、教学内容纲要第1章算法概述1.1什么是算法L2算法复杂性1.3 算法复杂性计量1.4 算法复杂性的表示1. 5算法复杂性的重要性第2章递归与分治策略2. 1递归的概念3. 2分治法的基本思想4. 3二分搜索技术5. 4大整数的乘法6. 5 Strassen矩阵乘法7. 6棋盘覆盖8. 7合并排序2. 8快速排序2.9循环赛日程表安排第3章动态规划法3.1动态规划法概述3. 2矩阵连乘问题3. 3动态规划算法的基本要素3. 4最长公共子序列问题3. 5凸多边形的最优三角剖分问题3. 6多边形游戏3. 7图像压缩第4章贪心算法4.1活动安排问题4. 2贪心算法的基本要素4. 3最优装载4. 4最短路径问题4. 5哈夫曼编码4.6 TSP问题4. 7最小生成树4.8套利问题第5章回溯法5.1 回溯法的算法框架5. 2 n后问题5.3 图的m着色问题5.4 回溯法的效率分析第6章分支限界算法6.1 分支限界法的基本思想6.2 分支限界法的算法实例6.3 单源最短路径问题6.4 装载问题第7章概率算法7.1随机数7. 2数值概率算法7. 3蒙特卡罗算法7. 4拉斯维加斯算法7. 5舍伍德算法五、课程教材教科书：李少芳.算法分析与设计M.北京：清华大学出版社，2023.参考书：刘汝隹 算法竞赛入门经典训练指南M.北京:清华大学出版社，2021.2刘瑜.算法之美-Python语言实现M.北京:中国水利水电出版社，202L 3王晓东.计算机算法设计与分析（第4版）M.北京：清华大学出版社，2018.4李春葆.算法设计与分析（第2版）M.北京：清华大学出版社，2018.5刘家瑛，郭炜,算法基础与在线实践M.北京：高等教育出版社，2017.6屈婉玲等.算法设计与分析（第2版）北京：清华大学出版社，2016.六、考核方式建议期末考核方式：笔试-闭卷，分值比例安排：平时（30%）,期中（20%）,期末（50%）。
