22
правки
Изменения
Нет описания правки
# Пусть полиномиальный вероятностный алгоритм $\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$, чтобы можно было решить задание 105, используя равномерный с точностью до $\rho \le 1/n^b$ генератор.
# Докажите, что если степень любой вершины в графе не меньше $n/2$, то выполнено условие $1/n^2 \le r \le n^2$ для задания 88105.
# Соедините предыдущие задания, чтобы получить из существования равномерного с точностью до $\rho \le 1/n^b$ генератора $\hat U_k$ для любого $k$ $\varepsilon$-$\delta$-FPRAS для числа совершенных паросочетаний в двудольном графе, где степени всех вершин не меньше $n/2$.
# Рассмотрим $\varepsilon$-$\delta$-FPRAS $A$ для числа паросочетаний в двудольном графе. Используя $A$, постройте полиномиальный вероятностный алгоритм, который является равномерным генератором с точностью до $\rho = o(1)$.
# Пусть матрица переходов эргодической марковской цепи является дважды стохастической (сумма элементов каждого столбца также равна 1). Докажите, что стационарное распределение $(1/n, 1/n, \ldots, 1/n)$.
# Пусть матрицы $A$ и $B$ имеют один и тот же собственный вектор $x$ для собственных чисел $\lambda$ и $\mu$, соответственно. Докажите, что $x$ является собственным вектором для $A+B$. Для какого собственного числа?
# Задана правильная скобочная последовательность с $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))$. Опишите с помощью операций предыдущих задач операции: перехода к родителю, перехода к первому ребенку, перехода к следующему ребенку.
# Размер поддерева. Опишите с помощью операций из предыдущих задач способ узнать размер поддерева для заданной вершины.
# Глубина вершины. Опишите с помощью операций из предыдущих задач способ узнать глубину вершины.
# Опишите в терминах скобочных последовательностей операцию LCA. Предложите решение за $O(1)$ и $o(n)$ дополнительной памяти.
