Сложность вычислений (семинары) 6. Класс L

Показать описание

Семинар от 09.10.2020.
Семинарист - Илья Степанов

00:00:00 -- HALF3COL, продолжение прошлого семинара
00:01:40 -- измерение памяти
00:03:15 -- определение DSPACE, L
00:04:40 -- PSPACE, вложение классов
00:05:40 -- вычисление функций в L
00:09:05 -- теорема Рейнгольда
00:11:40 -- SUBSEQUENCE (S является подпоследовательностью T)
00:14:30 -- MINPERIOD (кратчайший период строки равен k)
00:16:15 -- PAL (палиндром)
00:17:05 -- PAR (правильная скобочная последовательность)
00:18:25 -- PARBRA (правильная скобочная последовательность на двух типах скобок)
00:25:00 -- PERMUT (корректная перестановка)
00:28:00 -- LEQ (строка a меньше либо равна b)
00:29:00 -- SUB (a - b = c)
00:32:00 -- DIV ([a / b] = c)
00:36:10 -- UCONNECTED (неор. граф связен)
00:38:35 -- COMPS (в неор. графе ровно k компонент связности)
00:32:00 -- DIB ([a / b] = c)
00:42:35 -- EDGEUCYCLE (в неор. графе есть цикл через ребро e)
00:45:00 -- UCYCLE (в неор. графе есть цикл)
00:46:40 -- FOREST (в неор. графе нет цикла)
00:47:40 -- BIPARTITE (неор. граф двудолен)
00:53:30 -- преамбула NSPACE, NL

Съёмка, монтаж - Юманов Михаил
Таймкоды - Александр Стешенко