Лекция 5. Рандомизированные структуры данных, приближение Пуассона

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