国防科技大学2020年博士研究生入学考试自命题科目考试大纲

3A03《算法分析与设计》考试大纲

一、参考书目

1.《算法设计与分析基础》，Anany Levitin著，潘彦 译，清华大学出版社，2015年,第3版。

2. 《计算机算法设计与分析》，王晓东编著，电子工业出版社，2012年，第4版。

二、考试内容及要求

（一）算法基本概念

考试内容：算法概念，算法分析概念、NP完全性理论。

考试要求：

1. 算法概念

掌握算法的定义、分类、特点，掌握链表、树、图和集合等基本数据结构，理解算法求解的重要问题类型，理解算法在计算中的地位和作用。

2. 算法分析概念

掌握算法分析的主要方法，掌握算法的效率类型，掌握渐进符号和基本效率类型表示方法，理解函数增长率、渐近特性的概念和计算方法。

3．NP完全性理论

掌握P、NP和NP完全问题的定义和相互关系，了解团问题、顶点覆盖问题、哈密顿回路问题、旅行售货员问题等典型的NP完全问题实例，了解NP完全性的证明方法。

（二）算法分析方法

考试内容：算法效率分析框架、非递归和递归算法的数学分析。

考试要求：

1．算法效率分析框架

掌握算法时间复杂度分析和空间复杂度的组成，掌握算法分析的基本框架、算法最优、最差和平均效率分析方法。

2．非递归和递归算法的数学分析

掌握非递归算法的分析步骤和计算方法，掌握递归算法的分析步骤和计算方法，掌握递归方程的求解方法等。

（三）算法设计策略

考试内容：分治法、变治法、动态规划法、贪心法、迭代改进法、回溯法、分枝限界法、概率算法。

考试要求：

1．分治法

掌握分治法的基本思想，掌握归并排序、快速排序、折半查找、二叉树遍历、大整数乘法和矩阵相乘、棋盘覆盖、最近对问题与凸包问题的分治设计方法；了解排序问题的复杂性下限。

2．变治法

掌握变治法基本思想和三种类型，掌握预排序、高斯消去法、平衡查找树、堆和堆排序、霍纳法则和二进制幂等典型问题的变治设计方法；了解问题化简类问题的变治算法策略。

3．动态规划法

掌握动态规划的主要思想和基本要素；掌握矩阵连乘、最优二叉查找树、最长公共子序列、图像压缩、电路布线等问题的动态规划设计方法；了解自顶向下的动态规划方法设计策略。

4．贪心法

掌握贪心算法的主要思想和基本要素；掌握最小代价生成树、单起点最短路路径、自由前缀码编码等问题的贪心算法策略；了解数据结构在程序效率分析的重要性。

5．迭代改进法

掌握迭代改进法的主要思想，掌握单纯形法、最大流问题、二分图最大匹配问题等典型问题的迭代改进设计方法，了解迭代改进算法效率的评估方法。

6．回溯法

掌握回溯法的算法框架和解空间树概念，掌握装载问题、批处理作业调度、符号三角形问题、n后问题、0-1背包问题的回溯法设计策略，了解回溯算法效率的影响因素。

7．分枝限界法

掌握分支限界法的基本思想，掌握单源最短路径问题、装载问题、0-1背包问题、最大团问题、电路板排列问题、旅行售货员问题的分支限界法策略，理解回溯法与分枝限界法的异同点。

8．概率算法

掌握概率算法的主要思想，掌握数值概率算法，理解Sherwood算法、Las Vegas算法的基本思想及其应用示例，了解Monte Carlo算法的基本思想及其应用示例。

三、试卷结构（满分100分，时间180分钟）

按题型：