Город: Санкт-Петербург Новосибирск Казань Язык: Русский English

Fine-grained complexity
Санкт-Петербург / осень 2020, посмотреть все семестры

Запишитесь на курс, чтобы получать уведомления и иметь возможность сдавать домашние задания. Для записи требуется регистрация на сайте.
Перейти к регистрации Войти

В курсе будет рассказано о современном направлении в теории сложности - fine-grained complexity. В рамках этого направления ресурсы, необходимые для выполнения задачи (например, время работы алгоритма), изучаются с более высокой точностью, чем это делается в классической сложности. Например, в рамках классического подхода, если задача разрешима за полиномиальное время, то её считают простой. Однако на практике есть грандиозная разница между простой задачей, которая считается за \(n^2\), и простой задачей, которая считается за \(n^{100}\).

Fine grained complexity пытается ответить на вопрос — какой асимптотически лучший алгоритм существует для конкретной задачи. Таким образом, с одной стороны, это область вбирает в себя алгоритмы, а с другой — разнообразные методы доказательств нижних оценок.

В последние годы эта область породила много очень интересных результатов, включая:

  • несколько алгоритмов, которые исследователи пытались улучшить около полувека на самом деле оказались оптимальными. Этот список включает алгоритмы для задачи поиска наибольшей общей подпоследовательности и задачи нахождения редакционного расстояния.
  • для классических задач, таких как поиск всех кратчайших расстояний в графе или нахождения пары ортогональных векторов были найдены более быстрые алгоритмы.
Дата и время Название Место Материалы
17 сентября
18:30–20:00
Лекция 1, Лекция Конференция в zoom, Онлайн видео
24 сентября
19:00–20:30
Лекция 2, Лекция Конференция в zoom, Онлайн видео
01 октября
19:00–20:30
Лекция 3, Лекция Конференция в zoom, Онлайн видео
08 октября
19:00–20:30
Лекция 4, Лекция Конференция в zoom, Онлайн видео
15 октября
19:00–20:30
Лекция 5, Лекция Конференция в zoom, Онлайн видео
22 октября
19:00–20:30
Лекция 6, Лекция Конференция в zoom, Онлайн видео
29 октября
19:00–20:30
Лекция 7, Лекция Конференция в zoom, Онлайн видео
05 ноября
19:00–20:30
Лекция 8, Лекция Конференция в zoom, Онлайн видео
12 ноября
19:00–20:30
Лекция 9, Лекция Конференция в zoom, Онлайн видео
26 ноября
19:00–20:30
Лекция 10, Лекция Конференция в zoom, Онлайн Нет