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


Что: Лекция
Когда: Четверг, 03 ноября 2016, 18:30–19:50
Где: ПОМИ РАН

Описание

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