研究生工作

开元棋牌能作假吗

湖南科技大学博士生入学考试算法设计与分析复习大纲

2019-04-08 网络部
湖南科技大学博士生入学考试算法设计与分析复习大纲
1、算法分析技术
    (1) 冒泡排序

    (2) 插入排序
    (3) 渐近符号和相关定理
    (4) 递归函数的求解和相关定理(简化Master定理)
2、分治方法

    (1) 折半搜索算法
    (2) 归并排序算法
    (3) 快速排序算法
    (4) 采用划分的选择算法
3、贪心方法

    (1) 装载问题
    (2) 背包问题
    (3) 最小生成树算法
    (4) 单源最短路径算法
4、动态规划方法

    (1) 矩阵连乘问题
    (2) 多段图问题
    (3) 任意顶点间最短路径
5、回溯法

    (1) 子集问题和排列问题
    (2) Hamilton回路
    (3) 旅行商问题
    (4) 子集和问题
6、分枝限界方法

    (1) 子集问题和排列问题
    (2) 旅行商问题
    (3) 最大团问题
7、NP完全性理论

    (1) 非确定性算法与NP类问题
    (2) 一些典型的NP问题:3-SAT,团问题,顶点覆盖问题,0-1背包问题,旅行商问题,着色问题,皇后问题,多机调度问题。
    (3) 问题变换与NP完全类问题
    (4) 一些典型的NP完全问题:3-SAT,团问题,顶点覆盖问题,0-1背包问题,旅行商问题。
    (5) NP完全问题的证明方法:3-SAT,团问题,顶点覆盖问题,0-1背包问题,旅行商问题。
8、NP完全问题的近似算法

    (1) 求解NP完全问题的常用办法
    (2) 近似算法的性能比
    (3) 常数性能比的近似算法(顶点覆盖问题)
    (4) 非常数性能比的近似算法(顶点覆盖问题)
    (5) 概率上的好算法(顶点覆盖问题,最大团问题)
    (6) 完全多项式时间近似方案(子集和问题)
    (7) 近似算法与P = NP(旅行商问题)
9、参考书目

    (1) 计算机算法(C++语言描述)(第2版). Ellis Horowitz, Sartaj Sahni, Sanguthevar Rajasekeran着. 赵颖, 武永卫等译. 清华大学出版社, 2015.02
    (2) 计算机算法. 王志喜, 何勇. 电子科技大学出版社, 2016年11月
    (3) 计算机算法基础(第3版). 余祥宣, 崔国华, 邹海明. 华中科技大学出版社, 2006年4月

联系方式

  • 考试中心:0731-58290217
  • 就业指导:0731-58291319
  • 院党政办:0731-58290474
  • 院教务办:0731-58290130 / 0731-58290474-815
  • 研究生办:0731-58290190
  • 院学工办:0731-58290166 / 0731-58290474-802



关注微信「IT小助手」