Личный кабинет
Подробное описание документа
А. Д. Кузьмин
Изучение асимптотических свойств алгоритма Робинсона-Шенстеда-Кнута : студенческая научная работа / А. Д. Кузьмин ; Санкт-Петербургский государственный электротехнический университет «ЛЭТИ» им. В. И. Ульянова (Ленина). - Санкт-Петербург : б. и., 2021. -
Алгоритм RSK или соответствие Робинсона-Шенстеда-Кнута устанавливает взаимно однозначное соответствие между последовательностями натуральных чисел и парами таблиц Юнга одинаковой формы. Изучение асимптотических свойств алгоритма RSK на последовательностях большого размера является актуальной задачей асимптотической комбинаторики. В выпускной квалификационной работе с помощью компьютерных экспериментов исследовалось распределение первых элементов последовательностей, принадлежащих одному классу двойственной эквивалентности по Кнуту. Соответствующие таким классам таблицы Юнга генерировались с использованием предложенного эффективного алгоритма, основанного на комбинации RSK и марковского процесса Планшереля. Рассматривались таблицы, состоящие из миллионов клеток. Установлено, что количество возможных положений единицы в перестановках зависит от формы пары соответствующих таблиц Юнга. Исследовались асимптотические свойства леса выталкиваний записывающей таблицы в алгоритме RSK.
