Дополнительные главы алгоритмов
Санкт-Петербург / осень 2018, посмотреть все семестры

Это курс по алгоритмам для тех, кто уже что-то знает про алгоритмы. Мы постараемся поглубже разобраться как работают основные алгоритмы и структуры данных, а также изучим несколько алгоритмов посложнее.

Практика по курсу будет разбита на две части: решение теоретических задач и задач на программирование.

Для начала прохождения курса вы должны знать следующие темы:

  • Анализ времени работы алгоритмов, амортизационный анализ
  • Базовые структуры данных: двоичная куча, дерево отрезков, дерево поиска
  • Базовые алгоритмы на графах: обход в глубину, обход в ширину
  • Базовые алгоритмы на строках: КМП, хеши

Примерное содержание курса:

  • Cтруктуры данных: кучи, дерево отрезков, дерево поиска
  • Запросы на деревьях
  • Декомпозиция графа
  • Кратчайшие пути в графах
  • Игры на графах
  • Потоки, паросочетания
  • Алгоритмы на строках
  • Быстрое преобразование Фурье

Оценка будет складываться из:

  • Теоретические задачи (50%)
  • Задачи на программирование (50%)
Дата и время Название Место Материалы
14 сентября
18:30–19:50
Кучи, лекция Таймс, ауд. с белыми досками Нет
14 сентября
20:00–21:20
Семинар, семинар Таймс, ауд. с белыми досками Нет
21 сентября
18:30–19:50
Дерево отрезков, лекция Таймс, ауд. с белыми досками Нет
21 сентября
20:00–21:20
Семинар, семинар Таймс, ауд. с белыми досками Нет
28 сентября
18:30–19:50
Дерево поиска, лекция Таймс, ауд. с белыми досками Нет
28 сентября
20:00–21:30
Семинар, семинар Таймс, ауд. с белыми досками Нет
05 октября
18:30–19:50
LCA + RMQ, LA, лекция Таймс, ауд. с белыми досками Нет
05 октября
20:00–21:20
Семинар, семинар Таймс, ауд. с белыми досками Нет
12 октября
18:30–19:50
Heavy-Light декомпозиция, Link-cut дерево, лекция Таймс, ауд. с белыми досками Нет
12 октября
20:00–21:20
Семинар, семинар Таймс, ауд. с белыми досками Нет
19 октября
18:30–19:50
Центроидная декомпозиция, лекция Таймс, ауд. с белыми досками Нет
19 октября
20:00–21:20
Семинар 6, семинар Таймс, ауд. с белыми досками Нет
26 октября
18:30–19:50
Euler Tour Tree, динамическая связность, лекция Таймс, ауд. с белыми досками Нет
26 октября
20:00–21:20
Семинар 7, семинар Таймс, ауд. с белыми досками Нет
02 ноября
18:30–19:50
Мосты, точки сочленения, компоненты сильной связности, лекция Таймс, ауд. с белыми досками Нет
02 ноября
20:00–21:20
Семинар, семинар Таймс, ауд. с белыми досками Нет
09 ноября
18:30–19:50
2-SAT, Эйлеров цикл, лекция Таймс, ауд. с белыми досками Нет
09 ноября
20:00–21:20
Семинар, семинар Таймс, ауд. с белыми досками Нет
16 ноября
18:30–19:50
Минимальное остовное дерево, лекция Таймс, ауд. с белыми досками другие
16 ноября
20:00–21:20
Семинар, семинар Таймс, ауд. с белыми досками Нет
23 ноября
18:30–19:50
Игры на графах, лекция Таймс, ауд. с белыми досками Нет
23 ноября
20:00–21:20
Семинар, семинар Таймс, ауд. с белыми досками Нет
30 ноября
18:30–19:50
Невошедшее, лекция Таймс, ауд. с белыми досками Нет
07 декабря
18:30–19:50
Бонусная лекция, лекция Таймс, ауд. с белыми досками Нет