• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文学位 >Enumeration of general t-ary trees and universal types.
【24h】

Enumeration of general t-ary trees and universal types.

机译：通用三叉树和通用类型的枚举。

获取原文
获取原文并翻译 | 示例
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

Trees are the most important and fundamental data structure used in computer science. The number of t-ary trees with n nodes is known as the generalized Catalan number. Various questions about the statistics of binary trees were investigated in the past, such as height and path length distributions for a randomly selected tree. Seroussi first posed a problem motivated by information theory in the study of universal types of sequences: what is the number of trees of a given path length (the path length is the sum of the depths)? Two sequences of the same length p are said to be of the same universal type if and only if they produce the same set of phrases in the incremental parsing of the Lempel-Ziv'78 scheme, which is a commonly used data compression scheme. Seroussi observed that the number of possible parsings of sequences of length p corresponds to the cardinality of Tp which is defined as the collection of t-ary trees that have path length p. Knessl and Szpankowski studied the enumeration of binary trees (t = 2) and universal types. Seroussi first conjectured and later proved that for t-ary trees, as p → infinity, Tp =expht-1 tlntplnp 1+s1 where h(x) = - x ln x - (1- x) ln (1 - x).;In this dissertation, we denote the number of t-ary trees with n nodes and path length p by g(n, p). We shall study the limit n → infinity and various ranges of p such as p = ( n2 ) - O(1), p = O( n2), p = O( n3/2), p = O( n4/3) and p = n logt n + O( n). Our goal is to obtain a thorough understanding of the double sequence g(n, p) when n and p are large. The distribution of the trees by path length alone, or number of nodes alone, will follow as special cases. We derive various limiting distributions for the number of nodes when a tree is selected randomly from Tp . As a special case we compute the o(1) error term in Seroussi's formula, which involves the Airy function. We use methods of analytic algorithmics such as generating functions, recurrence relations and complex asymptotics. We also use methods of applied mathematics such as the WKB method and asymptotic matching.
机译：树是计算机科学中使用的最重要和最基本的数据结构。具有n个节点的三进制树的数量称为广义加泰罗尼亚数。过去，已经研究了有关二叉树统计信息的各种问题，例如随机选择的树的高度和路径长度分布。 Seroussi首先在研究通用序列类型时提出了一个信息理论所激发的问题：给定路径长度（路径长度是深度的总和）的树数是多少？当且仅当长度相同的两个序列在​​Lempel-Ziv'78方案（通常是数据压缩方案）的增量解析中产生相同的短语集合时，才被称为相同的通用类型。 Seroussi观察到长度为p的序列的可能解析次数对应于Tp的基数，Tp的基数定义为具有路径长度p的三叉树的集合。 Knessl和Szpankowski研究了二叉树（t = 2）和通用类型的枚举。 Seroussi首先推测，后来证明对于三叉树，当p→无穷大时，Tp = expht-1 tlntplnp 1 + s1其中h（x）=-x ln x-（1- x）ln（1- x）。 ；在本文中，我们用g（n，p）表示具有n个节点且路径长度为p的三叉树的数量。我们将研究极限n→无穷大以及p的各种范围，例如p =（n2）-O（1），p = O（n2），p = O（n3 / 2），p = O（n4 / 3）并且p = n logt n + O（n）。我们的目标是在n和p大时获得对双序列g（n，p）的透彻理解。在特殊情况下，将仅按照路径长度或仅通过节点数来分配树。当从Tp中随机选择树时，我们得出节点数量的各种限制分布。作为一种特殊情况，我们在Seroussi公式中计算o（1）误差项，其中涉及Airy函数。我们使用分析算法的方法，例如生成函数，递归关系和复杂渐近线。我们还使用诸如WKB方法和渐近匹配之类的应用数学方法。

著录项

  • 作者

    Zhang, Zhilong.;

  • 作者单位

    University of Illinois at Chicago.;

  • 授予单位 University of Illinois at Chicago.;
  • 学科 Mathematics.;Computer Science.
  • 学位 Ph.D.
  • 年度 2010
  • 页码 143 p.
  • 总页数 143
  • 原文格式 PDF
  • 正文语种 eng
  • 中图分类 遥感技术;
  • 关键词

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱：kefu@zhangqiaokeyan.com

京公网安备：11010802029741号 ICP备案号：京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有

  • 客服微信

  • 服务号