算法2015 提纲整理

算法2015

1.记号O、omga、theta 的意义

2.分治法的基本步骤

3.动态规划算法的两个基本要素

4.设计动态规划算法的步骤

5.分治和动规的异同点

6.贪心法的两个基本要素

7.贪心法的算法正确性证明的基本策略

8.贪心法与动态规划两种算法策略的异同点

9.最大流的概念、流通（circulation）的概念

10.最大流最小割定理的内容及其证明方法

11.“多项式归约（reduction）”的概念与用途；

12.P 问题、NP问题、NP完全问题、NP困难问题（NP-hard problem）的概念

13.NP完全问题的实际证明方法

14.常见的NP完全问题