2906-《高级算法设计与分析》考试大纲

博士研究生入学考试《高级算法设计与分析》考试大纲一、试卷结构1)试卷成绩本试卷满分为100分。2)答题方式：闭卷、笔试3)试卷内容结构：高级算法设计基本策略与算法复杂性分析方法4)题型结构a:填空题，10小题，共20分b:筒答题（包括计算题），4小题，共20分c:解答题（包括证明题），4小题，共60分二、考试内容与考试要求1、算法复杂性分析方法考试内容：算法复杂性分析的基本概念，常用的算法复杂性分析方法。考试要求：(1)理解算法的复杂性概念，掌握渐进复杂性的概念。(2)复杂性的递推式表达。(3)代入法、递归树、主定理法求解算法复杂性。(4)了解复杂性分析的摊还分析方法思想。2、分治策略算法设计方法考试内容：分治法算法设计思想和常用实例。考试要求：(1)掌握分治法的基本思想和适用条件。(2)掌握分治法应用的经典实例，如二分搜索法，快速排序，归并排序，大整数乘法，Strassen矩阵乘法，循环赛安排，线性选择问题等。掌握这些算法的基本思路、实现技术。(3)能写出分治法的递归伪代码，并进行复杂度分析。4、动态规划考试内容：动态规划的基本设计原理和应用条件，动态规划应用的经典实例。考试要求：(1)掌握动态规划的基本思想。