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

Randomized Algorithms
Novosibirsk / spring 2021, посмотреть все семестры

Enroll in the course to get notifications and to be able to submit home assignments.
Register to enroll now Login

Вниманию дистанционных студентов: Время занятий показывается согласно вашим настройкам часового пояса в профиле. Начинаются занятия, как правило, в 14:10 по московскому времени.

Вниманию студентов ММФ НГУ: курс будет засчитан только один раз — либо как спецкурс КафТК ММФ, либо в CS центре.

Что такое рандомизированный алгоритм?

Рандомизированные алгоритмы в процессе своего исполнения подбрасывают монетку для принятия решений. Они разделяются на два основных вида. Алгоритмы Монте-Карло имеют гарантированную верхнюю оценку времени работы, но могут выдавать ложные результаты. Алгоритмы Лас-Вегас всегда выдают правильный ответ, но время их работы является случайной величиной (желательно с небольшим математическим ожиданием).

Для чего их используют?

Рандомизированные алгоритмы часто проще (для понимания и программирования), чем детерминированные алгоритмы, решающие одну и ту же задачу: например, минимальный разрез в графе можно легко найти с помощью рандомизированного алгоритма. Также бывает, что рандомизированные алгоритмы легко решают задачи, для которых неизвестны эффективные детерминированные алгоритмы, например задачу о проверке тождественности двух полиномов, с помощью которой можно построить простой и быстрый параллельный алгоритм для поиска совершенного паросочетания в графе.

Но они могут ошибиться, это ведь плохо?

Рандомизированные алгоритмы обладают тем удобным свойством, что для снижения вероятности ошибки их можно просто запускать несколько раз. Допустим, алгоритм даёт ложный ответ с вероятностью ⅓. Тогда его можно запустить 20 раз и вероятность ложного ответа будет меньше, чем вероятность разрушения компьютера ударом молнией во время исполнения алгоритма.

Пререквизиты:

  • Базовые знания теории вероятностей (студентам будет выдана памятка базовых понятий и используемых неравенств)
  • Базовые знания подходов к построению алгоритмов

Содержание курса:

  • Парадигмы построения рандомизированных алгоритмов
  • Подходы к анализу рандомизированных алгоритмов
  • Рандомизированные структуры данных
  • Алгебраические подходы
  • Онлайновые алгоритмы
  • Параллельные алгоритмы
  • Дерандомизация
  • Вероятностный метод доказательства
  • Границы рандомизированных алгоритмов

Будут показаны рандомизированные алгоритмы, превосходящие детерминированные аналоги по быстродействию или простоте, для задач

  • выполнимости Булевых формул
  • распознавания тождественных полиномов
  • перемножения матриц
  • сортировки
  • поиска подстроки
  • сбалансирования выборки
  • маршрутизации в коммуникационных сетях
  • распределения нагрузки
  • минимальных и максимальных разрезов в графах
  • совершенного паросочетания в графах
  • распознавания простых чисел

Из рандомизированных структур данных будут рассмотрены

  • хэш-таблицы

  • фильтры Блюма

Оценивание

Студенты ММФ НГУ в конце семестра будут сдавать устный экзамен в виде получасового научного разговора по содержанию курса. Разрешается использование литературы во время экзамена (опыт показывает, что она или не понадобится или не поможет :-) ).

Студентам CS Center оценка будет выставляться по результатам решения домашних заданий.

За 85% решённых задач выставляется оценка отлично,

за 75% — хорошо,

за 60% — зачёт.

Date and time Class|Name Venue|short Materials
10 February
14:10–15:45
Содержание курса, вводные примеры (в.т.ч. минимальный разрез в графе), Монте Карло, Лас Вегас, и как жить с вероятностью ошибки, Lecture НГУ, ауд. 5210, НГУ, новый корпус
17 February
14:10–15:45
Построение дерева двоичного разбиения пространства, вероятностный метод, неравенство Буля, Lecture НГУ, ауд. 5210, НГУ, новый корпус
24 February
14:10–15:45
Границы Чернова, маршрутизация пакетов по коммуникационной сети, Lecture НГУ, ауд. 5210, НГУ, новый корпус
03 March
14:10–15:45
Рандомизированные структуры данных, фильтры Блюма как в Google Chrome, Lecture НГУ, ауд. 5210, НГУ, новый корпус
10 March
14:10–15:45
Рандомизированные структуры данных, приближение Пуассана, Lecture НГУ, ауд. 5210, НГУ, новый корпус
17 March
14:10–15:45
Вероятностный метод и дерандомизация, Lecture НГУ, ауд. 5210, НГУ, новый корпус
24 March
14:10–15:45
Генерируй и меняй, локальная лемма Ловаса, Lecture НГУ, ауд. 5210, НГУ, новый корпус
07 April
14:10–15:45
Доказательство локальной леммы Ловаса, поиск подсроки алгоритмом Карпа-Рабина, Lecture НГУ, ауд. 5210, НГУ, новый корпус
14 April
14:10–15:45
Полиномиальные скользящие хэш-функции, параллельный алгоритм для существования совершенного паросочетания, Lecture НГУ, ауд. 5210, НГУ, новый корпус
21 April
14:10–15:45
Доказательство леммы Шварца-Зиппеля, изоляционная лемма, и теорема Валианта-Варизани, Lecture НГУ, ауд. 5210, НГУ, новый корпус
28 April
14:10–15:45
Параллельный алгоритм для построения паросочетаний, Lecture НГУ, ауд. 5210, НГУ, новый корпус
12 May
14:10–15:45
Нижние оценки трудоёмкости рандомизированных алгоритмов -- принцип Яо, Lecture НГУ, ауд. 5210, НГУ, новый корпус