算法设计与分析课程教学大纲

1、算法设计与分析课程教学大纲课程名称：算法设计与分析英文名称：Algorithm Design and Analysis课程编号：2学 时 数：48其中实验（实训）学时数：16 课外学时数：0学 分 数：3适用专业：计算机科学与技术一、课程的性质和任务本课程是计算机科学与技术及相关专业的一门专业课，专业覆盖面较宽（如程序设计等课程）。是一门训练程序设计基本思想的主要课程。算法设计与分析是计算机科学的核心问题之一，数据结构主要研究组织大量数据的方法，而算法分析则是对算法运行时间的评估。本课程的任务是通过对常用的、有代表性的算法的研究，让学生理解并掌握算法设计的基本技术；培养学生分析算法复杂度的初步

2、能力，锻炼其逻辑思维能力和想象力，并使之了解算法理论的发展；鼓励学生运用算法知识解决实际问题，培养他们的独立科研的能力和理论联系实践的能力。本课程特别提倡学生广泛阅读参考书、独立思考、结合实际问题展开讨论的教学方式，并以此达到教师精讲、学生宽学的目的。二、课程教学内容的基本要求、重点和难点掌握算法分析与设计中每种方法的基本思想、基本方法和相关应用。 （一）算法及算法的复杂度掌握算法的定义和算法复杂度的计算。掌握时间、空间渐进分析法。会解递归方程。重点：算法复杂性的时空分析。难点：解递归方程。（二）贪婪法掌握贪婪法的基本思想。学习经典的贪婪法：背包问题和计算机网络的最短传输时间。重点：贪婪法的基

3、本思想，贪婪法的具体应用。难点：贪婪法的应用。（三）递归掌握递归的定义、递归调用的内部实现原理及递归程序的阅读的两种方法：模拟系统栈方式和指令流方法。熟练掌握递归转非递归的方法。学会递归算法的设计包括：简单0/1背包问题；N阶Hanoi塔问题；棋子移动问题；求N个元素的全排列和自然数分析。重点：递归算法的内部实现、递归算法的设计。难点：递归转非递归。（四）回溯法掌握回溯法的基本思想及回溯法的经典问题：子集和问题；皇后问题；哈密顿回路问题。重点：回溯法的基本思想。难点：回溯的具体应用。（五）动态规划掌握动态规划的定义及最优性原理，利用一些简单的例子对其方法加以说明。尤其让学生了解利用动态规划的解

4、题的优点：能够求最优并能够减少冗余爆炸，即如何进行表格的设计和填写，如组合问题等。熟练掌握动态规划的经典问题：最短路径问题和最优树问题。重点：动态规划的定义及最优性原理。难点：利用动态规划解决实际问题。（六）分治法掌握分治法的基本思想，分治法的设计特点及如何计算分治法的时间复杂性。最后学习分治法的应用：二分查找、合并排序、快速排序及矩阵乘法（常规算法和改进的斯特拉森分治法）。重点：分治法基本思想及分治法的时间复杂性分析。难点：分治法时间复杂性分析及其应用。（七）探索法掌握探索法的基本思想，探索法算法设计的常用的方法和特点，探索方法的应用。重点：探索法的基本思想。难点：探索法的具体应用。（八）分

5、枝限界法理解状态空间树上的三种检索方式：FIFO，LIFO，LC检索。掌握LC分枝限界法解决最优化问题。理解0/1背包的解法。重点：FIFO、LIFO、LC检索，分支限界法解最优化问题。难点：LC检索。（九）内存分类法掌握内存分类法。掌握求第K个元素及堆分类算法。重点：内部排序算法。难点：堆排序。（十）图的算法掌握图的两种遍历：DFS，BFS；掌握DFS树的定义和相关概念。学会分析、设计无向图的双连通分支和有向图的强连通分支。掌握流的相关算法。重点：图的遍历方法。难点：图的连通分支。三、教学方式及学时分配序号主要内容主要教学方式学时分配辅导答疑比例一算法及算法的复杂性讲授22：1二贪婪法讲授+

6、实验2+22：1三递归讲授42：1四回溯法讲授+实验2+22：1五动态规划讲授+实验4+22：1六分治法讲授+实验4+22：1七探索法讲授+实验2+22：1八分枝限界法讲授+实验4+22：1九内存分类法讲授22：1十图的算法讲授+实验6+42：1四、课程其他教学环节要求写出本课程的先修和后续课程（一）、实验环节实验一：计算机网络最短传输时间：要求掌握贪婪法程序设计思想与设计方法。实验二：图的着色问题：要求掌握回溯法程序设计思想与设计方法。实验三：最优调度：要求掌握动态规划法程序设计思想与设计方法。实验四：矩阵乘法：要求掌握分治法程序设计思想与设计方法。实验五：迷宫问题：要求掌握探索法程序设计思

7、想与设计方法。实验六：0/1背包问题：要求掌握分枝限界法程序设计思想与设计方法。实验七：算法可视化：要求将算法的执行过程和结果通过可视化界面表现出来，结合可视化语言进行综合性程序设计。（二）作业根据授课进度，布置作业，每章讲授结束后，收一次作业，批改后做集体答疑，讲解作业中出现的问题。作业的题型为：问答题、算法设计题，主要是以算法设计题为主。（三）课外充分利用上课的实验时间进行吸收消化所学理论，同时在完成课上布置的作业外，课下应利用业余时间进行自主学习，提高程学设计能力。五、本课程与其他课程的联系先修课程：数据结构六、教学参考书目算法设计与分析 周培德 著 机械工业出版社 1992算法设计与分析 吴哲辉, 曹立明, 蒋昌俊 编著 煤炭工业出版社