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

《算法分析与设计》课程教学大纲 一、课程基本信息 课程代码：110426 课程名称：算法分析与设计 英文名称：Analysis and Design of Algorithms 课程类别：专业基础课 学 时：45 学 分：2 适用对象: 信息与计算科学专业本科生 考核方式：考试（平时成绩占总成绩的30％） 先修课程：数学分析、高级语言程序设计、数据结构

二、课程简介 中文简介 《算法分析与设计》是软件开发人员必修专业课，软件的效率和稳定性取决于软件中所采用的算法；对于一般程序员和软件类专业学生，学习算法设计与分析课程，可以开阔编程思路，编写出优质程序。 英文简介 Analysis and Design of Algorithms is a compulsory specialty course for software developer. Efficiency and stability of software depends on algorithms used in it. For common coders and software relative students, learning this course could expand their programming vision and help them programming high quality codes.

三、课程性质与教学目的 通过对常用的、有代表性的算法的研究，让学生理解并掌握算法设计的基本技术。培养学生分析算法复杂度的初步能力，锻炼其逻辑思维能力和想象力，并使之了解算法理论的发展。 鼓励学生运用算法知识解决各自学科的实际问题，培养学生的独立科研的能力和理论联系实践的能力。

四、教学内容及要求 第一章 算法概述 (一) 目的与要求 掌握算法，算法复杂度的基本概念，及时间复杂度的估算方法。 (二) 教学内容 1. 主要内容 算法，算法复杂度的基本概念，及时间复杂度。 2. 基本概念和知识点 算法，算法复杂度的基本概念，及时间复杂度。 3. 问题与应用（能力要求） 掌握算法，算法复杂度的基本概念，及时间复杂度的估算方法。 (三) 课后练习 函数的渐进表达式。 (四) 教学方法与手段 课堂讲授为主，结合课堂分组讨论。

第二章 递归与分治法 （一）目的与要求 1. 掌握递归的概念，学会用递归方法解决实际问题； 2. 熟练掌握利用分治法解决问题的基本思想，会用某高级语言对算法进行描述，并对算法复杂度（时间和空间）进行分析。 （二）教学内容 1．主要内容 递归概念，分治法基本思想，二分搜索技术，大整数乘法，矩阵乘法，棋盘覆盖，合并排序，快速排序，线性时间选择，最接近点对问题，循环赛日程表。 2．基本概念和知识点 递归概念，分治法，二分搜索，大整数乘法，矩阵乘法，棋盘覆盖，合并排序，快速排序。 3．问题与应用（能力要求） 掌握递归的概念，学会用递归方法解决实际问题，熟练掌握利用分治法解决问题的基本思想，会用某高级语言对算法进行描述，并对算法复杂度（时间和空间）进行分析。 （三）课后练习 Hanoi塔问题的非递归算法。 （四）教学方法与手段 课堂讲授为主，结合课堂分组讨论。

第三章 动态规划 （一）目的与要求 1．熟练掌握利用动态规划方法解决问题的基本思想； 2．学会如何将问题化为多阶段图的方法； 3．能对具体问题写出正确的递推公式。 （二）教学内容 1．主要内容 动态规划的基本要素，矩阵连乘，最长公共子序列，最大子段和，凸多边形最优三角剖分，多边形游戏，图像压缩，电路布线，流水作业调度，0-1背包问题，最优二叉搜索树。 2．基本概念和知识点 动态规划的基本要素，最长公共子序列，最大子段和，凸多边形最优三角剖分,0-1背包问题，最优二叉搜索树。 3．问题与应用（能力要求） 熟练掌握利用动态规划方法解决问题的基本思想。 （三）课后练习 最长单调递增子序列。 （四）教学方法与手段 课堂讲授为主，结合分组课堂讨论。

第四章 贪心算法 （一）目的与要求 1．掌握利用贪心算法解决问题的基本思想； 2．会用某高级语言编写用贪心算法解决问题的程序，并能对算法的复杂度，可靠性进行分析。 （二）教学内容 1．主要内容 贪心算法的基本要素，活动安排问题，最优装载，哈夫曼编码，单源最短路径，最小生成树，多机调度。 2．基本概念和知识点 贪心算法，哈夫曼编码，单源最短路径，最小生成树。 3．问题与应用（能力要求） 掌握利用贪心算法解决问题的基本思想。 （三）实践环节与课后练习 活动安排问题的贪心选择算法。 （四）教学方法与手段 课堂讲授为主，结合课堂分组讨论。

