计算机问题求解一论题4.13 随机算法的概念 陶先平 2021年5月26日
计算机问题求解—论题4.13 随机算法的概念 陶先平 2021年5月26日
问题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→2QxT×{L, 例如，设非确定型图灵机的当前状态为q,当前读写头所读的符号为x,若 6(q,x)={(q1,x1,d1),（q92,x2,d2),,（qk,ck,dk)} 则M将任意选择-个(g,,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. 问题2：这两句话是一致的吗？ 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
问题2：这两句话是一致的吗？ 问题2：什么是随机算法