Список заданий по продвинутым алгоритмам 2022 осень

1. Задания с 1 по 12 только для магистратуры. Бакалавриат пока отдыхает. Используя формулу Стирлинга $n!\approx \sqrt{2\pi n}\left(\frac{n}{e}\right)^n$ оцените, чему равна вероятность, что на $2n$ брошенных честных монетах выпадет поровну нулей и единиц. Найдите асимптотическое поведение при $n \to \infty$
2. Найдите распределение и математическое ожидание следующей случайной величины: число бросков нечестной монеты до первого выпадения 1.
3. 10 шаров раскладываются по 5 корзинам. Для каждого шара равновероятно выбирается, в какую корзину он помещается. Какое математическое ожидание числа пустах корзин? Числа корзин, содержащих ровно один шар?
4. Предложите метод генерации случайной перестановки порядка $n$ с равновероятным распределением всех перестановок, если мы умеем генерировать равномерно распределенное целое число от 1 до $k$ для любых небольших $k$ ($k = O(n)$).
5. Дает ли следующий метод равномерную генерацию всех перестановок? ""p = [1, 2, ..., n]; for i from 1 to n: swap(p[i], p[random(1..n)] )""
6. Рассмотрим следующий метод генерации случайной перестановки. Применим алгоритм из задания 5, а затем к получившейся перестановке верный алгоритм из задания 4. Будет ли полученное распределение на перестановках равномерным? Применим верный алгоритм из задания 4, а затем к получившейся перестановке алгоритм из задания 5. Будет ли полученное распределение на перестановках равномерным?
7. Предложите метод генерации случайного сочетания из $n$ по $k$ с равновероятным распределением всех сочетаний, если мы умеем генерировать равномерно распределенное целое число от 1 до $t$ для любых небольших $t$ ($t = O(n)$), использующий $O(k)$ времени и памяти.
8. Улучшить неравенство Маркова в общем случае нельзя. Докажите, что для любого $c > 1$ найдется такая неотрицательная случайная величина $\xi$, что $P(\xi \ge cE\xi) = 1/c$.
9. Можно ли подобрать такую неотрицательную случайную величину $\xi$, чтобы для двух различных $c_1 > 1$ и $c_2 > 1$ выполнялось $P(\xi \ge c_iE\xi) = 1/c_i$ ($i \in \{1, 2\}$)?
10. Для какого максимального $\alpha$ можно подобрать такую неотрицательную случайную величину $\xi$, чтобы для двух различных $c_1 > 1$ и $c_2 > 1$ выполнялось $P(\xi \ge c_iE\xi) = \alpha/c_i$ ($i \in \{1, 2\}$)?
11. Улучшить неравенство Чебышева в общем случае нельзя. Докажите, что для любого $c > 0$ найдется такая отличная от константы случайная величина $\xi$, что $P(|\xi - E\xi| \ge c) = D\xi/c^2$.
12. Улучшить неравенство Чебышева нельзя даже для суммы. Докажите, что для любого $c > 0$ найдется такое семейство одинаково распределенных отличных от константы случайных величин $\xi_1, \xi_2, \ldots, \xi_n$, что $P(|\sum\xi_i - \sum E\xi_i| \ge c) = nD\xi/c^2$.
13. Докажите, что дисперсия возвращаемого значения в алгоритме Морриса не превышает $1/2n^2$
14. Докажите, что дисперсия возвращаемого значения в алгоритме Флажолета-Мартина не превышает $1/(t+1)^2$
15. Доминирующий элемент. Рассмотрим алгоритм, который ищет элемент, который встречается хотя бы $n/2$ раз в потоке $[a_1, \ldots, a_n]$. Пусть $0 \le a_i < N$ и $N \ge 2n$. Докажите, что детерминированный алгоритм, использующий $o(n\log(N/n))$ бит, не может решить поставленную задачу. Указание: рассмотрите состояние после половины элементов потока.
16. Предложите алгоритм, использующий $O(\log(N+n))$ бит, который решает предыдущую задачу в предположении, что доминирующий элемент существует.
17. Обобщите предыдущий алгоритм на случай $\varepsilon$-частых элементов: будем называть элемент $\varepsilon$-частым, если он составляет хотя бы $\varepsilon$ долю элементов во вводе. Как зависит память от $\varepsilon$?
18. Все различные. Докажите или опровергните, что любой детерминированный алгоритм, который всегда корректно отвечает, верно ли, что все элементы во вводе $[a_1, a_2, \ldots, a_n]$ различны, должен использовать хотя бы $\Omega(n\log(2N/n))$ памяти.
19. Недостающий элемент. Задан массив $[a_1, a_2, \ldots, a_{n-1}$, где все элементы от $1$ до $n$, кроме одного, встречаются ровно один раз. Найдите недостающий элемент, используя $O(\log n)$ памяти.
20. Два недостающих элемента. Задан массив $[a_1, a_2, \ldots, a_{n-2}$, где все элементы от $1$ до $n$, кроме двух, встречаются ровно один раз. Найдите недостающие элементы, используя $o(n)$ памяти.