Синхронизируемые автоматы. Лекция 2
ЛекцияПредмет:
- Computer Science
Лектор:
Курс лекций:
Дата записи:
13.11.10
Дата публикации:
13.11.10
Код для блога:
Алгоритмы и сложность
Обзор основных алгоритмических вопросов, связанных с синхронизируемыми автоматами. Полиномиальный алгоритм для распознавания синхронизируемости. NP-полнота задачи о существовании синхронизирующего слова данной длины. Жадный алгоритм построения синхронизирующего слова. Верхняя оценка для длины слова, возвращаемого жадным алгоритмом.
Страница лекции на сайте Computer Science клуба
Дополнительные материалы:
20101113_synchronizing_automata_volkov_lecture02.pdfДругие лекции курса
8