《算法设计与分析》考试大纲

第一部分 考试说明

一、考试性质

    《算法设计与分析》是武汉工程大学计算机科学与技术及相关专业硕士研究生入学考试科目之一，以高等学校计算机学科优秀本科毕业生能达到的及格或及格以上水平为评价标准，要求考生全面、系统地掌握“算法设计与分析”的基本概念、基本原理和典型方法，能灵活运用所学知识阐述求解实际问题的方法和途径。目的在于考察考生理论素养与专业知识，便于优秀人才的选拔。

    考试对象为参加硕士生入学考试的应届或非应届硕士毕业生，以及具有同等学历的在职人员。

二、评价目标

    1.掌握算法的基本概念和分析算法的基本方法;

    2.掌握分治策略、贪心方法、动态规划、回溯法、分支-限界法、图算法、概率算法、近似算法、NP完全性理论的基本原理。

    3.熟练掌握求解典型问题的算法的设计思想和实现方法，并能灵活运用，以能有效求解新的问题。

    4.具有较高的算法设计能力和设计技巧，可能设计出解决实际问题的有效算法。

    5.了解算法研究领域的现状与趋势。

三、考试形式与试卷结构

    1.考试形式：闭卷、笔试、上机。

    2.答题时间：笔试120分钟，上机90分钟。

    3.试卷题型：填空题、选择题、改错题、简答题、计算题、算法分析题、程序设计题。每年在上述题型中选用3种。重点考察对本课程知识点的掌握程度和综合应用能力。

四、参考教材

1.王晓东编著《算法设计与分析》（清华大学出版社）

2.李春葆、李筱驰、等《算法设计与分析（第二版）》（清华大学出版社）

    3.苏德富、钟诚著《计算机算法设计与分析》（电子工业出版社）

    4.POJ部分测试题（poj.org）

第二部分 考查要点

1.算法分析基础

1) 熟悉渐近表示法，掌握渐近符号O等的定义，能判断一个较复杂的函数属于哪个渐近增长阶；

2) 熟悉一些算法复杂度分析的方法，比如说主定理法等，能对结构复杂的算法进行分析。

2.算法设计基础

1) 熟悉算法设计的三大技巧：贪心算法、分而治之，动态规划。

2) 能证明各种算法的正确性。

3) 能用这三大技巧设计相应的算法。

3.NP完备性理论及近似算法

1) 了解并掌握NP 完备性理论及其实际意义；

2) 熟悉多项式规约。掌握证明一个问题NP完全性的基本方法和思路；

3) 熟悉最小点覆盖、最大独立集等问题的NP完备性证明；

4) 了解并掌握近似算法的设计步骤与技巧，掌握点覆盖等问题的近似算法的设计。

4.经典算法

    熟悉排序、最短路径、最小生成树、最大匹配、最大流、最大公共字符串等问题的一些经典算法。

5.其它智力算法问题