學術產出-國科會研究計畫
| 題名 | 隨機數位樹之高度及相關參數 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 |
| 上傳時間 | 16-四月-2025 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 |
| dc.contributor | 應數系 | |
| dc.creator (作者) | 符麥克 | |
| dc.date (日期) | 2022-12 | |
| dc.date.accessioned | 16-四月-2025 14:28:11 (UTC+8) | - |
| dc.date.available | 16-四月-2025 14:28:11 (UTC+8) | - |
| dc.date.issued (上傳時間) | 16-四月-2025 14:28:11 (UTC+8) | - |
| dc.identifier.uri (URI) | https://nccur.lib.nccu.edu.tw/handle/140.119/156608 | - |
| dc.description.abstract (摘要) | 在樹狀的資料結構的效能評估(performance measures)中，高度(height)是被廣泛地研究的對象之一。而在隨機數位樹(random digital trees) 的情況下，高度是第一個被研究的參數。然而，一直到最近，只有隨機樹 (random trees) 的高度被全面性的了解。對稱隨機數位搜尋樹 (symmetric random digital search trees) 的情況，其高度方面的猜想在80年代晚期被提出，並於最近由Drmota, Fuchs, Hwang和Neininger證明。至於非對稱數位搜尋樹(asymetric digital search trees) 以及對稱、非對稱PATRICIA tries高度的極限行為的相關了解較少(而後者有存在已久的猜想)。本計畫為期兩年，主要研究目的在於完成未被證明的猜想並研究相關參數及資料結構。 | |
| dc.description.abstract (摘要) | 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. | |
| dc.format.extent | 116 bytes | - |
| dc.format.mimetype | text/html | - |
| dc.relation (關聯) | 科技部, MOST109-2115-M004-003-MY2, 109.08-111.07 | |
| dc.subject (關鍵詞) | 離散機率論; 解析組合數; 資料結構; 位搜尋樹; 字典樹(trie); PATRICIA trie; 高度; 集中性 (concentration); node profile; 平均數; 變異數; 極限法則 | |
| dc.subject (關鍵詞) | Discrete probability theory; analytic combinatorics; data structures; digital search tree; trie; PATRICIA trie; height; concentration; node profile; mean; variance; limit laws | |
| dc.title (題名) | 隨機數位樹之高度及相關參數 | |
| dc.title (題名) | Height and Related Parameters of Random Digital Trees | |
| dc.type (資料類型) | report |