21 октября в Новосибирске пройдёт открытая лекция Рене ван Беверна «Рандомизированные алгоритмы. Как жить с вероятностью ошибки». Приглашаем в НГУ — ул. Пирогова д. 1, аудитория 4117, начало в 15:30 НСК (11:30 МСК). Планируется и онлайн-трансляция.
Регистрация: https://compscicenter.timepad.ru/event/1810962/
Рене Андреасович ван Беверн — заведующий лабораторией алгоритмики Новосибирского государственного университета, главный инженер проектов для новосибирского исследовательского центра Huawei, куратор направления Computer Science в CS центре в Новосибирске.
В информатике методы теории вероятностей встречаются в различных видах. На лекции мы посмотрим, для чего можно выгодно использовать случайность при построении алгоритмов. Увидим примеры, которые нам покажут общее свойство многих рандомизированных алгоритмов: они часто простые, порой даже такие простые, что до них сложно додуматься. С другой стороны мы увидим, что простота этих алгоритмов часто обусловлена их нетривиальным анализом: более сложные алгоритмы было бы слишком сложно анализировать.
Во второй части лекции мы ознакомимся с двумя главными видами рандомизированных алгоритмов: алгоритмы Монте-Карло и алгоритмы Лас-Вегас. А также поймём, как и какой ценой можно снизить вероятность ошибки и что малой вероятностью ошибки вполне можно пренебречь на фоне других рисков в жизни.