Лекция 4. Рандомизированные структуры данных, фильтры Блюма

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