算法分析与设计课程

《算法分析与设计课程》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

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

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

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

4、编码8.最小生成树9.贪心算法的理论基础*教学要求：掌握贪心法解决问题的一般步骤，掌握贪心法和动态规划方法的异同。学会使用贪心法解决实际问题。（六）回溯法教学内容：1.回溯法的基本框架2.0/1背包问题3.迷宫老鼠4.装载问题5.N后问题6.骑士遍历问题7.批处理作业调度8.回溯法的效率分析*教学要求：掌握回溯法解决问题的一般步骤，掌握回溯法与贪心法、动态规划法的异同以及不同算法的效率分析。学会使用回溯法解决实际问题。（七）分支限界法6教学内容：1.分支限界法的基本思想2.迷宫老鼠问题3.布线问题4.0/1背包问题5.装载问题

5、6.批处理作业调度问题教学要求：掌握分支限界法解决问题的基本思想，注意比较与前四种算法的异同，学会使用分支限界法解决实际问题。（八）NP完全性理论*教学内容：1.计算模型2.P类与NP类问题3.NP完全问题4.一些典型的NP完全问题教学要求：了解NP基本理论，了解NP问题和非NP问题的异同，研究新方法解决NP问题的可能性说明：本章为选修部分，可根据教学情况安排为讲授或自学。三、学时分配表序号内容讲授实验小计1算法概述2022递归的基本概念2023分治策略4154动态规划法102125贪心算法8196回溯法62867分支限界法6

6、288NP完全性理论*2029其它202小计40848四、实验学时分配表序号内容要求小计实验一分治策略掌握分治策略的基本思想以及用分治法解决问题的一般技巧1学时实验二动态规划掌握动态规划解决问题的一般过程，学会使用动态规划解决实际问题。2学时实验三贪心算法掌握贪心法解决问题的一般步骤，学会使用贪心法解决实际1学时实验四回溯法掌握回溯法解决问题的一般步骤，学会使用回溯法解决实际问题。2学时实验五分支限界法掌握分支限界法解决问题的基本思想，学会使用分支限界法解决实际问题。2学时小计8学时五、有关说明1、教学建议在教学中安排一定的习

7、题讨论时间，使学生锻炼分析问题的能力。教学中的一些习题建议学生安排上机，这样才能全面掌握常用算法的分析和设计技术。2、课程建议教材《计算机算法设计与分析》王晓东编著电子工业出版社3、课程建议参考书《计算机算法基础》邹海明编著华中理工大学出版社《计算机算法设计与分析》苏德富编著电子工业出版社4、本课程的先修课程和实践性环节的名称和内容安排在《C语言》、《数据结构》课程之后开设。6执笔人：陈利民审定人：胡智喜批准人：徐煜明6