关于截尾几何分布的随机变量的组合数的研究

摘要

计算机科学的日益发展,不断要求着数据结构和算法的优化与创新,Skip Lists作为一种新的数据结构,在1989年被Pugh提出以后,以其简单而迅速的运行特点,受到了普遍的欢迎.而Skip Lists的搜索花费等问题又与随机变量序列的左至右最大值、最小值以及右至左最大值、最小值的组合数问题存在着密切的关系.十多年来,Helmut Prodinger、Wilf等人先后致力于这方面的研究,并取得了很多成果.该文根据Pugh关于Skip Lists的原始思想,修正了Prodinger关于Skip Lists的概率模型,并在修正后的Skip Lists的概率模型中研究了服从截尾几何分布的随机变量的一类组合问题:强、弱状态下左至右最大值、最小值个数的均值与方差.另外,该文还研究了奇数型Stirling数,得到了奇数型Stirling数的几个性质,并相应地得到组合数欧拉数的一个性质.

目录

文摘

英文文摘

声明

第一章绪论

1.1Skip Lists与其他几种数据结构

1.2Skip Lists对元素的存放方式

1.3Skip Lists的搜索方法

1.4Skip Lists与随机变量序列的联系

1.5左至右最大值、最小值的实际背景及研究意义

1.6Stirling数的研究背景和意义

1.7本文的主要工作

第二章一些有关左至右最大值、最小值的已有结果

第三章修正Skip Lists的概率模型

第四章服从截尾几何分布的随机变量的组合数：左至右最大值、最小值

4.1修正的概率模型下左至右最大值个数的均值与方差

4.1.1强状态下左至右最大值个数的均值与方差

4.1.2弱状态下左至右最大值个数的均值与方差

4.2修正的概率模型下左至右最小值个数的均值与方差

4.2.1强状态下左至右最小值个数的均值与方差

4.2.2弱状态下左至右最小值个数的均值与方差

第五章奇数型Stirling数

第六章总结

参考文献

致谢