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

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

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

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

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

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

  • несколько алгоритмов, которые исследователи пытались улучшить около полувека на самом деле оказались оптимальными. Этот список включает алгоритмы для задачи поиска наибольшей общей подпоследовательности и задачи нахождения редакционного расстояния.
  • для классических задач, таких как поиск всех кратчайших расстояний в графе или нахождения пары ортогональных векторов были найдены более быстрые алгоритмы.
Дата и время Название Место Материалы
17 декабря
11:15–12:45
Лекция 1, лекция ПОМИ РАН Нет
17 декабря
12:55–14:25
Лекция 2, лекция ПОМИ РАН Нет
17 декабря
15:30–17:00
Лекция 3, лекция ПОМИ РАН Нет