Новосибирский государственный университет и CS центр приглашают на открытый курс Рене Андреасовича ван Беверна «Рандомизированные алгоритмы». Первое занятие пройдёт 10 февраля в 14:10 МСК.

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

Слушателям пригодятся базовые знания теории вероятностей и подходов к построению алгоритмов. В помощь будет выдана памятка базовых понятий и используемых неравенств.

Содержание курса:
— Обзор парадигм построения рандомизированных алгоритмов с примерами,
— Рандомизированные структуры данных (например, фильтры Блюма),
— Алгебраические подходы,
— Онлайновые алгоритмы,
— Вероятностный метод доказательства.

Занятия будут проходить по средам в 18:10 по Новосибирску с 10 февраля.
Зарегистрируйтесь для получения ссылок на трансляции лекций:
https://nsk.compsciclub.ru/courses/rand-algorithms/2021-spring/