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 Заочный просмотр video,  files
19 October
20:00–20:30
Биномиальные коэффициенты, Seminar Заочный просмотр video
19 October
20:30–21:00
Балансировка нагрузки — «the power of two choices». Часть I., Lecture Заочный просмотр video
23 October
19:30–21:00
Семинар 3, Seminar Онлайн, занятие в zoom video
29 October
19:30–21:00
The power of two choices. Часть II, Lecture Заочный просмотр video,  files
29 October
19:30–21:00
Доказательства вероятностных оценок для power of two choices, Lecture Заочный просмотр video,  files
30 October
19:30–21:00
Семинар 4, Seminar Онлайн, занятие в zoom video,  files
04 November
10:30–11:15
Оценки больших уклонений (Бернштейн, Хёфдинг, Чернов), Lecture Заочный просмотр video,  files
06 November
19:30–21:00
Семинар 5, Seminar Онлайн, занятие в zoom video
10 November
10:30–11:15
Случайная маршрутизация в гиперкубе, Lecture Заочный просмотр video
13 November
10:00–11:00
Азума - Хёфдинг для случайных величин (разбор задачи), Seminar Заочный просмотр video,  files
13 November
11:00–12:00
Неравенство Хёфдинга для мартингалов, Seminar Заочный просмотр video,  files
13 November
12:00–13:00
Нахождение частых элементов в потоке данных. Алгоритм Misra–Gries, Lecture Заочный просмотр video
13 November
19:30–21:00
Семинар 6, Seminar Онлайн, занятие в zoom video
20 November
19:30–21:00
Семинар 7, Seminar Онлайн, занятие в zoom video
24 November
10:00–11:00
Почему невозможен deterministic oblivious routing, Seminar Заочный просмотр
27 November
19:30–21:00
Алгоритм Count-Min Sketch, Lecture Заочный просмотр
04 December
20:30–22:00
Семинар 8 (ВРЕМЯ ИЗМЕНЕНО!), Seminar Онлайн, занятие в zoom
11 December
19:30–21:00
Семинар 10, Seminar Онлайн, занятие в zoom