《算法分析与设计》课程教学大纲 (Analysis Design of Algorithm)Teaching Outline 一、课程基本信息 课程代码：16158603 课程名称：算法分析与设计 英文名称：Analysis&Design of Algorithm 课程类别：专业课 学 时：48（课堂教学36，实验教学12） 学分：3 适用对象：计算机科学与技术专业本科生 考核方式：考试 先修课程：C或JAVA语言、数据结构 二、课程简介 中文简介 《算法分析与设计》是软件开发人员必修专业课，软件的效率和稳定性取决于软 件中所采用的算法技术：对于一般程序员和软件类专业学生，学习算法设计与分析课 程，可以开阔编程思路，找到最优问题的高效求解算法，提高程序的时间效率和空间 效率 英文简介 Analysis and Design of Algorithms is a compulsory specialty course for software developers.Effic ency and stability of software depends on algorithm-techniques used.For common coders and software relative students,learning this course could expand their programming vision and help them programming high quality codes.finding out the optimization solving algorithm in time and space 课程性质与教学目的 通过对常用的、有代表性的算法的研究，让学生理解并掌握算法设计的基本技术。 培养学生分析算法复杂度的初步能力，锻炼其逻辑思维能力和想象力，理解问题的难 度分类、并使之掌握算法理论的基本要点，了解算法理论的基本框架，并能够从辩证 唯物主义告诉我们的“真理是客观的，同时又是绝对的和相对的”角度，深入理解计 算机科学与 支不专 业中的NF 全理论体系。站在 学生具备 算法 术和相 的知识，去解决系统开发过程中的实际问题，从而培养学生的独立科研的能力和理论 联系实践的能力。 四、教学内容及要求
1 《算法分析与设计》课程教学大纲 《Analysis & Design of Algorithm》Teaching Outline 一、课程基本信息 课程代码：16158603 课程名称：算法分析与设计 英文名称：Analysis & Design of Algorithm 课程类别：专业课 学 时：48(课堂教学 36，实验教学 12) 学 分：3 适用对象: 计算机科学与技术专业本科生 考核方式：考试 先修课程：C 或 JAVA 语言、数据结构 二、课程简介 中文简介 《算法分析与设计》是软件开发人员必修专业课，软件的效率和稳定性取决于软 件中所采用的算法技术；对于一般程序员和软件类专业学生，学习算法设计与分析课 程，可以开阔编程思路，找到最优问题的高效求解算法，提高程序的时间效率和空间 效率。 英文简介 Analysis and Design of Algorithms is a compulsory specialty course for software developers. Effici ency and stability of software depends on algorithm-techniques used. For common coders and software relative students, learning this course could expand their programming vision and help them programming high quality codes, finding out the optimization solving algorithm in time and space. 三、课程性质与教学目的 通过对常用的、有代表性的算法的研究，让学生理解并掌握算法设计的基本技术。 培养学生分析算法复杂度的初步能力，锻炼其逻辑思维能力和想象力，理解问题的难 度分类、并使之掌握算法理论的基本要点，了解算法理论的基本框架，并能够从辩证 唯物主义告诉我们的“真理是客观的，同时又是绝对的和相对的”角度，深入理解计 算机科学与技术专业中的 NP 完全理论体系。站在。使学生具备运用算法技术和相关 的知识，去解决系统开发过程中的实际问题，从而培养学生的独立科研的能力和理论 联系实践的能力。 四、教学内容及要求
第一章算法引论 (一)目的与要求 掌握算法，算法复杂度的基本概念，及时间复杂度的估算方法。 (二)教学内容 第一节算法与程序 1.主要内容 算法特征、算法与程序的区别 2.基本念和知识点 算法的定义、算法的五大特徊 程序+数据结构+算法=编程 3.问题与应用 思考：只要是计算机程序，便是算法的实现吗？ 第二节算法描述 1.主要内容 算法的表示与规范化描述方法 2.基本概念和知识点 Seduocode,算法描术的基本格式 3.问题与应用 思考 :算法描述到什么程度，其描述粒度便是合适的？ 第三节算法复杂性分析 1.主要内容 算法的时间复杂性、空间复杂性，渐进表达式 2.基本概念和知识点 算法的时间复杂性、空间复杂性，渐进表达式 3.问题与应用 掌握算法复杂度的基本概念及时间复杂度的估算方法。 函数的渐进表达式。 在算法复杂性分析的教学中，要重点介绍时间复杂性从O)逐渐演化到 O2),也即“从易到难”的过程，并引出对“一分为二，这是个普遍的现象，这就 是辩证法。”(《毛泽东选集》第5卷第498页)这个哲学思想在计算机算法设计中的 体现、在算法时间复杂性研究和讨论中的体现。 (三)教学方法与手段 课堂讲授为主，结合课堂分组讨论。 第二章递归与分治策略 (一)目的与要求 1,掌握递归的概念，学会用递归方法解决实际问题： 2.熟练学握利用分治法解决问题的基本思想，会用某高级语言对算法进行描述， 2
2 第一章 算法引论 (一)目的与要求 掌握算法，算法复杂度的基本概念，及时间复杂度的估算方法。 (二) 教学内容 第一节 算法与程序 1．主要内容 算法特征、算法与程序的区别 2．基本概念和知识点 算法的定义、算法的五大特征 程序+数据结构+算法=编程 3．问题与应用 思考：只要是计算机程序，便是算法的实现吗？ 第二节 算法描述 1．主要内容 算法的表示与规范化描述方法 2．基本概念和知识点 Seduocode，算法描述的基本格式 3．问题与应用 思考：算法描述到什么程度，其描述粒度便是合适的？ 第三节 算法复杂性分析 1．主要内容 算法的时间复杂性、空间复杂性，渐进表达式 2．基本概念和知识点 算法的时间复杂性、空间复杂性，渐进表达式 3．问题与应用 掌握算法复杂度的基本概念及时间复杂度的估算方法。 函数的渐进表达式。 在算法复杂性分析的教学中，要重点介绍时间复杂性从 O(1)逐渐演化到 O(2^n)，也即“从易到难”的过程，并引出对“一分为二，这是个普遍的现象，这就 是辩证法。”（《毛泽东选集》第 5 卷第 498 页）这个哲学思想在计算机算法设计中的 体现、在算法时间复杂性研究和讨论中的体现。 (三) 教学方法与手段 课堂讲授为主，结合课堂分组讨论。 第二章 递归与分治策略 （一）目的与要求 1. 掌握递归的概念，学会用递归方法解决实际问题； 2. 熟练掌握利用分治法解决问题的基本思想，会用某高级语言对算法进行描述
并对算法复杂度（时间和空间）进行分析。 (二)教学内容 第一节递归的概念 1.主要内容 递归概念，递归的程序实现 2.基本概念和知识点 递归思想 3.问题与应用 从易到难举例：指数算法、阶乘算法：汉诺塔问题 第二节分治法的基本思想 1。主要内容 分治法基本思想、子问题与子问题相互独立性 2.基本概念和知 识点 分治思想及其应 3.问题与应用 二分搜索技术，大整数乘法 第三节应用实例 主要内容 矩阵乘法，棋盘覆盖，合并排序，快速排序，线性时间选择 2.基本概念和知识点 各类应用实例的分治思维方法 3。问题与应用 掌握递归的概念 学会用递归方法解决实际问题，熟练掌握利用分治法解法 问题的基本思想 会用某高级语言对算法进行描述，并对算法复杂度（时间 和空间)进行分析。 算法设计：CHESS COVERING问题、子段和问题 (三)课后练习 Han o塔问题的非递归算法 (四)教学方法与手段 课堂讲授为主，结合课堂分组讨论。 第三章动态规划 (一)目的与要 熟练掌握利用动态规划方法解决问题的基本思想 2.学会如何将问题化为子问题的方法： 3.能对具体问题写出正确的递推公式。 (二)教学内容 第一节动态规划算法的基本要素 1.主要内容 3
3 并对算法复杂度（时间和空间）进行分析。 （二）教学内容 第一节 递归的概念 1. 主要内容 递归概念，递归的程序实现 2. 基本概念和知识点 递归思想 3. 问题与应用 从易到难举例：指数算法、阶乘算法；汉诺塔问题 第二节 分治法的基本思想 1．主要内容 分治法基本思想、子问题与子问题相互独立性 2．基本概念和知识点 分治思想及其应用 3．问题与应用 二分搜索技术，大整数乘法 第三节 应用实例 1．主要内容 矩阵乘法，棋盘覆盖，合并排序，快速排序，线性时间选择 2．基本概念和知识点 各类应用实例的分治思维方法 3．问题与应用 掌握递归的概念，学会用递归方法解决实际问题，熟练掌握利用分治法解决 问题的基本思想，会用某高级语言对算法进行描述，并对算法复杂度（时间 和空间）进行分析。 算法设计：CHESS COVERING 问题、子段和问题 （三）课后练习 Hanoi 塔问题的非递归算法。 （四）教学方法与手段 课堂讲授为主，结合课堂分组讨论。 第三章 动态规划 （一）目的与要求 1．熟练掌握利用动态规划方法解决问题的基本思想； 2．学会如何将问题化为子问题的方法； 3．能对具体问题写出正确的递推公式。 （二）教学内容 第一节 动态规划算法的基本要素 1. 主要内容
动态规划的基本要素、动态规划思想、动态规划算法步骤 2.基本概念和知识点 动态规划思想、最优子结构性质、子问题重叠性质、动态规划算法的时间复 杂性分析 3.问题与应用 思考：动态规划与分治法思想的区别与比较 通过对动态规划和分治法思想这两种算法思想的比较，从算法效率的角 度，引出“科学是第 生产力 这个重要诊断！并从生产力的“劳动者、劳 动工具和劳动对象”这三大要素中，把计算机这个劳动工具进一步理解到算 法层面。 第二节最长公共子序列 1.主要内容 LCS问题的定义、LCS问题的DP求解思路 2,基本概念和知识点 LCS、自底向上的编程思维、算法时间复杂性分析 3,问题与应用 串的各种运算及其比较 第三节矩阵连乘问题 1.主要内容 矩阵连乘问题 2.基本概念和知识点 矩阵连乘、算法时间复杂性分析 问题与应用 矩阵连乘问题的算法设计 第四节其他应用 4.主要内容 最大子段和，凸多边形最优三角剖分，多边形游戏，图像压缩，电路布线， 流水作业调度 0-1背包问题 5.基本概念和知识点 各类问题的定义、DP思想的递推方程 6.问题与应用 如何设计能够应用DP算法的递推方程？ (三)课后练习 Triangle Problem的DP算法设计。 算法设计：TRIANGLE问题、LCS问题、数塔问题、矩阵连乘问题，等等 (四)教学方法与手段 课堂讲授为主，结合分组课堂讨论。 第四章贪心算法 4
4 动态规划的基本要素、动态规划思想、动态规划算法步骤 2. 基本概念和知识点 动态规划思想、最优子结构性质、子问题重叠性质、动态规划算法的时间复 杂性分析 3. 问题与应用 思考：动态规划与分治法思想的区别与比较 通过对动态规划和分治法思想这两种算法思想的比较，从算法效率的角 度，引出“科学是第一生产力”这个重要诊断！并从生产力的“劳动者、劳 动工具和劳动对象”这三大要素中，把计算机这个劳动工具进一步理解到算 法层面。 第二节 最长公共子序列 1．主要内容 LCS 问题的定义、LCS 问题的 DP 求解思路 2． 基本概念和知识点 LCS、自底向上的编程思维、算法时间复杂性分析 3． 问题与应用 串的各种运算及其比较 第三节 矩阵连乘问题 1．主要内容 矩阵连乘问题 2． 基本概念和知识点 矩阵连乘、算法时间复杂性分析 3． 问题与应用 矩阵连乘问题的算法设计 第四节 其他应用 4． 主要内容 最大子段和，凸多边形最优三角剖分，多边形游戏，图像压缩，电路布线， 流水作业调度，0-1 背包问题 5． 基本概念和知识点 各类问题的定义、DP 思想的递推方程 6． 问题与应用 如何设计能够应用 DP 算法的递推方程？ （三）课后练习 Triangle Problem 的 DP 算法设计。 算法设计：TRIANGLE 问题、LCS 问题、数塔问题、矩阵连乘问题，等等 （四）教学方法与手段 课堂讲授为主，结合分组课堂讨论。 第四章 贪心算法
(一)目的与要求 1.掌握利用贪心算法解决问题的基本思想： 2.会用某高级语言编写用贪心算法解决问题的程序，并能对算法的复杂度 可靠性进行分析。 (二)教学内容 第一节贪心算法的基本要素 1。主要内容 贪心选择性质、最优子结构性质 2基木概令和知识占 贪心选择、最优子结构、算法时间复杂性分析 3.问颗与应用 贪心算法与动态规划算法的差异 第二节单源最短路径 1.主要内容 算法基本思想、算法的正确性和计算复杂性 2.基本概念和知识点 单源最短路径、算法时间复杂性分析 3 问题与应用 单源最短路径的程序实现 第三节其他应用 1.主要内 活动安排问题，最优装载，哈夫曼编码，最小生成树，多机调度 2. 基本概念和知识点 问题的描述与理解 3.问题与应用 实现以上各类问题的程序、分析各类问题的算法时间复杂性 贪心算法在问题具有什么特征下，才是正确的？ (三)实践环节与课后练习 活动安排问题的贪心选择算法。 (四)教学方法与手段 课堂讲授为主，结合课堂分组讨论。 笋五音可湖法 (一)目的与要求 1,掌握利用回溯法解决问题的基本思想： 2,会用回溯法解决：个皇后问题，图的m着色问题，批处理作业调度问题 等，并能准确地分析回溯法的效率及稳定性。 (一)教学内容 第一节回溯法思想 5
5 （一）目的与要求 1．掌握利用贪心算法解决问题的基本思想； 2．会用某高级语言编写用贪心算法解决问题的程序，并能对算法的复杂度， 可靠性进行分析。 （二）教学内容 第一节 贪心算法的基本要素 1. 主要内容 贪心选择性质、最优子结构性质 2. 基本概念和知识点 贪心选择、最优子结构、算法时间复杂性分析 3. 问题与应用 贪心算法与动态规划算法的差异 第二节 单源最短路径 1．主要内容 算法基本思想、算法的正确性和计算复杂性 2． 基本概念和知识点 单源最短路径、算法时间复杂性分析 3． 问题与应用 单源最短路径的程序实现 第三节 其他应用 1．主要内容 活动安排问题，最优装载，哈夫曼编码，最小生成树，多机调度。 2． 基本概念和知识点 问题的描述与理解 3． 问题与应用 实现以上各类问题的程序、分析各类问题的算法时间复杂性 贪心算法在问题具有什么特征下，才是正确的？ （三）实践环节与课后练习 活动安排问题的贪心选择算法。 （四）教学方法与手段 课堂讲授为主，结合课堂分组讨论。 第五章 回溯法 （一）目的与要求 1．掌握利用回溯法解决问题的基本思想； 2．会用回溯法解决：n 个皇后问题，图的 m 着色问题，批处理作业调度问题 等，并能准确地分析回溯法的效率及稳定性。 （二）教学内容 第一节 回溯法思想