Пошук академічних текстів

Реєстраційний номер

0822U101014, Дисертація доктора філософії

Назва роботи

Дослідження асимптотичних властивостей випадкових дерев

Здобувач

Богун Владислав Анатолійович,

Керівник Маринич Олександр Віталійович
Опонент Нікітін Анатолій Володимирович
Опонент Пилипенко Андрій Юрійович
Рецензент Семенов Володимир Вікторович
Рецензент Самойленко Ігор Валерійович

На здобуття

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

Дата захисту

18-11-2022

Опис

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