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

Последнее изменение: 29/10/2012 00:00:00

Специальный курс. В осеннем семестре 2011/12 учебного года читается по средам с 12:50 в ауд. 607 (кафедра алгебры и дискретной математики)

Конспект лекций

Лекция 1: История задачи. Обзор курса

Лекции 2 и 3: Алгоритмические и теоретико-сложностные аспекты

Лекции 4 и 5: Гипотеза Черни

Лекция 6: Эйлеровы автоматы

Лекции 7 и 8: Апериодические автоматы

Лекции 9 и 10: Проблема раскраски дорог

Лекция 11: Автоматы и матрицы

Лекция 12: Открытые проблемы


Зачет (для желающих экзамен) состоится 28 декабря 2011 г. в ауд. 621, начало в 13:00 (но можно приходить и раньше - я буду в этой же аудитории принимать другой зачет).

Вопросы к зачету

  1. Синхронизируемые автоматы. Алгоритм для проверки синхронизируемости автомата
  2. Кубическая оценка длины синхронизирующего слова. Сведение к задаче о длине обновляемых последовательностей подмножеств
  3. Теорема Франкля о длине обновляемых последовательностей подмножеств
  4. NP-полнота задачи Short-Reset-Word
  5. co-NP-трудность задачи Shortest-Reset-Word
  6. Гипотеза Черни. Автоматы Черни
  7. Гипотеза расширения. Контрпример Берлинкова
  8. Синхронизация эйлеровых автоматов. Теорема Кари
  9. Синхронизация эйлеровых автоматов. Автоматы Гусева
  10. Редукция гипотезы Черни к случаю сильно связных автоматов
  11. Синхронизируемость сильно связных апериодических автоматов
  12. Синхронизация апериодических автоматов. Теорема Трахтмана
  13. Проблема раскраски дорог. Необходимые условия.
  14. Проблема раскраски дорог. Отношение стабильности. Сведение к задаче о существовании стабильной пары
  15. Решение проблемы раскраски дорог. Лемма о кликах и лемма о уровне
  16. Решение проблемы раскраски дорог. Доказательство существования стабильной пары

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