17 сентября, 18:30. Fine-grained complexity (И.А. Михайлин)

[Alexander V. Smal]

Добрый день!

В четверг 17 сентября начинается курс "Fine-grained complexity"
(лекции читает И.А. Михайлин). В этом курсе будет рассказываться о
современном направлении в теории сложности — fine-grained complexity
(тонкие оценки на время работы алгоритмов). В рамках этого направления
ресурсы, необходимые для выполнения задачи (например, время работы
алгоритма), изучаются с более высокой точностью, чем это делается в
классической сложности. Например, в рамках классического подхода, если
задача разрешима за полиномиальное время, то её считают простой.
Однако на практике есть грандиозная разница между простой задачей,
которая считается за n^2, и простой задачей, которая считается за
n^100. Fine grained complexity пытается ответить на вопрос — какой
ассимптотически лучший алгоритм существует для конкретной задачи.
Таким образом, с одной стороны, это область вбирает в себя алгоритмы,
а с другой — разноообразные методы доказательств нижних оценок.

Курс открыт для всех. Для получения информации о лекциях, практиках и
домашних заданиях нужно записаться на курс на сайте клуба (для этого
потребуется зарегистрироваться на сайте).
https://compsciclub.ru/courses/fine-grained-complexity/2020-autumn/

Саша

--
Alexander V. Smal
St. Petersburg Department of Steklov Mathematical Institute
27 Fontanka, St. Petersburg, 191023, Russia