RUS  ENG ЖУРНАЛЫ   ПЕРСОНАЛИИ   ОРГАНИЗАЦИИ   КОНФЕРЕНЦИИ   СЕМИНАРЫ   ВИДЕОТЕКА   ЛИЧНЫЙ КАБИНЕТ
Ближайшие семинары
Календарь семинаров
Список семинаров
Архив по годам
Регистрация семинара

Поиск
RSS
Ближайшие семинары





Для просмотра файлов Вам могут потребоваться








Семинар отдела дискретной математики МИАН
12 сентября 2005 г., г. Москва, МИАН, комн. 511 (ул. Губкина, 8)
 


Форма случайных деревьев

М. Дрмота

Количество просмотров:
Эта страница:54

Аннотация: В докладе будет сделан обзор последних результатов о форме случайных деревьев. Форма случайного дерева определяется его профилем, т.е. последовательностью $v_k=#\{x:\mathrm{dist}(x,root)=k\}$ $(k\ge 0)$ чисел вершин, находящихся на расстоянии $k$ от корня. По профилю можно найти ряд других параметров дерева: высоту $h=\max\{k\ge0:v_k>0\}$, ширину $w=\max\{v_k:k\ge 0\}$ и длину путей (= сумму всех расстояний до корня $l=\sum_{k\ge 0} k v_k$.
Будут рассмотрены деревья Гальтона–Ватсона (включающие несколько классических семейств деревьев, в частности двоичные деревья, деревья Мотцкина, корневые плоские деревья, помеченные деревья), деревья Пойа (в которых среднее расстояние до корня имеет порядок $\sqrt{n}$), а также так называемые $(\log n)$-деревья (бинарные деревья поиска, рекурсивные деревья, плоские ориентированные деревья, цифровые деревья поиска), в которых среднее расстояние до корня имеет порядок $\log n$.
Оказывается, профиль $\sqrt{n}$-деревьев можно аппроксимировать случайным процессом — локальным временем броуновской экскурсии, что позволяет получить предельные распределения высоты и ширины. В случае $\log n$-деревьев ситуация совершенно другая. Они больши похожи на «детерминистические». Для них тоже существуют аппроксимации процессами, но эти процессы не являются функционалами от броуновского движения.
Одной из целей доклада является демонстрация силы аналитических методов в специфическом разделе теории векроятностей, связанном с комбинаторными задачами. В основном используются метод производящих функций и их свойства как аналитических функций.

ОТПРАВИТЬ: VKontakte.ru FaceBook Twitter Mail.ru Livejournal Memori.ru
 
Обратная связь:
 Пользовательское соглашение  Регистрация  Логотипы © Математический институт им. В. А. Стеклова РАН, 2017