Operations on language 多项式时间内可求解问题 Union and intersection: same as the set 多项式时间内可求解的问题的特点 perations 多项式时间可求解的问题被认为是易处理 Complement ofL:I=2'-L Concatenation of two language L, and L2 理由1:尽管θ(n10)算法被认为是不 L={x1x2:x∈L1,x2∈L2} 易处理的,但事实上还没有什么实际问题有 如此之高的多项式算法。 Closure or Kleene Star 经验证明一但一个问题有多项式解,那 L*=GULULZULU 么常常会有更加有效的解决方案 清华大学宋域恒 请华大学宋恒 理由2:在某一种计算模型下有多项式算法则 在另一种计算模型下亦有多项式算法 2抽象问题 例如:一个问题在串行随机存取机上有 多项式算法,则在图林机上亦有多项式算 抽象问题Q是集合I和S上的二元关系。其中 法,在并行机上亦如此。 理由3:多项式算法时间问题集合有非常好的 ·例如:①最短路径问题:问题实例(G, 封闭性质,它在加、乘、复合运算下都是 u、v):一个圆和其上两个顶点;问题解 封闭的 是(u~v)一个从u到v的由边相连的顶点 【本课程研究的算法大部分是多项式的,研 究的问题也是在多项式时间内可解的,对 ②查找最小值问题:问题实例 于不能在多项式时间内求解的问题该如何 a1,…,an>一个数组。解:数m。 处理?】 清华大学末斌恒 请华大学宋恒 判决问题 3.编码:抽象对象集合S的编码是: 抽象对象集合S的编码是 · Decision问题:如果I={0,1}或 E:S→∑*即把S中的对象e转化成一个二进 yes,no},则称问题是判决问 制(可以是多进制)的串。 题,下面我们只关心判决问题。 优化问题一般都可以转换成判决 构成,称其为具体问题。我们称 辈漆 问题。 在0(T(n))时间内解决了一个具体问 题,如果此问题i的长度|i是n,此算法可 在0(T(n))时间内求解此问题 一个抽象问题可以编码成具体问题。 清华大学末破恒 请华大学宋5 清华大学 宋斌恒 25 Operations on language • Union and intersection: same as the set operations • Complement of L: • Concatenation of two language L1 and L2: • Closure or Kleene Star: – L*={ε}U L U L2 U L3 U… L = Σ − L * { : , } 1 2 1 1 2 L2 L = x x x ∈ L x ∈ 清华大学 宋斌恒 26 多项式时间内可求解问题 • 多项式时间内可求解的问题的特点 – 多项式时间可求解的问题被认为是易处理 的，有三条理由： 理由1：尽管Θ(n100)算法被认为是不 易处理的，但事实上还没有什么实际问题有 如此之高的多项式算法。 经验证明一但一个问题有多项式解，那 么常常会有更加有效的解决方案。 清华大学 宋斌恒 27 理由2：在某一种计算模型下有多项式算法则 在另一种计算模型下亦有多项式算法。 例如：一个问题在串行随机存取机上有 多项式算法，则在图林机上亦有多项式算 法，在并行机上亦如此。 理由3：多项式算法时间问题集合有非常好的 封闭性质，它在加、乘、复合运算下都是 封闭的 【本课程研究的算法大部分是多项式的，研 究的问题也是在多项式时间内可解的，对 于不能在多项式时间内求解的问题该如何 处理？】 清华大学 宋斌恒 28 2.抽象问题： 抽象问题Q是集合I和S上的二元关系。其中 I是问题实例集合，S是问题解集合。 • 例如：①最短路径问题：问题实例（G， u、v):一个圆和其上两个顶点；问题解 是（u～v)一个从u到v的由边相连的顶点 集。 ②查找最小值问题：问题实例： ＜a1,…,an＞一个数组。解:数m。 清华大学 宋斌恒 29 判决问题 • Decision问题：如果I＝｛0，1｝或 ｛yes,no｝，则称问题是判决问 题，下面我们只关心判决问题。 优化问题一般都可以转换成判决 问题。 清华大学 宋斌恒 30 3.编码：抽象对象集合S的编码是： 抽象对象集合S的编码是： E：S→∑＊即把S中的对象e转化成一个二进 制（可以是多进制）的串。 如果一个问题的实例是由二进制串集 构成，称其为具体问题。我们称一个算法 在O（T（n)）时间内解决了一个具体问 题，如果此问题i的长度|i|是n，此算法可 在O（T（n)）时间内求解此问题。 一个抽象问题可以编码成具体问题