Лекция 1. Рандомизированные алгоритмы. Как жить с вероятностью ошибки

Лекция №1 курса «Рандомизированные алгоритмы», весна 2021 (Новосибирск). На первой лекции курса мы поймём, для чего можно выгодно использовать случайность при построении алгоритмов --- посмотрим парадигмы построения рандомизированных алгоритмов. Мы увидим первые примеры, которые нам покажут общее свойство многих рандомизированных алгоритмов, мы увидим, что простота этих алгоритмов часто обусловлена их нетривиальным анализом: более сложные алгоритмы было бы слишком сложно анализировать. Мы ознакомимся с двумя главными видами рандомизированных алгоритмов: алгоритмы Монте-Карло, алгоритмы Лас-Вегас. В итоге мы увидим, как и какой ценой можно снизить вероятность ошибки и что малой вероятностью ошибки вполне можно пренебречь на фоне других рисков в жизни. Преподаватель курса: Рене Андреасович ван Беверн, заведующий лабораторией алгоритмики ММФ НГУ, старший преподаватель ММФ НГУ. Подробное описание занятия: