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