2018年南京信息工程大学2006算法设计与分析考博大纲

南京信息工程大学博士研究生招生入学考试
《算法设计与分析》考试大纲
科目代码：2006
科目名称：算法设计与分析
第一部分 课程评价目标
一、课程目标
算法设计与分析，主要使学生掌握算法设计的常用方法，提高学生算法
设计与复杂性分析的素质和能力，为学生能够独立进行算法的设计和计算复
杂性的分析奠定比较坚实的基础，以便使学生在将来从事计算机领域或其它
有关领域的研究中，能够运用这些方法来设计解决一些常用的或较为复杂的
实际问题的算法，并力争做到快捷、有效，从而提高程序的质量并较好地解
决科学研究与实际应用中所遇到的问题。
二、基本要求
要求学生掌握计算机科学技术领域中的一些常用的、经典的算法设计技
术，学会分析算法、估计算法的时空复杂性，在非数值计算的层面上，具备
把实际问题抽象描述为数学模型的能力，同时能针对不同的问题对象设计有
效的算法，用典型的方法来解决科学研究及实际应用中所遇到的问题。并且
具备分析算法效率的能力，能够科学地评估有关算法和处理方法的效率。
三、评价目标
1．掌握算法的基本概念和分析算法的基本方法；
2．掌握分治、动态规划、贪心算法、分支限界法、图的遍历、随机算法、
近似算法、NP 完全性问题的基本原理。
3．熟练掌握求解典型问题的算法设计思想和实现方法，能够有效运用，以
能高效解决新的问题。
4．具有较强的算法设计和分析能力，具备设计出解决实际应用与科学研究
问题的有效算法。
5．了解算法研究领域的现状与发展。
第二部分 考查要点
1．基本概念
算法的基本定义、基本性质，算法复杂度分析的基本方法。
2．递归算法设计技术
递归算法的实现机制，设计和分析递归算法的一般方法；归纳法等基本方法
的运用。
3．分治法
分治法的基本原理，典型问题如二分检索、合并排序、快速排序、矩阵乘法、
大整数乘法、最近点对问题等的算法设计原理、实现技术及其应用。
4．贪心方法
图和贪心方法的基本原理和性质，贪心解的最优性证明；典型问题如最短路
径问题、最小耗费生成树、文件压缩等的算法设计原理、实现技术及其应用。
5．动态规划
动态规划的基本原理和方法、最优性原理、无后效性、状态转移方程；典型
问题如最长公共子序列问题、矩阵链相乘、所有点对的的最短路径、背包问题等
的算法设计原理、实现技术及其应用。
6．图的遍历
广度优先搜索、深度优先搜索的原理、性质和异同；回溯法的原理和技术、
分支－限界法的原理和技术；典型问题如 8 皇后问题、3 着色问题等的算法设计
原理、实现技术及其应用。
7．随机算法和近似算法
随机算法、近似算法的原理和方法；关于典型问题如 Las Vegas 方法、Monte
Carlo 方法、TSP 问题、装箱问题、顶点覆盖、子集和问题等问题的近似算法讨
论。
8．NP 完全问题
NP 完全性的概念、可满足性、NP 完全性证明；了解典型 NP 完全问题如顶点
覆盖、独立集、团集问题等。