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

Дискретная математика, алгоритмы и структуры данных, 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))$.
Какой размер множества одинаковых равномерно распределенных от 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>

@@ Строка 1: / Строка 1: @@
 <wikitex>
 = Дискретная математика, алгоритмы и структуры данных, 2 семестр =
+# Постройте массив, в котором сортировка выбором делает максимальное число обменов
-# Докажите, что для монеты энтропия максимальна в случае честной монеты
+# Предложите алгоритм, который вычисляет число обменов, которое делает сортировка выбором, за $O(n \log n)$.
-# Докажите, что для n исходов энтропия максимальна если они все равновероятны
+# Найдите минимальное число сравнений для сортировки 4 элементов
-# Зафиксируйте ваш любимый язык программирования. Колмогоровской сложностью $K(x)$ для слова $x$ называется длина минимальной программы, которая выводит слово $x$. Докажите, что колмогоровская сложность не превышает $n H(x) + O(\log n)$, где $n$ - длина строки $x$, $H(x)$ - энтропия случайного источника с распределением соответствующим частотам встречания символов в $x$, константа в $O$, не зависит от слова $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)$ дополнительной памяти
-# Постройте схему получения вероятности 1/3 с помощью честной монеты, имеющую минимальное математическое ожидание числа бросков. Докажите оптимальность вашей схемы.
+# Укажите способ для алгоритма QSort с выбором среднего элемента в качестве элемента построить массив, на котором происходит максимальное число сравнений элементов
-# Рассмотрим случайное блуждание точки на прямой, пусть точка начинает в точке $p$ ($p$ - целое) и каждую секунду переходит равновероятно на 1 влево или вправо. Точка поглощается в точках 0 и $n$ ($n$ целое, больше $p$). Найдите вероятность поглощения в точке 0.
+# Укажите способ для любого детерминированного алгоритма выбора разделяющего элемента построить массив, на котором алгоритм QSort работает за $\Omega(n^2)$
-# Рассмотрим случайное блуждание точки на прямой, пусть точка начинает в точке 0  и каждую секунду переходит равновероятно на 1 влево или вправо. Докажите, что математическое ожидание максимума координаты точки за $n$ шагов есть $O(\sqrt{n})$.
+# Докажите, что с использованием только сравнений элементов нельзя выяснить, есть ли в массиве два одинаковых элемента быстрее, чем за $\Omega(n \log n)$
-# Докажите, что математическое ожидание числа экспериментов при симуляции одного распределения другим асимптотически равно отношению энтропий распределений (считайте, что энтропия симулируемого распределения больше).
+# Предложите алгоритм сортировки циклических сдвигов заданного массива с $n$ элементами, каждый из которых от 1 до $n$, за $O(n^2)$. Циклические сдвиги представлять единственным числом: номером первого элемента в исходном массиве.
-# Пусть $f$ и $g$ - непрерывные возрастающие функции, причем $\lim\limits_{x\to-\infty}f(x)=0$,  $\lim\limits_{x\to-\infty}g(x)=0$,  $\lim\limits_{x\to+\infty}f(x)=1$,  $\lim\limits_{x\to+\infty}g(x)=1$, кроме того считайте, что вы можете вычислять $f(x)$, $g(x)$, $f^{-1}(x)$ и $g^{-1}(x)$. У вас есть случайная величина с функцией распределения $f(x)$. Как вам получить случайную величину с функцией распределения $g(x)$?
+# Предложите алгоритм сортировки циклических сдвигов заданного массива с $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 раза с помощью метода потеницалов. Потенциал должен зависеть только от текущего состояния стека (размера выделенного массива и числа заполненных элементов) и не должен зависеть от истории операций.
@@ Строка 21: / Строка 42: @@
 # В массиве есть элемент, который встречается хотя бы $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)$ дополнительной памяти
