Адрес e-mail:

Псевдослучайность и дерандомизация (Д.В. Мусатов, осень 2021)

Лектор - Д.В. Мусатов

Время: четверг, 16:30 - 18:30, первое занятие - 9 сентября, ГК 533


Описание
Некоторые задачи решаются рандомизированными алгоритмами. Некоторые алгоритмы, например, проверка простоты числа или проверка связности графа, были дерандомизированы, т.е. превращены в детерминированные из того же сложностного класса (полиномиальное время, логарифмическая память и т.д.). Для других задач, прежде всего проверки арифметического выражения на тривиальность, дерандомизация пока неизвестна. Общий вопрос состоит в том, можно ли избавиться от случайных битов в общем случае или хотя бы существенно сократить их использованное количество. В курсе будет дан обзор классических результатов и новых продвижений по этой теме.

Если вы заметили в тексте ошибку, выделите её и нажмите Ctrl+Enter.

© 2001-2021 Московский физико-технический институт (национальный исследовательский университет)

Противодействие коррупции | Сведения о доходах

Политика обработки персональных данных МФТИ

Техподдержка сайта | API

Использование новостных материалов сайта возможно только при наличии активной ссылки на https://mipt.ru

МФТИ в социальных сетях