|
友情提示：本站提供全国400多所高等院校招收硕士、博士研究生入学考试历年考研真题、考博真题、答案，部分学校更新至2012年，2013年；均提供收费下载。 下载流程： 考研真题 点击“考研试卷””下载; 考博真题 点击“考博试卷库” 下载
华中科技大学博士研究生入学《算法设计与分析》考试大纲
（代码：3542）
第一部分 考试说明
一、考试性质
《算法设计与分析》是华中科技大学计算机科学与技术及相关专业博士研究生入学考
试科目之一，以高等学校计算机学科优秀硕士毕业生能达到的及格或及格以上水平为评价标
准，要求考生全面、系统地掌握“算法设计与分析”的基本概念、基本原理和典型方法，能
灵活运用所学知识阐述求解实际问题的方法和途径。目的在于考察考生理论素养与专业知
识，便于优秀人才的选拔。
考试对象为参加博士生入学考试的应届或非应届硕士毕业生，以及具有同等学历的在
职人员。
二、评价目标
1．掌握算法的基本概念和分析算法的基本方法；
2．掌握分治策略、贪心方法、动态规划、回溯法、分支-限界法、图算法、概率算法、
近似算法、NP 完全性理论的基本原理。
3．熟练掌握求解典型问题的算法的设计思想和实现方法，并能灵活运用，以能有效求
解新的问题。
4．具有较高的算法设计能力和设计技巧，可能设计出解决实际问题的有效算法。
5．了解算法研究领域的现状与趋势。
三、考试形式与试卷结构
1．考试形式：闭卷、笔试。
2．答题时间：180 分钟。
3．试卷题型：填空题、选择题、改错题、简答题、计算题、证明题、算法设计与综合
应用题。每年在上述题型中选用 3～5 种。重点考察对本课程知识点的掌握程度和综合应用
能力。
第二部分 考查要点
1．基本概念
算法的基本定义、基本性质，算法复杂度分析的基本技术和方法，计算时间的渐进表示
及其相关性质。
2．递归算法设计技术
递归算法的实现机制，设计和分析递归算法的一般方法，消去递归；递归关系式的计算，
数学归纳法、主方法等基本方法的运用。
3．分治法
分治法的基本原理，典型问题如二分检索、归并排序、快速排序、选择问题、Strassen
矩阵乘法、最近点对等的算法设计原理、实现技术及其应用。
4．贪心方法
贪心方法的基本原理和性质、最优子结构性，贪心解的最优性证明；典型问题如背包问
题、带有限期的作业排序问题、活动选择问题、Haffman 编码、最优归并模式、最小生成树、
单源点最短路径等的算法设计原理、实现技术及其应用。
5．动态规划
动态规划的基本原理和方法、最优性原理、无后效性、状态转移方程；典型问题如多段
图、0/1 背包、每对节点之间的最短路径、最优二分检索树、货郎担问题、矩阵链乘、装配
线调度等的算法设计原理、实现技术及其应用。
6．搜索算法
宽度优先搜索、深度优先搜索、D-Search 搜索的原理、性质和异同；回溯法的原理和技
术、分支-限界法的原理和技术；а -в 截断、LC-检索的原理和方法；典型问题如双连通分
图、与或树、对策树、8-皇后问题、子集和数问题、图的着色问题等的算法设计原理、实现
技术及其应用。
7．图的算法设计
图的基本定义；最小生成树算法（Kruskal 算法和 Prim 算法）、最短路径算法
（Bellman-Ford 算法、Dijkstra 算法、Floyd 算法）、最大流算法，相关算法的应用。
8．概率算法和近似算法
概率分析、随机算法、近似算法的原理和方法；关于典型问题如顶点覆盖、旅行商问题、
子集和数等问题的近似算法讨论。
9．NP 完全理论
NP 完全性的概念、可归约性、NP 完全性证明；了解典型 NP 完全问题如哈密顿回路问
题、旅行商问题、子集和数问题、顶点覆盖问题等。
免责声明：本文系转载自网络，如有侵犯，请联系我们立即删除，另：本文仅代表作者个人观点，与本网站无关。其原创性以及文中陈述文字和内容未经本站证实，对本文以及其中全部或者部分内容、文字的真实性、完整性、及时性本站不作任何保证或承诺，请读者仅作参考，并请自行核实相关内容。
|
文章搜索
您现在的位置： 
