TY - JOUR AU - Николай Николаевич Васильев AU - Василий Сергеевич Дужин AU - Артем Дмитриевич Кузьмин PY - 2021/12/20 Y2 - 2024/03/28 TI - О сходимости путей выталкиваний в алгоритме RSK к их предельной форме: численные эксперименты JF - Информационно-управляющие системы JA - ИУС VL - 0 IS - 6 SE - Теоретическая и прикладная математика DO - 10.31799/1684-8853-2021-6-2-9 UR - https://i-us.ru/index.php/ius/article/view/15161 AB - Введение: алгоритм Робинсона — Шенстеда — Кнута (RSK) преобразует последовательность элементов линейно упорядоченного множества в пару таблиц Юнга P, Q одинаковой формы. Это преобразование основано на выталкивании и вставке элементов в таблице P по специальным правилам. Траектория, которую образуют последовательно выталкиваемые клетки таблицы P в алгоритме RSK, называется путем выталкиваний. Явная формула предельной формы пути выталкиваний, которая определяется его начальным элементом, была получена Д. Ромиком и П. Сняды в 2016 г. Однако скорость сходимости путей выталкиваний к предельной форме ранее не исследовалась ни теоретически, ни с помощью численных экспериментов. Цель: проведение компьютерных экспериментов в целях изучения динамики путей выталкиваний, порождаемых алгоритмом RSK в таблицах Юнга, с ростом их размера; вычисление статистических средних и дисперсий отклонений путей выталкиваний от их предельных форм в метрике L2 для различных значений, подаваемых на вход алгоритма RSK. Результаты: проведена серия компьютерных экспериментов над таблицами Юнга размера до 10 млн клеток. Использовалось по 300 таблиц каждого размера. В каждую такую таблицу с помощью алгоритма RSK добавлялись различные входные значения (0,1; 0,3; 0,5; 0,7; 0,9) и были вычислены отклонения путей выталкиваний, построенных от этих значений, от соответствующих предельных форм. Построены графики средних значений и дисперсий этих отклонений. Замечено, что отклонения убывают пропорционально корню четвертой степени из размера таблицы n. Получена аппроксимация зависимости средних значений отклонений от n с помощью метода наименьших квадратов. ER -