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

（2013版）

课程编码：0611102103

课程名称：算法分析与设计

学时/学分：48/3

先修课程：《程序设计基础》、《数据结构》

适用专业：计算机科学与技术

开课教研室：软件工程教研室

执笔：

审定：

一、课程性质与任务

1．课程性质：

算法设计与分析是一门理论性与实践性兼顾的课程，是与计算科学专业的重要课程之一；为专业选修课。

2．课程任务

通过本课程的学习，应使学生掌握算法分析方法，掌握蛮力法、分治法、减治法、动态规划法、贪心法、回溯法分支限界法等算法设计技术，通过不同的算法设计技术在同一问题中的应用进行比较，牢固掌握算法设计技术的基本策略，深刻体会算法设计技术的思想方法，综合利用多种算法设计技术更有效地解决问题。

二、课程教学基本要求

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

本课程共计学时：48，理论学时32，实践学时16。

成绩考核形式：末考成绩（闭卷机试考查）（70%）＋平时成绩（平时测验、作业、实验、课堂讨论等）（30%)。成绩评定采用百分制，60分为及格。

三、课程教学内容

第一章 算法设计基础

1.教学基本要求

使学生初步认识课程的性质与作用，激发课程学习热情。

2.要求学生掌握的基本概念、理论、技能

通过本章教学使学生了解算法的概念，描述方法；了解常见的重要问题类型。

3.教学重点和难点

教学重点和难点是算法设计的一般过程。

4.教学内容

（1）算法的基本概念

主要知识点：算法及其重要特性；算法的描述方法；算法设计的一般过程。

（2）为什么要学习和研究算法

主要知识点：算法在问题求解中的地位；算法训练能够提高计算思维能力；算法研究是推动计算机技术发展的关键。

（3）重要的问题类型

主要知识点：查找问题；排序问题；图问题；组合问题。

第二章 算法分析基础

1.教学基本要求

掌握算法复杂度的分析方法。

2.要求学生掌握的基本概念、理论、技能

通过本章教学使学生掌握算法的时间和空间复杂度。

3.教学重点和难点

教学重点是时间复杂度分析。教学难点是递归和非递归算法的时间复杂度分析。

4.教学内容

（1）算法的时间复杂性分析

主要知识点：输入规模与基本语句；算法的渐进分析；最好、最坏和平均情况；非递归算法的时间复杂性分析；递归算法的时间复杂性分析。

（2）算法的空间复杂性分析

主要知识点：算法的空间复杂性分析。

（3）最优算法

主要知识点：问题的计算复杂性下界；平凡下界；判定树模型。

第三章 蛮力法

1.教学基本要求

掌握利用蛮力法解决问题的基本思想，会用某高级语言对算法进行描述，并对算法复杂度（时间和空间）进行分析。

2.要求学生掌握的基本概念、理论、技能

通过本章教学使学生掌握蛮力法的设计思想、时间性能以及查找、排序、图问题和组合问题中的蛮力法。

3.教学重点和难点

教学重点是蛮力法的几种情况和解题步骤。教学难点是组合问题中的蛮力法。

4.教学内容

（1）概述

主要知识点：蛮力法的设计思想；一个简单的例子-百元买百鸡问题。

（2）查找问题中的蛮力法

主要知识点：顺序查找；串匹配。

（3）排序问题中的蛮力法

主要知识点：选择排序；起泡排序。

（4）组合问题中的蛮力法

主要知识点：0/1背包问题；任务分配问题。

（5）图问题中的蛮力法

主要知识点：TSP问题；任务分配问题。

第四章 分治法

1.教学基本要求

掌握利用分治法解决问题的基本思想，会用某高级语言对算法进行描述，并对算法复杂度（时间和空间）进行分析。

2.要求学生掌握的基本概念、理论、技能

通过本章教学使学生掌握分治法的设计思想、求解步骤、时间性能、适用条件以及排序、组合问题中的分治法。

3.教学重点和难点

教学重点是分治法的设计思想、求题步骤、适用条件。教学难点是组合问题中的分治法。

4.教学内容

（1）概述

主要知识点：分治法的设计思想；一个简单的例子-数字旋转方阵。

（2）排序问题中的分治法

主要知识点：归并排序。

（3）组合问题中的分治法

主要知识点：最大子段和问题；棋盘覆盖问题。

第五章 减治法

1.教学基本要求

掌握利用减治法解决问题的基本思想，会用某高级语言对算法进行描述，并对算法复杂度（时间和空间）进行分析。

2.要求学生掌握的基本概念、理论、技能

通过本章教学使学生掌握减治法的设计思想、时间性能，与分治法的区别，以及查找、排序、组合问题中的减治法。

3.教学重点和难点

教学重点是减治法的设计思想，与分治法的区别。教学难点是组合问题中的减治法。

4.教学内容

（1）概述

主要知识点：减治法的设计思想；一个简单的例子--两个序列的中位数。

（2）查找问题中的减治法

主要知识点：折半查找；二叉查找树；选择问题。

（3）排序问题中的减治法

主要知识点：插入排序；堆排序。

（4）组合问题中的减治法

主要知识点：淘汰赛冠军问题；假币问题。

第六章 动态规划法

1.教学基本要求

掌握利用动态规划方法解决问题的基本思想；学会如何将问题化为多阶段图的方法；能对具体问题写出正确的递推公式。

2.要求学生掌握的基本概念、理论、技能

通过本章教学使学生掌握多阶段决策过程、最优性原理，掌握动态规划法的设计思想、求解步骤、时间性能、以及图、组合和查找问题中的动态规划法。

3.教学重点和难点

教学重点是把握动态规划法的设计思想、求解步骤、组合问题中的动态规划法。教学难点是最长递增子序列问题。

4.教学内容

（1）概述

主要知识点：多阶段决策过程；动态规划法的设计思想；一个简单的例子--数塔问题。

（2）图问题中的动态规划法

主要知识点：多段图的最短路径问题；多源点最短路径问题；TSP问题。

（3）组合问题中的动态规划法

主要知识点：最长递增子序列问题；最长公共子序列问题；0/1背包问题。

（4） 查找问题中的动态规划法

主要知识点： 最优二叉查找树；近似串匹配问题。

第七章 贪心法

1.教学基本要求

掌握利用贪心算法解决问题的基本思想；会用某高级语言编写用贪心算法解决问题的程序，并能对算法的复杂度，可靠性进行分析。

2.要求学生掌握的基本概念、理论、技能

通过本章教学使学生掌握贪心算法的设计思想、时间性能，能够用贪心法解决背包问题、多机调动、TSP等实际应用问题。

3.教学重点和难点

教学重点是贪心法的设计思想、组合问题中的贪心法。教学难点是组合问题中的贪心法。

4.教学内容

（1）概述

主要知识点：贪心法的设计思想；一个简单的例子--埃及分数。

（2） 图问题中的贪心法

主要知识点：TSP问题；图着色问题；最小生成树问题。

（3） 组合问题中的贪心法

主要知识点：背包问题；活动安排问题；多机调度问题。

第八章 基于搜索的算法设计技术

1.教学基本要求

掌握利用回溯法解决问题的基本思想，并能用此方法解法实际的应用问题。

2.要求学生掌握的基本概念、理论、技能

通过本章教学使学生了回溯算法的设计思想、时间性能，能够用回溯法解决：n个皇后问题，图的m着色问题，批处理作业调度问题等，并能准确地分析回溯法的效率及稳定性。

3.教学重点和难点

教学重点是回溯法的设计思想、图的m着色问题，批处理作业调度问题。教学难点是图着色问题、哈密顿回路问题。

4.教学内容

（1）概述

主要知识点：问题的解空间树；回溯法的设计思想；回溯法的时间性能；一个简单的例子——素数环问题。

（2）图问题中的回溯法

主要知识点：图着色问题；哈密顿回路问题。

（3）组合问题中的回溯法

主要知识点：八皇后问题；批处理作业调度问题。

第九章 分支限界法

1.教学基本要求

掌握利用分支限界法解决问题的基本思想，并能用此方法解法实际的应用问题。

2.要求学生掌握的基本概念、理论、技能

通过本章教学使学生掌握分支限界法的设计思想、时间性能，与回溯法的区别以及图问题和组合问题中的分支限界法。

3.教学重点和难点

教学重点是分支限界法的设计思想，与回溯法的区别，0/1背包问题，批处理作业调度。教学难点是图的TSP问题，0/1背包问题。

4.教学内容

（1）概述

主要知识点：分支限界法的设计思想；分支限界法的时间性能；简单的例子—圆排列问题。

（2） 图问题中的分支限界法

主要知识点：TSP问题；多段图的最短路径问题。

（3）组合问题中的分支限界法

主要知识点：0/1背包问题；任务分配问题；批处理作业调度问题。

四、学时分配表

理论部分：

章序	内容	课时	备注
一	算法设计基础	1
二	算法分析基础	1
三	蛮力法	2
四	分治法	6
五	减治法	2
六	动态规划法	6
七	贪心法	4
八	回溯法	5
九	分支限界法	5
合计		32

实践部分：

序号	项目 名称	内容提要	学时	必/选开
1	递归算法	任意输入一串整数或字符，输出结果能够用递归方法实现整数或字符的全排列。	2	必开
2	分治法算法	循环为n个运动员进行单循环赛编写比赛日程	2	必开
3	动态规划算法	三角形问题：给定一个由n行数字组成的数字三角形，设计一个算法，计算出从三角形的顶至底的一条路径，是该路径经过的数字	2	必开
4	动态规划算法	0-1背包问题	2	必开
5	贪心算法	键盘输入一个正整数ｎ，去掉任意ｓ个数字后剩下的数字按原左右次序将组成一个新的正整数。编程对给定的ｎ和ｓ，寻找一种方案，使得剩下的数最小。	2	必开
6	回溯算法	工作分配问题：设有ｎ件工作分配给n个人。将工作i分配给第ｊ个人所需的费用为ｃｉｊ。试设计一个算法为每一个人都分配１件不同的工作，并使总费用达到最小。	2	必开
7	回溯算法	0-1背包问题	2	必开
8	分支限界算法	0-1背包问题	2	必开
合计			16

五、主用教材及参考书

（一）主用教材：

《算法设计与分析》主编：王红梅、胡明 出版社：清华大学出版社 出版时间：2013年。

（二）参考书：

1. 《计算机算法设计与分析》主编：王晓东 出版社：电子工业出版社 出版时间：2012年。

2.《算法设计与分析》主编：屈婉玲、刘田、张立昂 出版社：清华大学出版社 出版时间：2011年。

3.《算法设计与分析》 主编：吕国英 出版社：清华大学出版社 出版时间：2008年。

4.《算法设计与分析》 主编：郑宗汉、郑晓明 出版社：清华大学出版社 出版时间：2011

年。