算法分析与设计教学大纲

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

1、《算法分析与设计》教学大纲课程名称：算法分析与设计学时：68学分：3课程性质：专业方向选修课考核方式：考查开课对象：计算机科学与技术专业学生一、教学目的与要求《算法分析与设计》的先修课程是Ｃ语言程序设计、数据结构。计算机科学是一种创造性思维活动，其教育必须面向设计。计算机算法设计与分析正是一门面向设计且处于计算机科学核心地位的课程。该课程系统地介绍计算机算法的设计方法与分析技巧，通过课程学习，为独立地设计算法和对算法进行分析奠定坚实的知识基础，对从事计算机软件和计算机应用的研究者来说是非常重要和必不可少的。通过学习该课程，使学生在知识

2、方面要求：掌握算法的定义及基本概念、计算模型和复杂度的衡量；为分析算法的复杂性作准备，要了解相应的数学知识；掌握算法设计的过程和方法；学会分析算法的时间复杂度、空间复杂度和稳定性；具有问题抽象和建模的初步能力。在能力方面要求：通过本课程的学习，学生要掌握几种常用的算法设计策略，包括递归与分治策略、动态规划算法、贪心算法、回溯法、分支限界法概率算法、线性规划和网络流法和NP完全性理论与近似算法等，并会分析算法的效率。能够用所学方法解决实际问题。本课程总授课68学时，在第五学期开设，为考查课程，其中理论教学为34学时，实践教学为34学时。

3、二、课程内容及学时分配章节内容学时第一章算法概述2第二章递归与分治法4第三章动态规划6第四章贪心算法4第五章回溯法6第六章分支限界法4第七章概率算法2第八章线性规划和网络流4第九章NP完全性理论与近似算法2实验一递归与分治法6实验二动态规划6实验三贪心算法4实验四回溯法6实验五分支限界法4实验六综合实验6考核考查2合计68第一部分理论教学第一章算法概述（2学时）主要内容：1、算法；2、算法复杂度的基本概念；3、时间复杂度的估算方法。要求：1、了解算法和算法复杂度的基本概念；2、掌握时间复杂度的估算方法。第二章递归与分治法（4学时）主要

4、内容：1、递归概念；2、分治法基本思想；3、二分搜索技术；4、大整数乘法；5、矩阵乘法；6、棋盘覆盖；7、合并排序；8、快速排序；9、线性时间选择；10、最接近点对问题；11、循环赛日程表。要求：1、掌握递归的概念，学会用递归方法解决实际问题；2、熟练掌握利用分治法解决问题的基本思想；3、会用某高级语言对算法进行描述；4、对算法复杂度（时间和空间）进行分析。第三章动态规划（6学时）主要内容：1、动态规划的基本要素；2、矩阵连乘；3、最长公共子序列；4、最大子段和；5、凸多边形最优三角剖分；6、多边形游戏；7、图像压缩；8、电路布线；9

5、、流水作业调度；10、0-1背包问题；11、最优二叉搜索树。要求：1、熟练掌握利用动态规划方法解决问题的基本思想；2、学会如何将问题化为多阶段图的方法；3、能对具体问题写出正确的递推公式。第四章贪心算法（4学时）主要内容：1、贪心算法的基本要素；2、活动安排问题；3、最优装载；4、哈夫曼编码；5、单源最短路径；6、最小生成树；7、多机调度。要求：1、掌握利用贪心算法解决问题的基本思想；2、会用某高级语言编写用贪心算法解决问题的程序；3、能对算法的复杂度，可靠性进行分析。第五章回溯法（6学时）主要内容：1、回溯法的算法框架、符号；2、三

6、角形问题；3、n个皇后问题；4、最大团问题；5、图的m着色问题；6、旅行售货员问题；7、圆排列问题；8、连续邮资问题；9、电路板排列问题。要求：1、掌握利用回溯法解决问题的基本思想；2、会用回溯法解决：n个皇后问题，图的m着色问题，批处理作业调度问题等；3、能准确地分析回溯法的效率及稳定性。第六章分支限界法（4学时）主要内容：1、分支限界的基本思想；2、单源最短路径；3、布线问题；4、0－1背包问题；5、批处理作业调度问题。要求：1、掌握利用分支限界法解决问题的基本思想；2、能用多种不同方法解法同一问题；3、分析各方法的效率。第七章概

7、率算法（2学时）主要内容：1、概率算法的基本思想；2、随机数；3、数值概率算法；4、舍伍德算法；5、拉斯维加斯算法；6、蒙特卡罗算法。要求：1、掌握利用概率算法的基本思想；2、会用概率算法解决有关问题。第八章线性规划和网络流（4学时）主要内容：1、线性规划的基本概念、定理及单纯形算法；2、最大网络流和最小费用流问题的解法。要求：1、了解线性规划模型的特点、线性规划问题的标准型及退化处理；2、掌握线性规划问题解的概念、有关解的基本定理；3、掌握单纯形法的的原理和求解方法；4、掌握实践中常见问题的建模方法；5、掌握最大网络流问题的求解方法

8、和最小费用流问题的求解方法。第九章NP完全性理论与近似算法（2学时）主要内容：1、计算模型；2、P类与NP类问题；3、NP完全问题；4、合取范式（CNF）顶点覆盖问题；5、哈密顿回路问题；6、近似算法的基本思想及性能；7