随机树

Drmota

Random Trees

2009

Hardback

ISBN 9783211753552

M.卓默塔著

树是图论和组合论的重要研究对象,也是计算机科学中数据结构和算法的基本对象。在过去数十年间,随机树的研究发展迅速,产生了若干用来刻画不同问题中的树的特征的渐近技术和概率技术。本书是关于这些现代成果的引论性专著,较全面地论述了随机树理论的各个方面,系统地研究了各种复杂的数学技术,通过这些论述显示了组合方法与概率方法的内容联系和互相影响,沟通了这些具有不同特点的技术,将计数技术(母函数方法、一一映射方法)、渐近方法(鞍点技术、奇性分析)以及渐近概率中的各种复杂技巧(随机过程的收敛性、鞅)有机地结合起来。

全书包含9章和1个附录。前2章是预备性材料,也是全书的基础。其余各章分别给出专门的论题。1.引进树的概念,概述了本书着重讨论的三类随机树,即组合树、递归树和搜索树;2.母函数方法的概要,汇集了主要结果,并着重给出满足函数方程或函数方程组的母函数的解析研究;3.给出树计数的高等方法,基于母函数概念推导出基本类型的树的个数的明显公式以及简单生成树和Polya树的渐近公式,还证明了某些树参数满足某个中心极限定理;4-7.着重研究不同类型的树的轮廓和有关的统计的极限性状,包括GaltonMWatson树和Pólya树的深度轮廓、GaltonMWatson树的垂直轮廓、递归树的轮廓和高度,还研究了检索和数字搜索树;8.讲述递归算法和缩并方法,用以研究随机递归关系;9.研究可平面图,着重用母函数方法研究标号随机可平面图的组合性质和渐近性质。附录汇集了一些重要母函数的系数的明显表达方式。

本书主要供图论、组合、计算机科学等专业科研人员、研究生阅读。

朱尧辰,研究员

(中国科学院应用数学研究所)

Zhu Yaochen, Professor

(Institute of Applied Mathematics,CAS)