Исследование распределения длин циклов преобразования Шютценберже над таблицами Юнга
Длины циклов случайных целочисленных перестановок являются предметом многочисленных исследований в области асимптотической комбинаторики. На множестве таблиц Юнга фиксированной формы перестановка может…
Алгоритмы карточных игр с применением криптографии без односторонних функций
Многие общеизвестные криптографические алгоритмы, входящие в архитектуру криптостойкой вычислительной системы, имеют достаточно сложную реализацию. Это следует из требований к односторонним функциям,…
Применение аппарата тропической математики в глубоких нейронных сетях
В последнее время глубокие нейронные сети получили большое распространение в связи с успешным использованием в решении задач искусственного интеллекта, компьютерного зрения,…
Задача поиска пути в компьютерных играх
Поиск кратчайшего пути является одной из важнейших задач в разработке современных компьютерных игр. В докладе будут рассмотрены алгоритмы поиска кратчайшего пути…
Деревья на шарнирах
При решении математических задач нередко возникает потребность в исследовании свойств деревьев. Одной из важнейших характеристик дерева является его высота. Целью данной…
Сравнение эффективности различных реализаций алгоритма RSK
Алгоритм Робинсона-Шенстеда-Кнута (RSK) задает биекцию между множеством перестановок и множеством пар таблиц Юнга одинаковой формы. Сложность алгоритма определяется способом поиска ближайшего…
Лаборатория функционирует на базе кафедры алгоритмической математики факультета компьютерных технологий и информатики (ФКТИ) Санкт-Петербургского государственного электротехнического университета «ЛЭТИ».
Научная тематика лаборатории включает в том числе
- Изучение различных вычислительных проблем асимптотической комбинаторики, таких как исследование марковских процессов и центральных мер на градуированных графах, исследование диаграмм Юнга с большими и максимальными размерностями, алгоритмы преобразований над таблицами Юнга (преобразования RSK, Шютценберже и др.), сортирующие сети, антицепи и другие объекты, связанные с таблицами Юнга и др.
- Проведение исследований с применением экспериментальной математики для нахождения свойств нулей дзета-функции Римана. Использование средств теории чисел для анализа закономерностей, полученных в ходе экспериментов.
- Изучение алгоритмов машинного обучения и применение их в прикладных задачах в областях обработки натуральных языков, анализа сетей (графов) и др.
- Исследование алгоритмов тропической математики, компьютерное вычисление тропических объектов для решения различных теоретических задач.
Цели лаборатории
- Решение актуальных фундаментальных и прикладных задач различными средствами компьютерной математики;
- Изучение студентами современной литературы по тематике лаборатории;
- Публикация статей, участие в конференциях;
- Налаживание контактов и сотрудничество с зарубежными коллегами;
- Создание дистанционных студенческих курсов;
- Подготовка студентами бакалаврских и магистерских работ.
Участники лаборатории регулярно выступают с докладами на студенческом онлайн семинаре, а также на кафедральном семинаре по алгоритмической математике.
Публикации участников лаборатории
Статьи
- Васильев Н. Н., Дужин В. С., Кузьмин А. Д. Моделирование путей выталкиваний в алгоритме RSK и анализ их приближения к предельной форме // Информационно-управляющие системы. –– 2022. –– Т. 121, № 6. –– С. 2––9.
- Васильев Н. Н., Дужин В. С., Кузьмин А. Д. О сходимости путей выталкиваний в алгоритме RSK к их предельной форме: численные эксперименты // Информационно-управляющие системы. –– 2021. –– Т. 115, № 6. –– С. 2––9.
- Васильев Н. Н., Дужин В. С., Кузьмин А. Д. Исследование свойств классов эквивалентности перестановок с помощью обратного преобразования Робинсона — Шенстеда — Кнута // Информационно-управляющие системы. –– 2019. –– Т. 98, № 1. –– С. 11––22.
- Дужин В. С., Чудновская А. А. Поиск диаграмм Юнга с большими размерностями // Компьютерные инструменты в образовании. –– 2019. –– № 4. –– С. 33––43.
Тезисы докладов
- Farid Mikhailov. Computing the dimensions of the components of tropical prevarieties. International Conference “Polynomial Computer Algebra 2022”, Saint-Petersburg, May 2-7, 2022, Ed. by N. N. Vassiliev, VVM Publishing, Saint-Petersburg, 2022, pp. 71-76.
- Vasilii Duzhin, Artem Kuzmin and Nikolay Vassiliev. RSK bumping trees and a fast RSK algorithm. International Conference “Polynomial Computer Algebra 2019”, Saint-Petersburg, April 15-20, 2019, Ed. by N. N. Vassiliev, VVM Publishing, Saint-Petersburg, 2019, pp. 64-66.
- Кузьмин А. Д. Построение полустандартных таблиц Юнга с планшерелевским распределением с помощью быстрого преобразования RSK / Наука настоящего и будущего: тез. докл. VII Научно-практической конференции с международным участием, СПб, 16-18 мая 2019 г., Т.1. / СПбГЭТУ «ЛЭТИ», СПб, 2019 С.91–93.
- Михайлов Ф. Вычисление размерностей компонент тропических предмногообразий в пакете GFAN / Наука настоящего и будущего: тез. докл. X Научно-практической конференции с международным участием, СПб, 19-20 мая 2022 г., Т.2. / СПбГЭТУ «ЛЭТИ», СПб, 2022 С.190–192.
- Тян Е. Асимптотика геометрических параметров типичных диаграмм Юнга для марковских процессов на графе твердых разбиений / Наука настоящего и будущего: тез. докл. VIII Научно-практической конференции с международным участием, СПб, 14-16 мая 2020 г., Т.1. / СПбГЭТУ «ЛЭТИ», СПб 2020 С. 262-265
- Чудновская А. А. Построение последовательностей нормализованных размерностей диаграмм Юнга / Наука настоящего и будущего: тез. докл. VII Научно-практической конференции с международным участием, СПб, 16-18 мая 2019 г., Т.1. / СПбГЭТУ «ЛЭТИ», СПб, 2019 С. 113–115.
- Чудновская А. А. Алгоритм поиска диаграмм Юнга с большими размерностями / 72 Научно-техническая конференция профессорско-преподавательского состава университета: сборник докладов студентов, аспирантов и молодых ученых. / СПбГЭТУ «ЛЭТИ», СПб, 2019 С. 112–114.
Достижения студентов
- Белов И. О.:
- Диплом III степени на студенческой конференции “Наука настоящего и будущего ‘2021”.
- Кузьмин А. Д.:
- Диплом I степени на конкурсе на лучшую научно-исследовательскую работу студентов по научно-образовательным направлениям СПбГЭТУ «ЛЭТИ», май 2019;
- Диплом III степени на студенческой конференции “Наука настоящего и будущего ‘2019”.
- Максимова А. А.:
- Диплом I степени на студенческой конференции “Наука настоящего и будущего ‘2022”;
- Диплом III степени на студенческой конференции “Наука настоящего и будущего ‘2021”.
- Михайлов Ф.:
- Диплом II степени за успешное выступление на региональной предметной олимпиаде студентов высших учебных заведений Санкт-Петербурга по математике в 2019 г.;
- Призёр всероссийского конкурса IT-специалистов «Цифровой прорыв 2021» в профессиональной области “Машинное обучение”: 22 место из 360.
- Тян Е.:
- Первое место в VI Всероссийском конкурсе лучших студенческих дипломов “Be First! ‘2021”;
- Диплом III степени на студенческой конференции “Наука настоящего и будущего ‘2020”.