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

Общая информация
ЛекторМ. В. Волков
Семестросень 2010
Дата начала13.11.2010
Количество пар10
Язык курсарусский
Вопросы к экзамену
Анонсы
Встреча ВКонтактеhttp://vkontakte.ru/event21344952
Аннотация

Детерминированный конечный автомат называется синхронизируемым, если существует такое слово w, что любой путь в автомате, вдоль которого читается w, заканчивается в одном и том же состоянии. Это понятие, естественно возникающее в задаче восстановления контроля над дискретной системой, текущее состояние которой неизвестно, оказалось математически весьма содержательным и породило много просто формулируемых, но оказавшихся весьма трудными задач. Среди таких проблем особо выделяются проблема раскраски дорог, совсем недавно решенная А.Н.Трахтманом, и гипотеза Черни, остающаяся недоказанной уже 46 лет.

В лекциях будет рассказано о связях теории синхронизируемых автоматов с различными смежными областями (теория кодов, символическая динамика и др.), изложено решение проблемы раскраски дорог и дан обзор новейших продвижений по гипотезе Черни.

Предварительные знания по теории автоматов, теории кодов и символической динамике не предполагаются. Для понимания некоторых результатов полезно знакомство с основами теории сложности вычислений.

Лекции Подсказка: слайды, видеозапись и другие материалы лекции доступны со страницы лекции, попасть на которую можно, нажав на её название.

1. История и мотивация
(13.11.2010 - 17:20 - 18:55)

Обзор математических и технических задач, приводящих к рассмотрению синхронизируемых автоматов. http://lektorium.tv/lecture/?id=13238
2. Алгоритмы и сложность
(13.11.2010 - 19:05 - 20:40)

Обзор основных алгоритмических вопросов, связанных с синхронизируемыми автоматами. Полиномиальный алгоритм для распознавания синхронизируемости. NP-полнота задачи о существовании синхронизирующего слова данной длины. Жадный алгоритм построения синхронизирующего слова. Верхняя оценка для длины слова, возвращаемого жадным алгоритмом. http://lektorium.tv/lecture/?id=13239
3. Гипотеза Черни
(14.11.2010 - 11:15 - 12:50)

Задача о длине кратчайшего синхронизирующего слова для автоматов с данным числом состояний. Серия Черни, нижняя оценка. Гипотеза Черни. Обзор экстремальных автоматов. Пример Кари. Гипотеза ранга. Метод расширения. Серия Берлинкова. http://lektorium.tv/lecture/?id=13240
4. Проблема раскраски дорог. Часть 1
(14.11.2010 - 13:00 - 14:35)

Сведение задачи о длине кратчайшего синхронизирующего слова для автоматов с данным числом состояний к случаю сильно связных автоматов. Примитивность орграфов сильно связных синхронизируемых автоматов. Проблема раскраски дорог. Отношение стабильности. Теорема Трахтмана о раскраске дорог. Сложностные аспекты проблемы раскраски дорог. http://lektorium.tv/lecture/?id=13241
5. Проблема раскраски дорог. Часть 2
(14.11.2010 - 15:35 - 17:10)

Сведение задачи о длине кратчайшего синхронизирующего слова для автоматов с данным числом состояний к случаю сильно связных автоматов. Примитивность орграфов сильно связных синхронизируемых автоматов. Проблема раскраски дорог. Отношение стабильности. Теорема Трахтмана о раскраске дорог. Сложностные аспекты проблемы раскраски дорог. http://lektorium.tv/lecture/?id=13242
6. Проблема Черни для апериодических автоматов. Часть 1
(20.11.2010 - 17:20 - 18:55)

Апериодические автоматы, беззвездные языки и логические характеризации языков формулами первого порядка. Монотонные и обобщенно монотонные автоматы. Теорема Трахтмана о длине кратчайшего синхронизирующего слова для апериодических автоматов с данным числом состояний. http://lektorium.tv/lecture/?id=13243
7. Проблема Черни для апериодических автоматов. Часть 2
(20.11.2010 - 19:05 - 20:40)

Апериодические автоматы, беззвездные языки и логические характеризации языков формулами первого порядка. Монотонные и обобщенно монотонные автоматы. Теорема Трахтмана о длине кратчайшего синхронизирующего слова для апериодических автоматов с данным числом состояний. http://lektorium.tv/lecture/?id=13244
8. Автоматы и матрицы
(21.11.2010 - 11:15 - 12:50)

Связь между длиной кратчайшего синхронизирующего слова синхронизируемого автомата и экспонентой его орграфа. Гибридная гипотеза. Медленно синхронизируемые автоматы. http://lektorium.tv/lecture/?id=13245
9. Открытые проблемы
(21.11.2010 - 13:00 - 14:35)

Длины кратчайших синхронизирующих слов для автоматов с различными ограничениями. Автоматы с буквой дефекта 2. Тотально синхронизируемые орграфы. Универсальные синхронизирующие слова. Бережная синхронизируемость. http://lektorium.tv/lecture/?id=13246
Ваша оценка: Пусто Средняя: 4.9 (11 votes)
Share |