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

  1. Проверка на простоту
    1. Проверка на простоту, тест Ферма, 1/2 (Кармайкал, коррейтный тест за n1/3)
    2. Проверка на простоту, тест Миллера-Рабина, 3/4 (1977)

  2. BPP
    1. Определение (1/3 vs 2/3)
    2. Понижение ошибки: алгоритм и доказательство

  3. Как ещё можно применить случайные числа?
    1. Идеальное кодирование (x + random) mod M
    2. Пример с вычислением средней зарплатой без разглашения
    3. Общая тема: доказательства без разглашения данных (zero-knowledge-proofs).
    4. [skipped] 0.5-приближение к MAX-SAT (будет в практике)

  4. random walk
    1. Решение SAT за 3n/2 (детерминированно)
    2. Решение SAT за 3n/2 (рандомизированно): что дал рандом? упрощение реализации
    3. Решение SAT за 1.334n (рандомизированно)
    4. Пример из жизни: вы в незнакомом городе, хотите найти хорошую кафешку. (а) перебор окрестности, (б) random walk, (в) repeat random walk

  5. Алгебра многочленов и Шварц-Зиппель
    1. Лемма Шварца-Зиппеля: P(x) над F, Prx[P(x) = 0] ≤ deg P / |F|
    2. Самый простой пример: матрица Татта (1947)
    3. Пример посложнее (только описание, без решения): Гамильтонов путь в неорграфе за 1.657n (2010) (будет на 3-м курсе)

  6. random shuffle
    1. Как его получить: random shuffle через цикл for (все n! перестановок с равной вероятностью)
    2. Зачем он нужен? Дерево поиска, добавление данных в случайном порядоке.

  7. [skipped] Игра на дереве (будет в практике)

  8. k-путь за exp(k) через рандом