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

1、1算法设计与分析一、 说明（一）课程性质计算机科学是一种创造性思维活动，其教育必须面向设计。计算机算法设计与分析正是一门面向设计，且处于计算机学科核心地位的教育课程。设计一个高效的程序不仅需要编程小技巧，更需要合理的数据组织和清晰高效的算法，这正是计算机科学领域里数据结构与算法设计所研究的主要内容。（二）教学目的通过对本课程的学习与研究，使学生掌握算法设计的主要方法，培养对算法的计算复杂性正确分析的能力，为独立设计算法和对算法复杂性分析奠定坚实的理论基础，对学生将来从事计算机系统结构、系统软件和应用软件的研究与开发提供一个广泛扎实的计算机算法知识基础。（三）教学内容算法及算法复杂性基本概念，算

2、法描述，有效算法最常用的设计策略递归和分治法，动态规划法的设计要点与适用性，贪心算法，回溯法和分支限界法，许多难解问题的高效算法概率算法，以及 NP 完全理论和 NP 难问题的近似解法。传统算法实例分析，算法领域研究热点介绍。（四）教学时数课堂教学 36 学时，实验部分 36 学时，总计 36+36/2=54 学时（五）教学方式讲授+上机实验+课题设计对每一教学内容，首先介绍一种算法设计策略的基本思想，然后从解决计算机科学和应用中的实际问题入手，由简到繁地描述几个经典的精巧算法。同时对每个算法所需的时间和空间进行分析，使学生既能学到一些常用的精巧算法，又能通过对算法设计策略的反复应用，牢固掌握

3、这些算法设计的基本策略，以期收到融会贯通之效。在为各种算法设计策略选择用于展示其设计思想与技巧的具体应用问题时，有意义重复选择某些经典问题，使学生能深刻地体会到一个问题可以用多种设计策略求解。同时通过对解同一问题的不同算法的比较，使学生更容易体会到每一种具体算法的设计要点。随着内容的逐步展开，学生也将进一步感受到综合应用多种设计策略可以更有效地解决问题。二、 本文（一） 课堂教学部分第一章 算法概述教学要点：算法的基本概念，算法的计算复杂性教学时数：建议 2 学时教学内容：第一节 算法与程序 （0.5 学时）掌握算法的概念及特性2理解算法与程序的区别了解算法的描述方法第二节 算法复杂性分析 （

4、1.5 学时）掌握算法复杂性分析的概念熟练掌握算法时间复杂性和空间复杂性的表示方法及 O 的定义了解 ， 和 O 的定义考核要求：识记相关概念，领会复杂性分析方法第二章 递归与分治策略教学要点：递归概念，分治策略，递归算法设计教学时数：建议 5 学时教学内容：第一节 递归概念 （1 学时）熟练掌握递归概念说明递归算法的工作原理第二节 分治法的基本思想 （0.5 学时）熟练掌握分治法的基本思想和一般原则理解分治算法设计模式掌握分治算法的复杂性分析方法第三节 基与分治策略的递归算法设计 （3.5 学时）熟练应用分治法设计递归算法：1.大整数乘法 （0.5 学时）2.Strassen 矩阵乘法 （0

5、.5 学时）3.棋盘覆盖 （0.5 学时）4.归并排序（0.5 学时） 5.快速排序 （0.5 学时）了解分治法所能解决的一些典型问题应用递归算法复杂性分析的一般方法分析各种具体算法的复杂性考核要求：领会递归与分治的基本概念应用分治策略解决实际问题并设计递归算法递归算法的复杂性分析第三章 动态规划教学要点：动态规划算法的设计思想 、适用性以及算法的设计要点。教学时数：建议 6 学时。教学内容：第一节 动态规划算法的基本思想 （2.5 学时）掌握动态规划算法的基本思想3理解动态规划算法和分治法的异同熟练掌握用动态规划算法求解问题的步骤第二节 动态规划算法的基本要素 （1.5 学时）熟练掌握用动态

