Синхронизируемые автоматы. Лекция 5
ЛекцияПредмет:
- Computer Science
Лектор:
Курс лекций:
Дата записи:
14.11.10
Дата публикации:
14.11.10
Код для блога:
Проблема раскраски дорог. Часть 2
Сведение задачи о длине кратчайшего синхронизирующего слова для автоматов с данным числом состояний к случаю сильно связных автоматов. Примитивность орграфов сильно связных синхронизируемых автоматов. Проблема раскраски дорог. Отношение стабильности. Теорема Трахтмана о раскраске дорог. Сложностные аспекты проблемы раскраски дорог.
Страница лекции на сайте Computer Science клуба
Дополнительные материалы:
20101114_synchronizing_automata_volkov_lecture04-05.pdf 20101114_synchronizing_automata_volkov_lecture04-05_0.pdfДругие лекции курса
8