Изменения
Нет описания правки
# Оцените число итераций, которые вещественный двоичный поиск с условием цикла "L != M and R != M" делает в худшем случае при начальной инициализации L = L0, R = R0, если числа L0 и R0 одного знака.
# Оцените число итераций, которые вещественный двоичный поиск с условием цикла "L != M and R != M" делает в худшем случае при начальной инициализации L = L0, R = R0, если числа L0 и R0 разных знаков, или одно из них равно 0.
# Предложите алгоритм определения глубины сортирующей сети за $O(k)$, где $k$ - число компараторов.# Докажите или опровергните, что для любого заданного неотсортированного набора из 0 и 1 существует сеть компараторов, которая сортирует все наборы кроме заданного# Докажите или опровергните, что для любой перестановки чисел от 1 до $n$ существует сеть компараторов, которая сортирует все перестановки, кроме заданной# Постройте сортирующую сеть для 5 проводов с минимальным числом компараторов# Предложите сортирующую сеть с $O(n \log^2 n)$ компараторов. # Разберитесь в том, как устроена сортирующая сеть с $O(n \log n)$ компараторов и изложите это за 15 минут, чтобы общие идеи были ясны# Докажите, что сортирующая сеть имеет глубину $\Omega(\log n)$# Как найти $s$-й по величине элемент в куче при малых $s$?# Предложите массив, который при превращении в кучу с помощью алгоритма за $O(n)$ требует выполнить максимальное число обменов.# Предложите массив, из кучи в отсортированный массив требует выполнить максимальное число обменов.# В массиве есть $k$ элементов, для которых нарушено условие кучи. Преваритите массив в кучу за $k \log n$ действий# Докажите, что нельзя проверить, есть ли в куче два одинаковых элемента быстрее, чем за $\Omega(n \log n)$.
</wikitex>
