Вероятностные алгоритмы

Этот курс посвящен использованию случайности и приближений в алгоритмах. Приблизительный список тем:

— Небольшой ликбез по теории вероятноти — оценки Маркова, Чебышева и Чернова.
— Классические вероятностные алгоритмы, такие как быстрая сортировка Хоара и алгоритм Каргера для минимального разреза графа.
— Псевдодетерминированные вероятностные алгоритмы, которые решают задачу поиска, но при этом почти всегда находят один и тот же ответ.
— Приближенные алгоритмы — нахождение достаточно хороших решений к задачам, которые сложно решить точно. Среди техник будут рассмотрены линейное и полуопределенное программирование.
— Сложность в среднем — анализ поведения алгоритма на случайных входах, в противовес классическому анализу в худшем случае.
— Гладкий анализ — анализ алгоритмов сочетающий преимущества анализа в среднем и в худшем случаях. Был придуман как попытка объяснить почему алгоритмы, которые доказуемо плохи, отлично работают на реальных данных.