+# Реализуйте менеджер памяти, позволяющий выделять и возвращать блоки одинакового размера за $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$ следует выбрать?
-# Как найти $s$-й по величине элемент в куче при малых $s$?
-# Приведите алгоритм построения кучи из $n$ заданных элементов за $O(n)$
-# На базе кучи разработайте алгоритм сортировки за $O(n \log n)$ c $O(1)$ дополнительной памяти
-# Левосторонние кучи. Будем называть двоичное дерево левосторонней кучей, если в нем выполнены следующие условия. 1) На элементах выполнен порядок кучи. 2) Будем называть отсутствующего ребенка "свободной позицией". Обозначим как $d(u)$ минимальное расстояние от вершины $u$ до свободной позиции в ее поддереве. У любой вершины $u$ с левым ребенком $L(u)$ и правым ребенком $R(u)$ должно быть выполнено $d(R(u)) \le d(L(u))$. Докажите, что для любой вершины $d(u) \le \log_2 n$. Как найти свободную позицию в левосторонней куче за $O(\log n)$?
-# Предложите реализацию операции merge для левосторонних куч.
-# Предложите реализацию операций insert, extractMin для левостронних куч.
-# Предложите реализацию операций decreaseKey для левостронних куч.
-# Как построить левостороннюю кучу из $n$ элементов за $O(n)$?
 # Пусть подряд выполняется $n$ операций insert в пустую биномиальную кучу. Какое среднее время операции?
 # Как можно модифицировать биномиальную кучу, чтобы insert выполнялось за истиное $O(1)$, а амортизированная стоимость остальных операций не поменялась?
-# Тонкие кучи. Будем называть дерево "тонким", если оно может быть получено из биномиального удалением у некоторых вершин ребенка максимального ранга. Тонкой кучей называется коллекция тонких деревьев. Операции insert, extractMin и merge выполняются в тонкой куче также, как в куче Фибоначчи. Разработайте операцию decreaseKey для тонкой кучи. Докажите, что амортизированное время выполнения есть $O(1)$ (используйте потенциал $2M + T$, где $M$ - число вершин, у которых удалили ребенка)
+# Тонкие кучи. Будем называть дерево "тонким", если оно может быть получено из биномиального удалением у некоторых вершин ребенка максимального ранга. Тонкой кучей называется коллекция тонких деревьев. Ограничений на число деревьев одного ранга нет. Разработайте операции merge и extractMin для тонких куч. Амортизированная стоимость операции extractMin должна быть $O(\log n)$. Амортизированная стоимость операции merge должна быть $O(1)$.
-# Тонкие кучи. Докажите, что операция decreaseKey в тонкой куче из предыдущего задания выполняется за истиные $O(\log n)$
+# Разработайте операцию decreaseKey для тонкой кучи. Докажите, что амортизированное время выполнения есть $O(1)$ (используйте потенциал $2M + T$, где $M$ - число вершин, у которых удалили ребенка)
-# Ускорение extractMin. Докажите, что в фибоначчиевой или тонкой куче можно добиться истинного $O(\log n)$ на extractMin, если обрабатывать корневой список, сливая деревья разных рангов, как при extractMin каждый раз, когда в корневом списке становится хотя бы $2\log n$ элементов.
+# Докажите, что операция decreaseKey в тонкой куче из предыдущего задания выполняется за истиные $O(\log n)$
-# Продемонстрируйте последовательность операций с фибоначчиевой кучей, при выполнении которой заключительная операция decreaseKey выполняется за истиное $\Omega(n)$
+# Ускорение extractMin. Докажите, что в тонкой куче можно добиться истинного $O(\log n)$ на extractMin, если обрабатывать корневой список, сливая деревья разных рангов, как при extractMin каждый раз, когда в корневом списке становится хотя бы $2\log n$ элементов.
-# Докажите оценку $O(\log n)$ для реализации СНМ со сжатием путей, но когда второе дерево всегда подвешивается на первое (а не обязательно меньшее на большее)
-# Докажите оценку $O(\log^* n)$ для СНМ, если вместо рангов используется число вершин в поддереве (меньшее дерево подвешивается на большее)
-# СНМ на списках с ранговой эвристикой. Будем хранить каждой множество в СНМ как список его элементов, каждый элемент знает голову, голова знает хвост. Тогда объедиенение двух списков происходит за время пропорциональное длине одного из них. Докажите, что если каждый раз добавлять меньший список к большему, суммарное время работы всех операций Union будет $O(n \log n)$.
-# Решите задачу: найти во взвешеном дереве минимальный по весу путь, состоящий ровно из $k$ ребер
-# Пусть в реализации СНМ с помощью леса корневых деревьев мы при объединении двух деревьев делаем корнем случайную из двух вершин. Сжатие путей не проводится. Докажите или опровергните, что в среднем время работы get будет $O(\log n)$.
-# Для каких $a$ определен $\log^*_a x$?
-# Докажите, что если для $a$ и $b$ определен $\log^*_a x$ и $\log^*_b x$, то $\log^*_a x = O(\log^*_b x)$?
-# АВЛ-дерево: у каждой вершины высота левого и правого поддерева различается не более чем на 1. Докажите, что высота АВЛ-дерева есть $O(\log n)$
-# Докажите, что после добавления элемента в АВЛ дерево можно восстановить баланс за $O(1)$ балансировок.
 # Предложите алгоритм удаления из АВЛ-дерева.
