Научно-учебная группа Питерской Вышки «Фундаментальные алгоритмы» под руководством профессора департамента информатики Сергея Федоренко достигла новых результатов в теоретических исследованиях дискретного преобразования Фурье. Основной прогресс команды отражен в статье студенток Олеси Ольшевской и Кристины Лотониной, которая готовится к публикации в авторитетном сборнике.
Дискретное преобразование Фурье (ДПФ) — одна из важных математических операций, с помощью которой можно разложить сложный цифровой сигнал на отдельные частоты (примерно так же, как музыка разбирается на ноты). Такой подход широко применяется в современных технологиях — для сжатия звуков или изображений, а также во всех областях, где нужно быстро анализировать и обрабатывать цифровые сигналы.
Исследование студентов посвящено разновидности ДПФ, в которой вычисления ведутся не с обычными числами, а c так называемыми конечными полями. Это системы, которые используются для расчетов больших данных в шифровании и передаче информации.
Главный результат работы Олеси Ольшевской и Кристины Лотониной — создание улучшенного алгоритма, который позволяет выполнять вычисления ДПФ с минимальными временными и ресурсными затратами. Метод требует наименьшего количества умножений и сложений по сравнению с существующими аналогами. Это особенно важно для разработки быстрых и надежных цифровых систем.
Научная статья Cooley-Tukey like discrete Fourier transform algorithm with the smallest complexity over a finite field будет направлена во флагманский журнал Общества обработки сигналов «Списка А» — IEEE Transactions on Signal Processing.
«Мы работаем над алгоритмами, которые находят применение в кодировании и защите информации. Сейчас наша главная задача — максимально ускорить вычисления при умножении специальных математических объектов, называемых матрицами, на векторы. Уже удалось построить содержательный пример такого быстрого расчета. Теперь мы стремимся создать полноценную теорию подобных вычислений», — объясняет студентка 1-го курса бакалаврской программы «Компьютерные технологии, системы и сети» Олеся Ольшевская.
Научная группа подготовила доклад для XIХ международной конференции International Symposium on Problems of Redundancy in Information and Control Systems (REDUNDANCY), которая пройдет в Москве с 5 по 7 ноября 2025 года.
«Мы прошли большой курс по конечным полям и научились с ними работать — это отдельная область в математике, с которой справиться было бы сложно без поддержки нашего научного руководителя. Он предоставил нам доступ к базе материалов и статей. Теперь регулярно встречаемся на семинарах, разбираемся в сложных алгоритмах и ищем способы их совершенствовать. Мы берем существующий алгоритм и пытаемся модернизировать его. Наибольшего прогресса на данный момент добились Олеся Ольшевская и Кристина Лотонина. В планах, конечно, развивать успех и масштабировать работу, публиковаться в статьях и принимать участие в конференциях», — рассказывает участник научно-учебной группы, студент 1-го курса бакалаврской программы «Компьютерные технологии, системы и сети» Борис Мартынов.
Научно-учебная группа «Фундаментальные алгоритмы» создана в рамках конкурса исследовательских проектов программы «Научный фонд НИУ ВШЭ» в 2025 году. В ней работают семь студентов бакалавриата, которые обучаются на образовательной программе «Компьютерные технологии, системы и сети». Группа занимается разработкой алгоритмов для различных цифровых систем — от сжатия данных до надежной передачи информации. Студенты проводят собственный семинар «Фундаментальные алгоритмы и приложения», на котором делятся открытиями и обсуждают новые идеи.