第七章 算法设计与分析考纲.docVIP

广播电视大学《算法设计与分析》课程考试大纲 一、考试内容与考试要求1、 算法概述 考试内容 算法的概念和性质 算法的复杂性概念和分析角度 计算时间的渐近表示及其相关性质 NP完全性理论中的基本概念 考试要求 （1）理解算法的概念和性质。 （2）理解程序与算法的区别和内在联系。 （3）理解算法的复杂性概念和时间复杂度分析角度（最佳、最差和平均情况）。 （4）掌握计算时间的渐近表示及其相关性质。 （5）掌握算法复杂度分析的基本技术和方法。 （6）理解P和NP类问题的概念，了解Cook定理和几个NP完全问题。 2、 递归算法设计与分析 考试内容 递归的概念 递归算法的实现机制 设计和分析递归算法的一般方法 消去递归 考试要求 （1）理解递归的概念。 （2）掌握递归算法的实现机制。 （3）掌握设计和分析递归算法的一般方法。 （4）了解如何消去递归。 3、 分治策略 考试内容 分治法的基本思想和适用条件 分治法的效率分析 分治法应用的经典实例 考试要求 （1）掌握分治法的基本思想和适用条件。 （2）掌握分治法的效率分析的一般性技巧。 （3）掌握分治法应用的经典实例，如二分有哪些信誉好的足球投注网站法，快速排序，归并排序，大整数乘法，Strassen矩阵乘法，循环赛安排，线性选择问题等。掌握这些算法的基本思路、实现技术以及复杂度分析过程。 （4）通过学习分治法，会用某高级语言对算法进行描述。 4、动态规划 考试内容 动态规划的基本原理和应用条件 动态规划的效率分析 动态规划应用的经典实例 考试要求 （1）掌握动态规划的基本思想。 （2）掌握动态规划的两个基本要素：最优子结构性质和重叠子问题性质。 （3）了解动态规划的一般性求解步骤，会将问题化为多阶段图，并能对具体问题写出正确的递推公式。 （4）掌握动态规划应用的经典实例：多段图、矩阵连乘、0/1背包、每对节点之间的最短路径、最优二分检索树、最长公共子序列以及最大子段和问题。针对这些实例，会用某高级语言对算法进行描述，掌握分析动态规划算法效率分析的一般性方法。 （5）理解动态规划与分治法的区别。 5、贪心法 考试内容 贪心法的基本原理和基本要素 贪心算法的效率分析和可靠性（正确性）分析 贪心法应用的经典实例 考试要求 （1）掌握贪心法的基本原理。 （2）掌握动态规划的两个基本要素：最优子结构性质和贪心选择性质。针对一些简单的问题，会证明算法的正确性。 （3）掌握典型问题如背包问题、最优装载问题、带有限期的作业排序问题、活动安排问题、最小生成树、单源点最短路径等的算法设计原理、实现技术以及算法效率的分析。 （4）掌握贪心法与动态规划算法的区别。 6、回溯法 考试内容 回溯法的基本思想 剪枝函数的设计 回溯法的效率分析 回溯法应用的经典实例 考试要求 （1）掌握利用回溯法解决问题的基本思想和算法的基本框架。 （2）理解活结点、死结点和扩展结点的概念。 （3）掌握回溯法在下述问题上的应用：n皇后问题、最优装载问题、0/1背包、图的m着色问题和旅行售货员问题。针对这些问题，掌握剪枝函数的设计和递归回溯法的实现，能准确地分析回溯法的效率。 7、分支限界法 考试内容 分支限界法的基本思想 分队列式分支限界法和优先队列式分支限界法 分支限界法应用的经典实例 考试要求 （1）掌握回溯法和分支限界法的不同。 （2）掌握并区分队列式分支限界法和优先队列式分支限界法的基本思想，能用多种不同方法解法同一问题，并分析各方法的效率。 （3）掌握不同分支限界法在下述问题上的应用：最优装载问题、0/1背包和旅行售货员问题。针对这些问题，掌握剪枝函数的设计，了解算法的实现机制，能准确地分析各算法的效率。 、参考书目 王晓东. 计算机算法设计与分析（第4版）. 电子工业出版社, 2012 1