Рандомизированные алгоритмы (5 февраля 2021)

  1. База
    1. Вероятностные алгоритмы (Probabilistic): Определение классов RP, coRP (работает на всех входах за полином, иногда ошибается)
    2. Вероятностные алгоритмы (Randomized): Определение класса ZPP. Работает всегда корректно, матожидание времение работы − полином.
    3. Отличие от детерминированных (есть подсказка = случайные биты, работает с некоторой вероятностью)
    4. Связь с недетерминированными (работает на половине подсказок)
    5. Понижение вероятности ошибки: p → pn
  2. Примеры
    1. Поиск числа, которое встречается в массиве больше половины раз: decision и search версии, RP и ZPP.
    2. k-я статистика и quick-sort (нам было сложно корректно выбрать медиану, что дал рандом? упрощение реализации)
    3. Пример алгоритма: 3-LIST-COLORING (подсказка − что выкинуть, работает на 2n из 3n подсказок)
    4. Поиск квадратичного невычета за O(log n).
    5. Проверка на простоту, тест Ферма, 1/2
    6. Проверка на простоту, тест Миллера-Рабина, 3/4 (1977)
    7. Проверка того, что AB = C: A(Bx) = Cx. Доказательство.
  3. Теорема: ZPP = RP ∩ coRP (можно запустить с будильником алгоритм из ZPP, а можно запускать по очереди алгоритмы из RP и coRP)
  4. BPP
    1. Определение (1/3 vs 2/3)
    2. Понижение ошибки: алгоритм и доказательство
  5. Как ещё можно применить случайные числа?
    1. Идеальное кодирование (x + random) mod M
    2. Пример с вычислением средней зарплатой без разглашения
    3. Общая тема: доказательства без разглашения данных (zero-knowledge-proofs).
    4. [skipped] 0.5-приближение к MAX-SAT
  6. Парадокс дней рождений и факторизация
    1. Сам парадокс. Оценка вероятностей в обе стороны.
    2. Факторизация: алгоритмы за корень, рандомизированный с gcd за корень.
    3. ро-эвристика Полларда для факторизации чисел.
  7. random walk
    1. Решение SAT за 3n/2 (детерминированно)
    2. Решение SAT за 3n/2 (рандомизированно): что дал рандом? упрощение реализации
    3. Решение SAT за 1.333n (рандомизированно)
    4. Пример из жизни: вы в незнакомом городе, хотите найти хорошую кафешку. (а) перебор окрестности, (б) random walk, (в) repeat random walk
  8. Алгебра многочленов
    1. Лемма Шварца-Зиппеля: P(x) над F, Prx[P(x) = 0] ≤ deg P / |F|
    2. Самый простой пример: матрица Татта (1947)
    3. Пример по сложнее: Гамильтонов путь в неорграфе за 1.657n (2010) (будет на 3-м курсе)
  9. random shuffle
    1. Как его получить: random shuffle через цикл for (все n! перестановок с равной вероятностью)
    2. Зачем он нужен? Дерево поиска, добавление данных в случайном порядоке.