Archive for Май 2010

Генерация случайного остовного дерева

Май 16, 2010

Представим себе, что у нас есть связный ненаправленный граф. Пусть мы хотим среди всех его остовных деревьев выбрать одно равновероятно. Это не такая простая задача, как может показаться на первый взгляд.

Первое, что приходит в голову — перебрать все остовные деревья, а потом выбрать из полученного списка случайный элемент. Такой метод работает хорошо, если остовных деревьев мало. Но в типичном случае их экспоненциально много.

Второй возможный способ — воспользоваться теоремой Кирхгофа и генерировать ребра остовного дерева по одному. Этот метод работает за полиномиальное время, но совершенно непрактичен.

И последний, самый изящный метод состоит в следующем. Встанем в первую вершину и начнем случайное блуждание по нашему графу. Как только мы приходим в какую-нибудь вершину первый раз, добавляем ребро, по которому мы туда пришли, в ответ. Способ простой, красивый и быстрый. Но неочевидно, что он правильный.

Реклама

Понижение размерности

Май 5, 2010

Пусть у нас есть n точек в \mathbb{R}^N. Допустим, N очень большое, и мы хотим как-нибудь его уменьшить. Пусть нас интересуют лишь попарные расстояния между точками, и мы хотим, чтобы при понижении размерности они изменились не более, чем на \varepsilon (в смысле относительной погрешности). Оказывается, что в этом случае можно понизить размерность до O(\log n / \varepsilon^2). В этом состоит содержание леммы Джонсона-Линденштраусса.

Идея доказательства такая: мы проектируем наш набор точек на случайное подпространство маленькой размерности и показываем, что при таком проектировании квадрат длины вектора сильно сконцентрирован вокруг своего матожидания. Из доказательства следует, что соответствующее вложение можно найти за вероятностное полиномиальное время.

Аналитическое доказательство неравенства Крафта-Макмиллана

Май 2, 2010

Пусть у нас есть текст в алфавите \{1, 2, \ldots, k\}. Мы хотим его закодировать: символ i заменить на двоичное слово w_i. Обозначим n_i := |w_i|. Само собой, мы хотим сделать кодовые слова как можно короче. Однако, произвольно уменьшать их мы не можем, если хотим, чтобы код был однозначно декодируемым.

Теорема (Крафт-Макмиллан). Если код однозначно декодируемый, то 2^{-n_1} + 2^{-n_2} + \ldots + 2^{-n_k} \leq 1.
Доказательство. Рассмотрим последовательность a_i — количество кодовых слов длины i. Рассмотрим ряд f(z) = a_0 + a_1 z + a_2 z^2 + \ldots. Несложно заметить, что он является степенным рядом голоморфной в окрестности нуля функции g(z) = 1 / (1 - z^{n_1} - z^{n_2} - \ldots - z^{n_k}). Пусть z_0 — самая маленькая по модулю особенность g(z) (полюс). Если предположить, что 2^{-n_1} + 2^{-n_2} + \ldots + 2^{-n_k} > 1, то можно заметить, что |z_0| < 1/2. Вспоминаем, что наш код однозначно декодируемый. Из этого следует, что a_i \leq 2^i, а это значит, что f(z) имеет радиус сходимости не меньше 1 / 2. Но так как g(z) голоморфная в круге \{z \mid |z| < |z_0|\}, значит f(z) и g(z) должны там совпадать. Но это не так, потому что \infty = \lim_{z \to z_0} f(z) \ne \lim_{z \to z_0} g(z) = g(z_0).

Односторонняя функция

Май 2, 2010

В криптографии и теории сложности нередко применяются односторонние функции. Это функции, которые легко вычислить, но трудно обратить. Дадим формальное определение:

Вспомогательное определение. Функция \varepsilon \colon \mathbb{N} \to [0, 1] называется исчезающе малой, если для любого c \in \mathbb{N} найдется n_0 такое, что для любого n > n_0 выполняется неравенство \varepsilon(n) < n^{-c}.

Определение. f \colon \{0, 1\}^* \to \{0, 1\}^* называется односторонней, если, во-первых, она вычисляется за полиномиальное время, а, во-вторых, для любого полиномиального вероятностного алгоритма A существует исчезающе малая функция \varepsilon такая, что P[A(f(x)) \in f^{-1}(f(x))] < \varepsilon(n), где вероятность берется по равномерному выбору x \in \{0, 1\}^n и броскам монетки при выполнении A.

Гипотеза. Односторонние функции существуют.

Ясно, что если \mathbf{P} = \mathbf{NP}, то односторонних функций нет. Так что эта гипотеза не слабее гипотезы \mathbf{P} \ne \mathbf{NP}. Левин придумал универсальную функцию U с таким свойством: если существуют односторонние функции, то U односторонняя.

Оказывается, что из существования односторонних функций следует много всего интересного: существование псевдослучайных генераторов, существование доказательств с нулевым разглашением для всего \mathbf{NP}, существование протоколов для бросания монетки и т. д. Но об этом в следующих сериях.

Удивительное доказательство

Май 2, 2010

Рассмотрим одну «олимпиадную» задачу с довольно-таки удивительным доказательством.

Назовем прямоугольник хорошим, если у него по крайней мере одна из сторон целая. Пусть прямоугольник R удалось разбить на несколько хороших прямоугольников R_1, R_2, \ldots, R_k. Докажем, что и R является хорошим. Будем рассматривать конечные формальные суммы точек из \mathbb{R}^2 вида \sum_i \alpha_i p_i, где \alpha_i \in \mathbb{R}, а p_i \in \mathbb{R}^2. Такие суммы можно складывать. Например, (2(0, 1) + 3(-2, 3)) - 4(-2,3) = 2(0,1) - (-2,3). Теперь построим по прямоугольнику P формальную сумму S(P), которая является суммой углов, причем левый нижний и правый верхний берутся с плюсом, а левый верхний и правый нижний — с минусом. Несложно проверить, что S(R) = S(R_1) + S(R_2) + \ldots + S(R_k). Теперь линейно отобразим формальные суммы точек из \mathbb{R}^2 в формальные суммы точек тора: \varphi \colon (x, y) \mapsto (x \bmod 1, y \bmod 1). Ясно, что \varphi(S(P)) = 0 тогда и только тогда, когда P хороший. Но мы знаем, что \varphi(S(R_i)) = 0. Значит и \varphi(S(R)) = 0. А значит R хороший.

Равномерные матрицы

Май 1, 2010

Рассмотрим матрицы размера n на n с элементами из поля \mathbb{F}. Скажем, что матрица A равномерная, если любая ее квадратная подматрица, которая прижата к левому краю, невырождена (обратите внимание, что мы рассматриваем не миноры, а именно подматрицы).

Лемма. Для любого поля \mathbb{F} и для любого натурального n найдется равномерная матрица размера n на n над \mathbb{F}.

Доказательство. Доказательство состоит в явном предъявлении искомой матрицы. По существу, это просто треугольник Паскаля. Более точно: a_{i,j} = a_{i-1,j} + a_{i-1,j-1}, a_{i,1} = 1, a_{1,i} = 0 при i > 1. Обозначим A^{i,j} квадратную подматрицу нашей матрицы, которая прижата к левому краю, начинается в строке i, и длина стороны которой равна j.

а) A^{1,i} невырождена, так как она нижнетреугольная с единицами на диагонали.
б) Рассмотрим A^{i,j} с i > 1. Вычтем из второго столбца первый, затем из третьего второй и т. д. Несложно понять, что мы получим A^{i - 1,j}. Таким образом, простая индукция помогает завершить рассуждение.