随机算法.ppt

随机算法简介计算机理论实验室蒋威2009-12-24Email: Iamjw.******@?研究领域?随机数理论?随机算法概述?简单应用?POJ例题分析2概要?研究领域?随机数理论?随机算法概述?简单应用?POJ例题分析3研究领域?概率论?基本工具?数论?密码学?NP理论?近似算法(随机)?人工智能?遗传算法、模拟褪火?。。。4概要?研究领域?随机数理论?随机算法概述?简单应用?POJ例题分析5随机数理论?随机序列的特征?概率相等(均匀随机)?不可预测?不可重现?“伪随机”(pseudo-random)?根据某种规则生成,这些随机数不是真正随机的,但在一定程度上可以模拟随机数,一般叫做伪随机数。?对于一个随机算法,使用真随机数和伪随机数,得到的结果近似相等。(Andrew Yao)Google “什么是随机数”后…6随机数的产生?“真随机数”的产生?电子噪声?噪音放大(AD转化)?量子噪声?“测不准原理”?放射性衰变?核放射源放射粒子数?。。。电子噪声量子噪声7随机数的产生?“伪随机数”的产生?“Any one who considers arithmetical methods of producing random digits is, of course, in a state of sin.” --- John von neumann?常用算法?线性同余,延搁的斐波那契算法,逆同余算法,KISS…?密码学相关?BBS,Micali-Schnorr,Rabin,…?。。。线性同余法8随机数的检验?“伪随机数”的检验?拟合优度检验(统计)?χ2检验,KS检验?经验检验?检验集:Knuth,Diehard,NIST?谱检验?。。。谱检验9概要?研究领域?随机数理论?随机算法概述?简单应用?POJ例题分析10