还剩2页未读,继续阅读
文本内容:
《算法分析与设计》课程教学大纲
一、课程说明课程名称算法分析与设计课程编号48英文译名总学时Algorithm analysisand design先修课程学分3《程序设计基础》、《数据结构》适用专业软件工程、大数据等计算机相关专业课程类型专业选修课
二、学时分配表教学内容讲授学时实践学时早P第1章算法概述20第2章递归与分治策略84第3章动态规划法64第4章贪心算法64第5章回溯法44第6章分支限界法40第7章概率算法203216合计
三、教学目的与要求开设本课程的目的是培养学生分析问题和解决问题的能力,使学生掌握算法设计的基本技巧和方法,熟悉算法分析的基本技术和常用算法,并能够熟练运用多种算法设计技术更有效地解决问题通过课堂讲授、课堂练习和讨论互动、课后作业等教学手段,系统介绍计算机算法的有关概念和算法设计的基本技巧,使学生掌握计算机算法的基本概念和特性,了解计算机相关学科中算法分析与设计技巧的重要性,掌握算法时间复杂性的分析方法和基本的算法设计策略,结合具体问题实例,使学生重点掌握递归算法、分治法、动态规划法、贪心算法、回溯法、分支限界法等常见的算法设计策略,了解计算复杂性基本理论,具备灵活运用所学解决实际应用问题的能力本课程各章的教学要求和知识考核点如下第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.5Strassen矩阵乘法
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.6TSP问题
4.7最小生成树
4.8套利问题第5章回溯法
5.1回溯法的算法框架
5.2n后问题
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%)。