231
правка
Изменения
Нет описания правки
# Обозначим как $D_v = \{d(u) | \mbox{ there is a query path $uw$ that contains $v$}\}$. Пусть $S_v = D_v \downarrow M_v$. Докажите, что в условии предыдущей задачи $\{d(u)\}\downarrow M_v = \{d(u)\} \downarrow S_v$.
# Предложите алгоритм подсчета $D_v$ для всех вершин дерева за $O(n + m)$ (считайте, что битовые операции выполняются за $O(1)$.
# Известно, что у учителя есть $2^k$ яблок для некоторого целого неотрицательного $k$. На глазах у студентов он съедает одно яблоко, а остальное раздает ученикам А и В, чтобы ни один из них не видел, сколько получает другой. А и В не знают числа $k$. Они могут показать друг другу по одному знаку из трёх возможных: почесать голову правой, левой или обеими руками. К удивлению учителя, ученики всегда знают, кто получил больше яблок или что учитель съел единственное яблоко сам. Как такое возможно?
# Петя хочет упростить алгоритм Каргера-Штайна. Он запускает алгоритм Каргера (стягивание по случайному ребру), пока количество вершин не станет равно $t$, а затем запускает алгоритм за $t^3$ поиска минимального глобального разреза. Затем он повторяет алгоритм, пока вероятность успеха не составит хотя бы $1/2$. Какое значение $t$ необходимо выбрать, чтобы минимизировать время работы получившегося алгоритма? Какое будет время работы?
# Докажите, что если в полном двоичном дереве высоты $h$ каждое ребро удаляется с вероятностью $1/2$, то путь от корня до листа сохраняется с вероятностью $\Theta(1/h)$.
# Обобщите предыдущее задание, если ребро удаляется с вероятностью $p$.
# С учетом предыдущего задания модифицируйте алгоритм Каргера-Штайна, чтобы разветвляться когда накопленная вероятность ошибки достигнет $p$. Найдите зависимость времени работы от $p$, какое значение $p$ оптимально выбрать?
# Назовем разрез $\alpha$-оптимальным, если его размер не больше $\alpha C_{min}$, где $C_{min}$ - минимальный разрез. Оцените вероятность, что один запуск алгоритма Каргера (без разветвлений) найдет $\alpha$-оптимальный разрез (в зависимости от $\alpha$).
# Докажите, что в графе не больше $n\choose 2$ различных минимальных глобальных разрезов.
# Сформулируйте и докажите аналогичный предыдущему заданию результат для $\alpha$-оптимальных разрезов.
# Докажите, что для полинома $p(x_1, \ldots, x_n)$ от $n$ переменных степени $d$ над полем $F$ и множества $S\subset F$ размера $s$ вероятность $P(p(x_1, \ldots, x_n)=0)\le d/s$, где вероятностное пространство - равновероятно все вектора $(x_1, \ldots, x_n)\in S^n$. Используйте без доказательства, что полином от одной переменной степени $d$ над любым полем имеет не более $d$ корней.
# Покажите, что требование, что $F$ поле в предыдущей задаче является существенным, приведите пример полинома степени $d$ над кольцом, которое не является полем, имеющего более $d$ корней.
# Покажите, что в определении PRAS можно заменить константу $3/4$ в требовании, что вероятность попасть в интервал $[1-\varepsilon;1+\varepsilon]$ должна быть $3/4$, на любое другое число, строго большее $1/2$.
# Можно ли в предыдущем задании заменить $1/2$ на $0$?
# Можно ли в решении задания 73 брать среднее значение в качестве оценки?
# Рассмотрим формулу в ДНФ. Обозначим как $t$ количество пар $($терм$,$ удовлетворяющее этот терм назначение переменных$)$. Выберем случайно терм, где вероятность выбрать терм пропорциональна числу удовлетворяющих этот терм назначений. Выберем случайное назначение $a$, удовлетворяющее этот терм. Рассмотрим случайную величину $X = t/cov(a)$, где $cov(a)$ - число термов, удовлетворенных назначением $a$. Докажите, что $EX = Y$, где $Y$ - число удовлетворяющих назначений заданной формулы.
# На базе предыдущего задания предложите альтернативный алгоритм апроксимации числа удовлетворяющих назначений ДНФ.
# Рандомизированный алгоритм для 2SAT. Рассмотрим следующий алгоритм решения задачи удовлетворимости булевой формулы в 2КНФ с $n$ переменными. Выберем случайное значение каждой переменной. Если формула не удовлетворена, выберем случайный не удовлетворенный клоз и инвертируем значение случайной переменной в нем. Докажите, что если удовлетворяющее назначение существует, оно будет найдено за $O(n^2)$ шагов. Указание: зафиксируйте любое удовлетворяющее формулу назначение и рассмотрите задачу как случайное блуждание по прямой, где координата - это число переменных, значение которых совпадает с значением в выбранном назначении.
# Почему алгоритм из предыдущего задания не работает для 3SAT?
# Докажите, что оценку из задания 78 нельзя улучшить: предложите формулу, для которой в среднем понадобится $\Omega(n^2)$ случайных шагов для поиска удовлетворяющего назначения.
# Предложите аналогичный заданию 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$. Для какого собственного числа?
# Задана правильная скобочная последовательность с $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$
