《算法设计与分析信息安全》课程教学大纲

1、 PAGE PAGE 6算法设计与分析教学大纲（71042411）一、说明（一）课程性质 本课程是一门面向算法设计的计算机科学与技术专业的专业必修课程。通过对这门课程的学习和研究，掌握算法设计的主要方法，培养对算法的计算复杂性正确分析的能力，为独立设计算法和对算法进行复杂性分析奠定坚实的理论基础。（二）教学目的算法是计算机科学的核心。算法设计与分析是计算机科学与技术专业的重要必修课程。 通过该课程的学习，使学生在算法设计、算法优化与算法分析等方面受到严格、系统的训练，从而能设计合适的算法解决实际问题，为后续专业课程的学习打下基础。 本课程于必修课程程序设计和数据结构之后开设，学生经过这两门课程

2、的学习已掌握常用的数据结构和基本算法，也具备了编写程序实现算法的能力。 本课程将一步深化先修课程所学的内容，强化学生的理论基础和动手实践能力；同时也适当介绍若干算法研究领域的前沿课题，培养学生对算法研究的兴趣。（三）教学内容 课程的主要内容包括： 算法分析的基本知识，渐进复杂度和大O记号，分治算法和递归关系，图的搜索，最短路、最大团算法，贪心算法，动态规划算法及其优化，NP完全问题的搜索算法和近似算法等。 （四）教学时数讲授: 54学时 实验: 36学时总学时: 90学时（五）教学方式 讲授为主, 讨论与实验为辅。二、本文理论部分第1章 算法概述教学要点：理解算法的概念。理解什么是程序，程序与

3、算法的区别和内在联系。掌握算法的计算复杂性概念。掌握算法渐近复杂性的数学表述。教学时数： 6学时教学内容：1.1 算法与程序 （2学时） 介绍算法的基本特征：有限步、无歧义、可实现；讲解描述算法的方式：伪代码、流程图和程序；给出简单的算法例子：计算斐波那契数列前n项的算法；介绍算法与程序的区别与内在联系。1.2 算法复杂性分析 （4学时） 详解算法时间复杂度和空间复杂度的概念；介绍最坏复杂度和平均复杂度的概念；详解渐进复杂度的概念；给出大O记号的严格数学定义；通过不同复杂度算法运行时间的巨大差异来阐明降低算法复杂度的重要意义；详解分析递归算法复杂度的主要方法：解递归方程；以计算斐波那契数列的两

4、种算法为例，使学生对多项式时间算法和指数时间算法有直观的认识。第2章 递归与分治策略教学要点：理解递归的概念。掌握设计有效算法的分治策略。 通过下面的范例学习分治策略设计技巧。（1）二分搜索技术； （2）大整数乘法；（3）Strassen矩阵乘法；（4）棋盘覆盖；（5）合并排序和快速排序；（6）最接近点对问题；教学时数： 6学时教学内容：2.1 分治算法的基本步骤 （2学时） 介绍分治算法的三个步骤：分解原问题为子问题，递归求解子问题，由子问题的解得到原问题的解。 详解整数乘法的两个算法：小学生算法和分治算法。 分析用分治策略进行乘法运算的时间复杂度。2.2 求解递归方程的通用算法 （1学时）

5、 介绍递归方程的概念。 介绍Master定理并分情况举例其在求解递归方程上的应用。2.3 分治算法的典型实例（3学时） 讲解二分搜索、合并排序和快速排序算法、基于分治策略的矩阵乘法算法和基于分治策略的最接近点对算法，分析算法的时间复杂度。 第3章 动态规划教学要点：理解动态规划算法的概念。掌握动态规划算法的基本要素（1）最优子结构性质（2）重叠子问题性质 掌握设计动态规划算法的步骤。(1)找出最优解的性质，并刻划其结构特征。(2)递归地定义最优值。(3)以自底向上的方式计算出最优值。(4)根据计算最优值时得到的信息，构造最优解教学时数： 10学时教学内容：3.1 动态规划算法的基本概念 （2学

6、时） 以计算斐波那契数列第n项为例讲解“重复子问题”的概念；讲解动态规划算法的目标：避免重复对子问题进行计算；以有向无环图的最短路为例详解最优子结构、状态和状态转移方程的概念；讲解动态规划算法复杂度分析的方法。3.2 序列上的动态规划 （4学时）详解最长上升子序列问题的动态规划算法及其复杂度分析；详解字符串编辑距离问题的动态规划算法及其复杂度分析；详解背包问题及其变种（可重复背包等）的动态规划算法及其复杂度分析；详解矩阵连乘问题的动态规划算法及其复杂度分析。3.3 动态规划算法的优化（2学时） 以最长上升子序列问题为例讲解如何利用单调性优化动态规划算法；以最优二叉搜索树为例讲解如何利用四边形不

7、等式优化动态规划算法（选讲）。3.4 其它结构上的动态规划 （2学时）以哈密顿路径为例讲解集合上的动态规划；以树上的独立集为例讲解树型动态规划；以最优三角剖分为例讲解凸多边形上的动态规划（选讲）。 第4章 贪心算法教学要点：理解贪心算法的概念。掌握贪心算法的基本要素 （1）最优子结构性质（2）贪心选择性质 理解贪心算法与动态规划算法的差异 理解贪心算法的一般理论 通过应用范例学习贪心设计策略。（1）活动安排问题；（2）最优装载问题；（3）哈夫曼编码；（4）单源最短路径；（5）最小生成树；教学时数： 6学时教学内容：4.1 贪心算法的策略 （2学时） 回顾最小生成树的两种算法（Kruskal算法

