计算机算法设计与分析教学大纲.doc

计算机算法设计与分析教 学 大 纲一课程性质与教学目的本课程是计算机科学与技术专业研究生一年级的专业选修课，是研究计算机算法设计与分析的基本理论、方法和应用。本课程的教学目的是，培养学生分析问题和解决问题的能力，使学生掌握算法设计的基本方法，熟悉算法分析的基本技术，并能熟练运用一些常用算法，为学生进一步学习后续课程奠定良好的基础。二课程要求(1)掌握算法的定义及基本概念,计算模型和复杂度的衡量;(2)为分析算法的复杂性做准备,要了解相应的数学知识;(3)掌握算法设计的过程和方法;(4)学会分析算法的时间复杂度,空间复杂度和稳定性;(5)具有问题抽象和建模的初步能力.三教学内容及要求教学内容教学要求第1章 算法概述1.1 算法与程序1.2 算法复杂性分析1.3 NP完全性理论掌握算法,算法复杂度的基本概念,及时间复杂度的估算方法，理解NP完全性理论第2章 递归与分治策略2.1 递归的概念2.2 分治法的基本思想2.3 二分搜索技术2.4 大整数的乘法2.5 Strassen矩阵乘法2.6 棋盘覆盖2.7 合并排序2.8 快速排序2.9 线性时间选择2.10最接近点对问题2.11循环赛日程表掌握递归的概念,学会用递归方法解决实际问题,熟练掌握利用分治法解决问题的基本思想,会用某高级语言对算法进行描述,并对算法复杂度(时间和空间)进行分析第3章 动态规划3.1 矩阵连乘问题3.2 动态规划算法的基本要素3.3 最长公共子序列3.4 最大子段和3.5 凸多边形最优三角剖分3.6 多边形游戏3.7 图像压缩3.8 电路布线3.9 流水作业调度3.10 0-1背包问题3.11最优二叉搜索树熟练掌握利用动态规划方法解决问题的基本思想,学会如何将问题化为多阶段图的方法,并能对具体问题写出正确的递推公式第4章 贪心算法4.1 活动安排问题4.2 贪心算法的基本要素4.3 最优装载4.4 哈夫曼编码4.5 单源最短路径4.6 最小生成树4.7 多机调度问题掌握利用贪心算法解决问题的基本思想,会用某高级语言编写用贪心算法解决问题的程序,并能对算法的复杂度,可靠性进行分析第5章 回溯法5.1 回溯法的算法框架5.2 装载问题5.3 批处理作业调度5.4 符号三角形问题5.5 n后问题5.6 0-1背包问题5.7 最大团问题5.8 图的m着色问题5.9 旅行售货员问题5.10圆排列问题5.11电路板排列问题5.12连续邮资问题5.13回溯法的效率分析掌握利用回溯法解决问题的基本思想,会用回溯法解决n个皇后问题,图的m着色问题,批处理作业调度问题等,并能准确地分析回溯法的效率及稳定性第6章 分支限界法6.1 分支限界法的基本思想6.2 单源最短路径问题6.3 装载问题6.4 布线问题6.5 0-1背包问题6.6 最大团问题6.7 旅行售货员问题6.8 电路板排列问题6.9 批处理作业调度掌握利用分支限界法解决问题的基本思想,能用多种不同方法解法同一问题,并分析各方法的效率第7章 随机化算法7.1 随机数7.2 数值随机化算法7.3 舍伍德(Sherwood)算法7.4 拉斯维加斯(Las Vegas)算法7.5 蒙特卡罗(Monte Carlo)算法掌握利用随机化算法的基本思想,会用随机化算法解决有关问题第8章 线性规划与网络流8.1 线性规划问题和单纯形算法8.2 最大网络流问题8.3 最小费用流问题了解线性规划模型的特点,线性规划问题的标准型及退化处理,掌握线性规划问题解的概念,有关解的基本定理;掌握单纯形法的的原理和求解方法;掌握实践中常见问题的建模方法.掌握最大网络流问题的求解方法和最小费用流问题的求解方法四使用教材和教学参考书 使用教材：王晓东编，计算机算法设计与分析（第4版），电子工业出版社，2012年1月。教