昆明理工大学博士研究生入学考试
《算法分析与设计》考试大纲
第一部分 考试形式和试卷结构
一、考试方式：考试采用闭卷笔试方式，试卷满分为100分。
二、考试时间：180分钟。
三、试卷内容结构
客观题部分，约占 30%。
主观题部分，约占 70%。
四、试卷题型结构
试卷由三部分组成：选择题、问答题、设计题。其中：
选择题 约占 30%。
问答题 约占 50%。
设计题 约占 20%。
第二部分 考察的知识及范围
一、总体要求
了解计算复杂性理论、概率算法设计思想、近似算法设计思想；理解NP完全理论、回溯法的基本思想及算法设计、分枝限界法的基本思想及算法设计；掌握算法时空复杂度分析、蛮力法的基本思想及算法设计、递归算法的实现机制及算法设计、分治法的基本思想及算法设计、减治法的基本思想及算法设计、动态规划的基本思想及算法设计、贪心法的基本思想及算法设计、搜索算法的基本思想及算法设计。
二、内容
1．基本概念
算法的基本定义、基本性质，算法复杂度分析的基本技术和方法，计算时间的渐进表示及其相关性质。
2．递归算法设计技术
递归算法的实现机制，设计和分析递归算法的一般方法，消去递归；递归关系式的计算、数学归纳法等基本方法的应用。
3．分治法
分治法的基本原理，典型问题如二分检索、归并排序、快速排序、选择问题等的算法设计原理、实现技术及其应用。
4．贪心方法
贪心方法的基本原理和性质，贪心解的最优性证明；典型问题如背包问题、带有限期的作业排序问题、活动选择问题、Huffman 编码、最优归并模式、最小生成树、单源点最短路径等的算法设计原理、实现技术及其应用。
5．动态规划
动态规划的基本原理和方法、最优性原理、状态转移方程；典型问题如多段图、0/1 背包、每对节点之间的最短路径、最优二分检索树、货郎担问题、装配线调度等的算法设计原理、实现技术及其应用。
6．搜索算法
广度优先搜索、深度优先搜索性质和异同；回溯法的原理和技术、分支-限界法的原理和技术； LC-检索的原理和方法；典型问题如双连通分图、与或树、8-皇后问题、图的着色问题等的算法设计原理、实现技术及其应用。
7．图的算法设计
图的基本定义；最小生成树算法（Kruskal算法和 Prime 算法）、最短路径算法（Dijkstra 算法、Floyd 算法）、最大流算法，相关算法的应用。
8．概率算法和近似算法
概率分析、随机算法、近似算法的原理和方法；关于典型问题如顶点覆盖、旅行商问题、子集和数等问题的近似算法讨论。
9．NP 完全理论
NP 完全性的概念、可归约性、NP 完全性证明；了解典型 NP 完全问题如哈密顿回路问题、旅行商问题、子集和问题、顶点覆盖问题等。
