Algorithm 10

第10章 算法能力的极限 Limitations of Algorithm Power 杨春明 © School of Computer Science and Technology, SWUST

算法能力的极限 Limitations of Algorithm Power „

教学内容 „ „ „ „

„

算法下界 决策树 P，NP和NP完全问题 数值算法的挑战

教学要求 „

了解求算法下界的方法，了解NP问题

http://mryang.stumental.com/

© School of Computer Science and Technology, SWUST

2

算法的下界 „

„

算法下界指的是求解某一问题的任意算 法可能具有的最佳效率。 平凡下界 „

„ „ „

对所求解问题的输入和输出中必须要处理的 项进行计数，所产生的结果就是平凡下界。 如：任何生成n个不同项的所有排列的算法 计算给定点x的n次多项式 计算两个n阶矩阵乘积的算法

http://mryang.stumental.com/

© School of Computer Science and Technology, SWUST

3

算法的下界 „

信息论下界 „ „

„

敌手下界 „

„

根据算法必须处理的信息量来建立效率下界。 如：“猜”数字游戏，排序和查找 不断把算法推向最消耗时间的路径。

问题化简 „

已知问题Q的下界，求未知问题P的下界，可将问题 Q在任意实例下转化为P，则说明Q的下界将会是P 的下界。

http://mryang.stumental.com/

© School of Computer Science and Technology, SWUST

4

决策树(Decision Trees) „

许多以输入项作比较的算法，都可以用 一种称为决策树的结构来研究它们的性 能。

求三个数中最 小数的决策树 h≥[log2l]

http://mryang.stumental.com/

© School of Computer Science and Technology, SWUST

5

排序算法的决策树

三元素的选择排序 http://mryang.stumental.com/

Cworst(n) ≥[log2n!]

© School of Computer Science and Technology, SWUST

6

排序算法的决策树

三元素的插入排序 http://mryang.stumental.com/

Cavg(n) ≥log2n!

© School of Computer Science and Technology, SWUST

7

查找有序数组的决策树

四元素折半查找的三叉决策树 http://mryang.stumental.com/

Cworst(n) ≥[log3(2n+1)]

© School of Computer Science and Technology, SWUST

8

查找有序数组的决策树

四元素折半查找的二叉决策树 http://mryang.stumental.com/

Cworst(n) ≥[log2(n+1)]

© School of Computer Science and Technology, SWUST

9

计算模型 „

„

算法是理论计算机的灵魂。在理论计算 机中，算法已不限于只是上面定义中的 计算机程序。 确定型图灵机模型。 „

„

给出固定的程序，模型按照程序和输入完全 确定性地运行。

非确定型图灵机。 „

它在进行计算的时候，会自动选择最优路径 进行计算。通俗地说，它有预测能力。

http://mryang.stumental.com/

© School of Computer Science and Technology, SWUST

10

P和NP问题 P＝NP？ „ „

„

理论计算机科学的核心问题 它是Clay研究所的七个百万美元大奖问 题之一 在2006国际数学家大会上，它是某个1小 时讲座的主题。

注：这里面的两个P都是指Polynomial(多项式) http://mryang.stumental.com/

© School of Computer Science and Technology, SWUST

11

P类 „

„

„

如果一个算法，它能在以输入规模为参 变量的某个多项式的时间内给出答案， 则称它为多项式时间算法。 P类问题是一类用(确定性) 算法在多项式 的时间内求解的判定问题。 P类问题指在确定型图灵机上的具有多项 式算法的问题集合。

http://mryang.stumental.com/

© School of Computer Science and Technology, SWUST

12

NP类 „

不确定算法是一个两个阶段的过程，它 把一个判定问题的实例l作为它的输入， 并做以下操作： „ „

„

非确定性(猜测)阶段：生成任意一个S。 确定(验证)阶段：验证S是否是l的一个解。

如果一个不确定算法在验证阶段的时间 效率是多项式级的，这个算法就是不确 定多项式类型的。

http://mryang.stumental.com/

© School of Computer Science and Technology, SWUST

13

NP类 „

„

„

NP类问题是一类可以用不确定多项式算 法求解的判定问题。 NP类问题指非确定型图灵机上具有多项 式算法的问题集合，这里N是NonDeterministic的意思。 在一般看来，P问题是指能够在多项式时 间求解的判定问题，而NP问题则是指那 些肯定解能够在给定正确信息下在多项 式时间内验证的判定问题。

http://mryang.stumental.com/

© School of Computer Science and Technology, SWUST

14

NP问题 P⊆NP „

„

P＝NP？

P vs NP问题指P是否完全等于NP，即确 定型图灵机和非确定图灵机的性能是否 一样。 人们为何要提出NP问题？因为，大多数 遇到的自然的难解问题，最后都发现它 们是NP问题。如果我们能证明NP跟P的 关系，则解决了无数问题的算法复杂度 问题。

http://mryang.stumental.com/

© School of Computer Science and Technology, SWUST

15

NP完全问题 „

„

NP里面有无数个不同的问题，我们是否要一个 一个地判定它们是否属于P呢？ NP完全(NP Complete，简记为NPC)问题，指 的是那些NP中最难的那些问题：所有其它的 NP问题都可以归约到这些NP完全问题。也就 是说，只要这些NP完全问题的某一个到解决， 无论是证明其存在多项式算法，还是不存在， 都意味着P vs NP问题的解决。

http://mryang.stumental.com/

© School of Computer Science and Technology, SWUST

16

NP完全问题 „

„

„

几乎所有NP里面无法确定是否属于P的问 题最后都被证明为NP完全。正因为如 此，多数理论计算机学家都猜测P≠NP。 如果NP≠P，那么NP-P中存在非NP完全 问题。 当然，这种问题具体是什么样子，是无 法用直观的语言表示出来，它纯粹是一 个数学上的构造性证明。

http://mryang.stumental.com/

© School of Computer Science and Technology, SWUST

17

相关资源 „

NP完全问题的不完全列表 „

„

Clay Mathematics Institute „

„

http://www.nada.kth.se/~viggo/problemlis t/compendium.html http://www.claymath.org/millennium/P_vs _NP/

图灵机- Wikipedia „

http://zh.wikipedia.org/wiki/图灵机

http://mryang.stumental.com/

© School of Computer Science and Technology, SWUST

18

数值算法的挑战 Challenges of Numerical Algorithms „

数值分析是指关心那些求解数学问题的算 法。这里指的问题是“连续”的数学问题。

http://mryang.stumental.com/

© School of Computer Science and Technology, SWUST

19

数值算法的挑战 Challenges of Numerical Algorithms „

数值算法的挑战来自于： „ „ „ „

在求解问题时不能得到精确的解。 这种不精确解的误差有两种： 截断误差：用有限来逼近无穷所造成的。 舍入误差：由于计算机在表示数字时的不精 确性造成的。

http://mryang.stumental.com/

© School of Computer Science and Technology, SWUST

20

算法能力的极限小结 „

„

„

„

„

„

下界指出了任何属于这个类型的算法能构具有的最佳 效率。 P是所有能够在多项式时间内求解的判定问题所构成的 类型。 NP是那些随意生成的解能够在多项式时间内得到验证 的问题所构成的类型。 对于P=NP是否成立，或P仅仅是NP的一个真子集，仍 然是计算机科学理论中最终要的一个待解决问题。 数值分析是计算机科学的一个分支，处理求解连续的 数学问题。 数值算法的挑战来自于：在求解问题时不能得到精确 的解。这种不精确解的误差有两种：截断误差和舍入 误差。

http://mryang.stumental.com/

© School of Computer Science and Technology, SWUST

21