可计算性问题

1、可计算性问题Tel: 31984767Email: 1计算复杂度假设有N个数据形成的一个链表。查找x是否在此列表中，采取顺序比较方式。如果x在此列表中，且位置处于i,则需要比较i次。则平均比较次数为如果x不在此列表中，则需要比较N次。因此该查找算法的平均查找复杂度为(N+1)/2，最大复杂度为N2大O分析为了简化数量级的分析，往往采用大O分析，选取最重要的部分，即使用随着问题的大小增长得最快的项表示计算时间（复杂度）。例如f(N)=N4+100N2+10N+50, O(f(N)=O(N4)f(n)=(N+1)/2, O(f(n)=O(N)3常见的数量级4可满足性问题对于有N个变量的布尔表达式（

2、仅仅包含AND， OR，NOT操作），可否存在一组变量使得该布尔表达式的值为15可计算问题的渊源1928年德国著名数学家希尔伯特(Hilbert)提出一个问题：可否有一个算法能对所有的数学原理自动给予证明1931年，奥地利数学家哥德尔证明了：对于一个相容的形式系统，存在一个算术命题，它在该系统中可以既未被证明，也未被证否。6图灵机用准确的数学形式来描述什么是“计算”图灵机包含了一条无限长的纸带和一个控制器。控制器可以：从纸带上读出一个符号；向纸带写入一个符号；使带子可以向左边移动一个位置，或向右移动一个位置停机Church-Turing理论：任何能直观计算的问题都内被图灵机计算。如果证明了某个

3、问题使用图灵机是不可解决的，那么这个问题就是不可解决的。7停机定理给定任意一个图灵机程序P和任意一组输入数据I，不存在一个图灵机程序，它能在有限多步后停机，并告诉我们P是否会结束输入数据I的处理。8P和NP问题P (Polynomially)类问题：算法能在多项式时间内完成的问题。NP (Nondeterministic Polynomially)问题：可以用多项式时间来验证一个解是否正确。已经可以证明：需要证明：PNP，或者P是NP的一个真子集9NP完全问题(NP-Complete Problems)NP问题中有一组问题，如果其中有一个问题具有多项式的算法可以完成，则这一组问题都可以使用多项

4、式时间完成。NP完全问题的例子：可满足问题；货担郎问题：在一个图中，可否找到一个路径满足：所有的节点经过且仅经过一次，而且最后可以回到起点；装箱问题：有有限多个容量为1的箱子，以及N个货物（每个货物的重量均小于1），需要最少的箱子把所有的N个货物完全装完。背包问题：背包的容量为C，有N个物体，体积分别为s1,sn以及价值分别为p1,pn，寻找一个最大价值的装背包的方案。10计算复杂度假设有N个数据形成的一个链表。查找x是否在此列表中，采取顺序比较方式。如果x在此列表中，且位置处于i,则需要比较i次。则平均比较次数为如果x不在此列表中，则需要比较N次。因此该查找算法的平均查找复杂度为(N+1)/

5、2，最大复杂度为N11大O分析为了简化数量级的分析，往往采用大O分析，选取最重要的部分，即使用随着问题的大小增长得最快的项表示计算时间（复杂度）。例如f(N)=N4+100N2+10N+50, O(f(N)=O(N4)f(n)=(N+1)/2, O(f(n)=O(N)12常见的数量级13图灵机用准确的数学形式来描述什么是“计算”图灵机包含了一条无限长的纸带和一个控制器。控制器可以：从纸带上读出一个符号；向纸带写入一个符号；使带子可以向左边移动一个位置，或向右移动一个位置停机Church-Turing理论：任何能直观计算的问题都内被图灵机计算。如果证明了某个问题使用图灵机是不可解决的，那么这个问题就是不可解决的。14P和NP问题P (Polynomially)类问题：算法能在多项式时间内完成的问题。NP (Nondeterministic Polynomially)问题：可以用多项式时间来验证一个解是否正