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

<wikitex>

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

1. Докажите, что для монеты энтропия максимальна в случае честной монеты
2. Докажите, что для n исходов энтропия максимальна если они все равновероятны
3. Зафиксируйте ваш любимый язык программирования. Колмогоровской сложностью $K(x)$ для слова $x$ называется длина минимальной программы, которая выводит слово $x$. Докажите, что колмогоровская сложность не превышает $n H(x) + O(\log n)$, где $n$ - длина строки $x$, $H(x)$ - энтропия случайного источника с распределением соответствующим частотам встречания символов в $x$, константа в $O$, не зависит от слова $x$ (но может зависеть от выбранного языка программирования)
4. Докажите, что для любого $c > 0$ найдется слово, для которого $K(x) < c H(x)$
5. Пусть заданы полные системы событий $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)$
6. Что можно сказать про $H(A | B)$ если $a_i$ и $b_j$ независимы для любых $i$ и $j$?
7. Что можно сказать про $H(A | A)$?
8. Постройте схему получения вероятности 1/3 с помощью честной монеты, имеющую минимальное математическое ожидание числа бросков. Докажите оптимальность вашей схемы.
9. Рассмотрим случайное блуждание точки на прямой, пусть точка начинает в точке $p$ ($p$ - целое) и каждую секунду переходит равновероятно на 1 влево или вправо. Точка поглощается в точках 0 и $n$ ($n$ целое, больше $p$). Найдите вероятность поглощения в точке 0.
10. Рассмотрим случайное блуждание точки на прямой, пусть точка начинает в точке 0 и каждую секунду переходит равновероятно на 1 влево или вправо. Докажите, что математическое ожидание максимума координаты точки за $n$ шагов есть $O(\sqrt{n})$.
11. Докажите, что математическое ожидание числа экспериментов при симуляции одного распределения другим асимптотически равно отношению энтропий распределений (считайте, что энтропия симулируемого распределения больше).
12. Пусть $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)$?
13. Проанализировать саморасширяющийся массив, если расширение происходит в $A$ раз ($1 < A$)
14. Проанализировать стек на саморасширяющемся массиве, если при полном заполнении происходит увеличение в 2 раза, а при заполнении менее чем на 1/4 - сужение в 2 раза с помощью метода потеницалов. Потенциал должен зависеть только от текущего состояния стека (размера выделенного массива и числа заполненных элементов) и не должен зависеть от истории операций.
15. Проанализировать стек на саморасширяющемся массиве, если при полном заполнении происходит увеличение в A раз, а при заполнении менее чем на B - сужение в C раза
16. Разработать вектор с добавлением/удалением с истинной стоимостью всех операций $O(\log n)$.
17. Задан односвязный список, каждый элемент знает следующий после себя. При этом возможно, что на самом деле список зацикливается (один из элементов ссылается как на следующий на элемент, который уже встречался в списке перед ним). Требуется проверить, зацикливается ли заданный односвязный список за $O(n)$ с $O(1)$ дополнительной памяти
18. В массиве есть элемент, который встречается хотя бы $n/2$ раз. Требуется найти его за $O(n)$ с $O(1)$ дополнительной памяти
19. Использования памяти без инициализации. Задан массив $a[1..n]$. Требуется поддержать две операции: $set(i, x)$ и $get(i)$. Операция $set$ должна присваивать $i$-му элементу массива значение $x$. Операция $get$ должна возвращать последнее присвоенное $i$-му элементу значение, либо 0, если присвоения не было. При этом исходно массив заполнен произвольными данными. Разрешается завести $O(1)$ дополнительных массивов (также заполненных произвольным мусором) и реализовать все операции за истинное $O(1)$.
20. Можно ли просимулировать два стека на одной очереди?
21. Счетчик Кнута. Рассмотрим массив $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)$ дополнительной памяти.
22. Реализуйте менеджер памяти, позволяющий выделять и возвращать блоки одинакого размера за $O(1)$ времени и $O(1)$ дополнительной памяти
23. В $d$-куче выполняется $m$ операций decreaseKey и $n$ операций extractMin. Какое оптимальное асимптотически $d$ следует выбрать?
24. В $d$-куче выполняется $m$ операций decreaseKey и $n$ операций extractMin. Время выполнения decreaseKey - $C_1 \log n$, а extractMin - $C_2 d \log n$. Какое $d$ следует выбрать?
25. Как найти $s$-й по величине элемент в куче при малых $s$?
26. Приведите алгоритм построения кучи из $n$ заданных элементов за $O(n)$
27. На базе кучи разработайте алгоритм сортировки за $O(n \log n)$ c $O(1)$ дополнительной памяти
28. Левосторонние кучи. Будем называть двоичное дерево левосторонней кучей, если в нем выполнены следующие условия. 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)$?
29. Предложите реализацию операции merge для левосторонних куч.
30. Предложите реализацию операций insert, extractMin для левостронних куч.
31. Предложите реализацию операций decreaseKey для левостронних куч.
32. Как построить левостороннюю кучу из $n$ элементов за $O(n)$?
33. Пусть подряд выполняется $n$ операций insert в пустую биномиальную кучу. Какое среднее время операции?
34. Как можно модифицировать биномиальную кучу, чтобы insert выполнялось за истиное $O(1)$, а амортизированная стоимость остальных операций не поменялась?
35. Тонкие кучи. Будем называть дерево "тонким", если оно может быть получено из биномиального удалением у некоторых вершин ребенка максимального ранга. Тонкой кучей называется коллекция тонких деревьев. Операции insert, extractMin и merge выполняются в тонкой куче также, как в куче Фибоначчи. Разработайте операцию decreaseKey для тонкой кучи. Докажите, что амортизированное время выполнения есть $O(1)$ (используйте потенциал $2M + T$, где $M$ - число вершин, у которых удалили ребенка)
36. Тонкие кучи. Докажите, что операция decreaseKey в тонкой куче из предыдущего задания выполняется за истиные $O(\log n)$
37. Ускорение extractMin. Докажите, что в фибоначчиевой или тонкой куче можно добиться истинного $O(\log n)$ на extractMin, если обрабатывать корневой список, сливая деревья разных рангов, как при extractMin каждый раз, когда в корневом списке становится хотя бы $2\log n$ элементов.
38. Продемонстрируйте последовательность операций с фибоначчиевой кучей, при выполнении которой заключительная операция decreaseKey выполняется за истиное $\Omega(n)$
39. Докажите оценку $O(\log n)$ для реализации СНМ со сжатием путей, но когда второе дерево всегда подвешивается на первое (а не обязательно меньшее на большее)
40. Докажите оценку $O(\log^* n)$ для СНМ, если вместо рангов используется число вершин в поддереве (меньшее дерево подвешивается на большее)
41. СНМ на списках с ранговой эвристикой. Будем хранить каждой множество в СНМ как список его элементов, каждый элемент знает голову, голова знает хвост. Тогда объедиенение двух списков происходит за время пропорциональное длине одного из них. Докажите, что если каждый раз добавлять меньший список к большему, суммарное время работы всех операций Union будет $O(n \log n)$.
42. Решите задачу: найти во взвешеном дереве минимальный по весу путь, состоящий ровно из $k$ ребер
43. Пусть в реализации СНМ с помощью леса корневых деревьев мы при объединении двух деревьев делаем корнем случайную из двух вершин. Сжатие путей не проводится. Докажите или опровергните, что в среднем время работы get будет $O(\log n)$.
44. Для каких $a$ определен $\log^*_a x$?
45. Докажите, что если для $a$ и $b$ определен $\log^*_a x$ и $\log^*_b x$, то $\log^*_a x = O(\log^*_b x)$?
46. АВЛ-дерево: у каждой вершины высота левого и правого поддерева различается не более чем на 1. Докажите, что высота АВЛ-дерева есть $O(\log n)$
47. Докажите, что после добавления элемента в АВЛ дерево можно восстановить баланс за $O(1)$ балансировок.
48. Предложите алгоритм удаления из АВЛ-дерева.
49. Красно-черное дерево: все вершины красные или черные, у красной вершины не может быть красного родителя, черная высота любой свободной позиции (отсутствующего сына вершины) одинаковая. Докажите, что высота красно-черного дерева есть $O(\log n)$
50. Предложите алгоритм добавления в красно-черное дерево
51. Предложите алгоритм удаления из красно-черного дерева
52. Статически оптимальное дерево поиска: пусть заданы ключи и известно для каждого ключа, сколько раз его потребуется искать: $p[i]$. Требуется построить дерево поиска, чтобы суммарное время доступа ко всем ключам было минимально.
53. Мальчик Петя в предыдущей задаче предложил построить декартово дерево с приоритетом $p[i]$. Приведите контрпример.
54. Предложите алгоритм слияния двух АВЛ-деревьев, при том, что в первом дереве все ключи меньше, чем во втором за $O(\log n)$
55. Предложите алгоритм разделения АВЛ-дерева на два, где в первом дереве все ключи меньше или равны заданному $x$, а во втором - больше, за $O(\log n)$
56. В АВЛ-дереве находятся вершины с ключами от 1 до $n$. Какие ключи могут быть в корне?
57. В красно-черном дереве находятся вершины с ключами от 1 до $n$. Какие ключи могут быть в корне?
58. Предложите реализацию АВЛ-дерева, в которой в каждом узле хранится $O(1)$ бит
59. Перекошенное сбалансированное дерево. Дерево называется перекошенным сбалансированным, если у каждой вершины разность высоты левого и правого поддерева 0, 1 или 2. Предолжите реализацию операций вставки и удаления для перекошенного сбалансированного дерева.
60. Мальчик Петя считает, что если в дереве поиска можно хранить несколько одинаковых ключей, то на пути от одного такого ключа до другого не может быть ключей с другим значением. Тогда можно легко найти все такие ключи. Прав ли он?
61. Пусть заданы наборы ключей $(x_1, x_2, ..., x_n)$ и $(y_1, y_2, ..., y_n)$, где все $x$-ы и все $y$-и различны. Докажите, что существует единственное декартово дерево с набором ключей в вершинах $(x_i, y_i)$
62. В условиях предыдущей задачи пусть $x_1 < x_2 < .. < x_n$, покажите как построить декартово дерево за $O(n)$
63. Петя предлагает сделать гибрид декартового дерева и сплей-дерева: при доступе к ключу в декартовом дереве удалять его и добавлять заново с приоритетом меньше текущего минимального. Что у него получилось?
64. Проведите анализ случай zig для сплей-дерева по аналогии с случаем zig-zag, рассмотренном на лекции
65. Проведите анализ случай zig-zig для сплей-дерева по аналогии с случаем zig-zag, рассмотренном на лекции
66. Статическая оптимальность сплей-дерева. Докажите, что если к ключам $1, ..., n$, сложенным в сплей-дерево выполняется m запросов, к $i$-му ключу осуществляется $k_i$ запросов, где $k_i > 0$, то суммарное время работы не превышает $O(m H(p_1, p_2, .., p_n))$, где $p_i = k_i / m$, $H$ - шенноновская энтропия
67. Постройте пример сплей-дерева, содержащего не менее 6 вершин, которое после выполнения операции splay для одного из самых глубоких листьев становится бамбуком
68. Постройте пример сплей-дерева, содержащего не менее 7 вершин, которое после выполнения операции splay для одного из самых глубоких листьев становится бамбуком
69. Теорема о близких запросах в сплей-дереве. Пусть в сплей-дерево сложены ключи $1, ..., n$, зафиксируем один из ключей $f$, пусть выполняется $m$ запросов к ключам. Докажите, что суммарное время на запросы есть $O(n \log n + m + \sum(\log(|q_i - f| + 1)))$, где $q_i$ - $i$-й запрос
70. Докажите, что математическое ожидание глубины вершины в декартовом дереве есть $O(\log n)$
71. Докажите, что математическое ожидание глубины самого глубокого листа в декартовом дереве есть $O(\log n)$
72. Какой размер множества одинаковых равномерно распределенных от 1 до $n$ независимых случайных величин необходимо, чтобы вероятность того, что две из них принимают одинаковое значение, была хотя бы $1/2$? Сделайте вывод о вероятности коллизий в хеш-таблице с игнорированием коллизий.
73. Пусть для хеширования строк используется полиномиальный хеш: $h(s) = (s[0]t^{n-1} + s[1]t^{n-2} + ... + s[n - 2]t + s[n-1]) \bmod 2^k$. Покажите, что в строке Туе-Морса есть много различных подстрок с одинаковым хеш-значением для любого $t$
74. Пусть для хеширования строк используется полиномиальный хеш: $h(s) = (s[0]t^{n-1} + s[1]t^{n-2} + ... + s[n - 2]t + s[n-1]) \bmod r$. Предложите способ получения двух строк с одинаковым значением $h$ для заданных $t$ и $r$
75. Пусть для хеширования строк используется полиномиальный хеш: $h(s) = (s[0]t^{n-1} + s[1]t^{n-2} + ... + s[n - 2]t + s[n-1]) \bmod r$. Покажите, что для достаточно большого $n$ существуют две различные строки длины $n$, которые отличаются в константном числе позиций, но имеющие одинаковое хеш-значение
76. Предложите алгоритм удаления из хеш-таблицы с разрешением конфликтов с помощью открытой адресации, который не использует пометок "удалено", а действительно удаляет элемент из таблицы
77. Пусть при хешировании используется разрешение конфликтов с открытой адресацией, размер хеш-пространства равено $cn$, где $n$ - число элементов. Оцените среднюю длину кластера (участка из подряд идущих занятых ячеек)
78. Универсальное семейство $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 \}$ обладает этим свойством.
79. Приведите пример универсального семейства хеш-функций для множества натуральных чисел, при вычислении хеш-функций в котором не используются операции деления и взятия по модулю. Достаточно $O(1/m)$-универсальности
80. Оцените вероятность неудачи при добавлении элемента в хешировании кукушки.
81. Докажите, что в хешировании кукушки добавление выполняется в среднем за $O(1)$.
82. Оцените среднюю длину максимального списка при разрешении конфликтов в хешировании с помощью метода списков. Пусть для хеширования $n$ элементов используются $n$ списков.

</wikitex>