Лаборатория алгоритмики ММФ НГУ и группа «Алгоритмика и теория сложности вычислений» Берлинского технического университета (TU Berlin) получили поддержку РФФИ и Германского научно-исследовательского общества (DFG) для проведения совместного научно-исследовательского проекта. Международный коллектив учёных будет изучать новые подходы к быстрым алгоритмам сокращения объёмов данных с гарантиями результативности.
.JPG "IMG_0165 (1).JPG")
Время работы алгоритмов для решения задач растёт с объёмом входных данных. Поэтому на практике ключевым приёмом для ускорения работы алгоритмов является сокращение объёма данных с помощью их быстрой предварительной обработки. Однако гарантий результативности алгоритмов сокращения данных чаще всего нет, объясняет заведующий Лабораторией алгоритмики Рене ван Беверн.
В рамках нового совместного проекта РФФИ и DFG «Компромиссы в параметризованных подходах к редукции данных» исследователи НГУ и TU Berlin будут получать гарантированные оценки результативности алгоритмов сокращения данных. Главный вопрос проекта заключается в том, насколько алгоритм сокращения данных за заданное время может доказуемо и гарантированно сократить объём входных данных, если требуется, чтобы оптимальное решение задачи из-за сокращения данных не менялось; или менялось не более, чем на заданный фактор; или не менялось с заданной вероятностью.
Ученые будут доказывать верхние и нижние оценки результативности алгоритмов сокращения данных в этих условиях.
Разрабатываемые в рамках проекта подходы являются общими и помогают ускорить точные, приближенные и рандомизированные алгоритмы (работа которых определяется исходом случайных экспериментов) для задач в разных областях. В том числе разрабатываемые подходы будут испытываться на примере задач маршрутизации транспорта, минимизации энергопотребления беспроводных коммуникационных сетей и кластеризации данных.
Германский партнёр ученых из НГУ — исследовательская группа «Алгоритмика и теория сложности вычислений» под руководством проф. Рольфа Нидермайера, который посетил НГУ летом 2017 года. С российской стороны руководить проектом будет заведующий Лабораторией алгоритмики Рене ван Беверн. В 2017 году совместная разработка этих двух коллективов выиграла премию на крупнейшем европейском конгрессе по алгоритмам ALGO.
Для Лаборатории алгоритмики НГУ это второй научно-исследовательский проект, получивший международную грантовую поддержку. В 2017 году лаборатория при поддержке РФФИ и Департамента науки и технологии правительства Индии запустила совместный проект с индийским суперкомпьютерным центром Бангалор.
.jpg "Четыре команды студентов НГУ вошли в число победителей и призеров онлайн-соревнований TechArena Siberian Challenge-2024")