Search academic texts

Registration Number

0822U101014, PhD dissertation

Title

Asymptotic properties of random trees

Author

Bogun Vladyslav A.,

popup.head Marynych Oleksandr Vitalijovich
popup.opponent Nikitin Anatolii V.
popup.opponent Pilipenko Andrey Yuriyovych
popup.review Semenov Volodymyr Viktorovych
popup.review Samoilenko Ihor V.

Status

Доктор філософії, 113, Математика та статистика. Прикладна математика

Date

18-11-2022

Description

Дисертаційна робота присвячена дослідженню асимптотичних властивостей випадкових дерев, коли кількість вершин у дереві прямує до нескінченності. В роботі розглянуто три класи випадкових дерев, представлено результати про асимптотичну поведінку профілів, моди, ширини, висоти, довжин певних шляхів та інших характеристик. Першим класом є випадкові дерева простої будови, що є класичною моделлю в літературі. Її можна описати наступним чином: на кожному кроці в дереві навмання вибирається вершина з певної підмножини та до неї додаються нові вершини. До цього класу належать випадкові рекурсивні дерева та бінарні дерева пошуку. Другою моделлю слугують дерева загальних гіллястих процесів. Третіми виступають VP-дерева, що виникають в комп'ютерних науках як структура даних для швидкого виконання запиту пошуку найближчого сусіда. В даній дисертаційній роботі продовжено дослідження випадкових дерев методами та техніками, використаними в нещодавніх роботах О. Іксанова, З. Каблучка, О. Маринича, Г. Зульцбаха та інших. При цьому отримано нові результати та збагачено загальну теорію, що використовується для доведень. Окрім цього в роботі досліджується новий клас дерев, що раніше не вивчався з ймовірнісної точки зору. Автором дисертації отримано повні асимптотичні розклади майже напевне для профілів випадкових дерев простої будови, доведено граничні теореми для моди і ширини та запропоновано нові характеризації для випадкових величин, що при цьому виникають, у вигляді стохастичних рівнянь нерухомої точки. Проаналізовано висоту дерев загального гіллястого процесу побудованого за збуреним випадковим блуканням. Додатково автором отримано асимптотики згорток Лебега-Стілтьєса функцій лінійного росту, що з'являються при дослідженні подібних дерев на проміжних рівнях, а відповідні результати застосовані до функцій відновлення. Також було доведено слабкий закон великих чисел для довжини найлівішого шляху у VP-дереві та граничну теорему щодо її збіжності вздовж підпослідовностей. Нарешті, були дослідженні розбиття простору, що породжує випадкове VP-дерево. Отримано результат про скінченність моменту першого повернення в певні стани цих розбиттів, доведено існування стаціонарного розподілу відповідного ланцюга Маркова на множині розбиттів та збіжність до нього, а сам стаціонарний розподіл підраховано у явному вигляді . Основні теоретичні результати супроводжуються математичним моделюванням та комп'ютерними симуляціями виконаними за допомогою мови програмування Python3, що підтверджують відповідні твердження та дають краще уявлення про досліджувані величини. Дисертаційна робота має як теоретичне так і прикладне значення. Випадкові дерева мають численні застосування в аналізі структур даних та алгоритмів, а також для моделювання процесів еволюції та поширення в багатьох прикладних науках, зокрема біології, медицині, соціології, економіці та інших. Отримані в роботі результати можуть знайти застосовування в згаданих сферах, а запропоновані математичні методи можна використовувати для подальших досліджень інших класів дерев.