第十五讲NP完全性理论与近似算法 内容提要 口理解RAM,RASP和图灵机计算模型 口理解非确定性图灵机的概念 口理解P类与NP类语言的概念 口理解NP完全问题的概念 口理解近似算法的性能比及多项式时间近似格式的概念 口通过范例学习NP完全问题的近似算法 (1)顶点覆盖问题(2)旅行售货员问题 (3)集合覆盖问题4)子集和问题1 内容提要  理解RAM，RASP和图灵机计算模型  理解非确定性图灵机的概念  理解P类与NP类语言的概念  理解NP完全问题的概念  理解近似算法的性能比及多项式时间近似格式的概念  通过范例学习NP完全问题的近似算法 （1）顶点覆盖问题 （2）旅行售货员问题 （3）集合覆盖问题 （4）子集和问题。 第十五讲 NP完全性理论与近似算法