Лектор - Д.В. Мусатов
Время: четверг, 16:30 - 18:30, первое занятие - 9 сентября, ГК 533
Описание
Некоторые задачи решаются рандомизированными алгоритмами. Некоторые алгоритмы, например, проверка простоты числа или проверка связности графа, были дерандомизированы, т.е. превращены в детерминированные из того же сложностного класса (полиномиальное время, логарифмическая память и т.д.). Для других задач, прежде всего проверки арифметического выражения на тривиальность, дерандомизация пока неизвестна. Общий вопрос состоит в том, можно ли избавиться от случайных битов в общем случае или хотя бы существенно сократить их использованное количество. В курсе будет дан обзор классических результатов и новых продвижений по этой теме.
© 2001-2022 Московский физико-технический институт (национальный исследовательский университет)
Противодействие коррупции | Сведения о доходах
Политика обработки персональных данных МФТИ
Использование новостных материалов сайта возможно только при наличии активной ссылки на https://mipt.ru
МФТИ в социальных сетях
