Изменения

 # ДокажитеПостройте массив, что для монеты энтропия максимальна в случае честной монетыкотором сортировка выбором делает максимальное число обменов# ДокажитеПредложите алгоритм, который вычисляет число обменов, которое делает сортировка выбором, что для n исходов энтропия максимальна если они все равновероятны# Зафиксируйте ваш любимый язык программирования. Колмогоровской сложностью за $KO(xn \log n)$ .# Найдите минимальное число сравнений для слова $x$ называется длина минимальной программысортировки 4 элементов# Найдите минимальное число сравнений для сортировки 5 элементов# Постройте массив, в котором сортировка слиянием делает максимальное число сравнений элементов# Укажите способ посчитать число массивов, которая выводит слово $x$. Докажитев которых сортировка слиянием делает максимальное число сравнений элементов# Предложите алгоритм слияния массива, что колмогоровская сложность не превышает состоящего из двух последовательно расположенных отсортированных фрагментов за $O(n H(x) + $ с использованием $O(\log sqrt{n})$дополнительной памяти# Предложите алгоритм слияния массива, где состоящего из двух последовательно расположенных отсортированных фрагментов за $O(n)$ - длина строки с использованием $xO(1)$дополнительной памяти# Укажите способ для алгоритма QSort с выбором среднего элемента в качестве элемента построить массив, на котором происходит максимальное число сравнений элементов# Укажите способ для любого детерминированного алгоритма выбора разделяющего элемента построить массив, на котором алгоритм QSort работает за $H\Omega(xn^2)$ - энтропия случайного источника # Докажите, что с распределением соответствующим частотам встречания символов использованием только сравнений элементов нельзя выяснить, есть ли в массиве два одинаковых элемента быстрее, чем за $x\Omega(n \log n)$, константа в # Предложите алгоритм сортировки циклических сдвигов заданного массива с $On$элементами, не зависит каждый из которых от слова 1 до $xn$ , за $O(но может зависеть от выбранного языка программированияn^2)$. Циклические сдвиги представлять единственным числом: номером первого элемента в исходном массиве.# ДокажитеПредложите алгоритм сортировки циклических сдвигов заданного массива с $n$ элементами, что для любого каждый из которых от 1 до $c > 0n$ найдется слово, для которого за $KO(xn \log n) < c H$. Циклические сдвиги представлять единственным числом: номером первого элемента в исходном массиве. Указание: зная порядок на подстроках длины $L$ порядок на подстроках длины $2L$ можно восстановить за $O(xn)$.# Пусть заданы полные системы событий известно, что массив длины $A = \{a_1, ..., a_n\}n$ из чисел от 1 до $ и n$B = \{b_1получен с помощью генератора случайных чисел, каждое число независимо получено с помощью равномерного распределения...Предложите модификацию алгоритма сортировки подсчетом, b_m\}который сортирует данный массив за $. Определим условную энтропию $HO(A | Bn)$ как используя лишь $-O(\sum\limits_sqrt{i = 1n}^m P)$ дополнительной памяти (b_iобе оценки должны выполняться в среднем) .# Задан массив, полученный циклическим сдвигом из отсортированного по возрастанию. Все элементы массива различны. Требуется за $O(\sum\limits_{j = 1}^log n P)$ найти в нем заданный элемент.# Задан массив, полученный приписыванием одного отсортированного по возрастанию массива в конец другому отсортированному по возрастанию. Все элементы массива различны. Требуется за $O(a_j | b_i) \log P(a_j | b_i)n)$найти в нем заданный элемент. Докажите# Задан массив, что полученный приписыванием отсортированного по убыванию массива в конец отсортированному по возрастанию. Все элементы массива различны. Требуется за $HO(A | B) + H(B) = H(B | A) + H(A\log n)$найти в нем заданный элемент. # Что можно сказать про Задан массив, полученный приписыванием отсортированного по убыванию массива в конец отсортированному по возрастанию и затем циклическим сдвигом получившегося массива. Все элементы массива различны. Требуется за $HO(A | B\log n)$ если найти в нем заданный элемент.# Пусть выполняется целочисленный двоичный поиск с начальными значениями L = 0, R = $a_i2^k$ и . Преложите алгоритм определения за $b_j$ независимы для любых $iO(1)$ по заданным значениям L и R, могут ли они возникнуть в процессе двоичного поиска.# Пусть выполняется целочисленный двоичный поиск с начальными значениями L = 0, R = $jn$?# Что можно сказать про . Преложите алгоритм определения за $HO(A | A\log n)$?по заданным значениям L и R, могут ли они возникнуть в процессе двоичного поиска.# Постройте схему получения вероятности 1/3 Оцените число итераций, которые вещественный двоичный поиск с помощью честной монетыусловием цикла "L != M and R != M" делает в худшем случае при начальной инициализации L = L0, R = R0, имеющую минимальное математическое ожидание если числа бросков. Докажите оптимальность вашей схемыL0 и R0 одного знака.# Рассмотрим случайное блуждание точки на прямойОцените число итераций, пусть точка начинает которые вещественный двоичный поиск с условием цикла "L != M and R != M" делает в точке $p$ ($p$ - целое) худшем случае при начальной инициализации L = L0, R = R0, если числа L0 и каждую секунду переходит равновероятно на 1 влево R0 разных знаков, или вправоодно из них равно 0. Точка поглощается в точках 0 и $n# Предложите алгоритм определения глубины сортирующей сети за $ O(k)$n$ целое, больше где $pk$). Найдите вероятность поглощения в точке 0- число компараторов.# Рассмотрим случайное блуждание точки на прямойДокажите или опровергните, пусть точка начинает в точке что для любого заданного неотсортированного набора из 0 и каждую секунду переходит равновероятно на 1 влево существует сеть компараторов, которая сортирует все наборы кроме заданного# Докажите или вправо. Докажитеопровергните, что математическое ожидание максимума координаты точки за для любой перестановки чисел от 1 до $n$ шагов есть существует сеть компараторов, которая сортирует все перестановки, кроме заданной# Постройте сортирующую сеть для 5 проводов с минимальным числом компараторов# Предложите сортирующую сеть с $O(n \sqrt{log^2 n})$компараторов.# Разберитесь в том, как устроена сортирующая сеть с $O(n \log n)$ компараторов и изложите это за 15 минут, чтобы общие идеи были ясны# Докажите, что математическое ожидание числа экспериментов при симуляции одного распределения другим асимптотически равно отношению энтропий распределений сортирующая сеть имеет глубину $\Omega(считайте, что энтропия симулируемого распределения больше\log n).$# Пусть $f$ и Как найти $gs$ - непрерывные возрастающие функции, причем й по величине элемент в куче при малых $\lim\limits_{x\to-\infty}f(x)=0s$?# Предложите массив, который при превращении в кучу с помощью алгоритма за $\lim\limits_{x\to-\infty}gO(xn)=0$требует выполнить максимальное число обменов.# Предложите массив, из кучи в отсортированный массив требует выполнить максимальное число обменов.# В массиве есть $\lim\limits_{x\to+\infty}f(x)=1k$элементов, для которых нарушено условие кучи. Преваритите массив в кучу за $k \lim\limits_{x\to+\infty}g(x)=1log n$, кроме того считайтедействий# Докажите, что вы можете вычислять $f(x)$нельзя проверить, $g(x)$есть ли в куче два одинаковых элемента быстрее, чем за $f^{-1}\Omega(x)$ и $g^{-1}(x)$. У вас есть случайная величина с функцией распределения $f(xn \log n)$. Как вам получить случайную величину с функцией распределения $g(x)$?

# Реализуйте менеджер памяти, позволяющий выделять и возвращать блоки одинакого одинакового размера за $O(1)$ времени и $O(1)$ дополнительной памяти# Предложите реализацию стека, которая дополнительно позволяет выполнить операцию "вернуть минимум значений в стеке"# Стек с множественным извлечением. Добавим в стек операцию multipop(k), которая снимает вершины стека k элементов. Докажите, что амортизированная стоимость операции multipop равна $O(1)$. Сформулируйте окончательное доказательство с использованием метода потенциалов.# Продемонстрируйте, как просимулировать очередь на двух стеках. Амортизированная стоимость операций push и pop должна быть $O(1)$.# Предложите реализацию очереди, которая дополнительно позволяет выполнить операцию "вернуть минимум значений в очереди". Амортизированная стоимость всех операций должна быть $O(1)$.# Можно ли реализовать два стека на очереди (ограничений на время выполнения операций нет)?

# Тонкие кучи. Будем называть дерево "тонким", если оно может быть получено из биномиального удалением у некоторых вершин ребенка максимального ранга. Тонкой кучей называется коллекция тонких деревьев. Операции insert, Ограничений на число деревьев одного ранга нет. Разработайте операции 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)$# Петя предлагает сделать гибрид декартового дерева и сплей-дерева: при выполнении которой заключительная операция decreaseKey доступе к ключу в декартовом дереве удалять его и добавлять заново с приоритетом меньше текущего минимального. Что у него получилось?# Проведите анализ случай 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 \Omegalog n + m + \sum(n\log(|q_i - f| + 1)))$, где $q_i$ - $i$-й запрос# Предложите реализацию insert в декартовом дереве.# Предложите реализацию insert в декартовом дереве, использующую не более одного вызова split/merge.# Предложите реализацию remove в декартовом дереве.# Предложите реализацию remove в декартовом дереве, использующую не более одного вызова split/merge.

