Лекция 2. Двоичное разбиение пространства, вероятностный метод, неравенство Буля

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