Асимптотичний розподіл індексу складності випадкового рекурсивного дерева
Вантажиться...
Дата
2025
Автори
Науковий керівник
Назва журналу
Номер ISSN
Назва тому
Видавець
КПІ ім. Ігоря Сікорського
Анотація
В роботі досліджено властивості експоненційного індексу складності випадкового рекурсивного дерева. Доведено, що послідовність нормованих індексів складності утворює обмежений в L_p, p≥1 мартингал, та встановлено існування граничної випадкової величини, до якої збігається ця послідовність, коли кількість вершин дерева прямує до нескінченності. Для граничної випадкової величини доведено існування щільності розподілу, встановлено вигляд рівняння, якому ця щільність задовольняє, а також перевірено виконання умови Карлемана, яка гарантує, що розподіл граничної випадкової величини визначається однозначно її моментами.
Опис
Ключові слова
випадкове рекурсивне дерево, індекс складності дерева, граничний розподіл нормованого індексу складності
Бібліографічний опис
Сачук, А. О. Асимптотичний розподіл індексу складності випадкового рекурсивного дерева / А. О. Сачук, І. І. Ніщенко // Теоретичні і прикладні проблеми фізики, математики та інформатики : матерiали XXIII Всеукраїнської науково-практичної конференцiї студентiв, аспiрантiв та молодих вчених, [Київ], 14−17 травня 2025 р. / КПІ ім. Ігоря Сікорського. – Київ, 2025. – С. 376-379.