1632
правки
Изменения
м
rollbackEdits.php mass rollback
# Предложите аналогичный заданию 78 алгоритм поиска раскраски графа в два цвета.
# Почему алгоритм из предыдущего задания не работает для поиска раскраски графа в три цвета?
# Обозначим как $m_k(G)$ количество паросочетаний размера $k$ в двудольном графе $G$, каждая доля которого содержит по $n$ вершин. Пусть граф содержит больше $k$ ребер. Докажите, что существует ребро $uv$, такое что $m_k(G)/m_k(G\setminus uv) \le n$.
# Пусть вероятностный алгоритм $U_k$ получает на вход граф $G$ и выдает случайное паросочетание в $G$ размера $k$, причем все паросочетания равновероятны. Покажите, как с использованием $U_k$ получить $\varepsilon$-$\delta$-FRPAS для доли паросочетаний, содержащих заданное ребро $uv$ в графе $G$.
# Покажите, как с использованием $U_k$ из предедыдущего задания получить $\varepsilon$-$\delta$-FRPAS для числа $m_k(G)$.
# Будем называть полиномиальный вероятностный алгоритм $U_k$ равномерным с точностью до $\rho$ генератором, если он получает на вход граф $G$ и выдает случайное паросочетание в $G$ размера $k$, причем для любого паросочетания $M$ $|P(U_k(G)=M) - 1/m_k(G)| \le \rho/m_k(G)$. Пусть $\rho \le 1/n^b$ для некоторого $b$. Подберите константу $b$, чтобы можно было решить задание 84, используя равномерный с точностью до $\rho$ генератор.
# Подберите константу $b$, чтобы можно было решить задание 85, используя равномерный с точностью до $\rho$ генератор.
# Пусть полиномиальный вероятностный алгоритм $\hat U_k$ получает на вход граф $G$ и выдает случайное паросочетание в $G$ размера $k$ или $k-1$, причем все паросочетания равновероятны. Пусть $r = m_k(G)/m_{k-1}(G)$ удовлетворяет условию $1/n^2 \le r \le n^2$. Докажите, что с помощью $\hat U_k$ можно получить $\varepsilon$-$\delta$-FRPAS для $m_k(G)$.
# Подберите константу $b$, чтобы можно было решить задание 88, используя равномерный с точностью до $\rho \le 1/n^b$ генератор.
# Докажите, что если степень любой вершины в графе не меньше $n/2$, то выполнено условие $1/n^2 \le r \le n^2$ для задания 88.
# Соедините предыдущие задания, чтобы получить из существования равномерного с точностью до $\rho \le 1/n^b$ генератора $\hat U_k$ для любого $k$ $\varepsilon$-$\delta$-FPRAS для числа совершенных паросочетаний в двудольном графе, где степени всех вершин не меньше $n/2$.
# Рассмотрим $\varepsilon$-$\delta$-FPRAS $A$ для числа паросочетаний в двудольном графе. Используя $A$, постройте полиномиальный вероятностный алгоритм, который является равномерным генератором с точностью до $\rho = o(1)$.
# Пусть существует полиномиальный детерминированный алгоритм, который возвращает число совершенных паросочетаний в двудольном графе, степень каждой вершины которого равна хотя бы $\beta n$, где $0 < \beta < 1$. Докажите, что существует полиномиальный детерминированный алгоритм, который возвращает число совершенных паросочетаний в произвольном двудольном графе.
# Рассмотрим алгоритм приближения числа $\pi$. Будем генерировать точки с равномерным распределением в квадрате $1 \times 1$ и считать долю попавших в круг диаметром 1, вписанный в этот квадрат. Оцените число итераций, необходимое, чтобы приблизить $\pi$ с точностью до $\varepsilon$.
# Пусть матрица переходов эргодической марковской цепи является дважды стохастической (сумма элементов каждого столбца также равна 1). Докажите, что стационарное распределение $(1/n, 1/n, \ldots, 1/n)$.
# Пусть матрицы $A$ и $B$ имеют один и тот же собственный вектор $x$ для собственных чисел $\lambda$ и $\mu$, соответственно. Докажите, что $x$ является собственным вектором для $A+B$. Для какого собственного числа?
# Задача приблизительного подсчета числа вхождений. Biased Sketch. Рассмотрим алгоритм: выберем случайную хеш-функцию $h: U\to \{0,1, \ldots, m-1\}$ из универсального семейства. Заведем счетчик $cnt[0\ldots m-1]$ и в качестве операцими $update(x)$ будем делать $cnt[h(x)]$++, а в качестве $query(x)$ будем возвращать $cnt[h(x)]$. Пусть выполнено $n$ запросов $update$. Обозначим как $a(x)$ количество вхождений числа $x$. Оцените $P(query(x) > a(x) + \varepsilon n)$.
# CountMin. В предыдущей задаче чтобы лучше оценить количество, будем использовать несколько хеш-функций. Пусть мы используем $r$ хеш-функций, для каждой свой массив $cnt_i$, в качестве ответа на запрос будем выдавать $\min(cnt_i[h_i(x)])$. Какое $r$ необходимо выбрать, чтобы выполнялось $P(query(x) > a(x) + \varepsilon n) < \delta$?
# Задача приблизительного подсчета числа вхождений. Unbiased Sketch. Рассмотрим алгоритм: выберем случайную хеш-функцию $h: U\to \{0,1, \ldots, m-1\}$ из универсального семейства, а также случайную знаковую функцию $s: U \to \{-1,1\}$. Заведем счетчик $cnt[0\ldots m-1]$ и в качестве операцими $update(x)$ будем делать $cnt[h(x)]$ += s(x), а в качестве $query(x)$ будем возвращать $cnt[h(x)]\cdot s(x)$. Пусть выполнено $n$ запросов $update$. Обозначим как $a(x)$ количество вхождений числа $x$. Докажите, что $D[query(x)] \le \frac{1}{m}\sum_y a(y)^2$.
# В условиях предыдущей задачи обозначим как $\lVert a \rVert_2 = \sqrt{\sum_x a(x)^2}$. Оцените $P(|query(x) - a(x)| > \varepsilon \lVert a \rVert_2)$.
# CountSketch В предыдущей задаче чтобы лучше оценить количество, будем использовать несколько хеш-функций. Пусть мы используем $r$ хеш-функций, для каждой свой массив $cnt_i$, в качестве ответа на запрос будем выдавать $median(cnt_i[h_i(x)])$. Какое $r$ необходимо выбрать, чтобы выполнялось $P(|query(x) - a(x)| > \varepsilon \lVert a \rVert_2) < \delta$?
# Сравните оценки по времени, памяти и точности для CountMin и CountSketch. Сделайте вывод, когда какой из них лучше.
# Поиск $k$ самых частых. Используем тот или иной аппроксимационный алгоритм (CountMin или CountSketch), мы хотим найти $k$ самых частых элементов в последовательности $a_1, \ldots, a_n$. Будем поддерживать $set$ из $k$ самых частых, упорядоченный по оценке на число их вхождений. Рассматривая очередной элемент, добавляем его в set, если его оценка на число вхождений становится больше, чем у самого редкого в $set$-е. Оцените вероятность, что для всех $x$ в $set$-е в конце выполнено $a(x) \ge (1-\varepsilon)a(y)$, где $y$ - это $k$-й по частоте встречаемости элемент.
# Доминирующий элемент. Рассмотрим алгоритм, который ищет элемент, который встречается хотя бы $n/2$ раз в потоке $[a_1, \ldots, a_n]$. Пусть $0 \le a_i < N$ и $N \ge 2n$. Докажите, что детерминированный алгоритм, использующий $o(n\log(N/n))$ бит, не может решить поставленную задачу. Указание: рассмотрите состояние после половины элементов потока.
# Предложите алгоритм, использующий $O(\log(N+n))$ бит, который решает предыдущую задачу в предположении, что доминирующий элемент существует.
# Обобщите предыдущий алгоритм на случай $\varepsilon$-частых элементов: будем называть элемент $\varepsilon$-частым, если он составляет хотя бы $\varepsilon$ долю элементов во вводе. Как зависит память от $\varepsilon$?
# Все различные. Докажите или опровергните, что любой детерминированный алгоритм, который всегда корректно отвечает, верно ли, что все элементы во вводе $[a_1, a_2, \ldots, a_n]$ различны, должен использовать хотя бы $\Omega(n\log(2N/n))$ памяти.
# Недостающий элемент. Задан массив $[a_1, a_2, \ldots, a_{n-1}$, где все элементы от $1$ до $n$, кроме одного, встречаются ровно один раз. Найдите недостающий элемент, используя $O(\log n)$ памяти.
# Два недостающих элемента. Задан массив $[a_1, a_2, \ldots, a_{n-2}$, где все элементы от $1$ до $n$, кроме двух, встречаются ровно один раз. Найдите недостающие элементы, используя $o(n)$ памяти.
# Задана правильная скобочная последовательность с $n$ открывающими скобками. Рассмотрим четыре операции: findclose($i$) - найти закрывающую парную скобку для открывающей скобки на позиции $i$, findopen($i$) - найти открывающую парную скобку для закрывающей на позиции $i$, enclose($i$) - найти позицию открывающей скобки для пары скобок, непосредственно внутри которой находится открывающая скобка на позиции $i$, balance($i$) - найти баланс на позиции $i$. Используйте с rank и select с лекции, чтобы вычислить balance за $O(1)$ и $o(n)$ дополнительной памяти.
# Используйте balance и идеи с лекции, чтобы реализовать $findclose$, $findopen$ и $enclose$.
# Задано дерево (не обязательно двоичное) с порядком на детях. Для представления дерева используется правильная скобочная последовательность: запись вершины $u$ с детьми $v_1, v_2, \ldots, v_k$, обозначенная как $R(u)$ устроена так: $R(u) = (R(v_1)R(v_2)\ldots R(v_l))$. Опишите с помощью операций из задачи 110 операции: перехода к родителю, перехода к первому ребенку, перехода к следующему ребенку.
# Размер поддерева. Опишите с помощью операций из задачи 110 способ узнать размер поддерева для заданной вершины.
# Глубина вершины. Опишите с помощью операций из задач 110 способ узнать глубину вершины.
# Опишите в терминах скобочных последовательностей операцию LCA. Предложите решение за $O(1)$ и $o(n)$ дополнительной памяти.
