2017年福州大学2001算法设计与分析考博大纲博士研究生入学考试大纲

福州大学
2017 年博士研究生入学考试专业课课程（考试）大纲
一、考试科目名称: 算法设计与分析
二、招生学院和专业：数学与计算机科学学院
基本内容:
第一部分考试说明
一、考试性质
《算法设计与分析》作为福州大学计算机科学与技术及相关专业博士研究生入学考试科目之
一，以高等院校计算机专业硕士教学的较高层次为基准，要求考生掌握算法设计的常用方法，
具备算法设计与复杂性分析的素质和能力，为考生后续能够独立进行算法的设计和计算复杂性
的分析奠定比较坚实的基础。该考试目的在于考察考生的专业综合素质和问题求解能力，便于
优秀人才的选拔。考试对象为参加博士生入学考试的应届或非应届硕士毕业生，以及具有同等
学历的在职人员。
二、考核目标
1.掌握算法的基本概念和分析算法的基本方法;
2.掌握分治、动态规划、贪心算法、分支限界法、图的遍历、随机算法、近似算法、NP 完
全性问题的基本原理;
3.熟练掌握求解典型问题的算法设计思想和实现方法，能够有效运用，以能高效解决新的
问题;
4.具有较强的算法设计和分析能力，具备设计出解决实际应用与科学研究问题的有效算法;
5.了解算法研究领域的现状与发展。
三、试卷结构
考试以闭卷笔试形式进行，题型包括填空题、选择题、改错题、简答题、计算题、证明题、
算法设计综合应用题。每年考试将从上述题型中抽取若干种（一般为 5 种左右），重点考察考生
的基础知识、分析能力、设计及实际问题求解能力等。
第二部分考察知识范围
1.算法设计与分析的基本概念
算法的基本定义、基本性质，算法设计和算法复杂度分析的基本技术和方法，计算时间的
渐进表示及其相关性质。
2.递归算法设计技术
递归算法的特点和实现机制，设计和分析递归算法的一般方法，消去递归;递归关系式的计
算，数学归纳法、主方法等基本方法的运用。
3.分治方法
分治方法的基本原理，典型问题如二分检索、合并排序、快速排序、线性选择问题、Strassen
矩阵乘法、最近点对、循环赛日程表等问题的算法设计原理、实现技术及其应用。
4.动态规划方法
动态规划的基本原理和方法;使用动态规划方法设计求解算法的适用问题的特点和基本步
骤;最优性原理、无后效性、状态转移方程;典型问题如 0/1 背包、每对节点之间的最短路径、
最优二分检索树、最长公共子序列、矩阵链乘、装配线调度等问题的算法设计原理、实现技术
及其应用;动态规划方法的变种：备忘录方法。
5. 贪婪方法
贪婪方法的基本原理和性质、最优子结构性，贪婪解的最优性证明;典型问题如背包问题、
活动选择问题、Haffman 编码、最小生成树、单源点最短路径等的算法设计原理、实现技术及
其应用。
6. 图的算法设计
图的基本定义与表示和图的基本算法;广度优先搜索、深度优先搜索、拓扑排序、最小生成
树算法(Kruskal 算法和 Prim 算法)、最短路径问题的算法(Bellman-Ford 算法、Dijkstra 算法、
Floyd 算法)、最大流问题的算法(Ford-Fulkerson 算法);相关算法的应用。
7.概率算法和近似算法
概率分析、随机算法、近似算法的原理和方法;关于典型问题如顶点覆盖、旅行商问题、集
合覆盖、子集和等问题的近似算法讨论。
8.NP 完全理论
NP 完全性的概念、可归约性、NP 完全性证明;了解典型 NP 完全问题如哈密顿回路问题、旅
行商问题、子集和问题、顶点覆盖问题等。
参考书目 (包括作者、书目、出版社、出版时间、版次)：
[1] 算法导论[M], Thomas H Cormen, Chzrles E Leiseron, Ronald L Rivest, etc，第二版，
机械工业出版社，2006.
编制人签名：博士点负责人签名：院长审核签名：
年月日