Дискретная математика в алгоритмах: продвинутые техники

Как превратить доказательство существования в работающую программу? Дерандомизация - мост между теоретической комбинаторикой и алгоритмами. Это финальная тема курса объединяет всё: Рамсея, вероятностный метод, производящие функции - и превращает их в алгоритмы.

• **Детерминированные алгоритмы приближения:** дерандомизированный Max-Cut даёт 1/2-аппроксимацию - гарантированно, без случайности, за O(nm)
• **SAT-солверы:** алгоритм Мозера-Тардоша - основа современных WalkSAT-подобных солверов; LLL объясняет их поведение на легко-выполнимых формулах
• **Криптографический анализ:** rho-алгоритм Полларда - стандартный инструмент факторизации; birthday attack задаёт нижние оценки на длины ключей

Предварительные знания

• Cryptographic Protocols and Discrete Math

Дерандомизация: метод условных вероятностей

Дерандомизация - превращение вероятностного алгоритма в детерминированный без потери качества гарантий. Метод условных вероятностей (Erdős-Selfridge): принимаем решения по одному, на каждом шаге выбирая значение, которое сохраняет «потенциальную функцию» (пессимистический оценщик) не превышающей 1.

**Числа Рамсея и дерандомизация:** нижняя оценка Эрдёша R(r,r) > 2^{r/2} - вероятностная. Дерандомизация через метод условных вероятностей даёт явную конструкцию 2-раскраски K_n без монохроматического K_r при n ≈ 2^{r/2}. Это первая конструктивная нижняя оценка R(r,r).

Производящие функции для анализа алгоритмов

Производящие функции позволяют точно решать рекуррентности T(n), возникающие в анализе алгоритмов. Для «разделяй и властвуй» с T(n) = aT(n/b) + f(n) мастер-теорема даёт асимптотику; производящие функции дают точный ответ для полиномиальных рекуррентностей.

**Точный vs асимптотический анализ:** мастер-теорема даёт O(n log n) для quicksort. Производящие функции дают точно 2n ln n ≈ 1.386 n log₂ n - с константой! Для сравнения сортировки слиянием: точно n log₂ n - n + 1. Производящие функции выявляют константы.

Birthday attacks и поиск коллизий в алгоритмах

Принцип Дирихле (ящиков) утверждает: если n+1 объектов разложить по n ящикам, хотя бы в одном будет ≥ 2 объекта. Это детерминированная версия birthday paradox - она даёт нижние оценки на worst-case алгоритмов и лежит в основе birthday attacks.

**Rho-алгоритм Полларда** нашёл 8-й делитель числа F₈ = 2^{256}+1 за время O(n^{1/4}) - применив birthday paradox к псевдослучайной последовательности в Z_{p} и детектировав цикл алгоритмом Флойда «черепаха и заяц».

Lovász Local Lemma и алгоритм Мозера-Тардоша

Локальная лемма Ловаса (LLL) - мощное обобщение принципа «E[X] > 0 → X > 0»: если «плохих» событий мало и каждое зависит лишь от немногих других, то вероятность избежать всех плохих событий положительна. LLL применяется в теории Рамсея, теории графов и SAT.

**Значение для CS:** алгоритм Мозера-Тардоша «алгоритмизировал» LLL - превратил существование в конструктивный алгоритм. Это образцовый пример дерандомизации: вероятностный аргумент существования → эффективный конструктивный алгоритм. Применяется для k-SAT, раскрасок гиперграфов, покрытий.

Ключевые идеи

• **Метод условных вероятностей:** дерандомизация через инвариантное условное ожидание - O(nm) детерминированный Max-Cut с гарантией ≥ m/2
• **Производящие функции для рекуррентностей:** точный анализ (с константами) quicksort, mergesort и других алгоритмов
• **Birthday paradox в алгоритмах:** принцип Дирихле → нижние оценки; rho-алгоритм Полларда - O(1) память при O(√N) итерациях
• **LLL и Мозер-Тардош:** e·p·(d+1) ≤ 1 → выполнимость; алгоритм Resample сходится за O(m) шагов - конструктивный LLL

Связанные темы

Этот урок - точка схождения всех продвинутых тем курса:

• Вероятностная комбинаторика — Метод условных вероятностей - дерандомизация метода Эрдёша; LLL обобщает базовый вероятностный принцип
• Теорема Рамсея — Дерандомизация нижней оценки R(r,r) > 2^{r/2} даёт первую явную конструкцию раскраски без монохроматического K_r

Вопросы для размышления

• Почему алгоритм Мозера-Тардоша сходится за O(m) шагов - в чём математический аргумент (подсказка: энтропийное доказательство Мозера)?
• Как принцип «дерандомизации через условные ожидания» связан с динамическим программированием - это разные техники или одна идея?
• Что из изученного в этом курсе (Рамсей, производящие функции, матроиды, спектральная теория) кажется вам наиболее применимым в вашей работе?

Связанные уроки

• alg-01-big-o