Вниманию дистанционных студентов: Время занятий указывается по новосибирскому времени (МСК+4), то есть они начинаются, как правило, в 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 |
Рандомизированные стурктуры данных, приближение Пуассана, Лекция | НГУ, ауд. 5210, НГУ, новый корпус | |
10 марта 18:10–19:45 |
Рандомизированные структуры данных, фильтры Блюма как в Google Chrome, Лекция | НГУ, ауд. 5210, НГУ, новый корпус |