Алгоритмы и структуры данных поиска - тест 6

Какие существуют основные операции для отображений Map/Dictionary?

С помощью каких структур данных можно реализовать Map/Dictionary?

В каких случаях можно использовать прямую адресацию при реализации отображения?

Какая скорость чтения и записи для отображения, реализованного с помощью прямой адресации?

Что такое хэш-коллизия?

Какая хэш-функция называется совершенной?

Для метода цепочек, использующегося при разрешении коллизий в чем заключается основная идея?

Какие сложности у операций добавления и извлечения для метода цепочек?

Для метода открытой адресации при разрешении коллизий, какие действия предпринимаются если ячейка с вставляемым хэш-ключем уже занята?

Какая формула задает линейный способ просматривания ячеек хэш-таблицы?

Какая формула задает метод двойного хэширования для просматривания ячеек хэш-таблицы?

Для метода двойного хэширования, использующегося при разрешении коллизий в чем заключается основная идея?

Какое предположение должно быть выполнено, чтобы была справедлива гипотеза простого равномерного хэширования?

Пусть мы выполняем запрос Get для некоторого ключа k и пусть перед этим в структуру были вставлены некоторые ключи k1,...,kn. Для каждого ключа ki обозначим через Xi,j случайную величину, равную 1, если h(ki)=h(kj), и 0 в противном случае. Какая будет длина цепочки с индексом i?

Для независимых, равномерно распределенных на множестве {0, ..., m1} случайных величин для каждого ключа ki обозначим через Xi,j случайную величину, равную 1, если h(ki)=h(kj), и 0 в противном случае. Чему равно матожидание случайной величины?

Как вычисляется коэффициент заполнения для равномерно распределенной хэш-функции H: k -> {0,..., N-1}?

В предположении гипотезы простого равномерного хэширования, чему равно среднее время безуспешного поиска ключа для хэш-функции H: k -> {0,..., N-1}?

Каким значением ограничена вероятность коллизий для двух различных ключей для универсального семейства хэш-функций H: k -> {0,..., N-1}?

В случае универсального хэширования чему равно среднее время успешного поиска ключа для хэш-функции H: k -> {0,..., N-1}, если k1, ..., kn - все ключи, присутствующие в хеш-таблице?

Если использовать универсальное семейство хэш-функций для хранения n ключей, то при размере хэш-таблицы M = n2, какова будет вероятность получить хотя бы одну коллизию?

Каким должне быть минимальный размер хэш-таблицы, чтобы вероятность получить хотя бы одну коллизию не превосходила 1/2, если n - количество ключей?

При каких условия можно получить свободную от коллизий хэш-функцию?

Какие характеристики имеет совершенная хэш-функция?

Отметьте верные утверждения, относящиеся к семейству универсальных хэш-функций: Ha,b = ((a*k + b) mod p) mod m, b - произвольный вычет

Как зависит размер памяти, необходимый для реализании метода совершенного хэширования от количества ключей n?

За какое в среднем количество проб можно обнаружить хэш-функцию, не дающую коллизий для второго уровня схемы совершенного хэширования?

Пусть на первом уровне схемы совершенного хэширования используется хеш-таблица размера m = n, n - количество ключей. Пусть ni обозначает количество ключей, получивших (на первом уровне) хеш-значение i (0 <= i < m). Тогда если использовать в каждой ячейке первого уровня вышеописанную схему, свободную от коллизий, сколько потребуется дополнительной памяти?

Что означает ложно-положительное срабатывание для интерфейса множества с ошибками фильтр Блюма?

Для фильтра Блюма как изменяется вероятность ложного срабатывания с увеличением размера хранимого множества (числа вставленных элементов)?

Для фильтра Блюма как изменяется вероятность ложного срабатывания если объем памяти, заране заданный пользователем для хранения битового массива, увеличивается?

Какие существуют стандартные операции для интерфейса множества с ошибками, например для фильтра Блюма?

Какие допустимы ситуации для односторонней ошибки в интерфейсе множества с ошибками?

Отметьте верные утверждения, относящиеся к фильтру Блюма

Как можно проверить, попадает ли ключ k в хэш-таблицу T фильтра Блюма, заданного хэш-функциями h1,...,hs: k -> [0, m-1] или нет?

Как происходит вставка (Insert(k)) ключа k в таблицу T, реализованную фильтром Блюма?

Предположим, что мы вставили различные k1,...,kn ключей в хэш-таблицу Блюм-фильтра с помощью хэш-функций h1(k),...,hs(k): k -> [0, m-1]. Какая будет вероятность ложного положительного срабатывания?

Для Блюм-фильтра, заданного хэш-функциями h1(k),...,hs(k): k -> [0, m-1], какая будет вероятность того, что после вставки n ключей произвольно выбранный бит будет равен False?

Для Блюм-фильтра, заданного хэш-функциями h1(k),...,hs(k): k -> [0, m-1], какая будет вероятность того, что после вставки n ключей одна хэш-функция выдает значение, отличное от произвольно выбранного бита в таблице?

При реализации структуры приближенного множества (Lossy Map) с помощью более блюмового фильтра, как будет работать операция Get(k)?

Предположим, что при реализации структуры приближенное множество (Lossy Map) с помощью более блюмового фильтра функция отображает из ключей в один бит. Как можно реализовать такую структуру?

При реализации структуры приближенное множество (Lossy Map) с помощью двух Блюм-фильтров (использованных для множеств-прообразов 0 и 1) что нужно сделать, чтобы избежать ситуации, когда при запросе Get(k) оба Блюм-фильтра вернули 1?