算法分析与设计课程

1、算法分析与设计课程教 学 大 纲课程代码：03020280算法分析与设计课程教学大纲（总学时数：48（408），学分数：3）一、课程的性质、任务和目的以算法设计策略为知识单元系统地介绍计算机算法的设计方法和分析方法。在教学中除介绍算法的基本概念、计算复杂性分析以外，重点介绍递归算法、分治算法、贪心算法、动态规划算法、回溯算法和分支定界算法的基本思想及应用，为计算机专业的学生提供一个广泛扎实的计算机算法知识基础。 二、课程的基本内容和要求（一）算法概述 教学内容：1. 算法与程序2. 算法分析的基本概念和理论3. 简单程序的算法复杂性分析教学要求：了解算法的基本概念，算法在程序设计中的重要性。掌

2、握程序复杂度度量的基本方法。（二）递归的基本概念 教学内容：1. 递归的概念2. 阶乘函数3. Fibonacci数列4. Ackerman函数5. Hanoi塔问题6. 整数划分问题教学要求：掌握递归程序复杂度的计算方法，了解经典递归问题解法。学会使用递归方法分析解决实际问题。（三）分治策略 教学内容：1. 分治法的基本思想2. 递归方程解的展开方法3. 二分搜索技术4. 大整数的乘法5. Strassen矩阵乘法6. 合并排序7. 快速排序8. 棋盘覆盖问题9. 循环赛日程表教学要求：掌握分治策略的基本思想以及用分治法解决问题的一般技巧。重点掌握二分搜索技术。（四）动态规划法 教学内容：1

3、. 动态规划算法的基本思想2. 动态规划算法的基本要素3. 矩阵连乘问题4. 最长公共子序列5. 最大子段和问题6. 0/1背包问题7. 流水作业调度8. 图像压缩问题9. 凸多边形最优三角剖分10. 动态规划的加速原理*教学要求：掌握动态规划解决问题的一般过程，掌握矩阵连乘问题的计算技巧。学会使用动态规划解决实际问题。（五）贪心算法 教学内容：1. 找零钱问题2. 贪心算法的基本要素3. 机器调度问题4. 活动安排问题5. 最优装载问题6. 单源最短路径问题7. 哈夫曼编码8. 最小生成树9. 贪心算法的理论基础*教学要求：掌握贪心法解决问题的一般步骤，掌握贪心法和动态规划方法的异同。学会使

4、用贪心法解决实际问题。（六）回溯法 教学内容：1. 回溯法的基本框架2. 0/1背包问题3. 迷宫老鼠4. 装载问题5. N后问题6. 骑士遍历问题7. 批处理作业调度8. 回溯法的效率分析*教学要求：掌握回溯法解决问题的一般步骤，掌握回溯法与贪心法、动态规划法的异同以及不同算法的效率分析。学会使用回溯法解决实际问题。（七）分支限界法教学内容：1. 分支限界法的基本思想2. 迷宫老鼠问题3. 布线问题4. 0/1背包问题5. 装载问题6. 批处理作业调度问题教学要求：掌握分支限界法解决问题的基本思想，注意比较与前四种算法的异同，学会使用分支限界法解决实际问题。（八）NP完全性理论* 教学内容：

5、1. 计算模型2. P类与NP类问题3. NP完全问题4. 一些典型的NP完全问题教学要求：了解NP基本理论，了解NP问题和非NP问题的异同，研究新方法解决NP问题的可能性说明：本章为选修部分，可根据教学情况安排为讲授或自学。三、学时分配表序号内容讲授实验小计1算法概述2022递归的基本概念2023分治策略4154动态规划法102125贪心算法8196回溯法6287分支限界法6288NP完全性理论*2029其它202小 计40848四、实验学时分配表序号内 容要 求小计实验一分治策略掌握分治策略的基本思想以及用分治法解决问题的一般技巧1学时实验二动态规划掌握动态规划解决问题的一般过程，学会使用动态规划解决实际问题。2学时实验三贪心算法掌握贪心法解决问题的一般步骤，学会使用贪心法解决实际1学时实验四回溯法掌握回溯法解决问题的一般步骤，学会使用回溯法解决实际问题。2学时实验五分支限界法掌握分支限界法解决问题的基本思想，学会使用分支限界法解决实际问题。2学时小计8学时五、有关说明1、 教学建议在教学中安排一定的习题讨论时间，使学生锻炼分析问题的能力。教学中的一些习题建议学生安排上机，这样才能全面掌握常用算法的分析和设计技术。2、 课程建议教材计算机算法设计与分析王晓东编著电子工业出版社3、 课程建议参考书计算机算法基础 邹海明编著华中理工大学出