Город: Санкт-Петербург Новосибирск Казань Язык: Русский English

Вероятностные алгоритмы
Санкт-Петербург / весна 2020, посмотреть все семестры

Запишитесь на курс, чтобы получать уведомления и иметь возможность сдавать домашние задания. Для записи требуется регистрация на сайте.
Перейти к регистрации Войти

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

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

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

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

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

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

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

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

Дата и время Название Место Материалы
15 февраля
17:15–18:45
Лекция 1, лекция ПОМИ РАН видео
15 февраля
19:00–20:30
Лекция 2, лекция ПОМИ РАН видео
16 февраля
11:15–12:45
Лекция 3, лекция ПОМИ РАН видео
16 февраля
13:00–14:30
Лекция 4, лекция ПОМИ РАН видео
16 февраля
15:30–17:00
Лекция 5, лекция ПОМИ РАН видео
22 февраля
17:15–18:45
Лекция 6, лекция ПОМИ РАН видео
22 февраля
19:00–20:30
Лекция 7, лекция ПОМИ РАН видео
23 февраля
11:15–12:45
Лекция 8, лекция ПОМИ РАН видео
23 февраля
13:00–14:30
Лекция 9, лекция ПОМИ РАН видео
23 февраля
15:30–17:00
Лекция 10, лекция ПОМИ РАН видео