Probability and Combinatorial Structures

- 建议编号：DMS 9803780 PI： 詹姆斯艾伦填充机构： 约翰霍普金斯大学 项目名称： 概率与组合结构 摘要： 本研究的主题是研究某些 重要的组合结构使用概率的方法。 其中一类重要的结构是自组织数据结构，它以易于检索的顺序动态地维护记录文件，同时占用很少的内存空间，并且已经被概率学家和计算机科学家研究了超过25年。 这种自组织系统已被应用于超大规模集成电路（VLSI）模拟，数据压缩，通信网络和遗传学的问题。 该研究分析了比迄今为止所处理的更现实的复杂概率模型，并为以前的研究提供了一个统一的框架。 树形成另一类重要的组合结构。 研究人员分析了随机m元搜索树的“形状”，这是计算机科学中的基本结构，也是与自组织数据结构有关的自然结构。 这项工作涉及对已经很大的递归树类进行归纳和分析，递归树已被用于对流行病的传播、古代手稿的家谱和金字塔计划等进行建模。 研究人员还开发了一种 连续时间模型的金字塔计划，并推导出它的操作特性，还没有得到相应的离散时间模型。 这项工作的另一个方面是不完整的数字搜索树（Trie）的高度分析的推广;推广应用于计算机网络中多个领导者的选举。 这项工作显然与高性能计算和通信的联邦战略领域有关。

----------------------------------------------------------------------- Proposal Number: DMS 9803780 PI: James Allen Fill Institution: The Johns Hopkins University Project: Probability and Combinatorial Structures Abstract: The theme of the this research is the study of certain important combinatorial structures using probabilistic methods. One important class of structures is that of self-organizing data structures, which dynamically maintain a file of records in easily retrievable order while using up little memory space and which have been investigated by probabilists and computer scientists for more than 25 years. Such self-organizing systems have been applied to problems in very large-scale integration (VLSI) circuit simulation, data compression, communications networks, and genetics. The research analyzes more realistically complex probability models than have heretofore been treated, and in doing so provides a unifying framework for previous studies. Trees form another important class of combinatorial structures. The investigator analyzes the "shape" of random m-ary search trees, fundamental structures in computer science that also arise naturally in connection with self-organizing data structures. The work involves generalizing and analyzing the already large class of recursive trees, which have been used to model such things as the spread of epidemics, family trees of ancient manuscripts, and pyramid schemes. The researcher also develops a continuous-time model for pyramid schemes and derives for it operational characteristics which have not been obtained under the corresponding discrete-time model. Another facet of this work is a generalization of the analysis of the height of an incomplete digital search tree, or trie; the generalization has applications to the election of multiple leaders in a computer network. This work relates clearly to the Federal Strategic Area of high-performance computing and communi cation.