隨機(jī)樹(shù)

Drmota

Random Trees

2009

Hardback

ISBN 9783211753552

M.卓默塔著

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

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

本書(shū)主要供圖論、組合、計(jì)算機(jī)科學(xué)等專業(yè)科研人員、研究生閱讀。

朱堯辰,研究員

(中國(guó)科學(xué)院應(yīng)用數(shù)學(xué)研究所)

Zhu Yaochen, Professor

(Institute of Applied Mathematics,CAS)