《算法设计与分析》教学大纲

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

课程编号:

课程名称：算法分析与设计 英文名称：The Design and Analysis of Algorithms 课程类型: 专业必修课 总 学 时：48 学 分：2.5

适用对象: 计算机科学与技术、软件工程等专业 先修课程：离散数学、程序设计语言、数据结构

讲课学时：32 实验学时：16

一、课程性质、目的和任务

课程性质：专业必修课； 课程目的和任务：

(1) 掌握各种主要的算法设计技术，领会其基本原理，并能应用理论知识对实际应用问题设计算法；

(2) 使学生了解算法复杂性的一些基本理论，掌握关于算法复杂性的基本概念和算法复杂性分析的各种基本方法；

(3) 使学生学会对具体问题设计高效的算法，对具体算法分析其复杂性，培养算法设计与分析的实践能力，进一步提高计算机程序设计的能力。

二、教学基本要求

通过本课程的学习，学生要掌握几种常用的算法设计策略，包括递归与分治策略、动态规划算法、贪心算法、回溯法、分支限界法概率算法等，并会分析算法的效率，能够用所学方法解决实际问题。软件的效率和稳定性取决于软件中所采用的算法，在完成本课程学习后，可以开阔学生的编程思路，编写出优质程序。主要包括：

(1)掌握算法的定义及基本概念，计算模型和复杂度的衡量； (2)为分析算法的复杂性做准备，要了解相应的数学知识； (3)掌握算法设计的过程和方法；

(4)学会分析算法的时间复杂度，空间复杂度和稳定性; (5)具有问题抽象和建模的初步能力。

在学习本课程之前，要求学生具备高等数学、离散数学、程序设计语言、数据结构等相关知识。

三、教学内容及要求

第1章 算法概述 2-4 1. 1 算法与程序

6-8

了解 掌握

必讲 必讲

1. 2 算法复杂性分析 第2章 递归与分治策略

1

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 最优二叉搜索树

3. 12 动态规划加速原理 第4章 贪心算法 4. 1 活动安排问题 4. 2 贪心算法的基本要素 4. 3 最优装载 4. 4 哈夫曼编码 4. 5 单源最短路径 4. 6 最小生成树 4. 7 多机调度问题 4. 8 贪心算法的理论基础 第5章 回溯法

5. 1 回溯法的算法框架 5. 2 装载问题

6-8 6-8 6-8

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 回溯法的效率分析 第6章 分支限界法 6. 1 分支限界法的基本思想 6. 2 单源最短路径问题 6. 3 装载问题 6. 4 布线问题 6. 5 0-1背包问题 6. 6 最大团问题 6. 7 旅行售货员问题 6. 8 电路板排列问题 6. 9 批处理作业调度

6-8

熟悉 熟悉 掌握 掌握 熟悉 熟悉 熟悉 了解 了解 了解 了解 理解 掌握 掌握 了解 熟悉 熟悉 熟悉 了解 了解

必讲 必讲 必讲 必讲 必讲 必讲 必讲 选讲 选讲 选讲 选讲 必讲 必讲 必讲 选讲 必讲 必讲 必讲 选讲 选讲

四、实践环节

1 C/C++环境及递归算法 2 演示性/验证性 必做 2 分治算法 2 综合性/设计性 必做 3 动态规划算法 4 综合性/设计性 必做 4 贪心算法 4 综合性/设计性 必做 5 回溯算法 2 综合性/设计性 必做 6 分支限界法 2 综合性/设计性 必做

六、考核方式

考试

七、推荐教材和教学参考书 （黑体，小4号字）

3

教 材：《算法设计与分析》, 王晓东编著, 清华大学出版社，2007

参考书：《算法设计技巧与分析》，M.H.Alsuwaiyel著，吴伟昶，方世昌等译，电子工业出版社，2005年

《计算机算法基础》（第二版），余祥宣、崔国华、邹海明，华中理工大学出版社，2003年

八、说明 （黑体，小4号字）

1.在课内学时中会安排1-2次的课堂练习 2.在实际讲课时，章节和时间安排可能会有所调整

4

大纲制订人：汪丽才 大纲审定人：宋曰聪 制订日期：