Лекция 3. Границы Чернова, маршрутизация пакетов по коммуникационной сети

Лекция №3 курса «Рандомизированные алгоритмы», весна 2021 (Новосибирск). Введём ещё одно базовое средство анализа рандомизированных алгоритмов: границы Чернова. Они говорят нам о том, что сумма независимых друг от друга случайных 0/1-величин существенно отклоняются от ожидаемого значения лишь с очень маленькой вероятностью. Подробное описание занятия: