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