算法设计与分析 王晓东 教案.ppt

* 8.1.4 图灵机 1. 多带图灵机 根据有限状态控制器的当前状态及每个读写头读到的带符号， 图灵机的一个计算步可实现下面3个操作之一或全部。 (1)改变有限状态控制器中的状态。 (2)清除当前读写头下的方格中原有带符号并写上新的带符号。 (3)独立地将任何一个或所有读写头，向左移动一个方格(L)或向右移动一个方格(R)或停在当前单元不动(S)。 k带图灵机可形式化地描述为一个7元组(Q，T，I，δ，b，q0，qf)，其中: (1)Q是有限个状态的集合。 (2)T是有限个带符号的集合。 (3)I是输入符号的集合，I?T。(4)b是惟一的空白符，b∈T-I。 (5)q0是初始状态。 (6)qf是终止(或接受)状态。 (7)δ是移动函数。它是从Q?Tk的某一子集映射到Q? (T?{L，R，S})k的函数。 * 8.1.4 图灵机 1. 多带图灵机 图灵机M的时间复杂性T(n)是它处理所有长度为n的输入所需的最大计算步数。如果对某个长度为n的输入，图灵机不停机，T(n)对这个n值无定义。 图灵机的空间复杂性S(n)是它处理所有长度为n的输入时，在k条带上所使用过的方格数的总和。如果某个读写头无限地向右移动而不停机，S(n)也无定义。 与RAM模型类似，图灵机既可作为语言接受器，也可作为计算函数的装置。 * 8.1.5 图灵机模型与RAM模型的关系 图灵机模型与RAM模型的关系是指同一问题在这2种不同计算模型下的复杂性之间的关系。 定理8-3 对于问题P的任何长度为n的输入，设求解问题P的算法A在k带图灵机模型TM下的时间复杂性为 ，那么，算法A在RAM模型下的时间复杂性为 。 定理8-4 对于问题P的任何长度为n的输入，设求解问题P的算法A在RAM模型下，不含有乘法和除法指令，且按对数耗费标准其时间复杂性为 ，那么，算法A在k带图灵机模型TM下的时间复杂性为 。 * 8.1.6 问题变换与计算复杂性归约 具体地说，假设有2个问题A和B，将问题A变换为问题B是指： (1)将问题A的输入变换为问题B的适当输入。 (2)解出问题B。 (3)把问题B的输出变换为问题A的正确解。 若用O(τ(n))时间能完成上述变换的第(1)步和第(3)步，则称问题A是τ(n)时间可变换到问题B，且简记为A∝τ(n)B。其中的n通常为问题A的规模(大小)。 当τ(n)为n的多项式时，称问题A可在多项式时间内变换为问题B。特别地，当τ(n)为n的线性函数时，称问题A可线性地变换为问题B。 通过问题变换的技巧，可以将2个不同问题的计算复杂性联系在一起。这样就可以将一个问题的计算复杂性归结为另一个问题的计算复杂性，从而实现问题的计算复杂性归约。 * 8.1.6 问题变换与计算复杂性归约 命题1(计算时间下界归约)：若已知问题A的计算时间下界为T(n)，且问题A是τ(n)可变换到问题B，即A∝τ(n)B，则 T(n)-O(τ(n))为问题B的一个计算时间下界。 命题2(计算时间上界归约)：若已知问题B的计算时间上界为T(n)，且问题A是τ(n)可变换到问题B，即A∝τ(n)B，则T(n)+O(τ(n))是问题A的一个计算时间上界。 问题的变换与问题的计算复杂性归约的关系： 在命题1和命题2中，当τ(n)=o(T(n))时，问题A的下界归约为问题B的下界，问题B的上界归约为问题A的上界。 * 8.1.6 问题变换与计算复杂性归约 通过问题变换获得问题的计算时间下界的例子： (1)判别函数问题：给定n个实数 ，计算其判别函数 。 元素惟一性问题可以在O(1)时间内变换为判别函数问题。任何一个计算判别函数的算法，计算出判别函数值后，再作一次测试，判断其值是否为0，即可得到元素惟一性问题的解。由命题1即知，元素惟一性问题的计算时间下界 也是判别函数问题的一个计算时间下界。 (2)最接近点对问题：给定平面上n个点，找出这n个点中距离最近的2个点。 在元素惟一性问题中，将每一个实数 ，1≤i≤n，变换为平面上的点( ，0)，1≤i≤n，则元素惟一性问题可以在线性时间内变换为最接近点对问题。 * 8.2 P类与NP类问题 8.2.1 非确定性图灵机 8.2.2 P类与NP类语言 8.2.3 多项式时间验证 * 8.2.1 非确定性图灵机 非确定性图灵机（ NDTM ）：一个k带的非确定性图灵机M是一个7元组：(Q，T，I，δ，b，q0，qf)。与确定性图灵机不同的是非确定性图灵机允许移动函数δ具有不确定性，即对于Q?Tk中的每一个值(q;x1,x2,