Full metadata record
DC FieldValueLanguage
dc.contributor.author余冠儒en_US
dc.contributor.authorGuan-Ru Yuen_US
dc.contributor.author符麥克en_US
dc.contributor.authorMichael Fuchsen_US
dc.date.accessioned2014-12-12T02:40:59Z-
dc.date.available2014-12-12T02:40:59Z-
dc.date.issued2013en_US
dc.identifier.urihttp://140.113.39.130/cdrfb3/record/nctu/#GT070152224en_US
dc.identifier.urihttp://hdl.handle.net/11536/74595-
dc.description.abstract  數位樹在電腦科學中的資料結構扮演極其重要的角色,而所謂的二階保護點在近期則受到相當大的矚目。舉例來說,J. Gaither、Y. Homma、M. Sellke以及M. D. Ward曾探討隨機的字典樹之二階保護點的數量進而求出它的期望值之漸近展開式。不但如此,J. Gaither與M. D. Ward更進一步求出它的變異數之漸近展開式,並猜測它數量的分布會滿足中央極限定理。   在這篇論文中,我們的主要目標是用M. Fuchs、黃顯貴和V. Zacharovas三人所提出來一個有系統的方法來重新驗證(也可說是糾正)他們的結果。經過運算,即便我們得到一個與他們截然不同的展開式,但我們的在數值上與他們的結果卻是完全相同的。不但如此,我們更是證實了他們猜想的中央極限定理。事實上,我們證明了一個更一般化的結果就是字典樹之內點與二階保護點的二元中央極限定理。根據這個結果我們不但是證明了J. Gaither與M. D. Ward的猜想,更是直接得知基數樹也會滿足中央極限定理。最後,我們還算出基數樹之二階保護點數量的期望值及變異數之漸近展開式。zh_TW
dc.description.abstractDigital trees are data structures which are of fundamental importance in Computer Science. Recently, so-called 2-protected nodes have attracted a lot of attention. For instance, J. Gaither, Y. Homma, M. Sellke, and M. D. Ward derived an asymptotic expansion for the mean of the number of 2-protected nodes in random tries. Moreover, J. Gaither and M. D. Ward found an asymptotic expansion of the variance and conjectured a central limit theorem. In this thesis, our main goal is to re-derive (and correct) their results by using a systematic method due to M. Fuchs, H.-K. Hwang, and V. Zacharovas. The resulting expressions we obtain are quite different from the paper from J. Gaither, Y. Homma, M. Sellke, and M. D. Ward, but numerically they of course coincide. Moreover, we prove the conjectured central limit theorem from J. Gaither and M. D. Ward. In fact, we prove even a more general result, namely, a bivariate central limit theorem for the number of internal nodes and the number of 2-protected nodes in random tries. From this, not only the conjecture from J. Gaither and M. D. Ward follows but we also obtain a central limit theorem for PATRICIA tries. Finally, we also derive asymptotic expansions of mean and variance for PATRICIA tries.en_US
dc.language.isoen_USen_US
dc.subject二階保護點zh_TW
dc.subject數位樹zh_TW
dc.subjectzh_TW
dc.subject中央極限定理zh_TW
dc.subject2-protected nodesen_US
dc.subjectdigital treesen_US
dc.subjectmomentsen_US
dc.subjectcentral limit theoremen_US
dc.title字典樹與基數樹之二階保護點的數量zh_TW
dc.titleThe Number of 2-Protected Nodes in Tries and PATRICIA Triesen_US
dc.typeThesisen_US
dc.contributor.department應用數學系所zh_TW
Appears in Collections:Thesis


Files in This Item:

  1. 222401.pdf

If it is a zip file, please download the file and unzip it, then open index.html in a browser to view the full text content.