算法分析与设计教学大纲

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

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

3、限界法4第七章概率算法2第八章线性规划和网络流4第九章np完全性理论与近似算法2实验一递归与分治法6实验二动态规划6实验三贪心算法4实验四回溯法6实验五分支限界法4实验六综合实验6考核考查2合计68第一部分 理论教学第一章 算法概述（2学时）主要内容：1、算法；2、算法复杂度的基本概念；3、时间复杂度的估算方法。要求：1、了解算法和算法复杂度的基本概念； 2、掌握时间复杂度的估算方法。第二章 递归与分治法（4学时）主要内容：1、递归概念；2、分治法基本思想；3、二分搜索技术；4、大整数乘法；5、矩阵乘法；6、棋盘覆盖；7、合并排序；8、快速排序；9、线性时间选择；10、最接近点对问题；11、循

4、环赛日程表。要求：1、掌握递归的概念，学会用递归方法解决实际问题；2、熟练掌握利用分治法解决问题的基本思想；3、会用某高级语言对算法进行描述；4、对算法复杂度（时间和空间）进行分析。 第三章 动态规划（6学时）主要内容：1、动态规划的基本要素；2、矩阵连乘；3、最长公共子序列；4、最大子段和；5、凸多边形最优三角剖分；6、多边形游戏；7、图像压缩；8、电路布线；9、流水作业调度；10、0-1背包问题；11、最优二叉搜索树。要求：1、熟练掌握利用动态规划方法解决问题的基本思想；2、学会如何将问题化为多阶段图的方法；3、能对具体问题写出正确的递推公式。第四章 贪心算法（4学时）主要内容：1、贪心算

5、法的基本要素；2、活动安排问题；3、最优装载；4、哈夫曼编码；5、单源最短路径；6、最小生成树；7、多机调度。要求：1、掌握利用贪心算法解决问题的基本思想；2、会用某高级语言编写用贪心算法解决问题的程序；3、能对算法的复杂度，可靠性进行分析。第五章 回溯法（6学时）主要内容：1、回溯法的算法框架、符号；2、三角形问题；3、n个皇后问题；4、最大团问题；5、图的m着色问题；6、旅行售货员问题；7、圆排列问题；8、连续邮资问题；9、电路板排列问题。要求：1、掌握利用回溯法解决问题的基本思想；2、会用回溯法解决：n个皇后问题，图的m着色问题，批处理作业调度问题等；3、能准确地分析回溯法的效率及稳定性

6、。第六章 分支限界法（4学时）主要内容：1、分支限界的基本思想；2、单源最短路径；3、布线问题；4、01背包问题；5、批处理作业调度问题。要求：1、掌握利用分支限界法解决问题的基本思想；2、能用多种不同方法解法同一问题；3、分析各方法的效率。第七章 概率算法（2学时）主要内容：1、概率算法的基本思想；2、随机数；3、数值概率算法；4、舍伍德算法；5、拉斯维加斯算法；6、蒙特卡罗算法。要求：1、掌握利用概率算法的基本思想；2、会用概率算法解决有关问题。第八章 线性规划和网络流（4学时）主要内容：1、线性规划的基本概念、定理及单纯形算法；2、最大网络流和最小费用流问题的解法。要求：1、了解线性规划

7、模型的特点、线性规划问题的标准型及退化处理；2、掌握线性规划问题解的概念、有关解的基本定理；3、掌握单纯形法的的原理和求解方法；4、掌握实践中常见问题的建模方法；5、掌握最大网络流问题的求解方法和最小费用流问题的求解方法。第九章 np完全性理论与近似算法（2学时）主要内容：1、计算模型；2、p类与np类问题；3、np完全问题；4、合取范式（cnf）顶点覆盖问题；5、哈密顿回路问题；6、近似算法的基本思想及性能；7、顶点覆盖问题的近似算法；8、集合覆盖问题的近似算法；9、子集合问题的近似算法。要求：1、了解np完全性问题；2、掌握p类与np类问题的划分；3、掌握利用近似算法解决问题的基本思想，能

8、对其可靠性进行分析。第二部分 实践教学环节序号实验项目学时数项目要求项目类型项目性质目的要求所在实验分室1递归与分治法6必修模拟设计掌握递归的概念，学会用递归方法解决实际问题；熟练掌握利用分治法解决问题的基本思想，会用某高级语言对算法进行描述，并对算法复杂度（时间和空间）进行分析。计算机应用2动态规划6必修模拟设计熟练掌握利用动态规划方法解决问题的基本思想，学会如何将问题化为多阶段图的方法，并能对具体问题写出正确的递推公式。计算机应用3贪心算法4必修模拟设计掌握利用贪心算法解决问题的基本思想，会用某高级语言编写用贪心算法解决问题的程序，并能对算法的复杂度，可靠性进行分析。计算机应用4回溯法6必

9、修模拟设计掌握利用回溯法解决问题的基本思想，会用回溯法解决：n个皇后问题，图的m着色问题，批处理作业调度问题等。计算机应用5分支限界法4必修模拟设计掌握利用分支限界法解决问题的基本思想，能用多种不同方法解法同一问题，并分析各方法的效率计算机应用6综合实验6必修模拟设计掌握几种常用的算法设计策略，包括递归与分治策略、动态规划算法、贪心算法、回溯法、分支限界法，并会分析算法的效率。能够用所学方法解决实际问题。计算机应用三、推荐教材和主要参考书目推荐教材：1 王晓东编著.计算机算法设计与分析(第二版). 电子工业出版社，2004年7月主要参考书目：1 余祥宣, 崔国华, 邹海明. 计算机算法基础（第二版）. 华中理工大学出版社，2000年1月第一版2 卢开澄编著，计算机算法导引-设计与分析，清华大学出版社，1996年12月3 sara baase, allen van gelder. computer algorithms introduct