-# Красно-черное дерево: все вершины красные или черные, у красной вершины не может быть красного родителя, черная высота любой свободной позиции (отсутствующего сына вершины) одинаковая. Докажите, что высота красно-черного дерева есть $O(\log n)$
 # Предложите алгоритм добавления в красно-черное дерево
 # Предложите алгоритм удаления из красно-черного дерева
 # Статически оптимальное дерево поиска: пусть заданы ключи и известно для каждого ключа, сколько раз его потребуется искать: $p[i]$. Требуется построить дерево поиска, чтобы суммарное время доступа ко всем ключам было минимально.
-# Мальчик Петя в предыдущей задаче предложил построить декартово дерево с приоритетом $p[i]$. Приведите контрпример.
 # Предложите алгоритм слияния двух АВЛ-деревьев, при том, что в первом дереве все ключи меньше, чем во втором за $O(\log n)$
 # Предложите алгоритм разделения АВЛ-дерева на два, где в первом дереве все ключи меньше или равны заданному $x$, а во втором - больше, за $O(\log n)$
@@ Строка 71: / Строка 77: @@
 # Постройте пример сплей-дерева, содержащего не менее 7 вершин, которое после выполнения операции splay для одного из самых глубоких листьев становится бамбуком
 # Теорема о близких запросах в сплей-дереве. Пусть в сплей-дерево сложены ключи $1, ..., n$, зафиксируем один из ключей $f$, пусть выполняется $m$ запросов к ключам. Докажите, что суммарное время на запросы есть $O(n \log n + m + \sum(\log(|q_i - f| + 1)))$, где $q_i$ - $i$-й запрос
-# Докажите, что математическое ожидание глубины вершины в декартовом дереве есть $O(\log n)$
+# Предложите реализацию insert в декартовом дереве.
-# Докажите, что математическое ожидание глубины самого глубокого листа в декартовом дереве есть $O(\log n)$
+# Предложите реализацию insert в декартовом дереве, использующую не более одного вызова split/merge.
-# Какой размер множества одинаковых равномерно распределенных от 1 до $n$ независимых случайных величин необходимо, чтобы вероятность того, что две из них принимают одинаковое значение, была хотя бы $1/2$? Сделайте вывод о вероятности коллизий в хеш-таблице с игнорированием коллизий.
+# Предложите реализацию remove в декартовом дереве.
-# Пусть для хеширования строк используется полиномиальный хеш: $h(s) = (s[0]t^{n-1} + s[1]t^{n-2} + ... + s[n - 2]t + s[n-1]) \bmod 2^k$. Покажите, что в строке Туе-Морса есть много различных подстрок с одинаковым хеш-значением для любого $t$
+# Предложите реализацию remove в декартовом дереве, использующую не более одного вызова split/merge.
-# Пусть для хеширования строк используется полиномиальный хеш: $h(s) = (s[0]t^{n-1} + s[1]t^{n-2} + ... + s[n - 2]t + s[n-1]) \bmod r$. Предложите способ получения двух строк с одинаковым значением $h$ для заданных $t$ и $r$
+# Докажите оценку $O(\log n)$ для реализации СНМ со сжатием путей, но когда второе дерево всегда подвешивается на первое (а не обязательно меньшее на большее)
-# Пусть для хеширования строк используется полиномиальный хеш: $h(s) = (s[0]t^{n-1} + s[1]t^{n-2} + ... + s[n - 2]t + s[n-1]) \bmod r$. Покажите, что для достаточно большого $n$ существуют две различные строки длины $n$, которые отличаются в константном числе позиций, но имеющие одинаковое хеш-значение
+# Докажите оценку $O(\log^* n)$ для СНМ, если вместо рангов используется число вершин в поддереве (меньшее дерево подвешивается на большее)
-# Предложите алгоритм удаления из хеш-таблицы с разрешением конфликтов с помощью открытой адресации, который не использует пометок "удалено", а действительно удаляет элемент из таблицы
+# Решите задачу: найти во взвешеном дереве минимальный по весу путь, состоящий ровно из $k$ ребер
-# Пусть при хешировании используется разрешение конфликтов с открытой адресацией, размер хеш-пространства равено $cn$, где $n$ - число элементов. Оцените среднюю длину кластера (участка из подряд идущих занятых ячеек)
+# Пусть в реализации СНМ с помощью леса корневых деревьев мы при объединении двух деревьев делаем корнем случайную из двух вершин. Приведите пример, где высота дерева в результате серии объединений будет $\Omega(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 \}$ обладает этим свойством.
+# Пусть в реализации СНМ с помощью леса корневых деревьев мы при объединении двух деревьев делаем корнем случайную из двух вершин. Сжатие путей не проводится. Докажите или опровергните, что в среднем время работы get будет $O(\log n)$.
-# Приведите пример универсального семейства хеш-функций для множества натуральных чисел, при вычислении хеш-функций в котором не используются операции деления и взятия по модулю. Достаточно $O(1/m)$-универсальности
+# Докажите, что если при реализации СНМ с помощью леса корневых деревьев подвешивать одно дерево на другое произвольным образом, но не проводить сжатие путей, то среднее время работы get будет $O(\log n)$.
-# Оцените вероятность неудачи при добавлении элемента в хешировании кукушки.
+# Докажите, что если при реализации СНМ с помощью леса корневых деревьев подвешивать одно дерево на другое случайным образом и проводить сжатие путей, то среднее время работы get будет $O(\log^* n)$.
-# Докажите, что в хешировании кукушки добавление выполняется в среднем за $O(1)$.
+# Для каких $a$ определен $\log^*_a x$?
-# Оцените среднюю длину максимального списка при разрешении конфликтов в хешировании с помощью метода списков. Пусть для хеширования $n$ элементов используются $n$ списков.
+# Докажите, что если для $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$ заданное число, получить сумму отрезке.
@@ Строка 98: / Строка 104: @@
 # В дереве отрезков любой отрезок можно разбить на $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)$.
