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

课程名称：	算法分析与设计	算法分析与设计	算法分析与设计
课程编号：	436416	408415	420416
适用专业：	软件工程	计算机科学与技术	网络工程
课程类别：	专业任选课	专业任选课	专业任选课
课程学分：	3	3	3
总学时：	48	48	48
其中：理论	32	32	32
实验	16	16	16
先修课程：	C语言程序设计

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

《算法分析与设计》是一门理论性与实践性兼顾的课程，是软件工程、计算机科学与技术、网络工程及相关专业的基础课程。课程是“编译原理”和“软件工程”等专业核心课程的基础课，为学习专业课程及提高软件设计水平打下良好的基础。

本课程向学生系统讲述软件设计中常用的算法设计与分析方法。学生通过对算法设计策略的系统学习与研究，理解和掌握算法设计的主要方法，锻炼独立分析问题和解决问题的能力，为开发高效的软件系统及相关领域的研究工作奠定坚实的基础。

通过本课程的学习，要求学生理解计算机算法效率分析与设计所涉及的基本概念和基础知识，掌握基本的算法分析方法和常见的算法设计方法，能熟练应用课程介绍的算法设计方法来解决软件开发中的实际问题。通过对算法实例的分析，进一步加深对算法设计方法的认识和理解。

二、课程教学基本内容与要求

第一章 概述

（一）基本教学内容

1.1 算法和程序

1.2 算法复杂性算法效率

（二）基本要求

教学目的：理解算法的概念、算法的时间复杂性和空间复杂性；掌握求解问题的基本步骤；掌握算法运行时间的估计。

教学重点：求解问题的基本步骤、算法的概念、程序与算法的区别、算法效率的分析。

教学难点：算法时间复杂性和空间复杂性的度量、算法运行时间的估计。

第二章 递归与分治策略

（一）基本教学内容

2.1 递归的概念

2.2 分治法的基本思想

2.3 二分搜索技术

2.4 大整数的乘法

2.5 矩阵乘法

2.6 棋盘覆盖

2.7合并排序

2.8快速排序

2.9线性时间选择

2.10最接近点对问题

2.11循环赛日程表

（二）基本要求

教学目的：掌握递归的概念与的基本原理；理解分治策略的基本原理和效率分析，掌握设计有效算法的分治策略。

教学重点：分治策略的基本原理与应用、递归算法的效率分析。

教学难点：分治策略的基本原理与应用、递归算法的效率分析。

第三章 动态规划

（一）基本教学内容

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.1 活动安排问题

4.2 贪心算法的基本要素

4.3 最优装载

4.4 哈夫曼编码

4.5 单源最短路径

4.6 最小生成树

4.7 多机调度问题

（二）基本要求

教学目的：理解贪心算法的基本思想、适用条件；掌握贪心算法的设计策略，掌握贪心算法典型问题的应用与分析。

教学重点：贪心策略的基本思想、适用条件及其应用、适用条件及其应用。

教学难点：贪心算法典型问题的解决方法及时间复杂性的分析。

第五章 回溯法

（一）基本教学内容

5.1 回溯法的算法框架

5.2 装载问题

5.3 批处理作业调度

5.4 符号三角形问题

5.5 n后问题

5.6 0-1背包问题

5.7 最大团问题

5.8 图的m着色问题

5.9 旅行售货员问题

5.1 0 圆排列问题

5.1 1 电路板排列问题

5.1 2 连续邮资问题

5.1 3 回溯法的效率分析

（二）基本要求

教学目的：理解回溯法的基本思想及效率估计，限界函数；掌握回溯法在典型问题的应用及分析。

教学重点：回溯法的基本思想、限界函数、效率估计、适用条件及其应用。

教学难点：回溯法的典型问题的解决方法及时间复杂性的分析。

第六章 分支限界法

（一）基本教学内容

6.1 分支限界法的基本思想

6.2 单源最短路径问题

6.3 装载问题

6.4 布线问题

6.5 0-1背包问题

6.6 最大团问题

6.7 旅行售货员问题

6.8 电路板排列问题

6.9 批处理作业调度

（二）基本要求

教学目的：理解分支限界法的基本思想及效率估计；掌握分支限界法的算法框架；掌握分支限界法在典型问题的应用。

教学重点：分支限界法的搜索策略、算法框架、典型问题的设计策略。

教学难点：分支限界法典型问题的设计策略。

第七章 随机化算法

（一）基本教学内容

7.1 随机数

7.2 数值随机化算法

7.3 舍伍德(Sherwood)算法

7.4 拉斯维加斯(Las Vegas)算法

7.5 蒙特卡罗(Monte Carlo)算法

（二）基本要求

教学目的：理解产生伪随机数的算法；掌握数值概率算法的设计思想；掌握蒙特卡罗算法、拉斯维加斯算法和舍伍德算法的设计思想。

教学重点：数值概率算法、蒙特卡罗算法、拉斯维加斯算法和舍伍德算法。

教学难点：概率算法的设计策略。

第八章 线性规划与网络流

（一）基本教学内容

8.1线性规划问题和单纯形算法

8.2最大网络流问题

8.3最小费用流问题

（二）基本要求

教学目的：理解线性规划算法的模型，理解网络与网络流的基本概念；掌握线性规划问题的单纯形算法；掌握网络最大流的增广路算法与预流推进算法；掌握网络最小费用流的消圈算法、最小费用路算法与单纯形算法。

教学重点：线性规划问题的单纯形算法、网络最大流的算法、网络最小费用流算法。

教学难点：网络最大流的算法、网络最小费用流算法。

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

（一）基本教学内容

9.1 计算模型

9.2 P类与NP类问题

9.3 NP完全问题

9.4 NP完全问题的近似算法

（二）基本要求

教学目的：理解RAM、RASP和图灵机的计算模型，理解非确定图灵机的概念；理解NP完全问题的概念；理解近似算法的性能比及多项式时间近似格式的概念；掌握近似算法在典型问题的应用。

教学重点：计算模型、NP完全问题、近似算法的性能比与典型应用。

教学难点：近似算法在典型问题的应用。

三、课程各章节学时分配

四、本课程课外学习与修学指导

本课程是“编译原理”和“软件工程”等专业核心课程的基础课，具有很强的实践性。要学好本课程，必须做到理论与实践紧密结合。要求学生多参阅相关书籍，特别是多做练习，多上机实验，掌握常用算法的基本原理与设计方法。为配合课程教学，将在学校的程序设计在线平台上开设算法分析与设计课程的专题练习。

五、本课程考核方式及成绩评定标准

考核方式：闭卷考试

成绩评定方法：本课程的考核是平时成绩、实验成绩和期终考试成绩相结合。具体比例为：上课出勤、作业占20%，实验占20%，期末考试成绩占60%。

其中期未考试总分100分，基础题占50%，中等难度题占40%，较难题占10%。考试题型主要有：选择题、填空题、判断题、程序填空题、程序分析题、编写程序题等。

六、教材及参考书

[1] 王晓东.《计算机算法分析与设计（第4版）》.北京：电子工业出版社，2012.

[2] 赵端阳 编著.《算法分析与设计》.北京：清华大学出版社，2012.

[3] 石志国，刘冀伟，姚亦飞 编著.《算法分析与设计（C++描述）》.北京：清华大学出版社，2010.

[4] 霍红卫 译.《算法分析与设计》.北京：人民邮电出版社，2006.

[5] 吴伟旭 方世昌译.《算法分析与设计》.北京：电子工业出版社，2004.

大纲撰写人： 袁辉勇

大纲审阅人： 罗如为

教学副主任：易叶青

编写日期：2012年6月