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

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

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

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

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

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

掷两颗骰子 ◼ 其样本空间S：36，,,…, ◼ 定义函数f：S->{2,3,…,12} ❑ 该函数又称：掷两颗骰子的和的随机变量 ❑ 骰子: 此时该函数的值是7，我们可以认为“随机变量f=7” ❑ 骰子: 此时该函数的值是12，我们可以认为“随机变量f=12” ❑ 随机变量f=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

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 1to 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 for i 1ton 4 interview candidate i 5 if candidate i is better than candidate best 6 best i 7 hire candidate i 问题2： 什么是随机算法？ 这个算法是“随机”的吗？

HIRE-ASSISTANT(n) 1 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? ·算法的性能依赖于输入数据的随机性 口“好”数据、“差”数据、“不好不差”数据 ·完全可以围绕“算法的性能”定义输入数据集（样本空间）上的随机变量 ■算法的平均开销就是这个随机变量的“平均” 口这个随机变量的“期望” 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 difficult of Average case Analysis of an Algorithm 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 difficult of Average case Analysis of an Algorithm 输入数据的分布特性假设失败，必定导致平均运行时间分析的失败