8、和Prim算法）中所采用的贪心策略；证明Kruskal算法和Prim算法的正确性；利用并查集实现Kruskal算法4.2 贪心算法的典型实例 （4学时）讲解哈夫曼编码的贪心算法及其最优性证明；讲解活动安排问题、最优装载问题的贪心算法及其正确性证明。 第5章 回溯法教学要点：理解回溯法的深度优先搜索策略。掌握用回溯法解题的算法框架（1）递归回溯（2）迭代回溯（3）子集树算法框架（4）排列树算法框架 教学时数： 7学时教学内容：5.1 回溯算法的策略 （2学时） 以n皇后问题为例，介绍回溯算法的基本思想及算法框架5.2 回溯算法的典型实例 （5学时）讲解0-1背包问题的回溯算法及其与动态规划算法的

9、比较；讲解旅行售货员问题、图的着色问题和最大团问题的回溯算法及其效率分析。 第6章 分支限界法教学要点：理解分支限界法的剪枝搜索策略。掌握分支限界法的算法框架（1）队列式(FIFO)分支限界法（2）优先队列式分支限界法 通过应用范例学习分支限界法的设计策略。（1）单源最短路径问题（2）装载问题；（3）布线问题（4）0-1背包问题；（5）最大团问题；（6）旅行售货员问题教学时数： 7学时教学内容：6.1 分支限界的基本思想 （2学时） 以单源最短路径问题为例，介绍分支限界算法的基本思想及算法框架，详解分支限界算法中上界和下界的概念；以哈密顿回路问题为例详解局部搜索算法；介绍局部搜索算法中跳出局部

10、最优的策略6.2 分支限界法的典型实例 （5学时）讲解0-1背包问题的分支限界算法及其与动态规划算法、回溯算法的比较；讲解旅行售货员问题、装载问题和最大团问题的回溯算法及其效率分析。 第7章 概率算法教学要点：理解产生伪随机数的算法掌握数值随机化算法的设计思想 掌握蒙特卡罗算法的设计思想 掌握拉斯维加斯算法的设计思想 掌握舍伍德算法的设计思想教学时数： 4学时教学内容：7.1 随机数 （0.5学时） 介绍线性同余法产生伪随机数。7.2 数值概率算法 （0.5学时）以随机投点法计算值为例介绍数值概率算法的思想。7.3 舍伍德（Sherwood）算法 （1学时） 以快速排序算法为例，介绍舍伍德算法

11、的思想。7.4 拉斯维加斯（Las Vegas）算法（1学时） 以n皇后问题为例，介绍拉斯维加斯算法思想及特点。7.5 蒙特卡罗（Monte Carlo）算法（1学时）以素数测试问题为例，介绍蒙特卡罗算法的思想及特点。 第8章 NP完全性理论与近似算法教学要点：掌握P、NP和NPC类问题基本概念了解一些典型的NPC问题了解处理NPC问题的方法教学时数： 8学时教学内容：8.1 NP问题的基本概念 （3学时） 回顾多项式时间算法和指数时间算法的概念；详解多项式时间归约的概念；介绍多项式时间归约的例子；详解多项式时间验证解的概念；详解P问题和NP问题的概念；详解NP完全和NP难的概念；介绍第一个被

12、证明为NP完全的问题：SAT问题。8.2 NP完全问题的典型实例 （2学时） 讲解3-SAT问题的NP完全性及如何将SAT问题归约为3-SAT问题；讲解图论中的完全子图（团）问题及如何将完全子图问题归约为3-SAT问题；讲解顶点覆盖问题及如何将其归约为顶点覆盖问题；讲解哈密顿回路问题及如何将其归约为顶点覆盖问题。8.3 处理NP完全问题的方法 （3学时） 详解顶点覆盖问题和哈密顿回路问题的近似算法，并给出其近似程度的证明。实验部分（一）基本要求牢固掌握算法设计的基本策略，体会每一种具体算法的设计要点，以期达到融会贯通的效果，可以综合应用多种策略，设计合适的算法有效的解决实际问题。（二）实验项目

13、总表序号实验项目名称学时数项目类别项目类型1递归与分治算法设计6设计必做2动态规划算法设计8设计必做3贪心算法设计4设计必做4回溯算法设计6设计必做5分支限界算法设计6设计必做60-1背包问题算法设计6综合设计必做（三）实验项目内容及要求 实验项目1、布置至少3道课后实验习题，内容覆盖递归与分治算法的设计。 实验项目2、布置2次，每次至少3道课后实验习题，题目以对给定问题设计动态规划算法为主，内容应覆盖多种类型的动态规划。 实验项目3、布置至少2道课后实验习题，内容主要是对给出的问题设计贪心算法。 实验项目4、布置至少3道课后实验习题，以对给定问题设计回溯算法。 实验项目5、布置至少3道课后实

14、验习题，以对给定问题设计分支限界算法。 实验项目6、就0-1背包这一NP难问题设计多个算法，并通过实验比较算法的优劣。三、参考书目1、T. Cormen， C. Leiserson， R. Rivest and C. Stein. Introduction to Algorithms, 2th Ed. The MIT Press, 2001, ISBN 0-262-33293-3影印版：算法导论（第2版），北京：高等教育出版社，2007，ISBN 7-040-11050-0中译版：潘金贵等译，算法导论（第2版），北京：机械工业出版社，2006，ISBN 7-111-18777-62、Algorithm Design（影印版）/（美