14 октября (понедельник) начнётся семинар по тонким оценкам на время работы алгоритмов.

14 октября (понедельник) начнётся семинар по тонким оценкам на время работы алгоритмов. Это странное название — попытка перевести на русский название области fine-grained complexity, которая зародилась совсем недавно и сейчас активно развивается. Пример одного из центральных вопросов, изучаемых в этой области: почему нам всем до сих пор так и не удалось улучшить классический алгоритм со временем n^2, основанный на методе динамического программирования, для задачи о редакционном расстоянии двух строк? почему мы до сих пор не умеем находить все пары кратчайших путей в графе быстрее, чем за n^3? что будет, если такие алгоритмы найдутся?

В последнее десятилетие были найдены и удивительные связи между этими задачами, и более эффективные алгоритмы для подобных задач. Мы познакомимся с наиболее примечательными результатами в этой области, а также узнаем много открытых задач. Приходите, пожалуйста, сами и приводите знакомых.

Подробное описание и расписание: https://compsciclub.ru/courses/fine-grained-complexity-seminar/2019-autumn/

Источник: compsciclub.ru

Комментарии: