Изменения
Нет описания правки
# Универсальное семейство $H$ хеш функций обладает свойством попарной независимости, если для любых двух злементов $x$ и $y$ и любых двух хеш-значений $a$ и $b$ вероятность того, что $h(x) = a$ и $h(x) = b$ есть $1/m^2 + o(1 / m^2)$ (вероятность берется по случайному выбору хеш-функции из множества $H$). Докажите, что семейство из предыдущего задания обладает этим свойством.
# Докажите, что если в ориентированном графе существует цикл, то в алгоритме dfs мы попытаемся пойти в серую вершину.
# Решите задачу: есть $n$ гирек разного веса. Сделали $m$ взвешиваний на чашечных весах: по одной гирьке на каждой чаше. Известны результаты этих взвешиваний. Определите какой-нибудь порядок гирек, который не противоречит результатам взвешивания за $O(n + m)$.# Решите задачу: есть $n$ гирек разного веса. Сделали $m$ взвешиваний по порядку на чашечных весах: по одной гирьке на каждой чаше. Известны возможные результаты этих взвешиваний, возможно, некоторые из них некорректные. Определите, после какого из взвешиваний, полученная информация стала противоречивой за $O((n + m) \log n)$.# Предложите алгоритм, который находит лексикографически минимальную топологическую сортировку за $O((V + E) \log V)$.
# Предложите алгоритм, который находит топологическую сортировку, у которой обратная перестановка минимальна лексикографически за $O((E + V) \log V)$.
# Предложите алгоритм, который добавляет в граф не более $k$ ребер, чтобы лексикографически минимальная топологическая сортировка была максимальна за $O((E + V) \log V)$.
