南京大学：《计算机问题求解》课程教学资源（课件讲稿）随机算法的概念

计算机问题求解一论题4.9 随机算法的概念 陶先平 2015年5月05日

计算机问题求解—论题4.9 随机算法的概念 陶先平 2015年5月05日

问题1：卷首语是什么含义？它和随机算法 有什么关联？ Randomized Algorithms “For him who seeks the truth, an error is nothing unknown." JOHANN WOLFGANG VON GOETHE

问题1: 卷首语是什么含义？它和随机算法 有什么关联？

确定性图灵机 一台图灵机是-个七元组(Q,∑，T,6,q0,Jaccept,9 reject)其中Q,∑，「都是有限集合，且满足 1. Q是状态集合； 2. 是输入字母表，其中不包含特殊的空白符口： 3.b∈为空白符 4.是带字母表，其中口∈且∑CT: 5. 0:Q×T→Q×T×{L,R}是转移函数，其中L,R表示读写头是向左移还是向右移； 6. q0∈Q是起始状态； 7. 9 accept∈Q是接受状态。9 reject∈Q是拒绝状态，且Areject卡9 accept 可以看出，转换函数决定了这么一个图灵机在每个格局（读写 头位置，当前带字母，当前状态)下，其转换新状态是唯一 的，计算是唯一的

确定性图灵机 可以看出，转换函数决定了这么一个图灵机在每个格局(读写 头位置，当前带字母，当前状态）下，其转换新状态是唯一 的，计算是唯一的

非确定图灵机 ·唯一的区别： 6:QXT→2Q×T×{L, 例如，设非确定型图灵机的当前状态为q,当前读写头所读的符号为x,若 6(9,x)={(q1,x1,d1),（q2,x2,d2),,(qk,xk,dk)} 则M将任意选择一个(q:,x:,d:),按其进行操作，然后进入下一步计算。 This means that a nondeterministic TM(algorithm)may have a lot of com- putations on an input x,while any deterministic TM (algorithm)has exactly one computation for every input

非确定图灵机 • 唯一的区别：

问题2：什么是随机算法 A randomized algorithm can be viewed as a nondeterministic algorithm that has a probability distribution for every noudeterministic choice. 问题3：这两句话是一致的吗？ Another possibility is to consider a randomized algorithm as a deterministic algorithm with an additional in- put that consists of a sequence of random bits

问题3：这两句话是一致的吗？ 问题2：什么是随机算法

问题4：你能根据这个描述画出随机算法的图灵机模 型的示意图吗？ If one wants to formalize the notion of randomized algorithms,then one can take deterministic Turing machines A with an infinite additional tape.This additional tape is read-only;it contains an infinite random sequence of 0s and 1s,and A may move on it only from the left to the right.Another possibility 问题5：你能根据下个描述写出随机算法的图灵机模 型吗？ Another possibility is to take a nondeterministic Turing machine with nondeterministic guesses over at most two possibilities and to assign the probability to every such possibility

问题4：你能根据这个描述画出随机算法的图灵机模 型的示意图吗？ 问题5：你能根据下个描述写出随机算法的图灵机模 型吗？

随机算法的概率空间 ·(SAx,Prob): SA.x ={ClC is a computation of A on x; Prob is a distribution over Sax, Probax(C):it is 1/2 to the power of the number of random bits asked in C. Prob(A(x)=y),is the sum ofall Proba(C),where Coutputs y

随机算法的概率空间 • 𝑆𝐴,𝑥, 𝑃𝑟𝑜𝑏 : • 𝑆𝐴,𝑥 = 𝐶 𝐶 𝑖𝑠 𝑎 𝑐𝑜𝑚𝑝𝑢𝑡𝑎𝑡𝑖𝑜𝑛 𝑜𝑓 𝐴 𝑜𝑛 𝑥 ; 𝑃𝑟𝑜𝑏 𝑖𝑠 𝑎 𝑑𝑖𝑠𝑡𝑟𝑖𝑏𝑢𝑡𝑖𝑜𝑛 𝑜𝑣𝑒𝑟 𝑆𝐴,𝑥, • 𝑃𝑟𝑜𝑏𝐴,𝑥 𝐶 : 𝑖𝑡 𝑖𝑠 1 2 𝑡𝑜 𝑡ℎ𝑒 𝑝𝑜𝑤𝑒𝑟 𝑜𝑓 𝑡ℎ𝑒 𝑛𝑢𝑚𝑏𝑒𝑟 𝑜𝑓 𝑟𝑎𝑛𝑑𝑜𝑚 𝑏𝑖𝑡𝑠 𝑎𝑠𝑘𝑒𝑑 𝑖𝑛 𝐶. • Prob(A(x) = y), is the sum of all ProbA,x (C), where C outputs y

如何评价随机算法：两个随机变量 算法的输出是随机变量 The probability that A outputs y for an input c,Prob(A()=y),is the sum of all Prb(C),where Coutputs y.Obviously,the aim of the randomized 算法的时间代价也是随机变量 Let Time(C)10 be the time complexity of the run C of A on x.Then the expected time complexity of A on x is Ezp-TimeA()=E(Time]=∑ProbA,z(C)·Tme(C)

如何评价随机算法：两个随机变量

问题5： 随机算法的期望时间复杂度和确定 算法的平均复杂度有什么不同？

问题5： 随机算法的期望时间复杂度和确定 算法的平均复杂度有什么不同？

For every randomized algorithm A we consider a new complexity measure- the number of random bits used.Let RandomA()be the maximum number of random bits used over all random runs (computations)of A on x.Then, for every n∈N, RandomA(n)=max [RandomA()x is an input of size n}. 问题6： 这是什么意忠？为什么品要这个定义？