计算理论(哈工大 第五章).pdfVIP

Chapter Five 随机计算的复杂性理论 李建中 海量数据计算研究中心 计算机科学与技术学院 Outline 5.1 随机算法概述 5.2 概率图灵机定义 5.3 随机复杂性类 5.4 复杂性类的关系 5.5 PTM的其他方面 5.1 随机算法概述 5.2 概率图灵机定义 5.3 随机复杂性类 5.4 复杂性类的关系 5.5 PTM的其他方面 确定的Quicksort算法 Partition(A, p,r ) QUICKSORT(A,p,r) x ←A[r ]; i ← p −1; If p r forj ←p tor − 1 Then q=Partition(A, p, r); do if A [ j ] ≤x QUICKSORT(A, p, q-1); i ←i +1; exchange A [i] ↔A[ j ]; QUICKSORT(A, q+1, r). exchange A [i +1] ↔A[r ]; return i + 1; 理想时间复杂性：T(n)=2T(n/2)+n=O(nlogn) 最坏时间复杂性：T(n)=O(n2) 随机Quicksort算法 Randomized-Quicksort(A, p, r) 1. If p r 2. Then q := Randomized-Partition(A, p, r); 3. Randomized-Quicksort(A, p, q-1); 4. Randomized-Quicksort(A, q+1, r). Randomized-Partition(A, p, r) 1. q := Random(p , r) 2. A [r] ↔A [i]; 3. Return Partition(A , p , r) 期望时间复杂性: T(n)=O(nlogn) 随机Max-3-CNF算法 输入: 合取范式CNF, 每个析取式有3个变量, 无变量及其非出现在同一析取式中. 输出: 一个变量赋值, 最大化值为1的析取式个数 Random-Max-3-CNF(CNF) 1. For 对于CNF 中的每个变量x Do 2. 随机地为x赋值: x=0的概率为1/2, x= 1的概率为1/2; 3. Return. 算法的近似比=优化解代价/近似解代价=8/7. 5.1 随机算法概述 5.2 概率图灵机定义 5.3 随机复杂性类 5.4 复杂性类的关系 5.5 PTM的其他方面 概率图灵机(PTM)的定义 有限 控制器