Изменения
Нет описания правки
# Укажите способ для любого детерминированного алгоритма выбора разделяющего элемента построить массив, на котором алгоритм QSort работает за $\Omega(n^2)$
# Модифицируйте рандомизированный алгоритм QSort, чтобы искать $k$-й по величине элемент в массиве за время $O(n)$ в среднем
# Докажите или опровергните, что для любого заданного неотсортированного набора из 0 и 1 существует сеть компараторов, которая сортирует все наборы кроме заданного
# Докажите или опровергните, что для любой перестановки чисел от 1 до $n$ существует сеть компараторов, которая сортирует все перестановки, кроме заданной
# Постройте сортирующую сеть для 5 проводов с минимальным числом компараторов
# Предложите сортирующую сеть с $O(n \log^2 n)$ компараторов.
# Разберитесь в том, как устроена сортирующая сеть с $O(n log n)$ компараторов и изложите это за 15 минут, чтобы общие идеи были ясны
# Докажите, что сортирующая сеть имеет глубину $\Omega(log n)$
# Задан массив, полученный циклическим сдвигом из отсортированного по возрастанию. Все элементы массива различны. Требуется за $O(\log n)$ найти в нем заданный элемент. Предложите способ или докажите, что это невозможно.
# Задан массив, полученный приписыванием одного отсортированного по возрастанию массива в конец другому отсортированному по возрастанию. Все элементы массива различны. Требуется за $O(\log n)$ найти в нем заданный элемент.
# Задан массив, полученный приписыванием отсортированного по убыванию массива в конец отсортированному по возрастанию. Все элементы массива различны. Требуется за $O(\log n)$ найти в нем заданный элемент.
# Задан массив, полученный приписыванием отсортированного по убыванию массива в конец отсортированному по возрастанию и затем циклическим сдвигом получившегося массива. Все элементы массива различны. Требуется за $O(\log n)$ найти в нем заданный элемент.
