1. База 1.1 Рандомизированные алгоритмы: RP, coRP 1.2 Понижение ошибки 1.3 Связь с классом NP 1.4 Класс ZPP 2. Алгоритмы-примеры 2.1 Поиск невычета за O(log(n)) [Плохой пример, они не очень проходили что такое вычет-невычет] 2.2 Тест Ферма 2.3 Тест Миллера-Рабина 2.4 Рандом это хорошо: quick-sort, nth-element 2.5 Поиск числа, которое встречается больше половины раз: decision (RP), search (ZPP) 2.6 3-LIST-COLORING 2.7 Проверка AB = C через ABx =? Cx 3. Теорема ZPP = RP ∩ coRP 4. BPP 4.1 Определение 4.2 Понижение вероятности, +доказательство 4. Парадокс дней рождений и факторизация 4.1 Сам парадокс. Оценка вероятностей в обе стороны. 4.2 Факторизация: алгоритмы за корень, рандомизированный с gcd за корень. 4.3 ро-эвристика Полларда для факторизации чисел. 4.4 [Забыто, в следующий раз] Избавляемся от log 5. random walk 5.1 Решаем 3-SAT за 3^{n/2} (детерминированно) 5.2 Решаем 3-SAT за 3^{n/2} (рандом) 5.3 Решаем 3-SAT за 1.5^n (рандом) 5.4 Решаем 3-SAT за 1.333^n (рандом) На потом ---------------------- 0. Доделать рассказ про Полларда 1. Как ещё можно применить случайные числа? 1.1 Идеальное кодирование (x + random) mod M 1.2 Пример с вычислением средней зарплатой без разглашения 1.3 Общая тема: доказательства без разглашения данных (zero-knowledge-proofs). Лектор, который пытается не доказать, а убедить... 2. Алгебра многочленов 2.1 Лемма Шварца-Зиппеля: P(x) над F, Prx[P(x) = 0] ≤ deg P / |F| 2.2 Самый простой пример: матрица Татта (1947) 3. random shuffle 3.1 Как его получить: random shuffle через цикл for (все n! перестановок с равной вероятностью) 3.2 Зачем он нужен? Дерево поиска, добавление данных в случайном порядке.