City: Saint Petersburg Novosibirsk Kazan Language: Русский English

Fine-grained complexity
Saint Petersburg / autumn 2020, посмотреть все семестры

Enroll in the course to get notifications and to be able to submit home assignments.
Register to enroll now Login

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

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

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

  • несколько алгоритмов, которые исследователи пытались улучшить около полувека на самом деле оказались оптимальными. Этот список включает алгоритмы для задачи поиска наибольшей общей подпоследовательности и задачи нахождения редакционного расстояния.
  • для классических задач, таких как поиск всех кратчайших расстояний в графе или нахождения пары ортогональных векторов были найдены более быстрые алгоритмы.
Date and time Class|Name Venue|short Materials
17 September
18:30–20:00
Лекция 1, Lecture Конференция в zoom, Онлайн video
24 September
19:00–20:30
Лекция 2, Lecture Конференция в zoom, Онлайн No
01 October
19:00–20:30
Лекция 3, Lecture Конференция в zoom, Онлайн No
08 October
19:00–20:30
Лекция 4, Lecture Конференция в zoom, Онлайн No
15 October
19:00–20:30
Лекция 5, Lecture Конференция в zoom, Онлайн No
22 October
19:00–20:30
Лекция 6, Lecture Конференция в zoom, Онлайн No
29 October
19:00–20:30
Лекция 7, Lecture Конференция в zoom, Онлайн No
05 November
19:00–20:30
Лекция 8, Lecture Конференция в zoom, Онлайн No
12 November
19:00–20:30
Лекция 9, Lecture Конференция в zoom, Онлайн No
19 November
19:00–20:30
Лекция 10, Lecture Конференция в zoom, Онлайн No