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

计算机问题求解一论题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：什么是随机算法

问题3：随机的01串，如何影响着算法执行？ ·确定性算法A在X上的运行： output 算法A在问题实例x及某个随机01位串上的runs: 随机01位串 随机采样 通情况下，随机算法将 某次运行，决定于x和01位串 通过多次独立的执行来获 得一个“好”的解 output

问题3：随机的01串，如何影响着算法执行？ •确定性算法A在x上的运行： •算法A在问题实例x及某个随机01位串上的runs： output 随机01位串 output 0 1 通常情况下，随机算法将 某次运行，决定于x和01位串 通过多次独立的执行来获 得一个“好”的解 随机采样

随机算法的概率空间 ·(SAx,Prob): SAx ={CIC 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 bitsasked in C. 什么意思？

随机算法的概率空间 • 𝑆𝐴,𝑥, 𝑃𝑟𝑜𝑏 : • 𝑆𝐴,𝑥 = 𝐶 𝐶 𝑖𝑠 𝑎 𝑐𝑜𝑚𝑝𝑢𝑡𝑎𝑡𝑖𝑜𝑛 𝑜𝑓 𝐴 𝑜𝑛 𝑥 ; 𝑃𝑟𝑜𝑏 𝑖𝑠 𝑎 𝑑𝑖𝑠𝑡𝑟𝑖𝑏𝑢𝑡𝑖𝑜𝑛 𝑜𝑣𝑒𝑟 𝑆𝐴,𝑥, • 𝑃𝑟𝑜𝑏𝐴,𝑥 𝐶 :𝑖𝑡 𝑖𝑠 Τ 1 2 𝑡𝑜 𝑡ℎ𝑒 𝑝𝑜𝑤𝑒𝑟 𝑜𝑓 𝑡ℎ𝑒 𝑛𝑢𝑚𝑏𝑒𝑟 𝑜𝑓 𝑟𝑎𝑛𝑑𝑜𝑚 𝑏𝑖𝑡𝑠 𝑎𝑠𝑘𝑒𝑑 𝑖𝑛 𝐶. 什么意思？

问题3：随机的01串，如何影响着随机算 法？ ·基于统计科学的随机算法 ·随机采样 •算法的时间复杂度：随机的性能 •算法结果的最优性：随机的功能 分析随机算法，主要关注这两个随机变量！

问题3：随机的01串，如何影响着随机算 法？ •基于统计科学的随机算法 •随机采样 •算法的时间复杂度：随机的性能 •算法结果的最优性：随机的功能 分析随机算法，主要关注这两个随机变量！

随机的01串，如何影响着随机算法？ 蒙特卡罗算法：算法结果被设定为随机变量 ·算法效率上的约束决定了采样空间的大小 采样空间的大小决定了算法结果的近似率（或者理解为：获得 好的近似结果的概率 ·算法得到最优解的概率可以用反复求解的次数增加而无限逼近 于1 ·拉斯维加斯算法：算法时间复杂度被设定为随机变量 ·算法一旦得解（解空间的某次采样），必定是最优解 ·算法失败的概率可以用反复求解（反复采样）的次数增加而无限 减小

随机的01串，如何影响着随机算法？ • 蒙特卡罗算法：算法结果被设定为随机变量 • 算法效率上的约束决定了采样空间的大小 • 采样空间的大小决定了算法结果的近似率（或者理解为：获得 好的近似结果的概率） • 算法得到最优解的概率可以用反复求解的次数增加而无限逼近 于1 • 拉斯维加斯算法：算法时间复杂度被设定为随机变量 • 算法一旦得解(解空间的某次采样)，必定是最优解 • 算法失败的概率可以用反复求解(反复采样)的次数增加而无限 减小

问题4：这是随机算法分析新指标？ For every randomized algorithm A we consider a new complexity measure- the number of random bits used.Let RandomA(x)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)x is an input of size n}. 随机算法A的computations的个数将会是2 RandomA(n)

问题4：这是随机算法分析新指标？ 随机算法A的computations的个数将会是