Вниманию дистанционных студентов: Время занятий указывается по новосибирскому времени (МСК+4), то есть они начинаются, как правило, в 14:10 по московскому времени.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Оценивание

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

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

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

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

за 60% — зачёт.