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

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