- 无标题文档
查看论文信息

中文题名:

 一类随机树的高度和宽度估计    

姓名:

 王钰乔    

保密级别:

 公开    

论文语种:

 中文    

学科代码:

 070101    

学科专业:

 数学与应用数学    

学生类型:

 学士    

学位:

 理学学士    

学位年度:

 2020    

学校:

 北京师范大学    

校区:

 北京校区培养    

学院:

 数学科学学院    

第一导师姓名:

 何辉    

第一导师单位:

 北京师范大学数学科学学院    

提交日期:

 2020-04-21    

答辩日期:

 2020-05-08    

中文关键词:

  ; 随机树 ; 排队序列 ; 广度优先搜索 ; 字典深度优先搜索 ; 逆向字典深度优先搜索    

中文摘要:
   

     本论文主要包含两个部分。
     
在第一个部分,通过阐述随机树的理论应用和实践应用,揭示关于随机树高度和宽度的估计在提升运行效率、优化算法、强化实践使用等多方面的重要意义。 在第二个部分,通过考虑深度遍历、广度遍历及排队过程的鞅,最终得出对于一类随机变量的宽度和高度的估计方法。
     
确定一个由n- 1个非负整数构成的序列C =C1,...,Cn)。对于一个有根树T,当它能够将节点排列为v1,...vn,并且对于每一个1 i nvi都正好存在ci个子数时,我们称其拥有子序列C
     
T是一个从所有拥有子序列??的平面树中均匀随机选出的一个平面树。本文将研究对T的宽度和高度估计。该类估计是当C满足∑i=1n ????2 = ??(??)时的最优解。对于高度的估计可被视作为这个子序列的“有限方差”条件。从这个思路着手,在已有理论的基础上,进一步探讨对随机树T的高度和宽度估计,并最终对估计进行了证明。

外文摘要:
   

 This paper mainly includes two parts.
    In the first part, by explaining the theoretical and practical applications of random trees, the importance of estimating the height and width of random trees in improving operating efficiency, optimizing algorithms, and strengthening practical use is revealed.
    In the second part, by considering the depth traversal, breadth traversal, and martingale in the queuing process, the method of estimating the width and height of a class of random variables is finally obtained.
    Fix a sequence ?? =
 ??1,...,????) composed of ?? ? 1 non-negative integers. For a rooted tree ??, when it can order the nodes as ??1,...,????, and for each 1 ?? ??, ???? has exactly ???? children, we call it a subsequence ??.
    Let ?? be a plane tree uniformly and randomly selected from all plane trees with subsequence ??. This article will study the estimation of the width and height of ?? . These estimation is the optimal solution when ??  satisfies ∑i=1n ????2 = ??(??).The estimation of height can be regarded as the "finite variance" condition of this subsequence. Starting from this idea, based on existing theories, the estimation of the height and width of the random tree ?? will be discussed and finally proved.

参考文献总数:

 22    

馆藏号:

 本070101/20051    

开放日期:

 2021-06-07    

无标题文档

   建议浏览器: 谷歌 360请用极速模式,双核浏览器请用极速模式