Список заданий по ДМ-сем2 — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
м (rollbackEdits.php mass rollback)
 
(не показана 31 промежуточная версия 15 участников)
Строка 1: Строка 1:
 
<wikitex>
 
<wikitex>
 
= Дискретная математика, алгоритмы и структуры данных, 2 семестр =
 
= Дискретная математика, алгоритмы и структуры данных, 2 семестр =
 
+
# Постройте массив, в котором сортировка выбором делает максимальное число обменов
# Докажите, что для монеты энтропия максимальна в случае честной монеты
+
# Предложите алгоритм, который вычисляет число обменов, которое делает сортировка выбором, за $O(n \log n)$.
# Докажите, что для n исходов энтропия максимальна если они все равновероятны
+
# Найдите минимальное число сравнений для сортировки 4 элементов
# Зафиксируйте ваш любимый язык программирования. Колмогоровской сложностью $K(x)$ для слова $x$ называется длина минимальной программы, которая выводит слово $x$. Докажите, что колмогоровская сложность не превышает $H(x) + C$ где $H(x)$ - энтропия случайного источника с распределением соответствующим частотам встречания символов в $x$, а $C$ - константа, не зависящая от слова $x$ (но зависящая от выбранного языка программирования)
+
# Найдите минимальное число сравнений для сортировки 5 элементов
# Докажите, что для любого $c > 0$ найдется слово, для которого $K(x) < c H(x)$
+
# Постройте массив, в котором сортировка слиянием делает максимальное число сравнений элементов
# Пусть заданы полные системы событий $A = \{a_1, ..., a_n\}$ и $B = \{b_1, ..., b_m\}$. Определим условную энтропию $H(A | B)$ как $-\sum\limits_{i = 1}^m P(b_i) \sum\limits_{j = 1}^n : P(a_j | b_i) \log P(a_j | b_i))$. Докажите, что $H(A | B) + H(B) = H(B | A) + H(A)$
+
# Укажите способ посчитать число массивов, в которых сортировка слиянием делает максимальное число сравнений элементов
# Что можно сказать про $H(A | B)$ если $a_i$ и $b_j$ независимы для любых $i$ и $j$?
+
# Предложите алгоритм слияния массива, состоящего из двух последовательно расположенных отсортированных фрагментов за $O(n)$ с использованием $O(\sqrt{n})$ дополнительной памяти
# Что можно сказать про $H(A | A)$?
+
# Предложите алгоритм слияния массива, состоящего из двух последовательно расположенных отсортированных фрагментов за $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))$.
 +
# Какой размер множества одинаковых равномерно распределенных от 1 до $n$ независимых случайных величин необходимо, чтобы вероятность того, что две из них принимают одинаковое значение, была хотя бы $1/2$? Сделайте вывод о вероятности коллизий в хеш-таблице с игнорированием коллизий.
 +
# Пусть для хеширования строк используется полиномиальный хеш: $h(s) = (s[0]t^{n-1} + s[1]t^{n-2} + ... + s[n - 2]t + s[n-1]) \bmod 2^k$. Покажите, что в строке Туе-Морса есть много различных подстрок с одинаковым хеш-значением для любого $t$
 +
# Пусть для хеширования строк используется полиномиальный хеш: $h(s) = (s[0]t^{n-1} + s[1]t^{n-2} + ... + s[n - 2]t + s[n-1]) \bmod r$. Предложите способ получения двух строк с одинаковым значением $h$ для заданных $t$ и $r$
 +
# Пусть для хеширования строк используется полиномиальный хеш: $h(s) = (s[0]t^{n-1} + s[1]t^{n-2} + ... + s[n - 2]t + s[n-1]) \bmod r$. Покажите, что для достаточно большого $n$ существуют две различные строки длины $n$, которые отличаются в константном числе позиций, но имеющие одинаковое хеш-значение
 +
# Предложите алгоритм удаления из хеш-таблицы с разрешением конфликтов с помощью открытой адресации, который не использует пометок "удалено", а действительно удаляет элемент из таблицы
 +
# Пусть при хешировании используется разрешение конфликтов с открытой адресацией, размер хеш-пространства равено $cn$, где $n$ - число элементов. Оцените среднюю длину кластера (участка из подряд идущих занятых ячеек)
 +
