跳到主要內容

臺灣博碩士論文加值系統

(44.200.86.95) 您好!臺灣時間:2024/05/25 15:28
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果 :::

詳目顯示

: 
twitterline
研究生:郭彥廷
研究生(外文):Kuo, Yen-Ting
論文名稱:分解隨機Cayley樹所需複雜度的極限分布
論文名稱(外文):Limit Theorems for the Cost of Splitting Random Cayley Trees
指導教授:符麥克
指導教授(外文):Michael Fuchs
學位類別:碩士
校院名稱:國立交通大學
系所名稱:應用數學系所
學門:數學及統計學門
學類:數學學類
論文種類:學術論文
論文出版年:2012
畢業學年度:100
語文別:英文
論文頁數:53
中文關鍵詞:生成函數極限分布奇異點分析樹遞迴
外文關鍵詞:generating functionslimiting distributionssingularity analysistree recurrencesCayley trees
相關次數:
  • 被引用被引用:0
  • 點閱點閱:111
  • 評分評分:
  • 下載下載:4
  • 收藏至我的研究室書目清單書目收藏:0
在計算科學中,常常需要處理將集合合併的問題,而為了有效率的解決這個問題,需要建造適當的的資料結構和相對應的演算法,這類的問題又稱為"Union-Find problem"﹔事實上,已經有許多種不同的資料結構和相對應的演算法被提出來以解決這個問題,為了了解各個方法的優劣,我們考慮最簡單的狀況,也就是將n 個不同的元素兩兩合併,直到成為一個集合為止所需的複雜度。在這篇論文中,我們假設每個合併過程所需的複雜度是被合併的兩個集合的大小之和的冪次方,求其在隨機生成樹的機率模型底下,所需總複雜度的極限分布。
在這裡,我們使用一個近幾年才發展出來的新工具,稱為奇異點分析(Singularity
Analysis)﹔這個工具可以讓我們直接由生成函數的漸進展開式得到生成函數係數的漸進式。我們將使用這個方法來計算總複雜度的各階動差,進而再利用動差法推導出總複雜度的極限分布。
這篇論文的一開始,也就是第一章我們先介紹問題的背景並給出我們研究的結果﹔在第二章我們介紹我們研究所使用的工具,也就是奇異點分析﹔而第三章是這篇這篇論文最主要的部分,我們利用奇異點分析導出複雜度的期望值和各階動差並在第四章利用動差法證明了我們的結果﹔最後在第五章我們對整篇論文做一個總結。
In computer science, the so-called "Union-Find problem" is concerned with establishing a data structure for maintaining a collection of disjoint sets such that the process of merging sets can be carried out efficiently. Indeed, several data structures and corresponding
algorithms for merging sets have been proposed. For the purpose of comparing the complexity of these algorithms, it is naturally to consider the total cost incurred from merging n singleton sets into one set. In this thesis, we assume that the cost of each merging step is the power of the sum of the sizes of the sets being merged and
then derive the expected value and the limiting distribution of the total cost under the random spanning tree model.
The main tool used in this thesis is singularity analysis, which is a method connecting the asymptotics of generating functions with the asymptotics of their coefficients. We will use it to derive the moments of each order. Then, with the method of moments, the limiting distribution of the total cost will follow.
In the first part of this thesis (Chapter 1), we introduce the problem of interest and state the results of our work. In Chapter 2, we give an introduction about our main tool, singularity analysis. The central part of this thesis, namely Chapter 3, is devoted
to the derivation of the expected value and higher moments. These results will will
then be used in Chapter 4 for prove our main result. Finally, we end the thesis with a
conclusion in Chapter 5.
Contents
1 Introduction 1
2 Tools 6
2.1 Singularity Analysis . . . . . . . . . . . . . . . . . . . . . . 6
2.1.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 6
2.1.2 Fundamentals of singularity analysis . . . . . . . . . . . . . 8
2.1.3 Differentiation and integration . . . . . . . . . . . . . . . 12
2.2 Polylogarithms and Hadamard Products . . . . . . . . . . . . . 14
2.2.1 Polylogarithms . . . . . . . . . . . . . . . . . . . . . . . 14
2.2.2 Hadamard product . . . . . . . . . . . . . . . . . . . . . . 15
3 Moments by Singularity Analysis 19
3.1 Expected Value -- Proof of Theorem 1.3 . . . . . . . . . . . . 19
3.2 Higher Moments . . . . . . . . . . . . . . . . . . . . . . . . 30
3.2.1 1/2 < α . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
3.2.2 0 < α < 1/2 . . . . . . . . . . . . . . . . . . . . . . . . . 38
4 Limiting Distributions 48
4.1 The Method of Moments . . . . . . . . . . . . . . . . . . . . . 48
4.2 Proof of Theorem 1.4 . . . . . . . . . . . . . . . . . . . . . 49
5 Conclusion 51
[1] M. Abramowitz and I. A. Stegun. Handbook of Mathematical Functions. Dover,
1973.
[2] A. V. Aho, J. E. Hopcroft, J. D. Ullman. The Design and Analysis of Computer
Algorithms. Addision-Wesley, 1974.
[3] P. Billingsley. Probability and Measure (3rd Edition). Wiley, New York, 1995 (a
Wiley-Interscience Publication).
[4] J. A. Fill, P. Flajolet, and N. Kapur (2005). Singularity analysis, Hadamard products,
and tree recurrences. Journal of Computational and Applied Mathematics,
174 , 271--313.
[5] J. A. Fill and N. Kapur (2004). Limiting distributions of addititive functionals on
Catalan trees. Theoretical Computer Science, 326, 69--102.
[6] P. Flajolet and A. M. Odlyzko (1990). Random mapping statistics. In Lecture
Notes in Computer Science, 434, EUROCRYPT '89, 329--354.
[7] P. Flajolet and A. M. Odlyzko (1990). Singularity analysis of generating functions.
SIAM Journal on Algebraic and Discrete Methods, 3, 216--240.
[8] P. Flajolet and R. Sedgewick. Analytic Combinatorics. Cambridge University
Press, 2009.
[9] W. B. Ford. Studies on Divergent Series and Summability and The Asymptotic Developments
of Functions Defined by Maclaurin Series, 3rd ed. Chelsea Publishing
Company, 1960 (from two books originally published in 1916 and 1936).
[10] D. E. Knuth and B. Pittel (1989). A recurrence related to trees. Proceedings of the
American Mathematical Society, 105 (2), 335--349.
[11] E. T. Whittaker and G. N. Watson. A Course of Modern Analysis, fourth ed. Cambridge
University Press, 1927. Reprinted 1973.
[12] C. C. Yao (1976). On the average behavior of set merging algorithms (extended
abstract). Proc. ACM Symp. Theory of Computation, 8, 192--195.
連結至畢業學校之論文網頁點我開啟連結
註: 此連結為研究生畢業學校所提供,不一定有電子全文可供下載,若連結有誤,請點選上方之〝勘誤回報〞功能,我們會盡快修正,謝謝!
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top