政大機構典藏-National Chengchi University Institutional Repository(NCCUR):Item 140.119/156608
English  |  正體中文  |  简体中文  |  Post-Print筆數 : 27 |  全文笔数/总笔数 : 115416/146442 (79%)
造访人次 : 55269497      在线人数 : 21
RC Version 6.0 © Powered By DSPACE, MIT. Enhanced by NTU Library IR team.
搜寻范围 查询小技巧：
  • 您可在西文检索词汇前后加上"双引号"，以获取较精准的检索结果
  • 若欲以作者姓名搜寻，建议至进阶搜寻限定作者字段，可获得较完整数据
    •  进阶搜寻


    请使用永久网址来引用或连结此文件: https://nccur.lib.nccu.edu.tw/handle/140.119/156608


    题名: 隨機數位樹之高度及相關參數
    Height and Related Parameters of Random Digital Trees
    作者: 符麥克
    贡献者: 應數系
    关键词: 離散機率論;解析組合數;資料結構;位搜尋樹;字典樹(trie);PATRICIA trie;高度;集中性 (concentration);node profile;平均數;變異數;極限法則
    Discrete probability theory;analytic combinatorics;data structures;digital search tree;trie;PATRICIA trie;height;concentration;node profile;mean;variance;limit laws
    日期: 2022-12
    上传时间: 2025-04-16 14:28:11 (UTC+8)
    摘要: 在樹狀的資料結構的效能評估(performance measures)中，高度(height)是被廣泛地研究的對象之一。而在隨機數位樹(random digital trees) 的情況下，高度是第一個被研究的參數。然而，一直到最近，只有隨機樹 (random trees) 的高度被全面性的了解。對稱隨機數位搜尋樹 (symmetric random digital search trees) 的情況，其高度方面的猜想在80年代晚期被提出，並於最近由Drmota, Fuchs, Hwang和Neininger證明。至於非對稱數位搜尋樹(asymetric digital search trees) 以及對稱、非對稱PATRICIA tries高度的極限行為的相關了解較少(而後者有存在已久的猜想)。本計畫為期兩年，主要研究目的在於完成未被證明的猜想並研究相關參數及資料結構。
    The height is one of the most widely studied performance measures of tree-based data structures. For random digital trees, it was one of the first parameter studied. Nevertheless, until very recently, only the height of random tries was fully understood. For symmetric random digital search trees, there existed a conjecture about the limiting behavior of the height which was raised in the late 80s and recently proved in a paper of Drmota, Fuchs, Hwang and Neininger. Still little isknown about the limiting behavior of the height of asymmetric digital search trees and symmetric and asymmetric PATRICIA tries (again there is a long-standing conjecture for the latter). The main purpose of this two-year project is the fill all remaining gaps and to investigate also related quantities and data structures.
    關聯: 科技部, MOST109-2115-M004-003-MY2, 109.08-111.07
    数据类型: report
    显示于类别:[應用數學系] 國科會研究計畫

    文件中的档案:

    档案 描述 大小格式浏览次数
    index.html0KbHTML14检视/开启


    在政大典藏中所有的数据项都受到原著作权保护.


    社群 sharing

    著作權政策宣告 Copyright Announcement
    1.本網站之數位內容為國立政治大學所收錄之機構典藏，無償提供學術研究與公眾教育等公益性使用，惟仍請適度，合理使用本網站之內容，以尊重著作權人之權益。商業上之利用，則請先取得著作權人之授權。
    The digital content of this website is part of National Chengchi University Institutional Repository. It provides free access to academic research and public education for non-commercial use. Please utilize it in a proper and reasonable manner and respect the rights of copyright owners. For commercial use, please obtain authorization from the copyright owner in advance.

    2.本網站之製作，已盡力防止侵害著作權人之權益，如仍發現本網站之數位內容有侵害著作權人權益情事者，請權利人通知本網站維護人員(nccur@nccu.edu.tw)，維護人員將立即採取移除該數位著作等補救措施。
    NCCU Institutional Repository is made to protect the interests of copyright owners. If you believe that any material on the website infringes copyright, please contact our staff(nccur@nccu.edu.tw). We will remove the work from the repository and investigate your claim.
    DSpace Software Copyright © 2002-2004  MIT &  Hewlett-Packard  /   Enhanced by   NTU Library IR team Copyright ©   - 回馈