算法设计与分析 教学大纲

《算法设计与分析》教学大纲

适用于四年制本科计算机应用技术、信息与计算科学专业 （参考学时数：64 学时） 一、课程代码

7100450，7100451

二、课程的性质、任务

算法设计与分析是计算机科学的核心问题之一，这门课是计算机专业以及相关专业的一门重要的课程。本课程的教学目的是：在学生学习掌握了编程的基本技术，掌握了数据结构的基本知识、理论的基础上，比较系统的学习算法理论中的基础部分内容。在这一课程教学中，培养学生掌握算法设计的方法论，掌握常用的算法设计的方法；掌握算法分析的基本工具、方法、技巧，在解决实际问题时，对于较复杂的问题能抽象出问题的数学模型，设计出有效的算法。在此基础上学习本课程的中级篇：结构上的算法设计（分类、图的高级部分、流），学生通过这部分的学习，了解算法优化的实现途径，很好的解决数据结构中未能解决的问题、最后是本课程的高级篇：NP完全理论、现代优化计算方法简介。学生通过这部分的学习初步了解计算复杂性理论的基本内容、现代算法的几个主要发展分支，为今后实际应用或者搞理论研究打下一些必备的理论基础。��

三 、课程基本要求

学生必备的先行课是：高等数学、离散数学、程序设计、数据结构。本课程不能求快，应循序渐进，培养学生浓厚的学习热情和求知欲。教学中注重和前期课程数据结构的衔接，使学生明白这门课不同于数据结构的是：数据结构是讨论三种基本数据结构上的基本操作的实现，它是完成“如何做”，算法设计与分析这门课强调的是：怎么巧做，做的更好。在本课程的后期教学中，特别提倡学生广泛阅读参考书、独立思考、结合实际问题展开讨论的教学方式，并以此达到教师精讲、学生宽学的目的。 课程的基本要求是：

1．掌握7种常用的算法设计方法，并能综合、灵活的使用这些基本方法，同时用所学到的知识解决一些实际问题；

2．掌握算法分析的基本工具、基本技巧、基本方法；

3．掌握数据结构中未能详细、深入了解的部分内容（内存分类，图的高级部分、流上的算法）；

4．了解计算复杂性理论中的基本内容，包括：机器模型，NP完全、NP难题，近似计算； 5．了解现代的计算算法和算法理论的发展趋势走向。 四、课程内容

第1章 算法及算法的复杂性

掌握算法，算法复杂度的基本概念，分析方法，及时间复杂度的估算方法。 第2章 贪婪法

掌握利用贪婪法解决问题的基本思想，并能对算法的复杂度，可靠性进行分析。

主要内容：贪婪法的基本思想，背包问题，有期限的计算机作业调度的贪婪算。增加阅读部分：计算机网络的最短传输时间等问题的贪婪法求解。 第3章 递归法

掌握递归的概念，递归调用的内部实现原理，递归算法的理解，递归转非递归的实现，递归算法的设计，并对算法复杂度（时间和空间）进行分析。

主要内容：递归调用的内部实现原理，递归算法的理解，递归转非递归的实现，递归算法的设计（若干例子：简单的0/1背包问题、汉诺塔问题、棋子的移动、求n个元素的全排列、自然数的拆分等问题）

第4章 回溯法

掌握利用回溯法解决问题的基本思想，通过解决子集和数、n个皇后问题、图的m着色问题、哈密尔顿回路等问题。掌握回溯法的递归与非递归的实现。

主要内容：回溯法的算法框架，子集和数、n个皇后问题、图的m着色问题、哈密尔顿回路等问题的回溯算法。

第5章 动态规划

熟练掌握利用动态规划方法解决问题的基本思想，学会如何将问题化为多阶段图的方法，并能对具体问题写出正确的递推公式。

主要内容：动态规划的基本要素，数塔、中国象棋马、最小代价子母树、最短路径问题、最优二叉搜索树、最优调度问题的动态规划算法设计。 第6章 分治法

掌握利用分治法解决问题的基本思想，时间复杂度分析；掌握分治法与递归法的区别和联系。 主要内容：分治法解决问题的基本思想，时间复杂度分析；斯特拉森矩阵乘法、多项式的乘法。

第7章 探索法

掌握利用探索法解决问题的基本思想，探索法的应用

主要内容：探索法解决问题的基本思想，探索法的应用：迷宫问题、计算机作业调度问题等。 第8章 分枝－限界法

掌握利用分支限界法解决问题的基本思想，能用多种不同方法解法同一问题，并分析各方法的效率。

主要内容：分支限界的基本思想，LC－检索，15－谜问题、带期限的作业调度、0/1背包问题等。

第9章 内存分类法

掌握求第K元素的求解，堆分类的优化算法，建立算法优化的概念。 主要内容：求第K元素的求解，堆分类的优化算法及算法分析。

第10章 图的算法

掌握图的两种遍历――DFS、BFS,DFS树，无向图的双连通分支，有向图的强连通分支，流的算法，解决数据结构中的部分扩展内容。

主要内容：图的两种遍历――DFS、BFS,DFS树，无向图的双连通分支，有向图的强连通分支，流的算法

五、学时分配

本课程总学时为64学时，全部是理论学时，计4个学分。

序号 教学内容 讲授学时 实验学时 1． 算法及算法的复杂性 12 2． 贪婪法 8 3． 递归 6 4． 回溯法 6 5． 动态规划 8 6． 分治法 4 7． 探索法 4 8． 分支－限界法 6 9． 内存分类 4 10． 图的算法 4 机动 2

六、课程实验（或设计）内容及基本要求

详见算法设计与分析课程设计的教学大纲。 七、推荐教材、参考书 教 材：《算法设计与分析》 宋 文等编 重庆大学出版社，2001。 参考书：

1．算法设计与分析，周培德，电子工业出版社，2001;

2．计算机算法设计与分析，王晓东，电子工业出版社，2004;

3．E.Horowitz, S.Sahni and D.Mehta, Fundamentals of Data Structure in C++. W. h. Freeeman, NewYork, NY, 1994;

4．计算科学导论，赵致琢，科学出版社，2000。 八、大纲使用说明

教材的第 11、12章不作要求。对于各章节所涉及的具体教学内容，教师可按实际情况适当增删