Синхронизируемые автоматы

Последнее изменение: 21/05/2018 10:28:03

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

Image:cerny4.jpg

На рисунке представлен синхронизируемый автомат: можно проверить, что слово baaabaaab синхронизирует его, т.е. переводит в состояние, не зависящее от того, в каком состоянии автомат находился первоначально. Гипотеза Черни утверждает, что для любого синхронизируемого автомата с n состояниями существует синхронизирующее слово длины (n-1)^2. (В примере на рисунке n=4 и указанное слово имеет длину 9=(n-1)^2.) Вопрос о её справедливости остаётся открытым уже более 50 лет.

В спецкурсе будет освещено современное состояние теории синхронизируемых автоматов и предложено несколько задач для исследовательской работы.

Для понимания спецкурса требуется владение базовым курсом линейной алгебры (2-й семестр 1-го курса) и элементами теории графов. Желательно (но необязательно) представление об NP-полных задачах. Предварительные знания по теории автоматов не предполагаются. Отчётность - экзамен или зачет (по выбору слушателя). Формально спецкурс адресован студентам потока ФИИТ, но приглашаются все заинтересованные студенты бакалавриата и магистратуры.

Спецкурс читается по четвергам 5-й парой (16:10-17:40) в ауд. 611.

Внимание: Лекции 10-го мая и 17-го мая не состоятся из-за моей болезни. Слайды лекций будут выложены позже для самостоятельной проработки.

Зачет будет проводиться 23-го мая с 16:10 в ауд. 609.

План спецкурса (с ссылками на слайды прочитанных лекций)

Конспект лекций (Версия от 24.04) Внимание: Текст пока остается нестабильным, поэтому, если Вы хотите сообщить мне о какой-нибудь опечатке или неточности, указывайте не только номер строки, но и дату версии (указана на первой странице конспекта).

Литература: M.V.Volkov. Synchronizing automata and the Cerny conjecture, in C. Martin-Vide, F. Otto, H. Fernau (eds.), Language and Automata Theory and Applications. LATA 2008 [Lect. Notes Comp. Sci., 5196], Springer-Verlag, Berlin-Heidelberg-N.Y., 2008, 11-27
http://dx.doi.org/10.1007/978-3-540-88282-4_4

Смотрите также: