计算机问题求解一论题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的个数将会是