Вы здесь

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

Курс
Предмет:

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

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

Источник информации