隨機樹

Drmota

Random Trees

2009

Hardback

ISBN 9783211753552

M.卓默塔著

樹是圖論和組合論的重要研究對象,也是計算機科學中數(shù)據(jù)結構和算法的基本對象。在過去數(shù)十年間,隨機樹的研究發(fā)展迅速,產生了若干用來刻畫不同問題中的樹的特征的漸近技術和概率技術。本書是關于這些現(xiàn)代成果的引論性專著,較全面地論述了隨機樹理論的各個方面,系統(tǒng)地研究了各種復雜的數(shù)學技術,通過這些論述顯示了組合方法與概率方法的內容聯(lián)系和互相影響,溝通了這些具有不同特點的技術,將計數(shù)技術(母函數(shù)方法、一一映射方法)、漸近方法(鞍點技術、奇性分析)以及漸近概率中的各種復雜技巧(隨機過程的收斂性、鞅)有機地結合起來。

全書包含9章和1個附錄。前2章是預備性材料,也是全書的基礎。其余各章分別給出專門的論題。1.引進樹的概念,概述了本書著重討論的三類隨機樹,即組合樹、遞歸樹和搜索樹;2.母函數(shù)方法的概要,匯集了主要結果,并著重給出滿足函數(shù)方程或函數(shù)方程組的母函數(shù)的解析研究;3.給出樹計數(shù)的高等方法,基于母函數(shù)概念推導出基本類型的樹的個數(shù)的明顯公式以及簡單生成樹和Polya樹的漸近公式,還證明了某些樹參數(shù)滿足某個中心極限定理;4-7.著重研究不同類型的樹的輪廓和有關的統(tǒng)計的極限性狀,包括GaltonMWatson樹和Pólya樹的深度輪廓、GaltonMWatson樹的垂直輪廓、遞歸樹的輪廓和高度,還研究了檢索和數(shù)字搜索樹;8.講述遞歸算法和縮并方法,用以研究隨機遞歸關系;9.研究可平面圖,著重用母函數(shù)方法研究標號隨機可平面圖的組合性質和漸近性質。……