Здравствуйте.

В эту субботу 13 ноября в Питерском Computer Science клубе при ПОМИ начнётся курс лекций "Синхронизируемые автоматы". Курс состоит из 10-ти лекций.

Приходите и расскажите, пожалуйста, знакомым.

Язык курса: русский

Посещение свободное

Лектор: Михаил Владимирович Волков, Уральский государственный университет.

Аннотация

Детерминированный конечный автомат называется синхронизируемым, если существует такое слово w, что любой путь в автомате, вдоль которого читается w, заканчивается в одном и том же состоянии. Это понятие, естественно возникающее в задаче восстановления контроля над дискретной системой, текущее состояние которой неизвестно, оказалось математически весьма содержательным и породило много просто формулируемых, но оказавшихся весьма трудными задач. Среди таких проблем особо выделяются проблема раскраски дорог, совсем недавно решенная А.Н.Трахтманом, и гипотеза Черни, остающаяся недоказанной уже 46 лет.

В лекциях будет рассказано о связях теории синхронизируемых автоматов с различными смежными областями (теория кодов, символическая динамика и др.), изложено решение проблемы раскраски дорог и дан обзор новейших продвижений по гипотезе Черни.

Предварительные знания по теории автоматов, теории кодов и символической динамике не предполагаются. Для понимания некоторых результатов полезно знакомство с основами теории сложности вычислений.

Страница курса.
Встреча вконтакте.

PS. Если вы ещё не знаете, то сообщаю: филиал Computer Science клуба открылся в Екатеринбурге. Подробности здесь.