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

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