Вниманию дистанционных студентов: Время занятий указывается по новосибирскому времени (МСК+4), то есть они начинаются, как правило, в 14:10 по московскому времени.
Вниманию студентов ММФ НГУ: курс будет засчитан только один раз — либо как спецкурс КафТК ММФ, либо в CS центре.
Рандомизированные алгоритмы в процессе своего исполнения подбрасывают монетку для принятия решений. Они разделяются на два основных вида. Алгоритмы Монте-Карло имеют гарантированную верхнюю оценку времени работы, но могут выдавать ложные результаты. Алгоритмы Лас-Вегас всегда выдают правильный ответ, но время их работы является случайной величиной (желательно с небольшим математическим ожиданием).
Рандомизированные алгоритмы часто проще (для понимания и программирования), чем детерминированные алгоритмы, решающие одну и ту же задачу: например, минимальный разрез в графе можно легко найти с помощью рандомизированного алгоритма. Также бывает, что рандомизированные алгоритмы легко решают задачи, для которых неизвестны эффективные детерминированные алгоритмы, например задачу о проверке тождественности двух полиномов, с помощью которой можно построить простой и быстрый параллельный алгоритм для поиска совершенного паросочетания в графе.
Рандомизированные алгоритмы обладают тем удобным свойством, что для снижения вероятности ошибки их можно просто запускать несколько раз. Допустим, алгоритм даёт ложный ответ с вероятностью ⅓. Тогда его можно запустить 20 раз и вероятность ложного ответа будет меньше, чем вероятность разрушения компьютера ударом молнией во время исполнения алгоритма.
Будут показаны рандомизированные алгоритмы, превосходящие детерминированные аналоги по быстродействию или простоте, для задач
Из рандомизированных структур данных будут рассмотрены
хэш-таблицы
фильтры Блюма
Студенты ММФ НГУ в конце семестра будут сдавать устный экзамен в виде получасового научного разговора по содержанию курса. Разрешается использование литературы во время экзамена (опыт показывает, что она или не понадобится или не поможет :-) ).
Студентам CS Center оценка будет выставляться по результатам решения домашних заданий.
За 85% решённых задач выставляется оценка отлично,
за 75% — хорошо,
за 60% — зачёт.
Date and time | Class|Name | Venue|short | Materials |
---|---|---|---|
10 February 18:10–19:45 |
Содержание курса, вводные примеры (в.т.ч. минимальный разрез в графе), Монте Карло, Лас Вегас, и как жить с вероятностью ошибки, Lecture | НГУ, ауд. 5210, НГУ, новый корпус | |
17 February 18:10–19:45 |
Построение дерева двоичного разбиения пространства, вероятностный метод, неравенство Буля, Lecture | НГУ, ауд. 5210, НГУ, новый корпус | |
24 February 18:10–19:45 |
Границы Чернова, маршрутизация пакетов по коммуникационной сети, Lecture | НГУ, ауд. 5210, НГУ, новый корпус | |
03 March 18:10–19:45 |
Рандомизированные стурктуры данных, приближение Пуассана, Lecture | НГУ, ауд. 5210, НГУ, новый корпус | |
10 March 18:10–19:45 |
Рандомизированные структуры данных, фильтры Блюма как в Google Chrome, Lecture | НГУ, ауд. 5210, НГУ, новый корпус |