1632
правки
Изменения
м
rollbackEdits.php mass rollback
# Использования памяти без инициализации. Задан массив $a[1..n]$. Требуется поддержать две операции: $set(i, x)$ и $get(i)$. Операция $set$ должна присваивать $i$-му элементу массива значение $x$. Операция $get$ должна возвращать последнее присвоенное $i$-му элементу значение, либо 0, если присвоения не было. При этом исходно массив заполнен произвольными данными. Разрешается завести $O(1)$ дополнительных массивов (также заполненных произвольным мусором) и реализовать все операции за истинное $O(1)$.
# Счетчик Кнута. Рассмотрим массив $a[0..n-1]$. Будем считать, что в каждом элементе может быть число 0, 1 или 2 и массив представляет собой число $a[0]+a[1]\cdot 2+a[2]\cdot 4 + \ldots + a[n-1]\cdot2^{n-1}$. Требуется реализовать операцию добавления $2^k$ к числу, представленному в массиве за истинное $O(1)$ и $O(n)$ дополнительной памяти.
# Реализуйте менеджер памяти, позволяющий выделять и возвращать блоки одинакого одинакового размера за $O(1)$ времени и $O(1)$ дополнительной памяти
# Предложите реализацию стека, которая дополнительно позволяет выполнить операцию "вернуть минимум значений в стеке"
# Стек с множественным извлечением. Добавим в стек операцию multipop(k), которая снимает вершины стека k элементов. Докажите, что амортизированная стоимость операции multipop равна $O(1)$. Сформулируйте окончательное доказательство с использованием метода потенциалов.
# Докажите, что в хешировании кукушки добавление выполняется в среднем за $O(1)$.
# Оцените среднюю длину максимального списка при разрешении конфликтов в хешировании с помощью метода списков. Пусть для хеширования $n$ элементов используются $n$ списков.
# Докажите, что $\sum\limits_{i=0}^n h(i) = O(n)$.
# Предложите обобщение дерева Фенвика на многомерный запрос
# Пусть операция в дереве Фенвика некоммутативна. Предложите модификацию, которая позволит использовать дерево Фенвика, время на запрос обновления $O(\log^2 n)$.
# Встречное дерево Фенвика. Пусть у операции в дереве Фенвика нет обратного. Будем хранить два дерева $f[i]$ и $g[i]$, где $f[i]$ - обычное дерево Фенвика, а $g[i]$ - сумма элементов с $a[i + 1]$ до $a[i + 2^{h(i)}]$. Предложите алгоритм выполнения операций изменения элемента и получения статистики на отрезке в получившемся дереве.
# Предложите реализацию операции удаления ключа в дереве Ван Эмде Боаса.
# Предложите модификацию дерева Ван Эмде Боаса, где и минимум и максимум хранятся отдельно, но не в детях.
</wikitex>
