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

1、算法设计与分析课程教学大纲课程名称：算法设计与分析英文名称：The Design and Analysis of Algorithm课程编号：x2050121学 时 数：48其中实验学时数：16 课外学时数：0学 分 数：3.0适用专业：软件工程、软件工程（金融方向）、软件工程（物流方向）、信息与计算科学一、课程的性质和任务算法设计与分析是软件工程、软件工程（金融方向）、软件工程（物流方向）和信息与计算科学等专业的一门专业基础课。软件的效率和稳定性取决于软件中所采用的算法；对于一般程序员和计算机专业学生，学习算法设计与分析课程，可以开阔编程思路，编写出优质程序。通过本课程的学习，学生要掌握几种

2、常用的算法设计策略，包括递归与分治策略、动态规划算法、贪心算法、回溯法、分支限界法、概率算法、线性规划和网络流法和NP完全性理论与近似算法等，并会分析算法的效率，能够用所学方法解决实际问题。二、课程教学内容的基本要求、重点和难点（一）算法概述掌握算法，算法复杂度的基本概念，及时间复杂度的估算方法。（二）递归与分治法掌握递归的概念，学会用递归方法解决实际问题，熟练掌握利用分治法解决问题的基本思想，会用某高级语言对算法进行描述，并对算法复杂度（时间和空间）进行分析。主要内容：递归概念，分治法基本思想，二分搜索技术，大整数乘法，矩阵乘法，棋盘覆盖，合并排序，快速排序，线性时间选择，最接近点对问题，循

3、环赛日程表。重点：递归，分治法的基本思想。难点：递归赫分治法的应用。（三）动态规划熟练掌握利用动态规划方法解决问题的基本思想，学会如何将问题化为多阶段图的方法，并能对具体问题写出正确的递推公式。主要内容：动态规划的基本要素，矩阵连乘，最长公共子序列，最大子段和，凸多边形最优三角剖分，多边形游戏，图像压缩，电路布线，流水作业调度，0-1背包问题，最优二叉搜索树。重点：动态规划算法的基本要素。难点：动态规划算法的设计。（四）贪心算法掌握利用贪心算法解决问题的基本思想，会用某高级语言编写用贪心算法解决问题的程序，并能对算法的复杂度，可靠性进行分析。主要内容：贪心算法的基本要素，活动安排问题，最优装载

4、，哈夫曼编码，单源最短路径，最小生成树，多机调度。重点：贪心算法的基本要素。难点：贪心算法的具体应用。（五）回溯法掌握利用回溯法解决问题的基本思想，会用回溯法解决：n个皇后问题，图的m着色问题，批处理作业调度问题等，并能准确地分析回溯法的效率及稳定性。主要内容：回溯法的算法框架、符号，三角形问题，n个皇后问题，最大团问题，图的m着色问题，旅行售货员问题，圆排列问题，连续邮资问题，电路板排列问题。重点：回溯法的基本思想，回溯法的效率分析。难点：回溯法的设计。（六）分支限界法掌握利用分支限界法解决问题的基本思想，能用多种不同方法解法同一问题，并分析各方法的效率。主要内容：分支限界的基本思想，单源最

5、短路径，布线问题，01背包问题，批处理作业调度问题。重点：分支限界法的基本思想和各方法的效率分析。难点：分支限界法限界函数的设计。（七）概率算法掌握利用概率算法的基本思想，会用概率算法解决有关问题。主要内容：概率算法的基本思想，随机数，数值概率算法，舍伍德算法，拉斯维加斯算法，蒙特卡罗算法。重点：概率算法的基本思想及准确应用。难点：概率算法的设计。（八）线性规划和网络流了解线性规划模型的特点、线性规划问题的标准型及退化处理，掌握线性规划问题解的概念、有关解的基本定理；掌握单纯形法的原理和求解方法；掌握实践中常见问题的建模方法。掌握最大网络流问题的求解方法和最小费用流问题的求解方法。主要内容：线

6、性规划的基本概念、定理及单纯形算法，最大网络流和最小费用流问题的解法。重点：线性规划的思想及单纯形算法、最大网络流问题最小费用流问题的求解方法。难点：算法的具体设计技巧。（九）NP完全性理论与近似算法了解NP完全性问题，掌握P类与NP类问题的划分。掌握利用近似算法解决问题的基本思想，能对其可靠性进行分析。主要内容：计算模型，P类与NP类问题，NP完全问题，合取范式（CNF）顶点覆盖问题，哈密顿回路问题；近似算法的基本思想及性能，顶点覆盖问题的近似算法，集合覆盖问题的近似算法，子集合问题的近似算法。重点：NP完全问题、近似算法的设计与可靠性分析。难点：NP和P类问题划分，近似法设计。三、教学方式

7、及学时分配序号主要内容主要教学方 式学时分配辅导答疑比 例一算法概述讲授22:1二递归与分治法讲授+实验4+22:1三动态规划讲授+实验4+22:1四贪心算法讲授+实验4+22:1五回溯法讲授+实验4+22:1六分支限界法讲授+实验4+22:1七概率算法讲授+实验4+22:1八线性规划和网络流讲授+实验4+22:1九NP完全性理论与近似算法讲授+实验2+22:1四、课程其他教学环节要求（一）实验环节：实验学时数为16，实验项目及内容详见实验教学大纲。（二）作业：根据授课进度，布置作业，每章讲授结束后，收一次作业，批改后做集体答疑，讲解作业中出现的问题。作业的题型主要是以算法设计题为主。（三）课外：充分利用上课的实验时间进行吸收消化所学理论，同时在完成课上布置的作业外，课下应利用业余时间进行自主学习，提高程学设计能力。五、本课程与其他课程的联系先修课程是C+程序设计、数据结构、离散数学，后续课程是培养计划中的各门专业课。六、教学参考书目（授课教材）算