2013集训队论文答辩(胡渊明)演示文稿

《2013集训队论文答辩(胡渊明)演示文稿》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、信息学竞赛中概率论的基础与应用江苏省扬州中学胡渊鸣引言为什么要讲概率论?近年来竞赛中概率问题大量涌现问题的解法需要理论支撑知其然,更要知其所以然概率空间的定义概率到底是什么?概率空间的三个要素样本空间事件所有事件的集合概率测度概率公理不是每个实值函数都是概率测度一个合理的概率测度,应该满足如下条件:非负性规范性可加性随机变量名字带来的误解不是随机性来源不是变量样本空间上的(实值)函数随机变量如为快速排序的每次执行情况之集,可定义为某次算法的执行时间.随机变量的期望一个重要属性期望是随机变量的属性表示平均情况下随机变量的输出.继上例,表示快速排序的平均执行时间.期望的性

2、质解题的基础线性性质(可加性)独立的随机变量期望可相乘应用:MazeAdaptedFormCF123E从树的根节点S出发,到叶子节点T点停止,求DFS算法期望要求多少步.每次DFS将从这个点出发未到达过的点random_shuffle以后按这个随机顺序往下试探.注意,DFS时返回(弹栈)的过程也算一步.题目本身不难,但是需要按部就班说清楚才能让解法使人信服.样本空间是什么?所有从到的可能的DFS路径.概率分布?表示走出路径的概率.对于任意的事件,随机变量?表示路径的走过的路程.要求什么?,即走过路程的期望.应用:MazeAdaptedFormCF123E路径数目巨大,

3、无法一一枚举.利用期望的线性性质按边分解.设随机变量表示路径经过边的次数.只需求出即可应用:MazeAdaptedFormCF123E现在问题变成,如何求所有必经路径(黄色)上的边,必然仅走1次应用:MazeAdaptedFormCF123ESTuv为根的子树w对于不在必经路径上的边,假设:距离必经路径上最近的点为u其所在子树以u的儿子v为根T所在子树以u的儿子w为根考虑DFS到达u时先进入w,则e走了0次先进入v,则e走了2次两种情况概率分别是期望走的次数为1次.应用:MazeAdaptedFormCF123ESTuv为根的子树w神奇的结论:每条边期望走的次数都是一

4、次,于是期望步数是.这种DFS期望时间仅和树的点数有关,与形态无关.应用:MazeAdaptedFormCF123E两个不等式对极端情况的估计Markov不等式对于非负随机变量,任意正实数,有Chebyshev不等式对于任意随机变量有应用:最小圆覆盖算法的分析众所周知的线性算法,会不会超时呢?利用Markov不等式来看看对于仅是最乐观的估计,已经相当小小于每个人死于交通事故的概率ThankYouforListening!时间紧迫,更多内容请见我的论文欢迎提问!