Лекция 9. Вычисления с (поли)логарифмической памятью

Четверг, 03 ноября 2016, 18:30–19:50
ПОМИ РАН

Описание

Теорема Савича: достижимость в неориентированном графе решается с использованием O(log^2n) памяти. Вероятностный алгоритм достижимости в неориентированном графе, использующий O(log n) памяти.