Вычислительный структурный анализ асимптотического поведения случайных процессов на комбинаторных объектах

КАРТОЧКА ПРОЕКТА ФУНДАМЕНТАЛЬНЫХ И ПОИСКОВЫХ НАУЧНЫХ ИССЛЕДОВАНИЙ,
ПОДДЕРЖАННОГО РОССИЙСКИМ НАУЧНЫМ ФОНДОМ

Информация подготовлена на основании данных из Информационно-аналитической системы РНФ, содержательная часть представлена в авторской редакции. Все права принадлежат авторам, использование или перепечатка материалов допустима только с предварительного согласия авторов.

ОБЩИЕ СВЕДЕНИЯ

Номер проекта 22-21-00669

НазваниеВычислительный структурный анализ асимптотического поведения случайных процессов на комбинаторных объектах

Руководитель Васильев Николай Николаевич, Кандидат физико-математических наук

Организация финансирования, регион Федеральное государственное автономное образовательное учреждение высшего образования "Санкт-Петербургский государственный электротехнический университет "ЛЭТИ" им. В.И. Ульянова (Ленина)" , г Санкт-Петербург

Конкурс №64 - Конкурс 2021 года «Проведение фундаментальных научных исследований и поисковых научных исследований малыми отдельными научными группами»

Область знания, основной код классификатора 01 - Математика, информатика и науки о системах; 01-102 - Алгебра

Ключевые слова компьютерное моделирование, параллельные алгоритмы, анализ сложности алгоритмов, диаграммы и таблицы Юнга, цепи и антицепи, преобразование RSK, моноид Гекке, канонические разбиения на антицепи, выравнивание строк, сети сортировки, шестивершинная модель, модель TASEP, инвариантные меры, стохастические клеточные автоматы, константа Хватала-Санкова

Код ГРНТИ27.41.41

ИНФОРМАЦИЯ ИЗ ЗАЯВКИ

Аннотация
Классические комбинаторные объекты (перестановки, размещения, сочетания и др.) изучались математиками на протяжении многих веков. В частности, комбинаторика разбиений, диаграмм и таблиц Юнга, уходящая корнями в работы Леонарда Эйлера, на протяжении многих десятилетий привлекает исследователей из разных областей математики. В дальнейшем это привело к выявлению многочисленных связей с другими математическими объектами и структурами из самых разнообразных областей математики: алгебры, геометрии, дискретной математики, теории графов и теории динамических систем. Например, диаграммы и таблицы Юнга имеют тесную связь с такими объектами и моделями, как слова Гекке, сети транспозиций, сортирующие сети, модель выравнивания строк (вычисление наибольшей общей подпоследовательности и редакционного расстояния), стохастическая шестивершинная модель, модели многочастичного рассеяния типа TASEP (Totally Asymmetric Simple Exclusion Process) и многие другие. Эти объекты важны как в комбинаторике, теории вероятностей, теории динамических систем, теоретической информатике, так и в их различных приложениях. Например, модель выравнивания строк играет ключевую роль в вычислительной молекулярной биологии. Часто один и тот же вопрос изучался независимо в разных областях, что приводило к различным методам и существенно различной терминологии. Недавняя тенденция состоит в том, чтобы рассматривать диаграммы и таблицы Юнга, а также связанные с ними объекты, в существенно более общих ситуациях, используя язык частичных порядков, дискретных стохастических моделей, слов Гекке. В связи с этим возникают как алгоритмические задачи взаимного преобразования этих объектов (например, обобщения RSK, преобразование Эдельмана-Грина и т.п.), так и теоретико-вероятностные задачи, связанные с изучением случайных процессов на этих объектах. Эти исследования актуальны и для практических приложений. В частности, новые алгоритмы для анализа последовательностей ДНК в геномах животных и растений были получены с использованием слов Гекке (липких кос) и сортирующих сетей (сетей транспозиций). В рамках данного проекта ставятся в том числе следующие цели: 1. Исследовать новые связи между такими комбинаторными структурами, как модель выравнивания строк, стохастическая шестивершинная модель, модели многочастичного рассеяния типа TASEP, стохастические клеточные автоматы, сети транспозиций, сортирующие сети, диаграммы и таблицы Юнга, слова Гекке и др. 2. Изучить теоретически и с помощью компьютерных экспериментов асимптотическое поведение таких структур, полученных из комбинаторных объектов с различными вероятностными распределениями. Исследовать предельные формы геометрических объектов, связанных с такими структурами, в т.ч. сходимость к этим предельным формам. Надо отметить, что в настоящий момент многие предельные формы даже классических объектов неизвестны. 3. Получить отсутствующие в настоящее время верхние оценки вычислительной сложности алгоритмов, связанных с операциями над объектами, представляющими рассматриваемые структуры, в том числе слова Гекке, сортирующие сети, стохастические клеточные автоматы. 4. Для повышения эффективности компьютерных экспериментов разработать новые эффективные параллельные алгоритмы для разнообразных операций над исследуемыми объектами и моделями (словами Гекке, стохастическими клеточными автоматами, сортирующими сетями и т.д.) 5. Обобщить известные результаты о свойствах соответствия Робинсона-Шенстеда-Кнута на другие структуры и модели. В настоящее время данная область исследований находится в центре внимания специалистов в комбинаторике, теории случайных процессов, теории динамических систем, теоретической информатики, моделей статистической физики и квантовой механики, а также некоторых других областей фундаментальных и прикладных наук.

ОТЧЁТНЫЕ МАТЕРИАЛЫ

Публикации

1. Васильев Н.Н., Дужин В.С., Кузьмин А.Д. Modeling of bumping routes in the RSK algorithm and analysis of their approach to limit shapes Информационно-управляющие системы (год публикации - 2022)

2. Тискин А. В. Fast RSK Correspondence by Doubling Search Leibniz International Proceedings in Informatics, LIPIcs, Том 244. 86:1-86:10 (год публикации - 2022)
10.4230/LIPIcs.ESA.2022.86

3. Тискин А. В. The Chvatal-Sankoff problem: Understanding random string comparison through stochastic processes Записки Научных Семинаров ПОМИ, Том 517, с.191-224 (год публикации - 2022)

4. Тискин А. В. The Chvátal-Sankoff problem as a problem of symbolic dynamics Записки научных семинаров ПОМИ, Том 528, 214-237 (год публикации - 2023)

5. Дужин В. С. Программный инструментарий для исследования задач асимптотической комбинаторики диаграмм и таблиц Юнга Информационно-управляющие системы (год публикации - 2023)

6. Дужин В. С., Смирнов-Мальцев Е. Д. Some geometric properties of shifted Young diagrams of maximum dimensions International Conference Polynomial Computer Algebra '2024 (год публикации - 2024)

7. Дужин В. С., Смирнов-Мальцев Е. Д. On Young diagrams of maximum dimension Communications in Mathematics (год публикации - 2023)

Публикации

7. Дужин В. С., Смирнов-Мальцев Е. Д. On Young diagrams of maximum dimension Communications in Mathematics (год публикации - 2023)