隨機數位樹上加法性參數之機率分析

Abstract

自圖靈獎得主高納德(D. E. Knuth) 於1963 年首開先河後，演算法分析成 為了一個在數學和理論計算機科學中皆具相當重要性的研究領域。本領域 的主要目標之一在於取得對演算法之隨機行為的全面了解。除此之外，資 料結構的漸進性質也是演算法分析所關注的重要議題。數位樹家族是在計 算機和資訊科學中最常被使用的資料結構之一。在本論文中，我們藉由研 究數位樹的加法性構型參數探討了此一資料結構的眾多漸進性質。 本論文的第一部份是對數位樹家族進行一個完整的介紹。內容包括了 構造方式、我們將使用的隨機模型、已知的研究成果和相關的數學工具。 我們也將利用一些例子來解釋這些數學工具在過去的研究中是如何被使用 的。

第二部分則是我們新獲得的研究成果，包括了Poisson-Laplace-Mellin 方法的新應用以及一套可用來證明隨機數位樹加法性構型參數的中央極限 定理的理論框架。過去使用Poisson-Laplace-Mellin 方法所獲得的結果大多 數是有關線性成長的構型參數的，我們在本論文中運用Poisson-Laplace- Mellin 方法對許多非線性成長的構型參數進行了研究並且推導出了這些參 數的期望值和變異數的漸進表示。我們還建立了一套可以近乎” 自動” 證明 構型參數的中央極限定理的理論框架− 只要此構型參數滿足一定條件，則 自動滿足一中央極限定理。

Established by D. E. Knuth in 1963, analysis of algorithms is an important area which lies in the overlap of mathematics and theoretical computer science. The main aim of this area is to understand the stochastic behavior of algorithms. Moreover, another important issue is to obtain asymptotic properties of data structures. In this thesis, we study one of the most often used data structure, the digital tree family, through additive shape parameters. The first part of this thesis is an introduction to the digital tree family, including the construction, the random model we are going to use and a survey of known results and related mathematical techniques. We also give some examples to illustrate how these mathematical techniques have been utilized in past researches of random digital trees.

The second part contains the new results we derived, including new applications of the Poisson-Laplace-Mellin method and general frameworks for central limit theorems of additive shape parameters in random digital trees. Most of the known applications of the Poisson-Laplace-Mellin method are for shape parameters of linear order. In this thesis, we study many shape parameters which are of sublinear and superlinear order via the Poisson-Laplace-Mellin method and derive asymptotic expressions for the means and variances of these shape parameters. We also establish frameworks which allows us to prove central limit theorems of the shape parameters in an almost automatic fashion.