6、规划算法求解问题的两个重要性质，即：最优子结构性质和子问题重叠性质理解自顶向下备忘录方法的基本思想第三节 动态规划算法设计（2 学时） 熟练应用动态规划思想解决具体应用问题1. 最长公共子序列 （1 学时）2 .最大子段和 （1 学时）了解动态规划算法所能解决的一些典型问题掌握动态规划算法的复杂性分析方法考核要求：领会动态规划算法的思想 、算法设计步骤及基本要素掌握用动态规划思想解决实际问题并设计动态规划算法动态规划算法复杂性分析第四章 贪心算法教学要点：贪心算法思想 、基本要素及贪心算法设计教学时数：建议 3 学时教学内容：第一节 贪心算法的基本思想 （1 学时）理解贪心算法的基本思想理解局

7、部最优和整体最优的概念第二节 贪心算法的基本要素 （1 学时）熟练掌握用贪心算法求解问题的两个重要性质。即：贪心选择性质和最优子结构性质了解贪心选择性质和最优子结构性质的证明方法理解贪心算法和动态规划算法的差异第三节 贪心算法设计 （1 学时）熟练应用贪心算法解决具体应用问题了解贪心算法可能解决的一些典型问题掌握贪心算法的复杂性分析方法考核要求：领会贪心酸法的思想及基本要素应用贪心算法思想解决实际问题并设计贪心算法贪心算法复杂性分析第五章 回溯法教学要点：回溯放的基本思想及算法框架，递归回溯，迭代回溯，回溯算法设计教学时数：4建议 4 学时教学内容：第一节 回溯法的算法框架 （2 学时）理解问

8、题的解空间掌握回溯法的基本思想熟练掌握回溯法解题的步骤理解递归回溯和迭代回溯了解子集树与排列树的概念第二节 回溯算法设计 （2 学时）熟练应用回溯算法解决具体应用问题转载问题了解回溯法解决的一些典型问题掌握回溯算法复杂性分析方法考核要求：领会回溯法的基本思想识记用回溯算法解题的步骤，子集树，排列树应用回溯法解决实际问题并设计回溯算法回溯算法复杂性分析第六章 分支界限法教学要点：分支界限法基本思想，分支界限法与回溯法的异同，分支界限算法设计教学时数：建议 3 学时教学内容：第一节 分支界限法的基本思想 （1.5 学时）掌握分支界限法的基本思想理解分支界限法与回溯法的异同理解分支界限法的搜索策略熟

9、练应用剪枝函数来加速搜索第二节 分支界限法算法设计 （1.5 学时）熟练应用分支界限法解决具体应用问题单源最短路径设计和应用剪枝函数了解分支界限法解决的一些典型问题熟练应用队列式分支界限法和优先队列式分支界限法考核要求：领会分支界限法的基本思想应用分支界限法设计算法识记分支界限法与回溯法的异同第七章 概率算法教学要点:数据概率算法,蒙特卡罗算法,拉斯维加斯算法,舍伍德算法,各类算法的优缺点教学时数:建议 5 学时5教学内容:第一节 概率算法的描述 (1 学时)理解概率算法的基本思想和基本特征掌握概率算法的分类区别各种概率算法了解概率算法的复杂度第二节 数据概率算法 （1 学时）理解数据概率算法

10、的内涵掌握数据概率算法的设计了解数据概率算法求解的一些典型问题第三节 舍伍德（ Sherwood）算法 （1 学时）理解舍伍德算法的基本思想了解舍伍德算法的复杂度掌握舍伍德算法求解的一些典型问题第四节 拉斯维加斯（Las Vegas）算法 （1 学时）理解拉斯维加斯算法的基本思想和基本特征了解拉斯维加斯算法的复杂性掌握拉斯维加斯算法的设计了解拉斯维加斯算法求解的一些经典问题第五节 蒙特卡罗（Moute Carlo）理解蒙特卡罗算法的基本思想应用蒙特卡罗算法解决实际应用问题了解蒙特卡罗算法求解的一些经典问题考核要求：领会各类概率算法的基本思想掌握各类概率算法的设计识记各类概率算法的优缺点第八章

