Город: Санкт-Петербург Новосибирск Казань Язык: Русский English

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

Что: Лекция
Когда: Понедельник, 12 октября 2020, 18:30–19:50
Где: Конференция в zoom, Онлайн

Описание

Множество регулярных языков совпадает с DSpace[1]. DSpace[\(\log \log n\)] содержит нерегулярные языки, а DSpace[\(o(\log \log n)\)]=DSpace[1]. Теорема Савича: Проверить наличие пути в ориентированном графе можно, используя \(\log^2 n\) памяти, PSPACE=NPSPACE.

Видео

Другие материалы

Текущая версия конспекта.