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