11、NP 完全性的理论教学要点：P 类与 NP 类问题，NP 完全问题，典型的 NP 完全问题教学时数：建议 5 学时教学内容：第一节 计算模型 （1.5 学时）理解三个重要的计算模型，即：随机存取和 RAM，随机存取存储程序机RASP，图灵机第二节 P 类与 NP 类问题 （1 学时）理解“易”解和“难”解问题的概念掌握非确定图灵机(DNTM)模型及其时间复杂度理解 P 类与 NP 类语言理解多项式时间验证的概念理解 COOK 定理的内涵及其重要性第三节 典型的 NP 完全问题 （1 学时）6理解一些典型的 NP 完全问题了解典型的 NP 完全问题的证明考核要求：领会三个重点的计算模型领会 P

12、类与 NP 类问题，NP 完全问题的概念设计 RAM 和 RASP 程序识记一些典型的 NP 完全问题第九章 近似算法教学要点：NP 完全问题有数近似算法的设计与分析方法教学时数：建议 2 学时教学内容：第一节 近似算法 （1 学时）理解近似算法的思想的应用范围理解近似算法的性能第二节 近似算法设计 （1 学时）掌握近似算法的设计与分析方法了解近似算法求解的一些典型问题考核要求：领会近似算法的设计与分析方法（二） 实验部分1基本要求（1）熟练操作有关 C+/JAVA 编程环境（2）运用理论部分介绍的各类算法设计思想在相关环境下设计，编写，调试和运行求解实际问题的程序2项目总表序号 实验项目名称

13、 学时 项目类别 项目类型1 熟悉 C+或 JAVA 编程的环境 2 基础 必做2 排列问题 2 设计 必做3 棋盘覆盖问题 2 设计 必做4 用栈模拟递归，消去算法 Quick sort 中的递归 2 综合 必做5 Sarassen 矩阵乘法 2 设计 选做6 矩阵连乘问题 （动态和备忘录） 2 设计 必做7 图象压缩 2 设计 必做8 找硬币（递归算法，动态规划算法，贪心算法） 4 综合 必做9 活动安排问题 2 设计 必做10 哈夫曼编码 2 设计 必做11 多机调度问题 2 设计 选做7注：必做项目数 17 个，选做项目数 6 个。3实验内容及其基本要求见实验教学大纲4考核要求 熟练应

14、用 C+或 JAVA 编程环境综合分析各类应用问题并设计相应算法编写、调试、运行程序，以求解相应问题各实验项目实验报告三、参考书目1 王哓东 编著， 计算机算法设计与分析 ，电子工业出版社，2001 年 11 月第一版2 陈增武 编著， 算法设计与分析 ，浙江大学出版社，1994 年 8 月第一版3 Sara Baase.Computer Algorithms:Introduction to Design and Analysis.Second edition.Addison-Wesley,1988本课程使用教具和现代教育技术的指导性意见微型计算机，C+编程环境，JAVA 编程环境序号 实验项目名称 学时 项目类别 项目类型12 多会场多活动安排问题 2 综合 选做 13 装载问题 2 设计 必做14 批处理作业调度问题 2 设计 选做15 图的 M 着色问题 2 设计 必做16 运动员最佳配对问题 2 设计 选做17 布线问题 2 设计 必做18 装载问题 2 设计 必做19 最大团问题 2 设计 选做20 用随机投点法计算值 2 设计 必做21 线性时间选择（Sherwood 算法） 2 设计 必做22 n 后问题（Las Vegas 算法） 2 设计 必做23 矩阵互逆问题（Monte Carlo 算法） 2 设计 必做