Дискретная математика, алгоритмы и структуры данных, 2 семестр

Постройте массив, в котором сортировка выбором делает максимальное число обменов
Предложите алгоритм, который вычисляет число обменов, которое делает сортировка выбором, за $O(n \log n)$.
Найдите минимальное число сравнений для сортировки 4 элементов
Найдите минимальное число сравнений для сортировки 5 элементов
Постройте массив, в котором сортировка слиянием делает максимальное число сравнений элементов
Укажите способ посчитать число массивов, в которых сортировка слиянием делает максимальное число сравнений элементов
Предложите алгоритм слияния массива, состоящего из двух последовательно расположенных отсортированных фрагментов за $O(n)$ с использованием $O(\sqrt{n})$ дополнительной памяти
Предложите алгоритм слияния массива, состоящего из двух последовательно расположенных отсортированных фрагментов за $O(n)$ с использованием $O(1)$ дополнительной памяти
Укажите способ для алгоритма QSort с выбором среднего элемента в качестве элемента построить массив, на котором происходит максимальное число сравнений элементов
Укажите способ для любого детерминированного алгоритма выбора разделяющего элемента построить массив, на котором алгоритм QSort работает за $\Omega(n^2)$
Докажите, что с использованием только сравнений элементов нельзя выяснить, есть ли в массиве два одинаковых элемента быстрее, чем за $\Omega(n \log n)$
Предложите алгоритм сортировки циклических сдвигов заданного массива с $n$ элементами, каждый из которых от 1 до $n$, за $O(n^2)$. Циклические сдвиги представлять единственным числом: номером первого элемента в исходном массиве.
Предложите алгоритм сортировки циклических сдвигов заданного массива с $n$ элементами, каждый из которых от 1 до $n$, за $O(n \log n)$. Циклические сдвиги представлять единственным числом: номером первого элемента в исходном массиве. Указание: зная порядок на подстроках длины $L$ порядок на подстроках длины $2L$ можно восстановить за $O(n)$.
Пусть известно, что массив длины $n$ из чисел от 1 до $n$ получен с помощью генератора случайных чисел, каждое число независимо получено с помощью равномерного распределения. Предложите модификацию алгоритма сортировки подсчетом, который сортирует данный массив за $O(n)$ используя лишь $O(\sqrt{n})$ дополнительной памяти (обе оценки должны выполняться в среднем).
Задан массив, полученный циклическим сдвигом из отсортированного по возрастанию. Все элементы массива различны. Требуется за $O(\log n)$ найти в нем заданный элемент.
Задан массив, полученный приписыванием одного отсортированного по возрастанию массива в конец другому отсортированному по возрастанию. Все элементы массива различны. Требуется за $O(\log n)$ найти в нем заданный элемент.
Задан массив, полученный приписыванием отсортированного по убыванию массива в конец отсортированному по возрастанию. Все элементы массива различны. Требуется за $O(\log n)$ найти в нем заданный элемент.
Задан массив, полученный приписыванием отсортированного по убыванию массива в конец отсортированному по возрастанию и затем циклическим сдвигом получившегося массива. Все элементы массива различны. Требуется за $O(\log n)$ найти в нем заданный элемент.
Пусть выполняется целочисленный двоичный поиск с начальными значениями L = 0, R = $2^k$. Преложите алгоритм определения за $O(1)$ по заданным значениям L и R, могут ли они возникнуть в процессе двоичного поиска.
Пусть выполняется целочисленный двоичный поиск с начальными значениями L = 0, R = $n$. Преложите алгоритм определения за $O(\log n)$ по заданным значениям L и R, могут ли они возникнуть в процессе двоичного поиска.
Оцените число итераций, которые вещественный двоичный поиск с условием цикла "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)$.
Проанализировать саморасширяющийся массив, если расширение происходит в $A$ раз ($1 < A$)
Проанализировать стек на саморасширяющемся массиве, если при полном заполнении происходит увеличение в 2 раза, а при заполнении менее чем на 1/4 - сужение в 2 раза с помощью метода потеницалов. Потенциал должен зависеть только от текущего состояния стека (размера выделенного массива и числа заполненных элементов) и не должен зависеть от истории операций.
Проанализировать стек на саморасширяющемся массиве, если при полном заполнении происходит увеличение в A раз, а при заполнении менее чем на B - сужение в C раза
Разработать вектор с добавлением/удалением с истинной стоимостью всех операций $O(\log n)$.
Задан односвязный список, каждый элемент знает следующий после себя. При этом возможно, что на самом деле список зацикливается (один из элементов ссылается как на следующий на элемент, который уже встречался в списке перед ним). Требуется проверить, зацикливается ли заданный односвязный список за $O(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)$.
Счетчик Кнута. Рассмотрим массив $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)$. Сформулируйте окончательное доказательство с использованием метода потенциалов.
Продемонстрируйте, как просимулировать очередь на двух стеках. Амортизированная стоимость операций push и pop должна быть $O(1)$.
Предложите реализацию очереди, которая дополнительно позволяет выполнить операцию "вернуть минимум значений в очереди". Амортизированная стоимость всех операций должна быть $O(1)$.
Можно ли реализовать два стека на очереди (ограничений на время выполнения операций нет)?
В $d$-куче выполняется $m$ операций decreaseKey и $n$ операций extractMin. Какое оптимальное асимптотически $d$ следует выбрать?
В $d$-куче выполняется $m$ операций decreaseKey и $n$ операций extractMin. Время выполнения decreaseKey - $C_1 \log n$, а extractMin - $C_2 d \log n$. Какое $d$ следует выбрать?
Пусть подряд выполняется $n$ операций insert в пустую биномиальную кучу. Какое среднее время операции?
Как можно модифицировать биномиальную кучу, чтобы insert выполнялось за истиное $O(1)$, а амортизированная стоимость остальных операций не поменялась?
Тонкие кучи. Будем называть дерево "тонким", если оно может быть получено из биномиального удалением у некоторых вершин ребенка максимального ранга. Тонкой кучей называется коллекция тонких деревьев. Ограничений на число деревьев одного ранга нет. Разработайте операции merge и extractMin для тонких куч. Амортизированная стоимость операции extractMin должна быть $O(\log n)$. Амортизированная стоимость операции merge должна быть $O(1)$.
Разработайте операцию decreaseKey для тонкой кучи. Докажите, что амортизированное время выполнения есть $O(1)$ (используйте потенциал $2M + T$, где $M$ - число вершин, у которых удалили ребенка)
Докажите, что операция decreaseKey в тонкой куче из предыдущего задания выполняется за истиные $O(\log n)$
Ускорение extractMin. Докажите, что в тонкой куче можно добиться истинного $O(\log n)$ на extractMin, если обрабатывать корневой список, сливая деревья разных рангов, как при extractMin каждый раз, когда в корневом списке становится хотя бы $2\log n$ элементов.
Предложите алгоритм удаления из АВЛ-дерева.
Предложите алгоритм добавления в красно-черное дерево
Предложите алгоритм удаления из красно-черного дерева
Статически оптимальное дерево поиска: пусть заданы ключи и известно для каждого ключа, сколько раз его потребуется искать: $p[i]$. Требуется построить дерево поиска, чтобы суммарное время доступа ко всем ключам было минимально.
Предложите алгоритм слияния двух АВЛ-деревьев, при том, что в первом дереве все ключи меньше, чем во втором за $O(\log n)$
Предложите алгоритм разделения АВЛ-дерева на два, где в первом дереве все ключи меньше или равны заданному $x$, а во втором - больше, за $O(\log n)$
В АВЛ-дереве находятся вершины с ключами от 1 до $n$. Какие ключи могут быть в корне?
В красно-черном дереве находятся вершины с ключами от 1 до $n$. Какие ключи могут быть в корне?
Предложите реализацию АВЛ-дерева, в которой в каждом узле хранится $O(1)$ бит
Перекошенное сбалансированное дерево. Дерево называется перекошенным сбалансированным, если у каждой вершины разность высоты левого и правого поддерева 0, 1 или 2. Предолжите реализацию операций вставки и удаления для перекошенного сбалансированного дерева.
Мальчик Петя считает, что если в дереве поиска можно хранить несколько одинаковых ключей, то на пути от одного такого ключа до другого не может быть ключей с другим значением. Тогда можно легко найти все такие ключи. Прав ли он?
Пусть заданы наборы ключей $(x_1, x_2, ..., x_n)$ и $(y_1, y_2, ..., y_n)$, где все $x$-ы и все $y$-и различны. Докажите, что существует единственное декартово дерево с набором ключей в вершинах $(x_i, y_i)$
В условиях предыдущей задачи пусть $x_1 < x_2 < .. < x_n$, покажите как построить декартово дерево за $O(n)$
Петя предлагает сделать гибрид декартового дерева и сплей-дерева: при доступе к ключу в декартовом дереве удалять его и добавлять заново с приоритетом меньше текущего минимального. Что у него получилось?
Проведите анализ случай zig для сплей-дерева по аналогии с случаем zig-zag, рассмотренном на лекции
Проведите анализ случай zig-zig для сплей-дерева по аналогии с случаем zig-zag, рассмотренном на лекции
Статическая оптимальность сплей-дерева. Докажите, что если к ключам $1, ..., n$, сложенным в сплей-дерево выполняется m запросов, к $i$-му ключу осуществляется $k_i$ запросов, где $k_i > 0$, то суммарное время работы не превышает $O(m H(p_1, p_2, .., p_n))$, где $p_i = k_i / m$, $H$ - шенноновская энтропия
Постройте пример сплей-дерева, содержащего не менее 6 вершин, которое после выполнения операции splay для одного из самых глубоких листьев становится бамбуком
Постройте пример сплей-дерева, содержащего не менее 7 вершин, которое после выполнения операции splay для одного из самых глубоких листьев становится бамбуком
Теорема о близких запросах в сплей-дереве. Пусть в сплей-дерево сложены ключи $1, ..., n$, зафиксируем один из ключей $f$, пусть выполняется $m$ запросов к ключам. Докажите, что суммарное время на запросы есть $O(n \log n + m + \sum(\log(|q_i - f| + 1)))$, где $q_i$ - $i$-й запрос
Предложите реализацию insert в декартовом дереве.
Предложите реализацию insert в декартовом дереве, использующую не более одного вызова split/merge.
Предложите реализацию remove в декартовом дереве.
Предложите реализацию remove в декартовом дереве, использующую не более одного вызова split/merge.
Докажите оценку $O(\log n)$ для реализации СНМ со сжатием путей, но когда второе дерево всегда подвешивается на первое (а не обязательно меньшее на большее)
Докажите оценку $O(\log^* n)$ для СНМ, если вместо рангов используется число вершин в поддереве (меньшее дерево подвешивается на большее)
Решите задачу: найти во взвешеном дереве минимальный по весу путь, состоящий ровно из $k$ ребер
Пусть в реализации СНМ с помощью леса корневых деревьев мы при объединении двух деревьев делаем корнем случайную из двух вершин. Приведите пример, где высота дерева в результате серии объединений будет $\Omega(n)$.
Пусть в реализации СНМ с помощью леса корневых деревьев мы при объединении двух деревьев делаем корнем случайную из двух вершин. Сжатие путей не проводится. Докажите или опровергните, что в среднем время работы get будет $O(\log n)$.
Докажите, что если при реализации СНМ с помощью леса корневых деревьев подвешивать одно дерево на другое произвольным образом, но не проводить сжатие путей, то среднее время работы get будет $O(\log n)$.
Докажите, что если при реализации СНМ с помощью леса корневых деревьев подвешивать одно дерево на другое случайным образом и проводить сжатие путей, то среднее время работы get будет $O(\log^* n)$.
Для каких $a$ определен $\log^*_a x$?
Докажите, что если для $a$ и $b$ определен $\log^*_a x$ и $\log^*_b x$, то $\log^*_a x = O(\log^*_b x)$.
Предложите решение задачи с помощью дерева отрезков (ДО). Задан массив $a[1..n]$. Поступают запросы: прибавить ко всем элементам с $L$ по $R$ заданное число, получить $i$-й элемент. Указание: не используйте групповые операции с модификаторами поддеревьев.
Предложите решение задачи с помощью ДО. Задан массив $a[1..n]$. Поступают запросы: прибавить ко всем элементам с $L$ по $R$ заданное число, получить сумму отрезке.
Предложите решение задачи с помощью ДО. Задан массив $a[1..n]$. Поступают запросы: прибавить ко всем элементам с $L$ по $R$ заданное число, получить произведение на отрезке.
Предложите решение задачи с помощью ДО. Задан массив $a[1..n]$. Поступают запросы: изменить элемент, найти элемент с минимальным индексом, больший или равный заданного значения.
Предложите решение задачи с помощью ДО. Задан массив $a[1..n]$. Поступают запросы: изменить элемент, найти на заданном отрезке элемент с минимальным индексом, больший или равный заданного значения.
Предложите решение задачи с помощью ДО. Задан массив $a[1..n]$. Поступают запросы: прибавить значение к элементам на отрезке, найти элемент с минимальным индексом, больший или равный заданного значения.
Предложите решение задачи с помощью ДО. Задан массив $a[1..n]$. Поступают запросы: найти $k$-й по величине элемент на отрезке с $i$-го по $j$-й. Время на запрос $O(\log^3 n)$. Заявляйте эту задачу только, если не умеете решать быстрее.
Предложите решение задачи с помощью ДО. Задан массив $a[1..n]$. Поступают запросы: найти $k$-й по величине элемент на отрезке с $i$-го по $j$-й. Время на запрос $O(\log^2 n)$. Заявляйте эту задачу только, если не умеете решать быстрее.
Предложите решение задачи с помощью ДО. Задан массив $a[1..n]$. Поступают запросы: найти $k$-й по величине элемент на отрезке с $i$-го по $j$-й. Время на запрос $O(\log n)$.
Предложите решение задачи с помощью ДО и деревьев поиска. Задан массив $a[1..n]$. Поступают запросы: найти $k$-й по величине элемент на отрезке с $i$-го по $j$-й, изменить элемент
Предложите решение задачи с помощью ДО. Задан массив $a[1..n]$. Поступают запросы: прибавить к всем элементам с $L$ по $R$ значение, к $i$-му значению прибавляется $ki+b$, где $k$ и $b$ - параметры запроса, получить сумму на отрезке
Предложите решение задачи с помощью ДО. Задан массив $a[1..n]$. Поступают запросы: прибавить к всем элементам с $L$ по $R$ значение, к $i$-му значению прибавляется $ki+b$, где $k$ и $b$ - параметры запроса, получить минимум на отрезке
В дереве отрезков любой отрезок можно разбить на $O(\log n)$ непересекающихся отрезков дерева. Предложите способ выделить $O(n \log n)$ отрезков в массиве индексов 1..$n$, чтобы любой отрезок можно было разбить на $O(1)$ (возможно пересекающихся) отрезков из выбранного множества
На базе предыдущего задания решите задачу о минимуме на отрезке без изменения элементов за $O(1)$ на запрос и $O(n \log n)$ предподготовки.
В дереве отрезков любой отрезок можно разбить на $O(\log n)$ непересекающихся отрезков дерева. Предложите способ выделить $O(n \log n)$ отрезков в массиве индексов 1..$n$, чтобы любой отрезок можно было разбить на $O(1)$ непересекающихся отрезков из выбранного множества
Дано $n$ прямоугольников на плоскости со сторонами, параллельными осям координат. Требуется найти точку, покрытую максимальным числом прямоугольников за $O(n \log n)$.
Дано $n$ прямоугольников на плоскости со сторонами, параллельными осям координат. Требуется найти площадь объединения прямоугольников за $O(n \log n)$.
Дано $n$ прямоугольников на плоскости со сторонами, параллельными осям координат. Требуется найти периметр объединения прямоугольников за $O(n \log n)$.
Дано $n$ точек на плоскости. Требуется найти наибольшую последовательность точек, в которой при переходе к следующей точке обе координаты строго возрастают, за $O(n \log n)$.
Дано $n$ прямоугольников на плоскости со сторонами, параллельными осям координат, и $m$ точек. Требуется найти точку среди заданных, покрытую максимальным числом прямоугольников, за $O((n+m) \log (n+m))$.
Дано $n$ прямоугольников на плоскости со сторонами, параллельными осям координат, и $m$ точек. Требуется найти прямоугольник среди заданных, содержащий максимальное число заданных точек, за $O((n+m) \log (n+m))$.

</wikitex>

Список заданий по ДМ-сем2

Дискретная математика, алгоритмы и структуры данных, 2 семестр

Навигация

Персональные инструменты

Пространства имён

Варианты

Просмотры

Ещё

Поиск

Навигация

Инструменты