Город: Санкт-Петербург Новосибирск Казань Язык: Русский English

Алгоритмы и сложность
Синхронизируемые автоматы


Что: Лекция
Когда: Суббота, 13 ноября 2010, 19:05–20:40
Где: ПОМИ РАН
Слайды: synchronizingautomata_lecture_131110.pdf

Описание

Обзор основных алгоритмических вопросов, связанных с синхронизируемыми автоматами. Полиномиальный алгоритм для распознавания синхронизируемости. NP-полнота задачи о существовании синхронизирующего слова данной длины. Жадный алгоритм построения синхронизирующего слова. Верхняя оценка для длины слова, возвращаемого жадным алгоритмом.

Видео

Материалы