-# Найдите минимальное число сравнений для сортировки 4 элементов
+# Дано $n$ прямоугольников на плоскости со сторонами, параллельными осям координат. Требуется найти периметр объединения прямоугольников за $O(n \log n)$.
-# Найдите минимальное число сравнений для сортировки 5 элементов
+# Дано $n$ точек на плоскости. Требуется найти наибольшую последовательность точек, в которой при переходе к следующей точке обе координаты строго возрастают, за $O(n \log n)$.
-# Докажите, что с использованием только сравнений элементов нельзя выяснить, есть ли в массиве два одинаковых элемента быстрее, чем за $\Omega(n \log n)$
+# Дано $n$ прямоугольников на плоскости со сторонами, параллельными осям координат, и $m$ точек. Требуется найти точку среди заданных, покрытую максимальным числом прямоугольников, за $O((n+m) \log (n+m))$.
-# Постройте массив, в котором сортировка слиянием делает максимальное число сравнений элементов
+# Дано $n$ прямоугольников на плоскости со сторонами, параллельными осям координат, и $m$ точек. Требуется найти прямоугольник среди заданных, содержащий максимальное число заданных точек, за $O((n+m) \log (n+m))$.
-# Предложите алгоритм слияния массива, состоящего из двух последовательно расположенных отсортированных фрагментов за $O(n)$ с использованием O(1) дополнительной памяти
+# Какой размер множества одинаковых равномерно распределенных от 1 до $n$ независимых случайных величин необходимо, чтобы вероятность того, что две из них принимают одинаковое значение, была хотя бы $1/2$? Сделайте вывод о вероятности коллизий в хеш-таблице с игнорированием коллизий.
-# Докажите, что алгоритм QSort с выбором среднего элемента в качестве разделяющего работает на случайном входном наборе в среднем за $O(n \log n)$
+# Пусть для хеширования строк используется полиномиальный хеш: $h(s) = (s[0]t^{n-1} + s[1]t^{n-2} + ... + s[n - 2]t + s[n-1]) \bmod 2^k$. Покажите, что в строке Туе-Морса есть много различных подстрок с одинаковым хеш-значением для любого $t$
-# Докажите, что алгоритм QSort с выбором случайного элемента в качестве разделяющего на любом входном наборе работает в среднем за $O(n \log n)$
+# Пусть для хеширования строк используется полиномиальный хеш: $h(s) = (s[0]t^{n-1} + s[1]t^{n-2} + ... + s[n - 2]t + s[n-1]) \bmod r$. Предложите способ получения двух строк с одинаковым значением $h$ для заданных $t$ и $r$
-# Укажите способ для любого детерминированного алгоритма выбора разделяющего элемента построить массив, на котором алгоритм QSort работает за $\Omega(n^2)$
+# Пусть для хеширования строк используется полиномиальный хеш: $h(s) = (s[0]t^{n-1} + s[1]t^{n-2} + ... + s[n - 2]t + s[n-1]) \bmod r$. Покажите, что для достаточно большого $n$ существуют две различные строки длины $n$, которые отличаются в константном числе позиций, но имеющие одинаковое хеш-значение
-# Модифицируйте рандомизированный алгоритм QSort, чтобы искать $k$-й по величине элемент в массиве за время $O(n)$ в среднем
+# Предложите алгоритм удаления из хеш-таблицы с разрешением конфликтов с помощью открытой адресации, который не использует пометок "удалено", а действительно удаляет элемент из таблицы
-# Докажите или опровергните, что для любого заданного неотсортированного набора из 0 и 1 существует сеть компараторов, которая сортирует все наборы кроме заданного
+# Пусть при хешировании используется разрешение конфликтов с открытой адресацией, размер хеш-пространства равено $cn$, где $n$ - число элементов. Оцените среднюю длину кластера (участка из подряд идущих занятых ячеек)
-# Докажите или опровергните, что для любой перестановки чисел от 1 до $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 \}$ обладает этим свойством.
-# Постройте сортирующую сеть для 5 проводов с минимальным числом компараторов
+# Приведите пример универсального семейства хеш-функций для множества натуральных чисел, при вычислении хеш-функций в котором не используются операции деления и взятия по модулю. Достаточно $O(1/m)$-универсальности
-# Предложите сортирующую сеть с $O(n \log^2 n)$ компараторов.
+# Оцените вероятность неудачи при добавлении элемента в хешировании кукушки.
-# Разберитесь в том, как устроена сортирующая сеть с $O(n \log n)$ компараторов и изложите это за 15 минут, чтобы общие идеи были ясны
+# Докажите, что в хешировании кукушки добавление выполняется в среднем за $O(1)$.
-# Докажите, что сортирующая сеть имеет глубину $\Omega(\log n)$
+# Оцените среднюю длину максимального списка при разрешении конфликтов в хешировании с помощью метода списков. Пусть для хеширования $n$ элементов используются $n$ списков.
-# Задан массив, полученный циклическим сдвигом из отсортированного по возрастанию. Все элементы массива различны. Требуется за $O(\log n)$ найти в нем заданный элемент. Предложите способ или докажите, что это невозможно.
+# Докажите, что $\sum\limits_{i=0}^n h(i) = O(n)$.
-# Задан массив, полученный приписыванием одного отсортированного по возрастанию массива в конец другому отсортированному по возрастанию. Все элементы массива различны. Требуется за $O(\log n)$ найти в нем заданный элемент.
+# Предложите обобщение дерева Фенвика на многомерный запрос
-# Задан массив, полученный приписыванием отсортированного по убыванию массива в конец отсортированному по возрастанию. Все элементы массива различны. Требуется за $O(\log n)$ найти в нем заданный элемент.
+# Пусть операция в дереве Фенвика некоммутативна. Предложите модификацию, которая позволит использовать дерево Фенвика, время на запрос обновления $O(\log^2 n)$.
-# Задан массив, полученный приписыванием отсортированного по убыванию массива в конец отсортированному по возрастанию и затем циклическим сдвигом получившегося массива. Все элементы массива различны. Требуется за $O(\log n)$ найти в нем заданный элемент.
+# Встречное дерево Фенвика. Пусть у операции в дереве Фенвика нет обратного. Будем хранить два дерева $f[i]$ и $g[i]$, где $f[i]$ - обычное дерево Фенвика, а $g[i]$ - сумма элементов с $a[i + 1]$ до $a[i + 2^{h(i)}]$. Предложите алгоритм выполнения операций изменения элемента и получения статистики на отрезке в получившемся дереве.
+# Предложите реализацию операции удаления ключа в дереве Ван Эмде Боаса.
+# Предложите модификацию дерева Ван Эмде Боаса, где и минимум и максимум хранятся отдельно, но не в детях.
+</wikitex>

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

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

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

Навигация

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

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

Варианты

Просмотры

Ещё

Поиск

Навигация

Инструменты