课程名称：算法设计与分析 课程编码：7090301 课程学分：2学分 课程学时：32学时 适用专业：计算机科学与技术 先修课程：数据结构、C程序设计 课程类别：专业选修课 《算法设计与分析》 教学大纲 一、课程简介与目标 本课程的授课对象为计算机科学与技术专业二年级学生，课程属性为专业基 础选修课，讲授典型计算机算法设计方法和算法复杂性概念及分析方法相关的知 识，培养学生分析问题和解决计算机领域相关算法问题的能力，使学生掌握算法 设计的基本方法，熟悉算法分析的基本技术，并能熟练运用一些常用算法，同时 为3-4年级相关课程的学习打下基础。具体的课程目标为： 课程目标1：掌握算法设计与分析的基本概念和知识，学会分析算法、评价 算法的方法，掌握典型类型算法的时间复杂性分析方法。 课程目标2：通过对分治法、贪心法、动态规划、回溯法、分支限界法等五 类经典算法设计方法的学习，理解算法设计的常用方法，掌握针对不同问题的算 法设计方法基本思路、程序设计框架和复杂度情况。 课程目标3：培养学生运用所需方法独立地设计解决计算机应用中的实际问 题的能力和算法程序开发实现的能力，了解新兴T领域的一些主要算法。 课程思政目标：在理解算法的通用概念和计算机领域具体概念同时，知悉我 国在算法领域的相关贡献和工作，了解算法在互联网、人工智能、智慧城市等国 家战略发展重点领域的应用和作用，树立为国家战略发展贡献力量的意识。 二、教学基本内容及基本要求 本课程共32学时，其中理论授课22学时、上机教学8学时、考试2学时。 学时分配如表2所示。 表1学时分配表 总学时 讲授学时 课内上机 考试 32 22 8
1 课程名称：算法设计与分析 课程编码：7090301 课程学分：2 学分 课程学时：32 学时 适用专业：计算机科学与技术 先修课程：数据结构、C 程序设计 课程类别：专业选修课 《算法设计与分析》 教学大纲 一、课程简介与目标 本课程的授课对象为计算机科学与技术专业二年级学生，课程属性为专业基 础选修课，讲授典型计算机算法设计方法和算法复杂性概念及分析方法相关的知 识，培养学生分析问题和解决计算机领域相关算法问题的能力，使学生掌握算法 设计的基本方法，熟悉算法分析的基本技术，并能熟练运用一些常用算法，同时 为 3-4 年级相关课程的学习打下基础。具体的课程目标为： 课程目标 1：掌握算法设计与分析的基本概念和知识，学会分析算法、评价 算法的方法，掌握典型类型算法的时间复杂性分析方法。 课程目标 2：通过对分治法、贪心法、动态规划、回溯法、分支限界法等五 类经典算法设计方法的学习，理解算法设计的常用方法，掌握针对不同问题的算 法设计方法基本思路、程序设计框架和复杂度情况。 课程目标 3：培养学生运用所需方法独立地设计解决计算机应用中的实际问 题的能力和算法程序开发实现的能力，了解新兴 IT 领域的一些主要算法。 课程思政目标：在理解算法的通用概念和计算机领域具体概念同时，知悉我 国在算法领域的相关贡献和工作，了解算法在互联网、人工智能、智慧城市等国 家战略发展重点领域的应用和作用，树立为国家战略发展贡献力量的意识。 二、教学基本内容及基本要求 本课程共 32 学时，其中理论授课 22 学时、上机教学 8 学时、考试 2 学时。 学时分配如表 2 所示。 表 1 学时分配表 总学时 讲授学时 课内上机 考试 32 22 8 2
1.课程重点 掌握（计算机）算法的一些通用设计方法，包括分治法、贪心法、动态规划 回溯法、分支限界法，学会分析算法的（时间）复杂性概念和典型算法的复杂性 分析方法。对一定的算法实际问题，能够设计相应算法并（通过理论及实验）分 析算法的效率。 2.课程难点 算法时间复杂性的渐进分析方法，算法复杂性递推方程的求解，动态规划思 想的理解和运用动态规划方法求解问题，贪心法求解最优化问题的正确性证明， 各种算法设计方法的实际运用和编码实现。 3.课堂教学(22学时) 各知识单元教学内容、考核要求和学时分配如下表所示： 第一知识单元算法基本概念 学时分配3学时 教学方式课堂讲授，PPT电子课件，板书 教学内容 重点难点 算法在计算机科学中的地位，计算机算法与人工算法的区 别，算法与数据结构的关系：算法的意义。 2计算机求解问题的一般步骤，即算法设计步骤。 3算法的一般特征、算法的描述、算法分类 算法复杂性基本概念，算法时间复杂性的渐进分析方法，对 4 简单的递归过程及函数能够归纳出递推方程并求解。 考核要点 算法的一般特征和问题求解步骤：算法复杂性概念：不同算法 复杂度的大小排序：给定程序的复杂度计算。 第二知识单元递归与分治 学时分配4学时教学方式课堂讲授，PPT电子课件，板书 教学内容 重点难点 1递归的概念和分治法的基本概念。 2分治法解决实际问题的一般步骤。 分治法的基本思想，典型问题分治法复杂度递推方程和基于 主定理的复杂度计算方法。 分治法实例：大整数乘法、Strrassen矩阵乘法、棋盘覆盖、 合并排序、快速排序，理解并掌握划分方法优化、不同子问 V 题重构、不平衡划分等不同情况下的分治求解方法。 分治法的适用准则，分治法复杂度递推方程求解，棋盘覆盖、 考核要点 快速排序、合并排序的分治法实现
2 1.课程重点 掌握（计算机）算法的一些通用设计方法，包括分治法、贪心法、动态规划、 回溯法、分支限界法，学会分析算法的（时间）复杂性概念和典型算法的复杂性 分析方法。对一定的算法实际问题，能够设计相应算法并（通过理论及实验）分 析算法的效率。 2.课程难点 算法时间复杂性的渐进分析方法，算法复杂性递推方程的求解，动态规划思 想的理解和运用动态规划方法求解问题，贪心法求解最优化问题的正确性证明， 各种算法设计方法的实际运用和编码实现。 3.课堂教学（22 学时） 各知识单元教学内容、考核要求和学时分配如下表所示： 第一知识单元 算法基本概念 学时分配 3 学时 教学方式 课堂讲授，PPT 电子课件，板书 教学内容 重点 难点 1 算法在计算机科学中的地位，计算机算法与人工算法的区 别，算法与数据结构的关系；算法的意义。 2 计算机求解问题的一般步骤，即算法设计步骤。 3 算法的一般特征、算法的描述、算法分类 √ 4 算法复杂性基本概念，算法时间复杂性的渐进分析方法，对 简单的递归过程及函数能够归纳出递推方程并求解。 √ √ 考核要点 算法的一般特征和问题求解步骤；算法复杂性概念；不同算法 复杂度的大小排序；给定程序的复杂度计算。 第二知识单元 递归与分治 学时分配 4 学时 教学方式 课堂讲授，PPT 电子课件，板书 教学内容 重点 难点 1 递归的概念和分治法的基本概念。 2 分治法解决实际问题的一般步骤。 √ 3 分治法的基本思想，典型问题分治法复杂度递推方程和基于 主定理的复杂度计算方法。 √ √ 4 分治法实例：大整数乘法、Strrassen 矩阵乘法、棋盘覆盖、 合并排序、快速排序，理解并掌握划分方法优化、不同子问 题重构、不平衡划分等不同情况下的分治求解方法。 √ 考核要点 分治法的适用准则，分治法复杂度递推方程求解，棋盘覆盖、 快速排序、合并排序的分治法实现
第三知识单元动态规划 学时分配5学时 教学方式课堂讲授，PPT电子课件，板书 教学内容 重点难点 1动态规划的基本思想和多阶段决策和状态转移方程理解。 2动态规划法的主要性质和分析方法及最优子结构性质证明！ 3利用动态规划解决实际问题的一般步骤和实现框架。 动态规划法实例：树塔问题、01背包问题、最长公共子序 4 列问题、矩阵连乘问题，学习不同类型的阶段决策和状态转 移差异。 动态规划法的最优子结构和重叠子问题性质判断，扩展问题的 考核要点 状态转移方程定义，01背包问题、最长公共子序列问题、矩 阵连乘问题的动态规划法实现，扩展问题的动态规划法求解。 第四知识单元贪心算法 学时分配4学时 教学方式课堂讲授，PPT电子课件，板书 教学内容 重点难点 1贪心算法的基本思想，以及贪心算法与动态规划法的关系。 2贪心算法的主要性质，运用的条件和限制及性质证明。 贪心算法的实现框架和分析：贪心算法求解最优化问题和近 3 似最代求解。 贪心算法实例：活动安排问题、背包问题、最优装载问题、 单源最短路径、多机作业调度问题。 考核要点 贪心法的最优子结构和贪心选择性质判断及证明，背包问题、 最优装载问题、单源最短路径、多机作业调度问题求解及实现 第五知识单元回溯法 学时分配3学时教学方式课堂讲授，PPT电子课件，板书 教学内容 重点难点 1回溯法的基本思想，解空间树及深度优先搜索的概念。 2回溯法的设计步骤及典型的算法实现框架和剪枝函数设计。 3利用子集树和排列树实现回溯法求解问题表达的方式。 回溯法实例：0-1背包问题、两艘船的装载问题、批处理作 4 业调度问题。 问题的解空间树模型建立，剪枝函数设计，01背包问题、货 考核要点 郎问题、两艘船的装载问题、批处理作业调度问题的回溯法求 解和实现
3 第三知识单元 动态规划 学时分配 5 学时 教学方式 课堂讲授，PPT 电子课件，板书 教学内容 重点 难点 1 动态规划的基本思想和多阶段决策和状态转移方程理解。 √ 2 动态规划法的主要性质和分析方法及最优子结构性质证明。 √ √ 3 利用动态规划解决实际问题的一般步骤和实现框架。 √ 4 动态规划法实例：树塔问题、0/1 背包问题、最长公共子序 列问题、矩阵连乘问题，学习不同类型的阶段决策和状态转 移差异。 √ √ 考核要点 动态规划法的最优子结构和重叠子问题性质判断，扩展问题的 状态转移方程定义，0/1 背包问题、最长公共子序列问题、矩 阵连乘问题的动态规划法实现，扩展问题的动态规划法求解。 第四知识单元 贪心算法 学时分配 4 学时 教学方式 课堂讲授，PPT 电子课件，板书 教学内容 重点 难点 1 贪心算法的基本思想，以及贪心算法与动态规划法的关系。 2 贪心算法的主要性质，运用的条件和限制及性质证明。 √ √ 3 贪心算法的实现框架和分析；贪心算法求解最优化问题和近 似最优求解。 √ 4 贪心算法实例：活动安排问题、背包问题、最优装载问题、 单源最短路径、多机作业调度问题。 √ 考核要点 贪心法的最优子结构和贪心选择性质判断及证明，背包问题、 最优装载问题、单源最短路径、多机作业调度问题求解及实现。 第五知识单元 回溯法 学时分配 3 学时 教学方式 课堂讲授，PPT 电子课件，板书 教学内容 重点 难点 1 回溯法的基本思想，解空间树及深度优先搜索的概念。 √ 2 回溯法的设计步骤及典型的算法实现框架和剪枝函数设计。 3 利用子集树和排列树实现回溯法求解问题表达的方式。 √ √ 4 回溯法实例：0-1 背包问题、两艘船的装载问题、批处理作 业调度问题。 √ 考核要点 问题的解空间树模型建立，剪枝函数设计，0-1 背包问题、货 郎问题、两艘船的装载问题、批处理作业调度问题的回溯法求 解和实现
第六知识单元分支限界法 学时分配2学 教学方式课堂讲授，PPT电子课件，板书 教学内容 重点难点 分支限界法的基本思想，广度优先搜索和优先队列式搜索 概念，分支限界法和回溯法的关系与区别。 2分支限界法算法设计步骤及常见问题的算法实现框架。 利用多种不同方法解决同一类问题（如01背包问题），并 3 分析各种方法的差异和适用情况。 分支限界法实例：0-1背包问题、货郎问题、两艘船的装载 问题。 分支限界法和回溯法的关系与区别，0-1背包问愿、两艘船的 考核要点 装载问题的分支限界法实现。 第七知识单元新兴算法简介 学时分配1学时 教学方式课堂讲授，PPT电子课件，板书 教学内容 重点难点 并行计算、分布式计算、数据挖掘、大数据、人工智能等 新兴算法的背景、来源以及面向的问题，算法在新兴领域发 展中的作用。 考核要点不同新兴算法的问题背景及主要特点 4.上机教学(8学时) 主要通过上机操作，使学生深入学握分治法、贪心法、动态规划、回溯法与 分支限界法的核心思想，特别是通过上机编程实现，使学生能够把所学的方法用 于具体的问题实例，并对所用算法实现进行比较分析，从而提高学生分析问题、 解决问题的能力，将理论和编程实现切实结合起来。 1.分治法程序设计(2学时)：汉诺塔、棋盘覆盖、自然合并排序程序或快速 排序问题的求解和编码实现。 2动态规划法程序设计(2学时)：求解矩阵连乘、最长增序子数组、0-1背 包问题，并上机编码实现。 3.贪心法程序设计(2学时)：求解单会议室和多会议室活动安排问题及多机 调度问题，并上机编码实现。 4.回溯法和分支限界法程序设计(2学时)：求解0-1背包问题和2艘船的最 优装载问题，并上机编码实现。 三、课程采用的教学方法
4 第六知识单元 分支限界法 学时分配 2 学时 教学方式 课堂讲授，PPT 电子课件，板书 教学内容 重点 难点 1 分支限界法的基本思想，广度优先搜索和优先队列式搜索 概念，分支限界法和回溯法的关系与区别。 √ 2 分支限界法算法设计步骤及常见问题的算法实现框架。 3 利用多种不同方法解决同一类问题（如 0-1 背包问题），并 分析各种方法的差异和适用情况。 √ 4 分支限界法实例：0-1 背包问题、货郎问题、两艘船的装载 问题。 √ √ 考核要点 分支限界法和回溯法的关系与区别，0-1 背包问题、两艘船的 装载问题的分支限界法实现。 第七知识单元 新兴算法简介 学时分配 1 学时 教学方式 课堂讲授，PPT 电子课件，板书 教学内容 重点 难点 1 并行计算、分布式计算、数据挖掘、大数据、人工智能等 新兴算法的背景、来源以及面向的问题，算法在新兴领域发 展中的作用。 考核要点 不同新兴算法的问题背景及主要特点 4.上机教学（8 学时） 主要通过上机操作，使学生深入掌握分治法、贪心法、动态规划、回溯法与 分支限界法的核心思想，特别是通过上机编程实现，使学生能够把所学的方法用 于具体的问题实例，并对所用算法实现进行比较分析，从而提高学生分析问题、 解决问题的能力，将理论和编程实现切实结合起来。 1.分治法程序设计（2 学时）：汉诺塔、棋盘覆盖、自然合并排序程序或快速 排序问题的求解和编码实现。 2.动态规划法程序设计（2 学时）：求解矩阵连乘、最长增序子数组、0-1 背 包问题，并上机编码实现。 3.贪心法程序设计（2 学时）：求解单会议室和多会议室活动安排问题及多机 调度问题，并上机编码实现。 4.回溯法和分支限界法程序设计（2 学时）：求解 0-1 背包问题和 2 艘船的最 优装载问题，并上机编码实现。 三、课程采用的教学方法
1.本课程采用课堂讲授、课下辅导的方式，以课堂讲授为主，附以一定比例 的上机实践时间，课堂讲授以能力培养为导向，注重理解算法设计中的各种概念、 方法、技巧。 2.使用PowerPoint幻灯片作为主要教学辅助工具，以多模式教学网为主要载 体，根据上课内容教师选择演示软件进行教学。 3.在抓好课堂学习和上机实践效果的同时，还应抓好课前预习、课后复习和 完成课后作业等环节，并通过增强师生间、同学间的多种形式的讨论，来提高课 程的教学效果和教学质量。 四、建议教材及教学参考书 1.教材： 王晓东，算法设计与分析（第4版），清华大学出版社，2018年10月 2.参考书： [1 Thomas H.Corrmen著，殷建平、徐云等译，算法导论（第3版），机械工 业出版社，2012年12月 [2]算法图解，Aditya Bhargava,.袁国忠译，人民邮电出版社，2017年3月 [3]算法（第4版），Robert Sedgewick等，谢路云译，人民邮电出版社，2012 年10月 3.推荐MOOC课程： [1]算法设计与分析，北京航空航天大学，童咏听等， https://www.icourse163.org/course/BUAA-1449777166?from=searchPage [2]算法设计与分析入门，哈尔滨工业大学，王宏志等， https://www.icourse163.org/course/HIT-356006 五、知识单元对课程目标的达成度设计 1.知识单元支撑课程目标情况表 围绕每一个具体的课程目标，从相关支撑知识单元的角度设计不同的考核方 式，如下表所示： 课程目标 知识单元 考核方式设计 第一知识单元：算法基本概念 目标1 以选择、填空题方式考核 第二知识单元：递归与分治 第二知识单元：递归与分治 第三知识单元：动态规划 以选择、填空、简答、计算 目标2 第四知识单元：贪心算法 题方式考核。 第五知识单元：回溯法
5 1.本课程采用课堂讲授、课下辅导的方式，以课堂讲授为主，附以一定比例 的上机实践时间。课堂讲授以能力培养为导向，注重理解算法设计中的各种概念、 方法、技巧。 2.使用 PowerPoint 幻灯片作为主要教学辅助工具，以多模式教学网为主要载 体，根据上课内容教师选择演示软件进行教学。 3.在抓好课堂学习和上机实践效果的同时，还应抓好课前预习、课后复习和 完成课后作业等环节，并通过增强师生间、同学间的多种形式的讨论，来提高课 程的教学效果和教学质量。 四、建议教材及教学参考书 1.教材： 王晓东，算法设计与分析（第 4 版），清华大学出版社，2018 年 10 月 2.参考书： [1]Thomas H. Corrmen 著，殷建平、徐云等译，算法导论（第 3 版），机械工 业出版社，2012 年 12 月 [2]算法图解，Aditya Bhargava，袁国忠译，人民邮电出版社，2017 年 3 月 [3]算法（第 4 版），Robert Sedgewick 等，谢路云译，人民邮电出版社，2012 年 10 月 3.推荐 MOOC 课程： [1]算法设计与分析，北京航空航天大学，童咏昕等， https://www.icourse163.org/course/BUAA-1449777166?from=searchPage [2]算法设计与分析入门，哈尔滨工业大学，王宏志等， https://www.icourse163.org/course/HIT-356006 五、知识单元对课程目标的达成度设计 1.知识单元支撑课程目标情况表 围绕每一个具体的课程目标，从相关支撑知识单元的角度设计不同的考核方 式，如下表所示： 课程目标 知识单元 考核方式设计 目标 1 第一知识单元：算法基本概念 第二知识单元：递归与分治 以选择、填空题方式考核。 目标 2 第二知识单元：递归与分治 第三知识单元：动态规划 第四知识单元；贪心算法 第五知识单元：回溯法 以选择、填空、简答、计算 题方式考核
第六知识单元：分支限界法 第二知识单元：递归与分治 第三知识单元：动态规划 第四知识单元：贪心算法 目标3 以选择、编程题方式考核 第五知识单元：回溯法 第六知识单元：分支限界法 第七知识单元：新兴算法简介 2课程的总体考核方法及量化评定标准 依照每部分知识单元对课程目标的支撑情况设计考核方法与成绩评定，本课 程成绩由平时成绩和期末考试成绩两部分组成，以百分制计算，平时成绩占40%， 期末考试成绩占60%。平时成绩由考勤、课后作业和上机成绩确定。 六、其它问题的说明 无。 大纲撰写人：赵卓峰 大纲审阅人：杨中国 系负责人：段建勇 学院负责人：马礼 制定（修订）日期：2021年8月
6 第六知识单元：分支限界法 目标 3 第二知识单元：递归与分治 第三知识单元：动态规划 第四知识单元；贪心算法 第五知识单元：回溯法 第六知识单元：分支限界法 第七知识单元：新兴算法简介 以选择、编程题方式考核。 2.课程的总体考核方法及量化评定标准 依照每部分知识单元对课程目标的支撑情况设计考核方法与成绩评定，本课 程成绩由平时成绩和期末考试成绩两部分组成，以百分制计算，平时成绩占 40%， 期末考试成绩占 60%。平时成绩由考勤、课后作业和上机成绩确定。 六、其它问题的说明 无。 大纲撰写人：赵卓峰 大纲审阅人：杨中国 系负责人：段建勇 学院负责人：马 礼 制定（修订）日期：2021 年 8 月
