计算机问题求解一论题4.9 随机算法的概念 陶先平 2017年5月15日
计算机问题求解—论题4.9 随机算法的概念 陶先平 2017年5月15日
问题1：卷首语是什么含义？它和随机算法 有什么关联？ Randomized Algorithms “For him who seeks the truth, an error is nothing unknown." JOHANN WOLFGANG VON GOETHE
问题1: 卷首语是什么含义？它和随机算法 有什么关联？
确定性图灵机 一台图灵机是-个七元组(Q,∑，T,d,90,Qaccept,qreject),其中Q,∑，T都是有限集合，且满足 1. Q是状态集合； 2. 是输入字母表，其中不包含特殊的空白符口： 3.b∈「为空白符； 4. 是带字母表，其中口∈且∑CT; 5. 6:Q×T→Q×T×{L,R}是转移函数，其中L,R表示读写头是向左移还是向右移； 6. q0∈Q是起始状态； 7. 9 accept∈Q是接受状态。9 reject∈Q是拒绝状态，且Areject卡Qaccept° 可以看出，转换函数决定了这么一个图灵机在每个格局（读写 头位置，当前带字母，当前状态)下，其转换新状态是唯一 的，计算是唯一的
确定性图灵机 可以看出，转换函数决定了这么一个图灵机在每个格局(读写 头位置，当前带字母，当前状态）下，其转换新状态是唯一 的，计算是唯一的
非确定图灵机 ·唯一的区别： 6:QXT→2Q×T×{L, 例如，设非确定型图灵机M的当前状态为q,当前读写头所读的符号为x,若 6(q,x)={(91,T1,d1),(92,x2,d2),,(qe,xk,dk)} 则M将任意选择一个(g,x1,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 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：你能根据这个描述写出随机算法的图灵机模 型吗？
随机算法的概率空间 ·(SAx,Prob): SAx ={CIC is a computation of A onx}; 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()=y),is the sum ofall Prob(C),where C outputsy
随机算法的概率空间 • 𝑆𝐴,𝑥, 𝑃𝑟𝑜𝑏 : • 𝑆𝐴,𝑥 = 𝐶 𝐶 𝑖𝑠 𝑎 𝑐𝑜𝑚𝑝𝑢𝑡𝑎𝑡𝑖𝑜𝑛 𝑜𝑓 𝐴 𝑜𝑛 𝑥 ; 𝑃𝑟𝑜𝑏 𝑖𝑠 𝑎 𝑑𝑖𝑠𝑡𝑟𝑖𝑏𝑢𝑡𝑖𝑜𝑛 𝑜𝑣𝑒𝑟 𝑆𝐴,𝑥, • 𝑃𝑟𝑜𝑏𝐴,𝑥 𝐶 :𝑖𝑡 𝑖𝑠 Τ 1 2 𝑡𝑜 𝑡ℎ𝑒 𝑝𝑜𝑤𝑒𝑟 𝑜𝑓 𝑡ℎ𝑒 𝑛𝑢𝑚𝑏𝑒𝑟 𝑜𝑓 𝑟𝑎𝑛𝑑𝑜𝑚 𝑏𝑖𝑡𝑠 𝑎𝑠𝑘𝑒𝑑 𝑖𝑛 𝐶. • Prob(A(x) = y), is the sum of all ProbA,x (C), where C outputs y. 什么意思？
随机算法设计日标 算法的输出是随机的 probability that A outputs y for an input x,Prob(A(x)=y),is the sum of all ProbA,(C),where C outputs y.Obviously,the aim of the randomized algorithm designer is to achieve high Prob(A(x)=y)if y is the correct output for the input x. S0
随机算法设计目标 算法的输出是随机的 So
问题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 z.Then, for every n∈N, RandomA(n)=max {RandomA(x)is an input of size n}. 问题6： 这是什么意思？为什么品要这个定义？