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

Рандомизированные алгоритмы
Новосибирск / весна 2021, посмотреть все семестры

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Оценивание

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

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

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

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

за 60% — зачёт.

Дата и время Занятие Место Материалы
10 февраля
18:10–19:45
Содержание курса, вводные примеры (в.т.ч. минимальный разрез в графе), Монте Карло, Лас Вегас, и как жить с вероятностью ошибки, Лекция НГУ, ауд. 5210, НГУ, новый корпус
17 февраля
18:10–19:45
Построение дерева двоичного разбиения пространства, вероятностный метод, неравенство Буля, Лекция НГУ, ауд. 5210, НГУ, новый корпус
24 февраля
18:10–19:45
Границы Чернова, маршрутизация пакетов по коммуникационной сети, Лекция НГУ, ауд. 5210, НГУ, новый корпус
03 марта
18:10–19:45
Рандомизированные структуры данных, фильтры Блюма как в Google Chrome, Лекция НГУ, ауд. 5210, НГУ, новый корпус
10 марта
18:10–19:45
Рандомизированные структуры данных, приближение Пуассана, Лекция НГУ, ауд. 5210, НГУ, новый корпус
17 марта
18:10–19:45
Вероятностный метод и дерандомизация, Лекция НГУ, ауд. 5210, НГУ, новый корпус
24 марта
18:10–19:45
Генерируй и меняй, локальная лемма Ловаса, Лекция НГУ, ауд. 5210, НГУ, новый корпус
07 апреля
18:10–19:45
Доказательство локальной леммы Ловаса, поиск подсроки алгоритмом Карпа-Рабина, Лекция НГУ, ауд. 5210, НГУ, новый корпус
14 апреля
18:10–19:45
Полиномиальные скользящие хэш-функции, параллельный алгоритм для существования совершенного паросочетания, Лекция НГУ, ауд. 5210, НГУ, новый корпус
21 апреля
18:10–19:45
Доказательство леммы Шварца-Зиппеля, изоляционная лемма, и теорема Валианта-Варизани, Лекция НГУ, ауд. 5210, НГУ, новый корпус
28 апреля
18:10–19:45
Параллельный алгоритм для построения паросочетаний, Лекция НГУ, ауд. 5210, НГУ, новый корпус
12 мая
18:10–19:45
Нижние оценки трудоёмкости рандомизированных алгоритмов — принцип Яо, Лекция НГУ, ауд. 5210, НГУ, новый корпус