算法设计与分析 第二章.ppt

第二章 P类NP类及NPC类 2.1 问题与算法 2.2 确定型图灵机与P类 2.3 非确定型计算与NP类 2.4 多项式变换与NPC类 2.1 问题与算法 定义2-1: 算法是一步一步求解问题的通 用程序 问题的两个要素 : 实例输入 询问输出 问题的形式分为两类 优化问题 判定问题 2.2 确定型图灵(Turning)机与P类 确定型单带图灵机构造如下图 定义2-2 : 如果把问题的任意实例I