Изменения
Нет описания правки
# Докажите, что математическое ожидание глубины вершины в декартовом дереве есть $O(\log n)$
# Докажите, что математическое ожидание глубины самого глубокого листа в декартовом дереве есть $O(\log n)$
# Какой размер множества одинаковых равномерно распределенных от 1 до $n$ независимых случайных величин необходимо, чтобы вероятность того, что две из них принимают одинаковое значение, была хотя бы $1/2$? Сделайте вывод о вероятности коллизий в хеш-таблице с игнорированием коллизий.
# Пусть для хеширования строк используется полиномиальный хеш: $h(s) = (s[0]t^{n-1} + s[1]t^{n-2} + ... + s[n - 2]t + s[n-1]) \bmod 2^k$. Покажите, что в строке Туе-Морса есть много различных подстрок с одинаковым хеш-значением для любого $t$
# Пусть для хеширования строк используется полиномиальный хеш: $h(s) = (s[0]t^{n-1} + s[1]t^{n-2} + ... + s[n - 2]t + s[n-1]) \bmod r$. Предложите способ получения двух строк с одинаковым значением $h$ для заданных $t$ и $r$
# Пусть для хеширования строк используется полиномиальный хеш: $h(s) = (s[0]t^{n-1} + s[1]t^{n-2} + ... + s[n - 2]t + s[n-1]) \bmod r$. Покажите, что для достаточно большого $n$ существуют две различные строки длины $n$, которые отличаются в константном числе позиций, но имеющие одинаковое хеш-значение
# Предложите алгоритм удаления из хеш-таблицы с разрешением конфликтов с помощью открытой адресации, который не использует пометок "удалено", а действительно удаляет элемент из таблицы
# Пусть при хешировании используется разрешение конфликтов с открытой адресацией, размер хеш-пространства равено $cn$, где $n$ - число элементов. Оцените среднюю длину кластера (участка из подряд идущих занятых ячеек)
# Универсальное семейство $H$ хеш функций обладает свойством попарной независимости, если для любых двух злементов $x$ и $y$ и любых двух хеш-значений $a$ и $b$ вероятность того, что $h(x) = a$ и $h(x) = b$ есть $1/m^2 + o(1 / m^2)$ (вероятность берется по случайному выбору хеш-функции из множества $H$). Докажите, что приведенная на лекции конструкция семейства $H = \{ (ax + b) \bmod p \bmod m \}$ обладает этим свойством.
# Приведите пример универсального семейства хеш-функций для множества натуральных чисел, при вычислении хеш-функций в котором не используются операции деления и взятия по модулю. Достаточно $O(1/m)$-универсальности
# Оцените вероятность неудачи при добавлении элемента в хешировании кукушки.
# Докажите, что в хешировании кукушки добавление выполняется в среднем за $O(1)$.
# Оцените среднюю длину максимального списка при разрешении конфликтов в хешировании с помощью метода списков. Пусть для хеширования $n$ элементов используются $n$ списков.
</wikitex>
