Обратите внимание, что время начала указано по Новосибирску, +4 часа к часовому поясу Москвы.

Рене ван Беверн — заведующий лабораторией алгоритмики Новосибирского государственного университета, главный инженер проектов для новосибирского исследовательского центра Huawei, куратор направления Computer Science в CS центре в Новосибирске.

В информатике методы теории вероятностей встречаются в различных видах. На лекции мы посмотрим, для чего можно выгодно использовать случайность при построении алгоритмов. Увидим примеры, которые нам покажут общее свойство многих рандомизированных алгоритмов: они часто простые, порой даже такие простые, что до них сложно додуматься. С другой стороны мы увидим, что простота этих алгоритмов часто обусловлена их нетривиальным анализом: более сложные алгоритмы было бы слишком сложно анализировать.

Во второй части лекции мы ознакомимся с двумя главными видами рандомизированных алгоритмов: алгоритмы Монте-Карло и алгоритмы Лас-Вегас. А также поймём, как и какой ценой можно снизить вероятность ошибки и что малой вероятностью ошибки вполне можно пренебречь на фоне других рисков в жизни.