2022年山东大学软件学院研究生随机算法

2022年山东大学软件学院研究生随机算法 本资源主要讲解了随机算法中的重要概念和技术，涵盖了随机算法的基础知识、随机算法的设计和分析、NP 完全性问题、Monte Carlo 算法和 Las Vegas 算法、延迟决策原理、马尔科夫不等式、条件期望方法、奖券收集问题和最大割问题等。 随机算法基础知识 在随机算法中，N(x)=0 和 N(x)=1 分别表示图灵机 N 在输入 x 下的输出结果。P 代表可以在多项式时间内解决的问题集合，而 NP 代表可以在多项式时间内验证的问题集合。由于 P ⊆ NP，因此可以得出任何可以在多项式时间内解决的问题都可以在多项式时间内验证。 NP 完全性问题 顶点覆盖问题是一个 NP 完全性问题，集合覆盖问题也可以被证明为 NP 完全性问题。集合覆盖问题可以被描述为：给定一个集合 U = {e1, e2, …, em} 和一个集合 S={S1, S2, …, Sn}，其中每个 Sk 是 U 的子集，询问是否有≤k 的诸 Sk，他们的并能覆盖 U。 Monte Carlo 算法和 Las Vegas 算法 Monte Carlo 算法是一种随机算法，用于解决概率问题。Las Vegas 算法是一种随机算法，用于解决确定性问题。二分图完美匹配是一个 Las Vegas 算法，随机的快速排序是一个 Monte Carlo 算法。 延迟决策原理 延迟决策原理是一种随机算法设计技术，用于解决NP 完全性问题。该原理可以将问题分解为多个子问题，然后使用随机算法解决每个子问题。 马尔科夫不等式 马尔科夫不等式是一种概率不等式，用于描述随机事件的概率。该不等式可以用来证明随机算法的正确性。 条件期望方法 条件期望方法是一种随机算法设计技术，用于解决最大化或最小化问题。该方法可以用来解决 CNF 问题，例如φ = (¬x1∨x2∨x3) ∧ (x1∨¬x3) ∧ (x2∨x3) ∧ (¬x1∨¬x2∨¬x3)，可以使用条件期望方法来求出一个真值指派，使得总权重最大。 奖券收集问题 奖券收集问题是一个概率问题，用于描述随机事件的概率。可以使用马尔科夫不等式来计算 X>2nHn 的概率，使结果尽可能精确。 最大割问题 最大割问题是一个 NP 完全性问题，用于描述图的割开问题。可以使用随机算法来解决最大割问题，例如设置顶点集 A、B，初始为空集，然后对于一个顶点，独立地以 1/2 的概率放入到集合 A，以 1/2 的概率放入到集合 B，最后返回 A 和 B。可以证明此方法割开的边数至少是最优解的一半那么多。