|
1.算法分析基础 1) 熟悉渐近表示法，掌握渐近符号O等的定义，能判断一个较复杂的函数属于哪个渐近增长阶； 2) 熟悉一些算法复杂度分析的方法，比如说主定理法等，能对结构复杂的算法进行分析。 2.算法设计基础 1) 熟悉算法设计的三大技巧：贪心算法、分而治之，动态规划。 2) 能证明各种算法的正确性。 3) 能用这三大技巧设计相应的算法。 3.NP完备性理论及近似算法 1) 了解并掌握NP 完备性理论及其实际意义； 2) 熟悉多项式规约。掌握证明一个问题NP完全性的基本方法和思路； 3) 熟悉最小点覆盖、最大独立集等问题的NP完备性证明； 4) 了解并掌握近似算法的设计步骤与技巧，掌握点覆盖等问题的近似算法的设计。 4.经典算法 熟悉排序、最短路径、最小生成树、最大匹配、最大流、最大公共字符串等问题的一些经典算法。 5.其它智力算法问题
| 
