概率论W9:随机算法

在某些程序的结果中,可以接受一定的不确定性:

如:

1. 加密算法Cryptography

允许程序的结果是由抛硬币来决定的.

在牺牲一定准确度的情况下去获取更好的性能.

分类

蒙特卡洛算法

对于每个输入都有可能获得一个错掉的结果,但是最坏的运算时间是有规范的.

拉斯维加斯算法

每个输出必然是正确的.

运行时间由一定概率超过特定值,但整体运行时间的期望较好.

随机算法举例

1. 随机化快排(蒙特卡洛算法)
2. MaxCut Problem

MaxCut Problem

蒙特卡洛算法

快排

拉斯维加斯算法

Bell lab

Data Stream

描述

数据库与数据流:数据库 相对静态的数据.

数据库与当前应用场景的不同:

数据是快速到达的,当数据来的快并且规模大到磁盘存储能力之外;

但我对数据的查询是固定的.

如何做到数据不存,而是看到数据,如果是我正好需要的数据时,即可使用?

数据流场景如下

1. 数据到达快

2. 数据规模大

3. 数据来不及存

分析任务不变;

具体举例

通信领域的流量监控.

监控的目的:

1. 垃圾流量检测

2. 机器是否受到攻击.

   流量分布标准

3. 调配流量游走方式

数据流的处理要求:

1. 数据只能被查看一遍
2. 存储(main memory)必须是有bound的.里面放的只是一个概要的压缩的数据结构.synopsis data structure;

对于这样分析的算法却不一定需要最准确的结果,但是我要求的结果要deterministic bounds.或是概率有限.

算法的效率是要变高的.

处理过程

取样

• 对数据的随机取样,a small random sample S of the data often well- represents all the data.

此时

赏

谢谢你请我吃糖果❤️

支付宝