標題: 更新理論在隨機Tries 上的應用
An Introduction to Renewal Theory with Applications to Random Tries
作者: 高名世
Kao, Ming-Shih
符麥克
Fuchs, Michael
應用數學系所
關鍵字: 更新理論;Renewal Theory
公開日期: 2014
摘要: 在電腦科學中,trie 是相當重要的資料結構,由於它的特殊生成方式,
在生活中有很多很好的應用,像是搜索物件,輸入一個開頭來找出所有的
可能,而trie 的演算法很容易修改也是被廣泛應用的原因之一,其中2-
protected nodes 更是在近期很多人研究的重點。
在這篇論文裡,我們的主要目標是用機率中的更新理論來分析trie 的一
些性質,我們先證明更新理論的一些定理,並證明關鍵更新定理,接著我們
介紹一些Svante Jason 在他的paper 中提出的一些結果並補足證明,最後我
們利用更新理論算出2-protected nodes 和3-protected nodes 在trie 中的期
望值。
接著我們介紹一下整篇論文的架構。
第一章我們先從電腦科學中的樹開始介紹,介紹樹的定義,樹中一些有
用到的名詞和各種樹的畫法與優缺點,最後介紹的trie 與patricia trie 的生
成方式和比較,並提出了接下來要研究的方向。
第二章我們討論要用到的研究工具-更新理論,從更新過程開始,中間
證明了一些接下來要使用的定理,最後證明了基本更新定理和關鍵更新定
理,並區分了算術型與d
The trie is a data structure of fundamental importance in Computer Science.
This is reflected by the fact that tries have found numerous applications, such
as in searching, sorting, contention tree algorithms, retrieving IP addresses
and satellite data, internet routing, etc.
In this master’s thesis, our primary target is to analyze some properties
of tries using renewal theory. First, we will give a brief, self-contained introduction
into renewal theory. Then, we will introduce some results of a recent
paper of S. Jason in which the application of renewal theory to the analysis of
tries was pioneered. Finally, we will add some new results.
The following is an outline of the structure of the thesis.
In Chapter 1, we will give some basics from Computer Science. More precisely,
we will give the definitions of some data structures (including tries) and
discuss their advantages and disadvantages. Moreover, the aim of this thesis
will be stated in Chapter 1.
In Chapter 2, we give a detailed review of renewal theory. The main focus
in this chapter will be on limit laws and we will discuss both the elementary
and the key renewal theorem in details. In particular, the latter will turn out
to be of key importance for the analysis of trie parameters. At the end of the
chapter, we will also briefly discuss results for the delayed renewal process.
In Chapter 3, the renewal theory from Chapter 2 will be applied to tries.First we will introduce some results from a recent paper of S. Jason and prove
them. Next, we will propose other interesting results which can also be handled
by S. Janson’s tools.
In Chapter 4, we use the method from Chapter 3 to calculate the asymptotic
mean of 2-protected and 3-protected nodes in tries. These kind of nodes have been recently introduced and have already been studied in many papers.
Parts of the extensive computations in this chapter will be done with the help
of Maple.
Finally, in Chapter 5, we give a conclusion to the thesis.
3
URI: http://140.113.39.130/cdrfb3/record/nctu/#GT070052211
http://hdl.handle.net/11536/76261
顯示於類別:畢業論文


文件中的檔案:

  1. 221101.pdf

若為 zip 檔案,請下載檔案解壓縮後,用瀏覽器開啟資料夾中的 index.html 瀏覽全文。