Вы здесь

Синхронизируемые автоматы. Лекция 2

Лекция
Предмет:
Дата записи:
13.11.10
Дата публикации:
13.11.10
Код для блога:

Алгоритмы и сложность

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

Страница лекции на сайте Computer Science клуба

Дополнительные материалы: 
Иконка PDF 20101113_synchronizing_automata_volkov_lecture02.pdf