Лаборатория алгоритмики НГУ и TU Berlin разработают новые способы эффективного сокращения объёмов данных

Рене ван Беверн (справа) и Рольф Нидермайер возле нового корпуса НГУ
Фото: nsu.ru

Лаборатория алгоритмики ММФ НГУ и группа «Алгоритмика и теория сложности вычислений» Берлинского технического университета (TU Berlin) получили поддержку РФФИ и Германского научно-исследовательского общества (DFG) для проведения совместного научно-исследовательского проекта. Международный коллектив учёных будет изучать новые подходы к быстрым алгоритмам сокращения объёмов данных с гарантиями результативности.

Рене ван Беверн (справа) и Рольф Нидермайер возле нового корпуса НГУ

Время работы алгоритмов для решения задач растёт с объёмом входных данных. Поэтому на практике ключевым приёмом для ускорения работы алгоритмов является сокращение объёма данных с помощью их быстрой предварительной обработки. Однако гарантий результативности алгоритмов сокращения данных чаще всего нет, объясняет заведующий Лабораторией алгоритмики Рене ван Беверн .

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

Ученые будут доказывать верхние и нижние оценки результативности алгоритмов сокращения данных в этих условиях.

Разрабатываемые в рамках проекта подходы являются общими и помогут ускорить точные, приближённые и рандомизированные алгоритмы (работа которых определяется исходом случайных экспериментов) для задач в разных областях. В том числе разрабатываемые подходы будут испытываться на примере задач маршрутизации транспорта, минимизации энергопотребления беспроводных коммуникационных сетей и кластеризации данных.

Германский партнёр ученых из НГУ — исследовательская группа «Алгоритмика и теория сложности вычислений» под руководством проф. Рольфа Нидермайера , который посетил НГУ летом 2017 года. С российской стороны руководить проектом будет заведующий Лабораторией алгоритмики Рене ван Беверн. В 2017 году совместная разработка этих двух коллективов выиграла премию на крупнейшем европейском конгрессе по алгоритмам ALGO .

Для Лаборатории алгоритмики НГУ это второй научно-исследовательский проект, получивший международную грантовую поддержку. В 2017 году лаборатория при поддержке РФФИ и Департамента науки и технологии правительства Индии запустила совместный проект с индийским суперкомпьютерным центром Бангалор .

 
По теме
Обвиняемый уже был ранее судим и вышел на свободу 7 марта по УДО Фото: freepik.com Жителя Коченевского района Новосибирской области заключили под стражу за ложные сообщения о минировании отдела полиции.
Прогноз возможных чрезвычайных ситуаций на территории НСО на 29 марта - Город Искитим При составлении прогноза использована информация ФГБУ «Западно-Сибирское УГМС», Верхне-Обского бассейнового водного управления Федерального агентства водных ресурсов, Алтае-Саянский филиал ГС СО РАН,
Город Искитим
Редкую патологию обнаружили у девочки из Новосибирска - более десяти лет потребовалось, чтобы установить диагноз Ребенок не может нормально питаться, твердая пища вызывает боль и кровотечения во рту.
ГТРК Новосибирск
С Сергеем Михалковым – весело! - ЦБС Баганского района Во второй день Недели детской книги в библиотеке состоялась встреча с воспитанниками детского сада «Колокольчик».
ЦБС Баганского района
С новым званием! - Краеведческий музей Поздравляем Риту Анатольевну Полянскую с присвоением звания «Почетный работник культуры» Новосибирской области!
Краеведческий музей
Поезд, идущий в овраге - Газета Ведомости «Собаки» и «Гадкий утёнок» — какие сюрпризы приготовили детям новосибирские театры?
Газета Ведомости