Алгоритмы

Randomized Algorithms: Сила случайности

Цели урока

Понимать преимущества рандомизации
Различать Monte Carlo и Las Vegas алгоритмы
Реализовать Miller-Rabin test
Анализировать ожидаемое время работы
Применять amplification для уменьшения ошибки

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

QuickSort
Основы теории вероятностей

Quick Sort

Случайность - не слабость, а сила. Криптография полагается на рандомизированные алгоритмы. Машинное обучение работает на стохастическом градиентном спуске. Распределённые системы используют рандомизацию для консенсуса. Это фундаментальная парадигма современного CS.

Криптография: генерация ключей, primality testing
ML: SGD, random forests, dropout
Распределённые системы: load balancing, consensus
Игры: процедурная генерация, AI

Рабин, Соловей и Штрассен: случайность как инструмент

Идея намеренно использовать случайность в алгоритмах оформилась в середине 1970-х. В 1976 году Майкл Рабин опубликовал работу 'Probabilistic Algorithms', а вскоре, в 1977 году, Роберт Соловей и Фолькер Штрассен предложили вероятностный тест простоты Соловея-Штрассена. Эти результаты показали, что случайный выбор может давать быстрые ответы с управляемой вероятностью ошибки там, где детерминированные методы слишком медленны. Ещё раньше, в 1961 году, Тони Хоар придумал quicksort, и позже случайный выбор опорного элемента стал классическим приёмом, защищающим алгоритм от наихудшего случая O(n^2).

Зачем случайность?

**Randomized algorithms** используют случайные числа для принятия решений. Это не хак - это мощная парадигма с математическими гарантиями.

**Примеры, которые вы уже знаете:**

**Randomized QuickSort**: random pivot избегает O(n²)
**Hash tables**: рандомизированные хеш-функции
**Skip List**: вероятностная альтернатива BST
**Bloom Filter**: вероятностный membership test
**HyperLogLog**: подсчёт уникальных элементов

**Ключевое:** рандомизация не делает алгоритм ненадёжным. При правильном анализе мы получаем строгие вероятностные гарантии.

Почему Randomized QuickSort лучше детерминированного?

Monte Carlo vs Las Vegas

**Два основных типа рандомизированных алгоритмов:**

**Подтипы Monte Carlo:**

**Можно конвертировать:** Las Vegas → Monte Carlo (ограничить время, вернуть 'не знаю'). Monte Carlo → Las Vegas (повторять пока не уверены).

Randomized QuickSort - это:

Monte Carlo: примеры

**Miller-Rabin Primality Test** - проверка простоты за O(k log³n).

**Karger's Min-Cut** - минимальный разрез графа.

**Karger's алгоритм:** O(n²) на один запуск, O(n⁴ log n) для высокой вероятности. Улучшенная версия Karger-Stein: O(n² log³ n).

Как уменьшить вероятность ошибки Monte Carlo?

Las Vegas: примеры

**Randomized QuickSort** - классический Las Vegas алгоритм.

**Randomized Selection (QuickSelect):**

**Random Treap (дерево + куча):**

**Las Vegas гарантирует корректность.** Если нужен результат "наверняка" - используй Las Vegas. Если допустима малая ошибка ради скорости - Monte Carlo.

Treap использует случайные приоритеты для:

Анализ рандомизированных алгоритмов

**Ожидаемое время (Expected running time)** - среднее по всем случайным выборам алгоритма.

**Хвостовые неравенства (Tail bounds):**

**На практике:** рандомизированные алгоритмы редко работают намного хуже ожидания. Хвостовые неравенства дают формальные гарантии.

Что означает 'w.h.p.' (with high probability)?