# Универсальное семейство $H$ хеш функций обладает свойством попарной независимости, если для любых двух злементов $x$ и $y$ и любых двух хеш-значений $a$ и $b$ вероятность того, что $h(x) = a$ и $h(x) = b$ есть $1/m^2 + o(1 / m^2)$ (вероятность берется по случайному выбору хеш-функции из множества $H$). Докажите, что приведенная на лекции конструкция семейства $H = \{ (ax + b) \bmod p \bmod m \}$ обладает этим свойством.
 +
# Приведите пример универсального семейства хеш-функций для множества натуральных чисел, при вычислении хеш-функций в котором не используются операции деления и взятия по модулю. Достаточно $O(1/m)$-универсальности
 +
# Оцените вероятность неудачи при добавлении элемента в хешировании кукушки.
 +
# Докажите, что в хешировании кукушки добавление выполняется в среднем за $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>
 
</wikitex>

Текущая версия на 19:03, 4 сентября 2022

<wikitex>

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

  1. Постройте массив, в котором сортировка выбором делает максимальное число обменов
  2. Предложите алгоритм, который вычисляет число обменов, которое делает сортировка выбором, за $O(n \log n)$.
  3. Найдите минимальное число сравнений для сортировки 4 элементов
  4. Найдите минимальное число сравнений для сортировки 5 элементов
  5. Постройте массив, в котором сортировка слиянием делает максимальное число сравнений элементов
  6. Укажите способ посчитать число массивов, в которых сортировка слиянием делает максимальное число сравнений элементов
  7. Предложите алгоритм слияния массива, состоящего из двух последовательно расположенных отсортированных фрагментов за $O(n)$ с использованием $O(\sqrt{n})$ дополнительной памяти
  8. Предложите алгоритм слияния массива, состоящего из двух последовательно расположенных отсортированных фрагментов за $O(n)$ с использованием $O(1)$ дополнительной памяти
  9. Укажите способ для алгоритма QSort с выбором среднего элемента в качестве элемента построить массив, на котором происходит максимальное число сравнений элементов
  10. Укажите способ для любого детерминированного алгоритма выбора разделяющего элемента построить массив, на котором алгоритм QSort работает за $\Omega(n^2)$
  11. Докажите, что с использованием только сравнений элементов нельзя выяснить, есть ли в массиве два одинаковых элемента быстрее, чем за $\Omega(n \log n)$
  12. Предложите алгоритм сортировки циклических сдвигов заданного массива с $n$ элементами, каждый из которых от 1 до $n$, за $O(n^2)$. Циклические сдвиги представлять единственным числом: номером первого элемента в исходном массиве.
  13. Предложите алгоритм сортировки циклических сдвигов заданного массива с $n$ элементами, каждый из которых от 1 до $n$, за $O(n \log n)$. Циклические сдвиги представлять единственным числом: номером первого элемента в исходном массиве. Указание: зная порядок на подстроках длины $L$ порядок на подстроках длины $2L$ можно восстановить за $O(n)$.
  14. Пусть известно, что массив длины $n$ из чисел от 1 до $n$ получен с помощью генератора случайных чисел, каждое число независимо получено с помощью равномерного распределения. Предложите модификацию алгоритма сортировки подсчетом, который сортирует данный массив за $O(n)$ используя лишь $O(\sqrt{n})$ дополнительной памяти (обе оценки должны выполняться в среднем).
  15. Задан массив, полученный циклическим сдвигом из отсортированного по возрастанию. Все элементы массива различны. Требуется за $O(\log n)$ найти в нем заданный элемент.
  16. Задан массив, полученный приписыванием одного отсортированного по возрастанию массива в конец другому отсортированному по возрастанию. Все элементы массива различны. Требуется за $O(\log n)$ найти в нем заданный элемент.
  17. Задан массив, полученный приписыванием отсортированного по убыванию массива в конец отсортированному по возрастанию. Все элементы массива различны. Требуется за $O(\log n)$ найти в нем заданный элемент.
  18. Задан массив, полученный приписыванием отсортированного по убыванию массива в конец отсортированному по возрастанию и затем циклическим сдвигом получившегося массива. Все элементы массива различны. Требуется за $O(\log n)$ найти в нем заданный элемент.
  19. Пусть выполняется целочисленный двоичный поиск с начальными значениями L = 0, R = $2^k$. Преложите алгоритм определения за $O(1)$ по заданным значениям L и R, могут ли они возникнуть в процессе двоичного поиска.
  20. Пусть выполняется целочисленный двоичный поиск с начальными значениями L = 0, R = $n$. Преложите алгоритм определения за $O(\log n)$ по заданным значениям L и R, могут ли они возникнуть в процессе двоичного поиска.
  21. Оцените число итераций, которые вещественный двоичный поиск с условием цикла "L != M and R != M" делает в худшем случае при начальной инициализации L = L0, R = R0, если числа L0 и R0 одного знака.
  22. Оцените число итераций, которые вещественный двоичный поиск с условием цикла "L != M and R != M" делает в худшем случае при начальной инициализации L = L0, R = R0, если числа L0 и R0 разных знаков, или одно из них равно 0.
  23. Предложите алгоритм определения глубины сортирующей сети за $O(k)$, где $k$ - число компараторов.
  24. Докажите или опровергните, что для любого заданного неотсортированного набора из 0 и 1 существует сеть компараторов, которая сортирует все наборы кроме заданного
  25. Докажите или опровергните, что для любой перестановки чисел от 1 до $n$ существует сеть компараторов, которая сортирует все перестановки, кроме заданной
  26. Постройте сортирующую сеть для 5 проводов с минимальным числом компараторов
  27. Предложите сортирующую сеть с $O(n \log^2 n)$ компараторов.
  28. Разберитесь в том, как устроена сортирующая сеть с $O(n \log n)$ компараторов и изложите это за 15 минут, чтобы общие идеи были ясны
  29. Докажите, что сортирующая сеть имеет глубину $\Omega(\log n)$
  30. Как найти $s$-й по величине элемент в куче при малых $s$?
  31. Предложите массив, который при превращении в кучу с помощью алгоритма за $O(n)$ требует выполнить максимальное число обменов.
  32. Предложите массив, из кучи в отсортированный массив требует выполнить максимальное число обменов.
  33. В массиве есть $k$ элементов, для которых нарушено условие кучи. Преваритите массив в кучу за $k \log n$ действий
  34. Докажите, что нельзя проверить, есть ли в куче два одинаковых элемента быстрее, чем за $\Omega(n \log n)$.
  35. Проанализировать саморасширяющийся массив, если расширение происходит в $A$ раз ($1 < A$)
  36. Проанализировать стек на саморасширяющемся массиве, если при полном заполнении происходит увеличение в 2 раза, а при заполнении менее чем на 1/4 - сужение в 2 раза с помощью метода потеницалов. Потенциал должен зависеть только от текущего состояния стека (размера выделенного массива и числа заполненных элементов) и не должен зависеть от истории операций.
  37. Проанализировать стек на саморасширяющемся массиве, если при полном заполнении происходит увеличение в A раз, а при заполнении менее чем на B - сужение в C раза
  38. Разработать вектор с добавлением/удалением с истинной стоимостью всех операций $O(\log n)$.
  39. Задан односвязный список, каждый элемент знает следующий после себя. При этом возможно, что на самом деле список зацикливается (один из элементов ссылается как на следующий на элемент, который уже встречался в списке перед ним). Требуется проверить, зацикливается ли заданный односвязный список за $O(n)$ с $O(1)$ дополнительной памяти
  40. В массиве есть элемент, который встречается хотя бы $n/2$ раз. Требуется найти его за $O(n)$ с $O(1)$ дополнительной памяти
  41. Использования памяти без инициализации. Задан массив $a[1..n]$. Требуется поддержать две операции: $set(i, x)$ и $get(i)$. Операция $set$ должна присваивать $i$-му элементу массива значение $x$. Операция $get$ должна возвращать последнее присвоенное $i$-му элементу значение, либо 0, если присвоения не было. При этом исходно массив заполнен произвольными данными. Разрешается завести $O(1)$ дополнительных массивов (также заполненных произвольным мусором) и реализовать все операции за истинное $O(1)$.
  42. Счетчик Кнута. Рассмотрим массив $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)$ дополнительной памяти.
  43. Реализуйте менеджер памяти, позволяющий выделять и возвращать блоки одинакового размера за $O(1)$ времени и $O(1)$ дополнительной памяти
  44. Предложите реализацию стека, которая дополнительно позволяет выполнить операцию "вернуть минимум значений в стеке"
  45. Стек с множественным извлечением. Добавим в стек операцию multipop(k), которая снимает вершины стека k элементов. Докажите, что амортизированная стоимость операции multipop равна $O(1)$. Сформулируйте окончательное доказательство с использованием метода потенциалов.
  46. Продемонстрируйте, как просимулировать очередь на двух стеках. Амортизированная стоимость операций push и pop должна быть $O(1)$.
  47. Предложите реализацию очереди, которая дополнительно позволяет выполнить операцию "вернуть минимум значений в очереди". Амортизированная стоимость всех операций должна быть $O(1)$.
  48. Можно ли реализовать два стека на очереди (ограничений на время выполнения операций нет)?
  49. В $d$-куче выполняется $m$ операций decreaseKey и $n$ операций extractMin. Какое оптимальное асимптотически $d$ следует выбрать?
  50. В $d$-куче выполняется $m$ операций decreaseKey и $n$ операций extractMin. Время выполнения decreaseKey - $C_1 \log n$, а extractMin - $C_2 d \log n$. Какое $d$ следует выбрать?
  51. Пусть подряд выполняется $n$ операций insert в пустую биномиальную кучу. Какое среднее время операции?
  52. Как можно модифицировать биномиальную кучу, чтобы insert выполнялось за истиное $O(1)$, а амортизированная стоимость остальных операций не поменялась?
  53. Тонкие кучи. Будем называть дерево "тонким", если оно может быть получено из биномиального удалением у некоторых вершин ребенка максимального ранга. Тонкой кучей называется коллекция тонких деревьев. Ограничений на число деревьев одного ранга нет. Разработайте операции merge и extractMin для тонких куч. Амортизированная стоимость операции extractMin должна быть $O(\log n)$. Амортизированная стоимость операции merge должна быть $O(1)$.
  54. Разработайте операцию decreaseKey для тонкой кучи. Докажите, что амортизированное время выполнения есть $O(1)$ (используйте потенциал $2M + T$, где $M$ - число вершин, у которых удалили ребенка)
  55. Докажите, что операция decreaseKey в тонкой куче из предыдущего задания выполняется за истиные $O(\log n)$
  56. Ускорение extractMin. Докажите, что в тонкой куче можно добиться истинного $O(\log n)$ на extractMin, если обрабатывать корневой список, сливая деревья разных рангов, как при extractMin каждый раз, когда в корневом списке становится хотя бы $2\log n$ элементов.
  57. Предложите алгоритм удаления из АВЛ-дерева.
  58. Предложите алгоритм добавления в красно-черное дерево
  59. Предложите алгоритм удаления из красно-черного дерева
  60. Статически оптимальное дерево поиска: пусть заданы ключи и известно для каждого ключа, сколько раз его потребуется искать: $p[i]$. Требуется построить дерево поиска, чтобы суммарное время доступа ко всем ключам было минимально.
  61. Предложите алгоритм слияния двух АВЛ-деревьев, при том, что в первом дереве все ключи меньше, чем во втором за $O(\log n)$
  62. Предложите алгоритм разделения АВЛ-дерева на два, где в первом дереве все ключи меньше или равны заданному $x$, а во втором - больше, за $O(\log n)$
  63. В АВЛ-дереве находятся вершины с ключами от 1 до $n$. Какие ключи могут быть в корне?
  64. В красно-черном дереве находятся вершины с ключами от 1 до $n$. Какие ключи могут быть в корне?
  65. Предложите реализацию АВЛ-дерева, в которой в каждом узле хранится $O(1)$ бит
  66. Перекошенное сбалансированное дерево. Дерево называется перекошенным сбалансированным, если у каждой вершины разность высоты левого и правого поддерева 0, 1 или 2. Предолжите реализацию операций вставки и удаления для перекошенного сбалансированного дерева.
  67. Мальчик Петя считает, что если в дереве поиска можно хранить несколько одинаковых ключей, то на пути от одного такого ключа до другого не может быть ключей с другим значением. Тогда можно легко найти все такие ключи. Прав ли он?
  68. Пусть заданы наборы ключей $(x_1, x_2, ..., x_n)$ и $(y_1, y_2, ..., y_n)$, где все $x$-ы и все $y$-и различны. Докажите, что существует единственное декартово дерево с набором ключей в вершинах $(x_i, y_i)$
  69. В условиях предыдущей задачи пусть $x_1 < x_2 < .. < x_n$, покажите как построить декартово дерево за $O(n)$
  70. Петя предлагает сделать гибрид декартового дерева и сплей-дерева: при доступе к ключу в декартовом дереве удалять его и добавлять заново с приоритетом меньше текущего минимального. Что у него получилось?
  71. Проведите анализ случай zig для сплей-дерева по аналогии с случаем zig-zag, рассмотренном на лекции
  72. Проведите анализ случай zig-zig для сплей-дерева по аналогии с случаем zig-zag, рассмотренном на лекции
  73. Статическая оптимальность сплей-дерева. Докажите, что если к ключам $1, ..., n$, сложенным в сплей-дерево выполняется m запросов, к $i$-му ключу осуществляется $k_i$ запросов, где $k_i > 0$, то суммарное время работы не превышает $O(m H(p_1, p_2, .., p_n))$, где $p_i = k_i / m$, $H$ - шенноновская энтропия
  74. Постройте пример сплей-дерева, содержащего не менее 6 вершин, которое после выполнения операции splay для одного из самых глубоких листьев становится бамбуком
  75. Постройте пример сплей-дерева, содержащего не менее 7 вершин, которое после выполнения операции splay для одного из самых глубоких листьев становится бамбуком
  76. Теорема о близких запросах в сплей-дереве. Пусть в сплей-дерево сложены ключи $1, ..., n$, зафиксируем один из ключей $f$, пусть выполняется $m$ запросов к ключам. Докажите, что суммарное время на запросы есть $O(n \log n + m + \sum(\log(|q_i - f| + 1)))$, где $q_i$ - $i$-й запрос
  77. Предложите реализацию insert в декартовом дереве.
  78. Предложите реализацию insert в декартовом дереве, использующую не более одного вызова split/merge.
  79. Предложите реализацию remove в декартовом дереве.
  80. Предложите реализацию remove в декартовом дереве, использующую не более одного вызова split/merge.
  81. Докажите оценку $O(\log n)$ для реализации СНМ со сжатием путей, но когда второе дерево всегда подвешивается на первое (а не обязательно меньшее на большее)
  82. Докажите оценку $O(\log^* n)$ для СНМ, если вместо рангов используется число вершин в поддереве (меньшее дерево подвешивается на большее)
  83. Решите задачу: найти во взвешеном дереве минимальный по весу путь, состоящий ровно из $k$ ребер
  84. Пусть в реализации СНМ с помощью леса корневых деревьев мы при объединении двух деревьев делаем корнем случайную из двух вершин. Приведите пример, где высота дерева в результате серии объединений будет $\Omega(n)$.
  85. Пусть в реализации СНМ с помощью леса корневых деревьев мы при объединении двух деревьев делаем корнем случайную из двух вершин. Сжатие путей не проводится. Докажите или опровергните, что в среднем время работы get будет $O(\log n)$.
  86. Докажите, что если при реализации СНМ с помощью леса корневых деревьев подвешивать одно дерево на другое произвольным образом, но не проводить сжатие путей, то среднее время работы get будет $O(\log n)$.
  87. Докажите, что если при реализации СНМ с помощью леса корневых деревьев подвешивать одно дерево на другое случайным образом и проводить сжатие путей, то среднее время работы get будет $O(\log^* n)$.
  88. Для каких $a$ определен $\log^*_a x$?
  89. Докажите, что если для $a$ и $b$ определен $\log^*_a x$ и $\log^*_b x$, то $\log^*_a x = O(\log^*_b x)$.
  90. Предложите решение задачи с помощью дерева отрезков (ДО). Задан массив $a[1..n]$. Поступают запросы: прибавить ко всем элементам с $L$ по $R$ заданное число, получить $i$-й элемент. Указание: не используйте групповые операции с модификаторами поддеревьев.
  91. Предложите решение задачи с помощью ДО. Задан массив $a[1..n]$. Поступают запросы: прибавить ко всем элементам с $L$ по $R$ заданное число, получить сумму отрезке.
  92. Предложите решение задачи с помощью ДО. Задан массив $a[1..n]$. Поступают запросы: прибавить ко всем элементам с $L$ по $R$ заданное число, получить произведение на отрезке.
  93. Предложите решение задачи с помощью ДО. Задан массив $a[1..n]$. Поступают запросы: изменить элемент, найти элемент с минимальным индексом, больший или равный заданного значения.
  94. Предложите решение задачи с помощью ДО. Задан массив $a[1..n]$. Поступают запросы: изменить элемент, найти на заданном отрезке элемент с минимальным индексом, больший или равный заданного значения.
  95. Предложите решение задачи с помощью ДО. Задан массив $a[1..n]$. Поступают запросы: прибавить значение к элементам на отрезке, найти элемент с минимальным индексом, больший или равный заданного значения.
  96. Предложите решение задачи с помощью ДО. Задан массив $a[1..n]$. Поступают запросы: найти $k$-й по величине элемент на отрезке с $i$-го по $j$-й. Время на запрос $O(\log^3 n)$. Заявляйте эту задачу только, если не умеете решать быстрее.
  97. Предложите решение задачи с помощью ДО. Задан массив $a[1..n]$. Поступают запросы: найти $k$-й по величине элемент на отрезке с $i$-го по $j$-й. Время на запрос $O(\log^2 n)$. Заявляйте эту задачу только, если не умеете решать быстрее.
  98. Предложите решение задачи с помощью ДО. Задан массив $a[1..n]$. Поступают запросы: найти $k$-й по величине элемент на отрезке с $i$-го по $j$-й. Время на запрос $O(\log n)$.
  99. Предложите решение задачи с помощью ДО и деревьев поиска. Задан массив $a[1..n]$. Поступают запросы: найти $k$-й по величине элемент на отрезке с $i$-го по $j$-й, изменить элемент
  100. Предложите решение задачи с помощью ДО. Задан массив $a[1..n]$. Поступают запросы: прибавить к всем элементам с $L$ по $R$ значение, к $i$-му значению прибавляется $ki+b$, где $k$ и $b$ - параметры запроса, получить сумму на отрезке
  101. Предложите решение задачи с помощью ДО. Задан массив $a[1..n]$. Поступают запросы: прибавить к всем элементам с $L$ по $R$ значение, к $i$-му значению прибавляется $ki+b$, где $k$ и $b$ - параметры запроса, получить минимум на отрезке
  102. В дереве отрезков любой отрезок можно разбить на $O(\log n)$ непересекающихся отрезков дерева. Предложите способ выделить $O(n \log n)$ отрезков в массиве индексов 1..$n$, чтобы любой отрезок можно было разбить на $O(1)$ (возможно пересекающихся) отрезков из выбранного множества
  103. На базе предыдущего задания решите задачу о минимуме на отрезке без изменения элементов за $O(1)$ на запрос и $O(n \log n)$ предподготовки.
  104. В дереве отрезков любой отрезок можно разбить на $O(\log n)$ непересекающихся отрезков дерева. Предложите способ выделить $O(n \log n)$ отрезков в массиве индексов 1..$n$, чтобы любой отрезок можно было разбить на $O(1)$ непересекающихся отрезков из выбранного множества
  105. Дано $n$ прямоугольников на плоскости со сторонами, параллельными осям координат. Требуется найти точку, покрытую максимальным числом прямоугольников за $O(n \log n)$.
  106. Дано $n$ прямоугольников на плоскости со сторонами, параллельными осям координат. Требуется найти площадь объединения прямоугольников за $O(n \log n)$.
  107. Дано $n$ прямоугольников на плоскости со сторонами, параллельными осям координат. Требуется найти периметр объединения прямоугольников за $O(n \log n)$.
  108. Дано $n$ точек на плоскости. Требуется найти наибольшую последовательность точек, в которой при переходе к следующей точке обе координаты строго возрастают, за $O(n \log n)$.
  109. Дано $n$ прямоугольников на плоскости со сторонами, параллельными осям координат, и $m$ точек. Требуется найти точку среди заданных, покрытую максимальным числом прямоугольников, за $O((n+m) \log (n+m))$.
  110. Дано $n$ прямоугольников на плоскости со сторонами, параллельными осям координат, и $m$ точек. Требуется найти прямоугольник среди заданных, содержащий максимальное число заданных точек, за $O((n+m) \log (n+m))$.
  111. Какой размер множества одинаковых равномерно распределенных от 1 до $n$ независимых случайных величин необходимо, чтобы вероятность того, что две из них принимают одинаковое значение, была хотя бы $1/2$? Сделайте вывод о вероятности коллизий в хеш-таблице с игнорированием коллизий.
  112. Пусть для хеширования строк используется полиномиальный хеш: $h(s) = (s[0]t^{n-1} + s[1]t^{n-2} + ... + s[n - 2]t + s[n-1]) \bmod 2^k$. Покажите, что в строке Туе-Морса есть много различных подстрок с одинаковым хеш-значением для любого $t$
  113. Пусть для хеширования строк используется полиномиальный хеш: $h(s) = (s[0]t^{n-1} + s[1]t^{n-2} + ... + s[n - 2]t + s[n-1]) \bmod r$. Предложите способ получения двух строк с одинаковым значением $h$ для заданных $t$ и $r$
  114. Пусть для хеширования строк используется полиномиальный хеш: $h(s) = (s[0]t^{n-1} + s[1]t^{n-2} + ... + s[n - 2]t + s[n-1]) \bmod r$. Покажите, что для достаточно большого $n$ существуют две различные строки длины $n$, которые отличаются в константном числе позиций, но имеющие одинаковое хеш-значение
  115. Предложите алгоритм удаления из хеш-таблицы с разрешением конфликтов с помощью открытой адресации, который не использует пометок "удалено", а действительно удаляет элемент из таблицы
  116. Пусть при хешировании используется разрешение конфликтов с открытой адресацией, размер хеш-пространства равено $cn$, где $n$ - число элементов. Оцените среднюю длину кластера (участка из подряд идущих занятых ячеек)
  117. Универсальное семейство $H$ хеш функций обладает свойством попарной независимости, если для любых двух злементов $x$ и $y$ и любых двух хеш-значений $a$ и $b$ вероятность того, что $h(x) = a$ и $h(x) = b$ есть $1/m^2 + o(1 / m^2)$ (вероятность берется по случайному выбору хеш-функции из множества $H$). Докажите, что приведенная на лекции конструкция семейства $H = \{ (ax + b) \bmod p \bmod m \}$ обладает этим свойством.
  118. Приведите пример универсального семейства хеш-функций для множества натуральных чисел, при вычислении хеш-функций в котором не используются операции деления и взятия по модулю. Достаточно $O(1/m)$-универсальности
  119. Оцените вероятность неудачи при добавлении элемента в хешировании кукушки.
  120. Докажите, что в хешировании кукушки добавление выполняется в среднем за $O(1)$.
  121. Оцените среднюю длину максимального списка при разрешении конфликтов в хешировании с помощью метода списков. Пусть для хеширования $n$ элементов используются $n$ списков.
  122. Докажите, что $\sum\limits_{i=0}^n h(i) = O(n)$.
  123. Предложите обобщение дерева Фенвика на многомерный запрос
  124. Пусть операция в дереве Фенвика некоммутативна. Предложите модификацию, которая позволит использовать дерево Фенвика, время на запрос обновления $O(\log^2 n)$.
  125. Встречное дерево Фенвика. Пусть у операции в дереве Фенвика нет обратного. Будем хранить два дерева $f[i]$ и $g[i]$, где $f[i]$ - обычное дерево Фенвика, а $g[i]$ - сумма элементов с $a[i + 1]$ до $a[i + 2^{h(i)}]$. Предложите алгоритм выполнения операций изменения элемента и получения статистики на отрезке в получившемся дереве.
  126. Предложите реализацию операции удаления ключа в дереве Ван Эмде Боаса.
  127. Предложите модификацию дерева Ван Эмде Боаса, где и минимум и максимум хранятся отдельно, но не в детях.

</wikitex>