天津理工大学2016博士研究生招生算法设计与分析考试大纲
一、考试科目：算法设计与分析( 2002)
二、考试方式：
考试采用笔试形式，考试时间为180分钟，试卷满分为100分。
三、试卷结构与分数比重：
题型包括选择题、判断题、填充题和简答题(不超过40%，从中选取2~3种题型)，计算题、证明题、算法设计与综合应用题(至少占60%)
四、考查的知识范围：
要求考生全面、系统地掌握算法设计与分析的基本概念、基本原理和典型方法，能灵活运用所学知识来阐述解决问题的方法和途径。具体考试内容如下：
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.
机械工业出版社，2007.3.
注意：本文归作者所有，未经作者允许，不得转载
