Вниманию дистанционных студентов: Время занятий показывается согласно вашим настройкам часового пояса в профиле. Начинаются занятия, как правило, в 14:10 по московскому времени.
Вниманию студентов ММФ НГУ: курс будет засчитан только один раз — либо как спецкурс КафТК ММФ, либо в CS центре.
Рандомизированные алгоритмы в процессе своего исполнения подбрасывают монетку для принятия решений. Они разделяются на два основных вида. Алгоритмы Монте-Карло имеют гарантированную верхнюю оценку времени работы, но могут выдавать ложные результаты. Алгоритмы Лас-Вегас всегда выдают правильный ответ, но время их работы является случайной величиной (желательно с небольшим математическим ожиданием).
Рандомизированные алгоритмы часто проще (для понимания и программирования), чем детерминированные алгоритмы, решающие одну и ту же задачу: например, минимальный разрез в графе можно легко найти с помощью рандомизированного алгоритма. Также бывает, что рандомизированные алгоритмы легко решают задачи, для которых неизвестны эффективные детерминированные алгоритмы, например задачу о проверке тождественности двух полиномов, с помощью которой можно построить простой и быстрый параллельный алгоритм для поиска совершенного паросочетания в графе.
Рандомизированные алгоритмы обладают тем удобным свойством, что для снижения вероятности ошибки их можно просто запускать несколько раз. Допустим, алгоритм даёт ложный ответ с вероятностью ⅓. Тогда его можно запустить 20 раз и вероятность ложного ответа будет меньше, чем вероятность разрушения компьютера ударом молнией во время исполнения алгоритма.
Будут показаны рандомизированные алгоритмы, превосходящие детерминированные аналоги по быстродействию или простоте, для задач
Из рандомизированных структур данных будут рассмотрены
хэш-таблицы
фильтры Блюма
Студенты ММФ НГУ в конце семестра будут сдавать устный экзамен в виде получасового научного разговора по содержанию курса. Разрешается использование литературы во время экзамена (опыт показывает, что она или не понадобится или не поможет :-) ).
Студентам CS Center оценка будет выставляться по результатам решения домашних заданий.
За 85% решённых задач выставляется оценка отлично,
за 75% — хорошо,
за 60% — зачёт.