# Решите задачу: найти во взвешеном дереве минимальный по весу путь, состоящий ровно из $k$ ребер# Пусть в реализации СНМ с помощью леса корневых деревьев мы при объединении двух деревьев делаем корнем случайную из двух вершин. Приведите пример, где высота дерева в результате серии объединений будет $\Omega(n)$.# Пусть в реализации СНМ на списках с ранговой эвристикойпомощью леса корневых деревьев мы при объединении двух деревьев делаем корнем случайную из двух вершин. Будем хранить каждой множество Сжатие путей не проводится. Докажите или опровергните, что в среднем время работы get будет $O(\log n)$.# Докажите, что если при реализации СНМ как список его элементовс помощью леса корневых деревьев подвешивать одно дерево на другое произвольным образом, каждый элемент знает головуно не проводить сжатие путей, голова знает хвост. Тогда объедиенение двух списков происходит за то среднее время пропорциональное длине одного из нихработы get будет $O(\log n)$. # Докажите, что если каждый раз добавлять меньший список к большемупри реализации СНМ с помощью леса корневых деревьев подвешивать одно дерево на другое случайным образом и проводить сжатие путей, суммарное то среднее время работы всех операций Union 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)$.# Предложите обобщение дерева Фенвика на многомерный запрос# Пусть операция в дереве Фенвика некоммутативна. Предложите модификацию, которая позволит использовать дерево Фенвика, время работы get будет на запрос обновления $O(\log ^2 n)$.# Встречное дерево Фенвика. Пусть у операции в дереве Фенвика нет обратного. Будем хранить два дерева $f[i]$ и $g[i]$, где $f[i]$ - обычное дерево Фенвика, а $g[i]$ - сумма элементов с $a[i + 1]$ до $a[i + 2^{h(i)}]$. Предложите алгоритм выполнения операций изменения элемента и получения статистики на отрезке в получившемся дереве.# Предложите реализацию операции удаления ключа в дереве Ван Эмде Боаса.# Предложите модификацию дерева Ван Эмде Боаса, где и минимум и максимум хранятся отдельно, но не в детях.