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

计算机问题求解一论题2-8 概率分析与随机算法 2022年04月13日

计算机问题求解 – 论题2-8 - 概率分析与随机算法 2022年04月13日

问题0： 说明什么是随机变量？解释 为什么它本质上是函数？ A random variable for an experiment with a sample space S is a function that assigns a number to each element/outcome of S. Discrete Continuous

A random variable for an experiment with a sample space S is a function that assigns a number to each element/outcome of S. Discrete Continuous

掷两颗骰子 ■其样本空间S(36个元素) 0,,., ■定义函数f:S→{2,3，.，12 口该函数又称：掷两颗骰子的和的随机变量 ▣骰子：此时该函数的值是7，我们可以认为“随机变量f=7” 口骰子：此时该函数的值是12，我们可以认为“随机变量f=12” 口随机变量f=7的概率是多少？等价于两个骰子掷出7点的概率 ■还可以： 口定义随机变量X:掷出豹子点

掷两颗骰子 ◼ 其样本空间 𝑆 36个元素 ❑ , , … , ◼ 定义函数𝑓：𝑆 → {2,3, …, 12} ❑ 该函数又称：掷两颗骰子的和的随机变量 ❑ 骰子: 此时该函数的值是7，我们可以认为“随机变量𝑓 = 7” ❑ 骰子: 此时该函数的值是12，我们可以认为“随机变量𝑓 = 12” ❑ 随机变量𝑓 = 7的概率是多少？等价于两个骰子掷出7点的概率 ◼ 还可以： ❑ 定义随机变量X：掷出豹子点

问题00： 什么是随机变量的期望值？ 如何理解“期望反映了随机变量的均值” 它与平均值有什么不同？ We define the expected value,or expectation,of a random variable X whose values are the set {x1,x2,...,xk}to be E(X)=xi P(X=xi). i=1

问题00： 什么是随机变量的期望值？ 如何理解“期望反映了随机变量的均值” 它与平均值有什么不同？

HIRE-ASSISTANT (n) 1 best =0 /candidate 0 is a least-qualified dummy candidate 2 fori =1ton 3 interview candidate i 4 if candidate i is better than candidate best 5 best i 6 hire candidate i

HIRE-ASSISTANT (n) 1 best =0 /candidate 0 is a least-qualified dummy candidate 2 for i 1 to n 3 interview candidate i 4 if candidate i is better than candidate best 5 best i 6 hire candidate i 问题1： 什么是”确定性”算法？ 这个算法是“确定”的吗？

RANDOMIZED-HIRE-ASSISTANT(n) randomly permute the list of candidates 2 best =0 /candidate 0 is a least-qualified dummy candidate 3 fori 1to n 4 interview candidate i 5 if candidate i is better than candidate best 6 best i 7 hire candidate i 问题2： 什么是随机算法？ 一这个算法是“随机”的吗？

HIRE-ASSISTANT(n) best 0 /candidate 0 is a least-qualified dummy candidate 2 for i 1ton 3 interview candidate i 4 if candidate i is better than candidate best 5 best i 6 hire candidate i 般情况下， 代价会如何？ 问题3： 这个确定算法有“随机”性吗？ 如果我们分析第六条语句的执行条数， 你能给出这个“随机”的概率模型吗？

一般情况下， 代价会如何？

什么是算法的Average-Case Analysis'? 算法的性能依赖于输入数据的随机性 口“好”数据、“差”数据、“不好不差”数据 ■3 完全可以围绕“算法的性能”定义输入数据集（样本空间)上的随机变量 ■算法的平均开销就是这个随机变量的“平均” 口这个随机变量的“期望” We focus on computing the running time of various algorithms. When the running time of an algorithm is different for different inputs of the same size,we can think of the running time of the algorithm as a random variable on the sample space of inputs,and thus,we can analyze the expected running time of the algorithm.This gives us an understanding different from studying just the worst-case running time for an input of a given size

什么是算法的Average-Case Analysis? ◼ 算法的性能依赖于输入数据的随机性 ❑ “好”数据、“差”数据、“不好不差”数据 ◼ 完全可以围绕“算法的性能”定义输入数据集（样本空间）上的随机变量 ◼ 算法的平均开销就是这个随机变量的“平均” ❑ 这个随机变量的“期望

The Difficulty of Average Case Analysis In order to perform a probabilistic analysis,we must use knowledge of,or make assumptions about,the distribution of the inputs Then we analyze our algorithm,computing an average-case running time,where we take the average over the distribution of the possible inputs.Thus we are,in effect,averaging the running time over all possible inputs.When reporting such a running time,we will refer to it as the average-case running time. 输入数据的分布特性失败，必假设定导致平均运行时间分析的失败

The Difficulty of Average Case Analysis 输入数据的分布特性失败，必假设定导致平均运行时间分析的失败