Город: Санкт-Петербург Новосибирск Казань Язык: Русский 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–21:00
Быстрая сортировка: анализ сложности, Лекция Заочный просмотр
23 октября
19:30–21:00
Семинар 3, Семинар Онлайн, занятие в zoom
30 октября
19:30–21:00
Семинар 4, Семинар Онлайн, занятие в zoom
06 ноября
19:30–21:00
Семинар 5, Семинар Онлайн, занятие в zoom