# 臺灣博碩士論文加值系統

(44.200.86.95) 您好！臺灣時間：2024/05/25 15:28

:::

### 詳目顯示

:

• 被引用:0
• 點閱:111
• 評分:
• 下載:4
• 書目收藏:0
 在計算科學中，常常需要處理將集合合併的問題，而為了有效率的解決這個問題，需要建造適當的的資料結構和相對應的演算法，這類的問題又稱為"Union-Find problem"﹔事實上，已經有許多種不同的資料結構和相對應的演算法被提出來以解決這個問題，為了了解各個方法的優劣，我們考慮最簡單的狀況，也就是將n 個不同的元素兩兩合併，直到成為一個集合為止所需的複雜度。在這篇論文中，我們假設每個合併過程所需的複雜度是被合併的兩個集合的大小之和的冪次方，求其在隨機生成樹的機率模型底下，所需總複雜度的極限分布。在這裡，我們使用一個近幾年才發展出來的新工具，稱為奇異點分析(SingularityAnalysis)﹔這個工具可以讓我們直接由生成函數的漸進展開式得到生成函數係數的漸進式。我們將使用這個方法來計算總複雜度的各階動差，進而再利用動差法推導出總複雜度的極限分布。這篇論文的一開始，也就是第一章我們先介紹問題的背景並給出我們研究的結果﹔在第二章我們介紹我們研究所使用的工具，也就是奇異點分析﹔而第三章是這篇這篇論文最主要的部分，我們利用奇異點分析導出複雜度的期望值和各階動差並在第四章利用動差法證明了我們的結果﹔最後在第五章我們對整篇論文做一個總結。
 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 correspondingalgorithms 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 andthen 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 devotedto the derivation of the expected value and higher moments. These results will willthen be used in Chapter 4 for prove our main result. Finally, we end the thesis with aconclusion in Chapter 5.
 Contents1 Introduction 12 Tools 62.1 Singularity Analysis . . . . . . . . . . . . . . . . . . . . . . 62.1.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 62.1.2 Fundamentals of singularity analysis . . . . . . . . . . . . . 82.1.3 Differentiation and integration . . . . . . . . . . . . . . . 122.2 Polylogarithms and Hadamard Products . . . . . . . . . . . . . 142.2.1 Polylogarithms . . . . . . . . . . . . . . . . . . . . . . . 142.2.2 Hadamard product . . . . . . . . . . . . . . . . . . . . . . 153 Moments by Singularity Analysis 193.1 Expected Value -- Proof of Theorem 1.3 . . . . . . . . . . . . 193.2 Higher Moments . . . . . . . . . . . . . . . . . . . . . . . . 303.2.1 1/2 < α . . . . . . . . . . . . . . . . . . . . . . . . . . . 313.2.2 0 < α < 1/2 . . . . . . . . . . . . . . . . . . . . . . . . . 384 Limiting Distributions 484.1 The Method of Moments . . . . . . . . . . . . . . . . . . . . . 484.2 Proof of Theorem 1.4 . . . . . . . . . . . . . . . . . . . . . 495 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 ComputerAlgorithms. Addision-Wesley, 1974.[3] P. Billingsley. Probability and Measure (3rd Edition). Wiley, New York, 1995 (aWiley-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 onCatalan trees. Theoretical Computer Science, 326, 69--102.[6] P. Flajolet and A. M. Odlyzko (1990). Random mapping statistics. In LectureNotes 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 UniversityPress, 2009.[9] W. B. Ford. Studies on Divergent Series and Summability and The Asymptotic Developmentsof Functions Defined by Maclaurin Series, 3rd ed. Chelsea PublishingCompany, 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 theAmerican Mathematical Society, 105 (2), 335--349.[11] E. T. Whittaker and G. N. Watson. A Course of Modern Analysis, fourth ed. CambridgeUniversity Press, 1927. Reprinted 1973.[12] C. C. Yao (1976). On the average behavior of set merging algorithms (extendedabstract). Proc. ACM Symp. Theory of Computation, 8, 192--195.
 電子全文
 國圖紙本論文
 連結至畢業學校之論文網頁點我開啟連結註: 此連結為研究生畢業學校所提供，不一定有電子全文可供下載，若連結有誤，請點選上方之〝勘誤回報〞功能，我們會盡快修正，謝謝！
 推文當script無法執行時可按︰推文 網路書籤當script無法執行時可按︰網路書籤 推薦當script無法執行時可按︰推薦 評分當script無法執行時可按︰評分 引用網址當script無法執行時可按︰引用網址 轉寄當script無法執行時可按︰轉寄

 無相關論文

 無相關期刊

 1 海運貨櫃運輸從業人員採用RFID技術意願之研究 2 小發散角的發光二極體照明器之設計 3 以碳、氮、矽原子及乙烯基為共價橋樑所形成之七與五環熔合多電子平面分子：合成、鑑定及其共軛高分子於有機太陽能電池與有機場效電晶體之應用 4 高浮慣比混合對流之熱傳效益提升 5 運用螞蟻演算法求解動態船席指派問題 6 運用狀態轉換圖於高中數學轉移矩陣教學之研究 7 開盤前價格發現-台灣現貨、期貨、選擇權之比較分析 8 直銷產業競爭優勢與經營策略之研究—以中國大陸安利為例 9 背光滑鼠瑕疵機器視覺檢測系統 10 高頻率穩態視覺誘發電位對人眼視網膜中央窩與其外圍的反應 11 合理使用於數位圖書搜尋之適用—以Google Book Search為中心 12 由創新動態學檢視習慣領域學說的推展 13 ERP企業流程監控：導入 SAP BPMon 之研究 14 以工作與事件為導向建置知識管理系統之研究 15 高階主管之領導風格對員工行為態度影響之研究--以房仲業F公司仲介事業處為例

 簡易查詢 | 進階查詢 | 熱門排行 | 我的研究室