City: Saint Petersburg Novosibirsk Kazan Language: Русский English

Randomized Algorithms
Saint Petersburg / spring 2020, посмотреть все семестры

Enroll in the course to get notifications and to be able to submit home assignments.
Register to enroll now Login

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

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

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

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

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

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

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

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

Date and time Class|Name Venue|short Materials
15 February
17:15–18:45
Лекция 1, Lecture ПОМИ РАН video
15 February
19:00–20:30
Лекция 2, Lecture ПОМИ РАН video
16 February
11:15–12:45
Лекция 3, Lecture ПОМИ РАН video
16 February
13:00–14:30
Лекция 4, Lecture ПОМИ РАН video
16 February
15:30–17:00
Лекция 5, Lecture ПОМИ РАН video
22 February
17:15–18:45
Лекция 6, Lecture ПОМИ РАН video
22 February
19:00–20:30
Лекция 7, Lecture ПОМИ РАН video
23 February
11:15–12:45
Лекция 8, Lecture ПОМИ РАН video
23 February
13:00–14:30
Лекция 9, Lecture ПОМИ РАН video
23 February
15:30–17:00
Лекция 10, Lecture ПОМИ РАН video