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