Алгоритмы и модели вычислений 6. Классы L и NL.

Описание: 00:00 История памяти
05:40 Рабочая память
10:00 DSPACE и NSPACE
11:40 Классы L, NL, PSPACE, polyL
13:10 Теорема Сэвича
14:40 Следствия из теоремы
16:55 Связь классов по памяти
27:00 Вложенность NL в P, конфиг. граф
33:00 Вложенность NP в PSPACE
35:51 Начало и конец перерыва
36:15 Примеры задач из L, арифметика двоичных чисел
46:30 Сложение
51:20 Умножение
57:00 Скобочные последовательности
01:00:00 Критерий через баланс скобок
01:03:15 Несколько типов скобок