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

来源：在职研究生招生信息网发布时间：2023-12-14 14:10:18

　　一、整体要求

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

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

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

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

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

　　二、复习要点

　　(一)渐近复杂性分析

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

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

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

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

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

　　(1)分治算法

　　(2)动态规划算法

　　(3)贪心算法

　　(4)近似算法

　　(三) 图算法

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

　　(2)图的表示方法;

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

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

　　(四) 计算复杂性

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

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

报考资格评估

请提供以下信息，招生老师会尽快与您联系。符合报考条件者为您提供正式的报名表，我们承诺对您的个人信息严格保密。

学历

大专以下大专本科有学位本科无学位硕士博士

所在地区

北京天津河北山西内蒙古辽宁吉林黑龙江上海江苏浙江安徽福建江西山东河南湖北湖南广东广西海南重庆四川贵州云南西藏陕西甘肃青海宁夏新疆台湾香港澳门

热门简章