Изменения
Нет описания правки
# Докажите, что конструкция семейства $H = \{ (ax + b) \bmod p \bmod m \}$, где случайно выбираются $a$ и $b$, $0 < a, b < p$, является универсальным семейством хеш-функций.
# Универсальное семейство $H$ хеш функций обладает свойством попарной независимости, если для любых двух злементов $x$ и $y$ и любых двух хеш-значений $a$ и $b$ вероятность того, что $h(x) = a$ и $h(x) = b$ есть $1/m^2 + o(1 / m^2)$ (вероятность берется по случайному выбору хеш-функции из множества $H$). Докажите, что семейство из предыдущего задания обладает этим свойством.
# Докажите, что если в ориентированном графе существует цикл, то в алгоритме dfs мы попытаемся пойти в серую вершину.# Предложите алгоритм, который находит лексикографически минимальную топологическую сортировку за $O((V + E) \log V)$# Предложите алгоритм, который находит топологическую сортировку, у которой обратная перестановка минимальна лексикографически за $O((E + V) \log V)$.# Предложите алгоритм, который добавляет в граф не более $k$ ребер, чтобы лексикографически минимальная топологическая сортировка была максимальна за $O((E + V) \log V)$.# Предложите алгоритм, который находит в ацикличном ориентированном графе какой-нибудь путь, который проходит по каждой вершине ровно один раз за $O(E + V)$.# Предложите алгоритм, который проверяет, что в ориентированном графе для любой пары вершин $(v, u)$ существует как путь из $v$ в $u$, так и путь из $u$ в $v$, за $O(E + V)$.# Задан ориентированный граф, у каждой вершины исходящая степень равна 1. У каждого ребра есть вес. Вы забыли про ориентацию ребер, найдите паросочетание максимального веса за $O(E + V)$.#
</wikitex>
