Изменения
Нет описания правки
# Для маленьких вершин $B(v)$ помещается в машинное слово, однако вместо списка $B(v)$ будем хранить вспомогательный список $C(v)$, устроенный так. Если самое тяжелое ребро на $i$-м по глубине пути из $A(v)$ находится ниже, чем $bigp[v]$, то будем хранить просто $l_i$. Иначе будем хранить $z_i$ - номер $l_i$ в $B(bigp[v])$. Обозначим упакованный в машинное слово список $C(v)$ за $C[v]$. Предложите алгоритм пересчета $С[v]$ за $O(1)$, перед этим можно выполнить общий для всех вершин предподсчет за $O(n+m)$. Вы можете использовать посчитанные для родителей и предков $C[u]$, $B(u)$, $A[u]$, $bigp[u]$.
# Объедините результаты всех предыдущих заданий, чтобы получить алгоритм обработки $m$ запросов поиска максимального ребра на пути между двумя вершинами на дереве за $O(n+m)$.
# Покажите, как свести задачу поиска минимального разреза в графе к $O(n)$ запускам алгоритма поиска минимального $s-t$ разреза.
# Покажите, как свести задачу поиска минимального $s-t$ разреза в графе к полиномимальному числу запусков алгоритма поиска глобального минимального разреза.
# Петя хочет упростить алгоритм Каргера-Штайна. Он запускает алгоритм Каргера (стягивание по случайному ребру), пока количество вершин не станет равно $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$ корней.
