Изменения
Новая страница: «<wikitex> = Алгоритмы и структуры данных, 1 семестр = # Можно ли построить структуру данных, с д...»
<wikitex>
= Алгоритмы и структуры данных, 1 семестр =
# Можно ли построить структуру данных, с двумя видами операций, одна из которых работает за истинное $O(2^n)$, а вторая за истинное $O(\log{n})$, и при этом амортизированное время работы обеих операций $O(1)$. Почему?
# Можно ли построить структуру данных, с двумя видами операций, одна из которых работает за истинное $O(\sqrt{n})$, а вторая за истинное $\Theta(\log{n})$, и при этом амортизированное время работы обеих операций $O(1)$. Почему?
# Пусть структура данных выполняет два типа запросов. Первый тип запроса выполняется за $O(f(s) k \log{k})$, а второй {{---}} за $O(\frac{g(s)}{k \sqrt{k}})$, причем значение $k$ можно выбрать любым натуральным числом, а $f(s)$ и $g(s)$ известны и зависят от размера структуры данных. Вам стало известно, что к структуре данных сделают $n$ запросов первого типа, и $m$ запросов второго типа. Какое $k$ нужно выбрать, чтобы среднее время работы запросов было минимальным.
# Проанализировать саморасширяющийся массив, если расширение происходит в $A$ раз ($1 < A$)
# Проанализировать стек на саморасширяющемся массиве, если при полном заполнении происходит увеличение в 2 раза, а при заполнении менее чем на 1/4 - сужение в 2 раза с помощью метода потеницалов. Потенциал должен зависеть только от текущего состояния стека (размера выделенного массива и числа заполненных элементов) и не должен зависеть от истории операций.
# Проанализировать стек на саморасширяющемся массиве, если при полном заполнении происходит увеличение в A раз, а при заполнении менее чем на B - сужение в C раз
# Разработать вектор с добавлением/удалением с истинной стоимостью всех операций $O(\log n)$.
# Разработать вектор с добавлением/удалением с истинной стоимостью всех операций $O(1)$.
# В массиве есть элемент, который встречается хотя бы $n/2$ раз. Требуется найти его за $O(n)$ с $O(1)$ дополнительной памяти
# Использования памяти без инициализации. Задан массив $a[1..n]$. Требуется поддержать две операции: $set(i, x)$ и $get(i)$. Операция $set$ должна присваивать $i$-му элементу массива значение $x$. Операция $get$ должна возвращать последнее присвоенное $i$-му элементу значение, либо 0, если присвоения не было. При этом исходно массив заполнен произвольными данными. Разрешается завести $O(1)$ дополнительных массивов (также заполненных произвольным мусором) и реализовать все операции за истинное $O(1)$.
</wikitex>
= Алгоритмы и структуры данных, 1 семестр =
# Можно ли построить структуру данных, с двумя видами операций, одна из которых работает за истинное $O(2^n)$, а вторая за истинное $O(\log{n})$, и при этом амортизированное время работы обеих операций $O(1)$. Почему?
# Можно ли построить структуру данных, с двумя видами операций, одна из которых работает за истинное $O(\sqrt{n})$, а вторая за истинное $\Theta(\log{n})$, и при этом амортизированное время работы обеих операций $O(1)$. Почему?
# Пусть структура данных выполняет два типа запросов. Первый тип запроса выполняется за $O(f(s) k \log{k})$, а второй {{---}} за $O(\frac{g(s)}{k \sqrt{k}})$, причем значение $k$ можно выбрать любым натуральным числом, а $f(s)$ и $g(s)$ известны и зависят от размера структуры данных. Вам стало известно, что к структуре данных сделают $n$ запросов первого типа, и $m$ запросов второго типа. Какое $k$ нужно выбрать, чтобы среднее время работы запросов было минимальным.
# Проанализировать саморасширяющийся массив, если расширение происходит в $A$ раз ($1 < A$)
# Проанализировать стек на саморасширяющемся массиве, если при полном заполнении происходит увеличение в 2 раза, а при заполнении менее чем на 1/4 - сужение в 2 раза с помощью метода потеницалов. Потенциал должен зависеть только от текущего состояния стека (размера выделенного массива и числа заполненных элементов) и не должен зависеть от истории операций.
# Проанализировать стек на саморасширяющемся массиве, если при полном заполнении происходит увеличение в A раз, а при заполнении менее чем на B - сужение в C раз
# Разработать вектор с добавлением/удалением с истинной стоимостью всех операций $O(\log n)$.
# Разработать вектор с добавлением/удалением с истинной стоимостью всех операций $O(1)$.
# В массиве есть элемент, который встречается хотя бы $n/2$ раз. Требуется найти его за $O(n)$ с $O(1)$ дополнительной памяти
# Использования памяти без инициализации. Задан массив $a[1..n]$. Требуется поддержать две операции: $set(i, x)$ и $get(i)$. Операция $set$ должна присваивать $i$-му элементу массива значение $x$. Операция $get$ должна возвращать последнее присвоенное $i$-му элементу значение, либо 0, если присвоения не было. При этом исходно массив заполнен произвольными данными. Разрешается завести $O(1)$ дополнительных массивов (также заполненных произвольным мусором) и реализовать все операции за истинное $O(1)$.
</wikitex>
