Список заданий по ДМ-сем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)$ дополнительной памяти

</wikitex>