Город: Санкт-Петербург Новосибирск Казань Язык: Русский English

Алгоритмы: дополнительные главы
Санкт-Петербург / осень 2020, посмотреть все семестры

Запишитесь на курс, чтобы получать уведомления и иметь возможность сдавать домашние задания. Для записи требуется регистрация на сайте.
Перейти к регистрации Войти

Программа примерно соответствует курсу 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

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