中国地质大学（武汉）2016算法设计与分析博士考试大纲
2293 《算法设计与分析》考试大纲
适用专业： 地学信息工程 0818Z3
《算法设计与分析》考试大纲适用于中国地质大学(武汉)地学信息工程专业博士研究生入学考试。算法设计与分析是计算机及相关学科的重要学科基础。要求考生全面、系统地掌握“算法设计与分析”的基本概念、基本原理和典型方法，能灵活运用所学知识阐述求解实际问题的方法和途径。
一、试卷结构
试卷题型：简答题、计算题、证明题、算法设计与综合应用题，试卷满分为100分。重点考察对本课程知识点的掌握程度和综合应用能力。
二、考试形式
闭卷、笔试。
考试时间：180分钟。
三、参考书藉
1.计算机算法基础。余祥宣,崔国华,邹海明著，华中科技出版社，2006.4
2. 算法设计与分析。王晓东编著，清华大学出版社，2003.1
四、考试要求
1.掌握算法的基本概念和分析算法的基本方法。
2.掌握分治策略、贪心方法、动态规划、回溯法、分支-限界法、图算法、概率算法、近似算法、NP完全性理论的基本原理。
3.熟练掌握求解典型问题的算法的设计思想和实现方法，并能灵活运用，以能有效求解新的问题。
4.具有较高的算法设计能力和设计技巧，可以设计出解决实际问题的有效算法。
5.了解算法研究领域的现状与趋势。
五、考试内容
1.基本概念
算法的基本定义、基本性质，算法复杂度分析的基本技术和方法，计算时间的渐进表示及其相关性质。
2.递归算法设计技术
递归算法的实现机制，设计和分析递归算法的一般方法，消去递归;递归关系式的计算，数学归纳法等基本方法的运用。
3.分治法
分治法的基本原理，典型问题如二分检索、归并排序、快速排序、选择问题、Strassen矩阵乘法、最近点对等的算法设计原理、实现技术及其应用。
4.贪心方法
贪心方法的基本原理和性质、最优子结构性，贪心解的最优性证明;典型问题如背包问题、带有限期的作业排序问题、Haffman编码、最优归并模式、最小生成树、单源点最短路径等的算法设计原理、实现技术及其应用。
5.动态规划
动态规划的基本原理和方法、最优性原理、无后效性、状态转移方程;典型问题如多段图、0/1背包、每对节点之间的最短路径、最优二分检索树、背包问题、货郎担问题、矩阵连乘、作业调度等的算法设计原理、实现技术及其应用。
6.搜索算法
宽度优先搜索、深度优先搜索;回溯法的原理和技术、分支-限界法的原理和技术;典型问题如双连通分图、与或树、对策树、8-皇后问题、子集和数问题、图的着色问题等的算法设计原理、实现技术及其应用。
7.概率算法和近似算法
概率分析、随机算法、近似算法的原理和方法;关于典型问题如顶点覆盖、旅行商问题、子集和数等问题的算法讨论。
8.NP完全理论
NP完全性的概念、可归约性、NP完全性证明;了解典型NP完全问题如哈密顿回路问题、旅行商问题、子集和数问题、顶点覆盖问题等。
注意：本文归作者所有，未经作者允许，不得转载
