2024年北京航空航天大学非全日制研究生招生考试《算法设计与分析》考试大纲

　　一、整体要求

　　(一)掌握算法的定义、性质和表示方法，并能够使用伪代码对算法进行描述;

　　(二)能够熟练采用渐近上界、渐近下界与渐近紧确界分析算法的运行时间;

　　(三)掌握算法设计的常用方法，包括分而治之、动态规划、贪心、近似算法;掌握图的基本概念和重要的基础图算法;

　　(四)掌握计算复杂性的基本概念和证明P类、NP类问题的方法;

　　(五)具有对简单计算问题的建模、分析、算法设计、算法优化和编程求解能力。

　　二、复习要点

　　(一)渐近复杂性分析

　　(1)O、Ω、Θ符号定义;

　　(2)分析给定算法的渐近复杂性;

　　(3)比较具有不同渐近上界的算法的效率;

　　(4)递归函数的运行时间分析。

　　(二)常用算法设计方法的基本思想和特点，以及针对具体问题设计相应的算法并分析其效率

　　(1)分治算法

　　(2)动态规划算法

　　(3)贪心算法

　　(4)近似算法

　　(三) 图算法

　　(1)图的基本概念和基本性质;

　　(2)图的表示方法;

　　(3)图的遍历与搜索方法;

　　(4)最小生成树和最短路径等图具体问题算法。

　　(四) 计算复杂性

　　(1)计算复杂性的基本概念，如判定问题、优化问题等;

　　(2)P类和NP类问题的定义和证明。