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

1、算法设计与分析课程教学大纲课程名称算法设计与分析 / Algorithms Design and Analysis课程编码10000502810课程类型专业选修课课程性质专业主干课适用范围信息与计算科学专业、信息安全专业学分数3先修课程C语言、数据结构、离散数学学时数54实验/实践学时无课外学时无考核方式考查一、教学大纲说明（一）课程的地位、作用和任务算法设计与分析是信息与计算科学及信息安全专业的一门重要的课程。该课程的主要内容是计算机领域及其有关领域中的一些非数值计算的常用算法。学生通过这门课的学习，熟悉计算机解决问题的常用算法思想、并分析其复杂性，能够增强自身的逻辑思维、分析问题以及解决问

2、题的能力，同时，为学生进一步学习奠定良好的基础。（二）课程教学的目的和要求通过本课程的学习，使学生了解算法设计与分析的基本概念、算法优化的基本要求和方法以及常见算法解决同一问题的算法的效率分析。理解算法设计的基本步骤和算法分析的基本过程。掌握算法设计的基本方法，以便解决信息安全与工程领域中较为复杂的实际问题；掌握算法分析的基本技术并能熟练运用算法分析的基本方法对算法的复杂度进行分析；同时，能熟练运用一些常用的算法。对这门课程的学习，还要求学生必须利用课外时间实现主要算法，并上机调试。（三）课程教学的方法与手段本课程的教学采用讲授和习题结合的方法。课程的内容主要由老师授课，同时布置适当的习题，要

3、求学生利用课外时间完成，包括算法的程序实现与上机调试。（四）课程与其它课程的联系本课程涉及到高级程序设计、离散数学、数据结构等基础知识。因而本课程的先修课程有高级程序设计语言、数据结构、离散数学等。（五）教材与教学参考书教材：1、王晓东，计算机算法设计与分析（第3版），北京，电子工业出版社，2007年5月2、王晓东，算法设计与分析（第2版），北京，清华大学出版社，2008年1月教学参考书：1、计算机算法基础（第二版），余祥宣、崔国华、邹海明，华中理工大学出版社,2004 2、E. Horowitz and S. Sahni，Fundamentals of Computer Algorithms

4、， Computer Science Press, 1978 3、A.V.Aho,J.E.Hopcroft, and J.D.Ullman，The Design and Analysis of Computer Algorithms， Addison-Wesley Publishing Company，19784、T.H.Cormen、 C.E.Leiserson、R.L.Rivest and C.Stein，Introduction To Algorithms（Second Edition），The MIT Press，2001二、课程教学内容、重点和难点第一章 算法概述内容：程序与算法的概

5、念、算法复杂度基本概念。重点：算法复杂度基本概念和算法复杂度分析。难点：算法复杂度分析。第二章 递归与分治策略内容：递归与分治概念、递归算法的基本框架和分治的基本思想、递归算法实例（二分搜索技术、矩阵乘法、大整数的乘法、棋盘覆盖、合并排序、线性时间选择、最接近点对问题、循环赛日程表）和递归效率分析。重点：递归算法基本框架、递归算法分析、递归算法实例（大整数的乘法、线性时间选择、棋盘覆盖、最接近点对问题）和递归算法效率分析。难点：递归算法基本框架、线性时间选择、最接近点对问题、递归算法效率分析。第三章 动态规划内容：动态规划算法的概念、动态规划算法的基本要素（最优子结构性质和重叠子问题性质）、动

6、态规划算法的步骤（最优解性质与刻画、递归定义最优值、计算最优值）、动态规划算法实例（距阵连乘问题、最长公共子序列、流水作业问题和0-1背包问题）、动态规划算法效率分析。重点：动态规划算法的基本要素、动态规划算法的步骤、动态规划算法实例、动态规划算法效率分析。难点：最优解性质与刻画、递归定义最优值、计算最优值、算法正确性证明、最长公共子序列、和0-1背包问题、动态规划算法效率分析。第四章 贪心算法内容：贪心算法的基本概念、贪心算法基本要素（最优子结构性质和贪心选择性质）、贪心算法与动态规划算法的差异、贪心算法的实例（最优装载问题、哈夫曼编码、单源最短路径问题、最小生成树和多机调度问题）、贪心算法

7、效率分析。重点：贪心算法基本要素、贪心算法正确性证明、哈夫曼编码、最优装载问题和多机调度问题、贪心算法效率分析。难点：贪心算法正确性证明、最优装载问题、多机调度问题和贪心算法效率分析。第五章 回溯法内容：回溯算法的基本概念、回溯算法框架（递归回溯最优子结构性质、迭代回溯贪心选择性质、子集树算法框架和排序树算法框架）、回溯算法实例（装载问题、批处理作业调度、n皇后问题、0-1背包问题、图的n着色问题）、回溯算法效率分析。重点：递归回溯最优子结构性质、迭代回溯贪心选择性质、子集树算法框架和排序树算法框架、装载问题、批处理作业调度、n皇后问题、0-1背包问题、回溯算法分析。难点：递归回溯最优子结构性

8、质、迭代回溯贪心选择性质、子集树算法框架和排序树算法框架、装载问题、0-1背包问题和回溯算法效率分析。 第六章 分支限界法 内容：分支限界基本概念、分支限界的剪枝策略、分支限界法的基本框架和分支限界实例（装载问题、0-1背包问题、单源路径问题和批处理作业调度调度问题）、分支限界法的效率分析。重点：分支限界法的基本框架和分支限界实例（装载问题、0-1背包问题、单源路径问题和批处理作业调度调度问题）、分支限界法的效率分析。难点：分支限界法的基本框架、装载问题、0-1背包问题、单源路径问题、分支限界法的效率分析。 第七章 随机化算法内容：概率算法的基本概念和分类、随机数的算法、数值概率算法设计思想、

9、蒙特卡罗算法设计思想、拉斯维加斯的设计思想、舍伍德算法设计思想、概率算法的分析。重点：数值概率算法设计思想、蒙特卡罗算法设计思想、拉斯维加斯的设计思想、舍伍德算法设计思想、概率算法的分析。难点：数值概率算法设计思想、蒙特卡罗算法设计思想、拉斯维加斯的设计思想、舍伍德算法设计思想、概率算法的分析。第八章 线性规划与网络流内容：线性规划问题及其表示、线性规划的基本原理、线性规划问题的单纯形算法、最大网络流问题及其求解算法、最小费用流问题及其求解算法。重点：线性规划的基本原理、线性规划问题的单纯形算法、最大网络流问题及其增广路算法、最小费用流问题及其求解算法难点：线性规划问题的单纯形算法、最大网络流的求解算法、最小费用流问题的求解算法。第九章 NP完全理论与近似算法内容：RAM计算模型、RASP计算模型和图灵机计算模型、P类与NP类问题、NP完全问题、近似算法基本概念、近似算法的性质、多项式时间近似算法格式概念、近似算法实例、近似算法分析。重点：图灵机计算模型、P类与NP类问题、NP完全问题、近似算法的性质、多项式时间近似算法格式概念、近似算法实例、近似算法分析。难点：图灵机计算模型、P类与NP类问题、NP完全问题多安全策略支持框架、多项式时间近似算法格式概念、近似算法实例、近似算法分析。三、学时分配 教学内容各教学