问题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： 这是什么意忠？为什么品要这个定义？