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

Алгоритмы: дополнительные главы
Saint Petersburg / autumn 2020, посмотреть все семестры

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

Программа примерно соответствует курсу Advanced Algorithms для аспирантов университета Northwestern (Иллинойс, США).

Рандомизированные алгоритмы

  • Хэширование

  • Универсальные хэш функции

  • Фильтры Блума

  • Балансировка нагрузки — «the power of two choices»

  • Вероятности больших уклонений. Границы Бернштейна, Чернова и Хёфдинга

  • Permutation routing in the hypercube

  • Разбор одной задачи с собеседования на работу

Потоковые алгоритмы

  • Нахождение самого частого элемента в потоке
  • Алгоритм Misra–Gries
  • Count–Min Sketch
  • Подсчёт числа различных элементов в потоке
  • HyperLogLog

Онлайн алгоритмы

  • Задача о прокате лыж

  • Кэш LRU

  • Анализ LRU в модели «resource augmentation»

Динамические алгоритмы на графах

  • Ориентация ребер графа

Параметризованные алгоритмы

  • Введение в FPT алгоритмы

  • FPT алгоритм для задачи о самом длинном пути в графе

  • FPT алоритм для задачи о вершинном покрытии

Приближенные алгоритмы

  • Приближенный алгоритм для задачи о вершинном покрытии

  • Приближенный алгоритм для задачи о покрытии множествами

Линейное программирование

  • Введение в линейное программирование
  • Двойственность в линейном программировании
  • Условия Каруша – Куна – Таккера
  • Лемма Фаркаша и её физическая интерпретация
  • Доказательство леммы Фаркаша

Приложения линейного программирования

  • Минимальные разрезы и максимальные потоки в графах

Другие темы

  • Dimensionality reduction

  • Bourgain's Theorem

  • Cheeger's Inequality

  • Karger's algorithm

  • Principal component analysis

Date and time Class|Name Venue|short Materials
28 September
18:00–18:10
Краткий обзор курса, Lecture Заочный просмотр video,  files
28 September
18:10–18:20
Хеширование, Lecture Заочный просмотр video
28 September
18:20–18:30
Универсальные хэш функции, часть 1, Lecture Заочный просмотр video
28 September
18:30–18:40
Универсальные хэш функции, часть 2, Lecture Заочный просмотр video
09 October
20:00–21:30
Семинар 1, Seminar Конференция в zoom, Онлайн video
10 October
10:00–10:20
Совершенные хэш таблицы, Lecture Заочный просмотр video
10 October
10:20–10:40
Хэш функции применяемые на практике, Lecture Заочный просмотр video
10 October
10:40–11:00
Обсуждение задачи по программированию о равенстве двух можеств, Lecture Заочный просмотр video
11 October
12:00–12:10
Фильтры Блума. Часть 1, Lecture Онлайн, занятие в zoom video
11 October
12:10–12:20
Фильтры Блума. Часть 2, Seminar Онлайн, занятие в zoom video
16 October
20:00–21:30
Семинар 2, Seminar Онлайн, занятие в zoom video
19 October
19:30–20:00
Быстрая сортировка: анализ сложности, Lecture Заочный просмотр
19 October
20:00–20:30
Биномиальные коэффициенты, Seminar Заочный просмотр
19 October
20:30–21:00
Балансировка нагрузки — «the power of two choices». Часть 1, Seminar Заочный просмотр video
23 October
19:30–21:00
Семинар 3, Seminar Онлайн, занятие в zoom
30 October
19:30–21:00
Семинар 4, Seminar Онлайн, занятие в zoom
06 November
19:30–21:00
Семинар 5, Seminar Онлайн, занятие в zoom