Фурье и длинка (17 мая 2016)

  1. Классы
    1. P, NP, NPc, NPh
    2. Decision problems, search problems (обозначение: тот же класс, с волной?)
    3. Определение сведения. Пример сведения: (что к чему?)
    4. Другие классы (определения): L, EXP, PSPACE
  2. Вероятностные алгоритмы
    1. Работает на всех входах. Вероятность по случайным битам, которые генерит сама программа.
    2. Las Vegas algorithm is a randomized algorithm that always gives correct results
    3. Monte Carlo algorithm is a randomized algorithm whose running time is deterministic, but whose output may be incorrect
    4. [wiki,Las Vegas] [wiki,Monte Carlo] [wiki,Randomized algorithm]
    5. Randomized algorithm: алгоритм всегда завершается корректно.
    6. Probablistic algorithm: алгоритм работает детерминированное время, ответ корректен с некоторой вероятностью
    7. Другая терминология Zero-Side-Error, One-Side-Error, Two-Side-Error
    8. Примеры #1. Лас-Вегас: найти число, которое встречается в массиве длины n хотя бы n/2 раз (probablistic algorithm)
    9. Примеры #2. QSort (randomized algorithm)
    10. Определяем классы RP, coRP, ZPP, BPP.
    11. Наши знания с приведёнными классами не связаны. Т.к. все наши вероятностные алгоритмы не помогают прийти в P или EXP из другого класса, они в рамках того же класса уменьшают время.
  3. Улучшаем алгоритмы
    1. Понижаем ошибку у RP
    2. Запускаем с будильником, получаем ZPP = RP ∩ coRP
  4. Примеры конкретных алгоритмов и структур данных
    1. Каргер-Штейн. Probablistic algorithm, понижение ошибки.
    2. Хеш-таблица. Randomized data structure, можем запускать с будильником, тогда структура будет нам иногда говорить "ой, не получилось добавить элемент"
    3. 3-List-Coloring за O(1.5n). Randomized algorithm, можем запускать с будильником, тогда получим Probablistic algorithm за O(1.5n).
    4. Что мы ещё прошли? Treap, Skip-List, Полиномиальные хеши без коллизий
    5. Что ещё пройдём? Факторизация, проверка на простоту, игра на дереве размера 232.