2020年南京信息工程大学硕士研究生招生入学考试算法设计与分析（专业学位）考试大纲

科目代码：F23

科目名称：算法设计与分析

第一部分：大纲内容

1、算法复杂度性分析

1）理解算法的复杂性概念；

2）掌握计算时间的渐进表示及其相关性质；

3）掌握算法复杂度分析的基本方法

2、递归与分治策略

1）理解递归和分治的概念，掌握递归和分治算法的适用条件；

2）掌握递归和分治算法的实现机制；

3）掌握设计和分析递归和分治算法的基本方法；

4）掌握如何消除递归的技巧和方法；

3、动态规划

1）掌握动态规划的基本思想以及两个基本要素；

2）熟悉动态规划的求解步骤和实现机制；

3）掌握动态规划应用的经典案例，比如0-1背包、最短路径、最大字段和以及最长公共子序列等

4）理解动态规划和分治方法的区别；

4、贪心算法

1）掌握贪心算法的基本原理和基本要素；

2）掌握动态规划和贪心算法的区别；

3）掌握经典问题的贪心算法设计原理、实现技术以及效率分析，比如背包问题、最有装载问题、单源点最短路径等

5、回溯法

1）掌握回溯法的基本思想和基本框架；

2）理解活结点、死结点和扩展结点的概念；

3）熟练分析回溯法的效率；

4）掌握回溯法在经典问题上的应用，比如最优装载、0-1背包、图着色等 

6、分支限界法

1）掌握分支限界法的基本原理；

2）掌握并区分队列式分支限界法和优先队列式分支界定法的基本思想与区别；

3）能够实现多种分支限界算法求解同一问题，并准确分析各自的效率；

4）掌握分支限界法与回溯法的不同；

5）掌握分支限界法在经典问题上的应用，比如最优装载、0-1背包等

7、线性规划与网络流

1）掌握线性规划的基本定理和思想；

2）熟悉线性规划问题的单纯形算法设计与分析；

3）掌握线性规划方法在经典问题上的应用，如最大网络流问题、最小费用流问题、最小费用路算法、网络单纯形算法等

第二部分：说明

1、基本要求：

要求考生掌握递归、分治策略、贪心方法、动态规划、回溯法、分支限界法、线性规划等经典算法的基本原理和思想，熟练掌握求解典型问题的算法设计思想和实现方法，从而全面、系统地掌握“算法设计与分析”的基本概念、基本原理和典型方法，进而具备较高的算法设计能力与技巧，可设计出解决实际问题的有效算法。

2、分值比例：

算法复杂度分析：  10％

递归与分治策略：  20％

动态规划：        20％

贪心算法：        20％

回溯法：          10％

分支限界法：      10％

线性规划与网络流：10%

2、题型分布：

单项选择题：30%

填空题：    25%

算法分析题：15%

算法设计题：30%

3、其他规定：

考试方式为闭卷笔试，总分150分，考试时间180分钟。