Город: Санкт-Петербург Новосибирск Казань Язык: Русский English

Рандомизированные стурктуры данных, приближение Пуассана
Рандомизированные алгоритмы

Что: Лекция
Когда: Среда, 03 марта 2021, 18:10–19:45
Где: НГУ, ауд. 5210, НГУ, новый корпус

Описание

При анализе рандомизированных структурах данных часто возникает следующая проблема: например, для оценки времени отыскания элемента в хэш-таблице нужно знать, какое максимальное число элементов в ячейке хэш-таблицы. Однако уровни нагрузки ячеек хэш-таблицы зависимы друг от друга: если мы знаем, что в хэш-таблице хранится хотя бы один элемент и первые n-1 ячейки хэш-таблицы пустые, то n-ая ячейка пуста с вероятностью 0. Зависимость этих случайных величин мешает нам, например, оценить число пустых ячеек с помощью границ Чернова.

В этой лекции мы ознакомимся с приближением Пуассана: мы бпредположим, что уровни нагрузки ячеек --- независимые случайные величины с распределением Пуассана, и оценим ошибку, которую мы таким образом совершаем. Сделаем вывод, что чаще всего достаточно оценить алгоритм в модели Пуассана.