207
правок
Изменения
Нет описания правки
# Пусть матрица переходов эргодической марковской цепи является дважды стохастической (сумма элементов каждого столбца также равна 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)$ дополнительной памяти.
