211
правок
Изменения
Нет описания правки
# Пусть матрица переходов эргодической марковской цепи является дважды стохастической (сумма элементов каждого столбца также равна 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)$ дополнительной памяти.
# $1 | p_i=1 | L_{max}$.
# $1 | r_i, d_i=d | L_{max}$.
# $1 | prec, r_i, p_i=1 | L_{max}$.
# Рассмотрим задачу $1 | p_i = 1, d_i | -$. Докажите, что подмножества работ, которые можно выполнить, образуют семейство независимых множеств некоторого матроида.
# $1 | p_i = 1, d_i | \sum w_iU_i$. Время $O(n\log n)$.
# $1 | p_i = 1, d_i, r_i | \sum U_i$. Время - полином от $n$.
# $1 | p_i = 1, d_i, r_i | \sum w_iU_i$. Время - полином от $n$.
# $1 | p_i = p, pmtn, r_i | \sum w_iU_i$ за $O(n^{10})$.
# $1 || \sum U_i$
# $1 | r_i, p_i = p | \sum w_iC_i$ за $O(n^7)$
# Обозначение outtree означает, что граф зависимостей представляет собой исходящее дерево: каджая работа зависит не более чем от одной другой. $1 | outtree | \sum w_iC_i$
# Обозначение intree означает, что граф зависимостей представляет собой входящее дерево: от каждой работы зависит не более одной другой. $1 | intree | \sum w_iC_i$
# $P | pmtn, r_i | C_{max}$
# $P | pmtn, r_i | L_{max}$
# $Q | pmtn, r_i | C_{max}$
# $P | p_i = p, r_i, d_i | \sum C_i$ за $O(n^3 \log n)$ (бонус за $O(n^3 \log\log n)$)
# $P | p_i = 1 | \sum w_iU_i$ - доведите доказательство с пары до конца# $F | p_{ij} = 1 | \sum C_i$
# $P | p_i = 1 | \sum w_iC_i$
# $P | p_i = 1, pmtn | \sum w_iC_i$
# $Q | pmtn | \sum C_i$
# $Q | pmtn | \sum f_i$ (напомним, что f_i - произвольная неубывающая функция, может быть своя у каждой работы)
# $Q | pmtn | f_{max}$
# $P2 | p_i = 1, prec, r_i | \sum C_i$ за $O(n^9)$
# Сведите задачу $R|pmtn|C_{max}$ к задаче линейного программирования.
# $P|intree, p_i=1|L_{max}$
# $F | p_{ij} = 1 | \sum C_i$
# $F2 | pmtn | C_{max}$
# $F | p_{ij} = 1 | \sum U_i$
# $F | p_{ij} = 1 | \sum w_iU_i$
# $O | p_{ij} = 1 | C_{max}$
# $O | p_{ij} = 1 | \sum C_i$
# $O | p_{ij} = 1 | \sum w_iC_i$
# $O | p_{ij} = 1, d_i | -$
# $O | p_{ij} = 1 | \sum U_i$
# $O | p_{ij} = 1 | \sum w_iU_i$
# $O | p_{ij} = 1, r_i | C_{max}$
# $O2 | p_{ij} = 1, prec | \sum C_i$