第五章 回溯法 （一）目的与要求 1．掌握利用回溯法解决问题的基本思想； 2．会用回溯法解决：n个皇后问题，图的m着色问题，批处理作业调度问题等，并能准确地分析回溯法的效率及稳定性。 （二）教学内容 1. 主要内容 回溯法的算法框架、符号，三角形问题，n个皇后问题，最大团问题，图的m着色问题，旅行售货员问题，圆排列问题，连续邮资问题，电路板排列问题。 2. 基本概念和知识点 回溯法，三角形问题，n个皇后问题，最大团问题，图的m着色问题，旅行售货员问题。 3. 问题与应用（能力要求） 掌握利用回溯法解决问题的基本思想。 （三）课后练习 装载问题的改进回溯法。 （四）教学方法与手段 课堂讲授为主，结合课堂分组讨论。

第六章 分支限界法 （一）目的与要求 1. 掌握利用分支限界法解决问题的基本思想； 2. 能用多种不同方法解法同一问题，并分析各方法的效率。 （二）教学内容 1．主要内容 分支限界的基本思想，单源最短路径，布线问题，0－1背包问题，批处理作业调度问题。 2．基本概念和知识点 分支限界，单源最短路径，布线问题，0－1背包问题，批处理作业调度问题。 3. 问题与应用（能力要求） 掌握分支限界法解决问题的基本思想，能用多种不同方法解法同一问题，并分析各方法的效率。 （三）实践环节 0-1背包问题的栈式分支限界法。 （四）教学方法与手段 课堂讲授为主，结合课堂分组讨论。

*第七章 概率算法（选学） （一）目的与要求 1. 掌握利用概率算法的基本思想； 2. 会用概率算法解决有关问题。 （二）教学内容 1．主要内容 概率算法的基本思想，随机数，数值概率算法，舍伍德算法，拉斯维加斯算法，蒙特卡罗算法。 2．基本概念和知识点 概率算法，随机数，数值概率算法，舍伍德算法，拉斯维加斯算法，蒙特卡罗算法。 3. 问题与应用（能力要求） 掌握利用概率算法的基本思想,会用概率算法解决有关问题。 （三）实践环节与课后练习 模拟正态分布随机变量。 （四）教学方法与手段 课堂讲授为主，结合课堂分组讨论。

*第八章 线性规划和网络流（自学） （一）目的与要求 1. 了解线性规划模型的特点、线性规划问题的标准型及退化处理； 2. 掌握线性规划问题解的概念、有关解的基本定理； 3. 掌握单纯形法的的原理和求解方法； 4. 掌握实践中常见问题的建模方法； 5. 掌握最大网络流问题的求解方法和最小费用流问题的求解方法。 （二）教学内容 1．主要内容 线性规划的基本概念、定理及单纯形算法，最大网络流和最小费用流问题的解法。 2．基本概念和知识点 线性规划概念、定理及单纯形算法，最大网络流和最小费用流问题的解法。 3. 应用（能力要求） 掌握线性规划问题解的概念、有关解的基本定理；掌握单纯形法的的原理和求解方法；掌握实践中常见问题的建模方法。掌握最大网络流问题的求解方法和最小费用流问题的求解方法。 （三）实践环节与课后练习 单源最短路径与线性规划。 （四）教学方法与手段 课堂讲授为主，结合课堂分组讨论。

*第九章 NP完全性理论与近似算法（选学） （一）目的与要求 1．了解NP完全性问题； 2．掌握P类与NP类问题的划分； 3．掌握利用近似算法解决问题的基本思想，能对其可靠性进行分析。 （二）教学内容 1．主要内容 计算模型，P类与NP类问题，NP完全问题，合取范式（CNF）顶点覆盖问题，哈密顿回路问题；近似算法的基本思想及性能，顶点覆盖问题的近似算法，集合覆盖问题的近似算法，子集合问题的近似算法。 2．基本概念和知识点 计算模型，P类与NP类问题，NP完全问题，合取范式（CNF）顶点覆盖问题，哈密顿回路问题。 3．问题与应用（能力要求） 了解NP完全性问题,掌握P类与NP类问题的划分。掌握利用近似算法解决问题的基本思想，能对其可靠性进行分析。 （三）实践环节与课后练习 RAM和RASP程序。 （四）教学方法与手段 课堂讲授为主，结合课堂分组讨论。

五、各教学环节学时分配 教学环节

教学时数 课程内容 讲 课 习 题 课 讨 论 课 实验 其他教学环节 小 计

第一章 算法概述 3 0 0 0 0 3

第二章 递归与分治法 6 0 0 0 0 6

第三章 动态规划 6 0 0 3 0 9

第四章 贪心算法 6 0 0 0 0 6 第五章 回溯法 6 0 0 3 0 9

第六章 分支限法 6 0 0 0 0 6

第七章 概率算法 3 0 0 0 0 3

第八章 线性规划和网络流 0 0 0 0 0 0

第九章NP完全性理论与近似

算法 3 0 0 0 0 3

课程设计一周 合计 39 0 0 6 0 45