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

Приблизительный список тем

• Небольшой ликбез по теории вероятноти - оценки Маркова, Чебышева и Чернова.

• Классические вероятностные алгоритмы, такие как быстрая сортировка Хоара и алгоритм Каргера для минимального разреза графа.

• Псевдодетерминированные вероятностные алгоритмы, которые решают задачу поиска, но при этом почти всегда находят один и тот же ответ.

• Приближенные алгоритмы - нахождение достаточно хороших решений к задачам, которые сложно решить точно. Среди техник будут рассмотрены линейное и полуопределенное программирование.

• Сложность в среднем - анализ поведения алгоритма на случайных входах, в противовес классическому анализу в худшем случае.

• Гладкий анализ - анализ алгоритмов сочетающий преимущества анализа в среднем и в худшем случаях. Был придуман как попытка объяснить почему алгоритмы, которые доказуемо плохи, отлично работают на реальных данных.