106
правок
Изменения
→Хранение множества со сверхбыстрым запросом элементов
===Хранение множества со сверхбыстрым запросом элементов===
Мы организуем хранение m-элементного множества <tex>S \subset \{1, . . . , n\}</tex> в виде описания <tex>X</tex>, состоящего из <tex>O(m log n)</tex> битов. При этом проверка принадлежности <tex>a \in S</tex> будет производиться чрезвычайно быстро. А именно, мы построим такой вероятностный алгоритм, который по любому входу <tex>a</tex> запрашивает из <tex>X</tex> один бит; если этот бит оказывается равным единице, то алгоритм отвечает, что <tex>a</tex> является элементом <tex>S</tex>; в противном случае алгоритм говорит, что <tex>a</tex> множеству не принадлежит. При этом для каждого <tex>a \in \{1, . . . , n\}</tex> алгоритм ошибается с вероятностью не более <tex>1/3</tex>.
Чтобы построить нужное нам хранилище <tex>X</tex>, мы сначала зафиксируем некоторый экспандер, у которого левая доля <tex>L</tex> состоит из <tex>n</tex> вершин, правая <tex>R</tex> из <tex>k = O(m log n)</tex> вершин, степень всех вершин левой доли одинакова и равна некоторому <tex>d</tex>, и для каждого <tex>A \subset L</tex> размера не более <tex>2m</tex>
<tex>|\Gamma(A)| \geqslant \frac{7}{8}d|A|</tex>
<tex>X</tex> будет состоять в разметке вершин правой доли нулями и единицами. Эту разметку нужно выбрать таким образом, чтобы у каждой вершины из <tex>S</tex> не менее <tex>2/3</tex> соседей были помечены единицей, а у каждой вершины не из <tex>S</tex> не менее <tex>2/3</tex> соседей были помечены нулями.<tex>X</tex> будет состоять в разметке вершин правой доли нулями и единицами. Эту разметку нужно выбрать таким образом, чтобы у каждой вершины из <tex>S</tex> не менее <tex>2/3</tex> соседей были помечены единицей, а у каждой вершины не из <tex>S</tex> не менее <tex>2/3</tex> соседей были помечены нулями.
Остаётся объяснить, как построить нужную нам разметку правой доли графа. Будем строить её последовательными приближениями. Сначала пометим всех соседей всех вершин из <tex>S</tex> единицами, а все остальные вершины – нулями. На данной разметке наш алгоритм с вероятностью <tex>1</tex> возвращает правильный ответ для всех <tex>a \in S</tex>. Однако для <tex>a</tex> не из <tex>S</tex> проверочный алгоритм может работать неверно. Обозначим T множество всех таких вершин вне <tex>S</tex>, у которых более <tex>d/3</tex> соседей помечены единицей. Поменяем разметку: пометим всех соседей <tex>T</tex> нулём. Теперь разметка может стать плохой для части вершин из <tex>S</tex>. Обозначим <tex>S'</tex> множество всех таких вершин из <tex>S</tex>, у которых более <tex>d/3</tex> соседей помечены нулями. Далее, поменяем разметку у
всех соседей <tex>S'</tex> на единицы. После этого может вновь возникнуть множество ‘неправильных’ вершин вне <tex>S</tex>, и т.д.
Чтобы доказать, что данный процесс в конце концов сойдётся, нужно показать, что на каждом шаге число ‘проблемных’ вершин уменьшается в константу раз. Поскольку все шаги аналогичны, достаточно разобрать самый первый: докажем, что <tex>T</tex> в константу раз меньше, чем <tex>S</tex>. Мы воспользуемся тем, что для <tex>S \cup T</tex> выполнено свойство расширения:
<tex>(7/8)d(|S|+|T|) \leqslant |\Gamma(S \cup T)| \leqslant d|S| + (2/3)d|T|</tex>
Откуда получаем <tex>|T| \leqslant 3/5|S|</tex>.
==Приложения и полезные свойства==
