Семинар лаборатории 1

В докладе будет дан краткий обзор методов построения надёжных схем для хранения и переработки информации из ненадёжных (спорадически ошибающихся) базовых элементов. Мы рассмотрим максимально "нелокальную" модель вычислений - надёжные булевы схемы из ненадёжных функциональных элементов (по работам Дж.фон Неймана, Р.Л.Добрушина и С.И.Ортюкова, А.В.Кузнецова, Н.Пиппенгера, А.Гал, Д.Спилмана), а также максимально "локальную" модель - самокорректирующиеся вычисления на клеточных автоматах (по работам А.Л.Тоома, П.Гача, Дж.Рейфа). Мы обсудим несколько красивых математических идей (из теории вероятностей, теории графов, математической логики), использующихся при построении и анализе схем самокорректирующихся вычислений.