Новосибирский государственный университет и CS центр приглашают на
открытый курс Рене Андреасовича ван Беверна «Рандомизированные
алгоритмы». Первое занятие пройдёт 10 февраля в 14:10 МСК.
Курс будет интересен как теоретикам, так и прикладным программистам:
рандомизированные алгоритмы часто быстрее и проще для понимания и
реализации, чем детерминированные. Они могут ошибаться, так как в
процессе своего исполнения подбрасывают монетку для принятия решений.
Однако для снижения вероятности ошибки их можно просто запускать
несколько раз. Таким образом можно получать вероятность ложного ответа
меньше, чем вероятность разрушения компьютера ударом молнией во время
исполнения алгоритма.
Слушателям пригодятся базовые знания теории вероятностей и подходов к
построению алгоритмов. В помощь будет выдана памятка базовых понятий и
используемых неравенств.
Содержание курса:
— Обзор парадигм построения рандомизированных алгоритмов с примерами,
— Рандомизированные структуры данных (например, фильтры Блюма),
— Алгебраические подходы,
— Онлайновые алгоритмы,
— Вероятностный метод доказательства.
Занятия будут проходить по средам в 14:10 по Москве с 10 февраля.
Зарегистрируйтесь для получения ссылок на трансляции лекций:
https://nsk.compsciclub.ru/courses/rand-algorithms/2021-spring/
(на сайте у этого курса время указано по Новосибирску)
Саша
--
Alexander V. Smal
St. Petersburg Department of Steklov Mathematical Institute
27 Fontanka, St. Petersburg, 191023, Russia