[М/М 4 Матис] Программа по С/к (теории автоматов) - Public forum of MSU united student networks

Лежит тут:
http://forum.local/user/upload/file1553.zip

Программа с/курса 'Теория автоматов'

1. Понятие автомата. Конечные и бесконечные автоматы. Функционирование конечного автомата. Основные способы задания конечного автомата: таблица, диаграмма Мура, канонические уравнения. Конечно-автоматные функции.
2. Обобщения понятия автомата: недетерминированные, частичные, асинхронные автоматы.
Вероятностные автоматы. Линейные автоматы. Автоматы над термами.
3. Детерминированные функции. Информационные деревья. Остаточные функции детерминированной функции. Ограниченно-детерминированные функции. Вес о.-д. функции.
4. Преобразование периодических последовательностей ограниченно-детерминированными
функциями.
5. Неотличимость состояний конечного автомата. Автомат приведенного вида.
Неотличимость и изоморфизм конечных автоматов. Теорема о существовании единственного
с точностью до изоморфизма автомата приведенного вида в классе K(A,B), неотличимого от заданного автомата. Пример автомата приведенного вида, не имеющего одного слова, отличающего любые два его состояния.
6. Слабая неотличимость автоматов. Различие отношений неотличимости и слабой неотличимости. Счетность множества классов отношения слабой неотличимости.
7.Достижимость состояний. Сильно связные автоматы. Совпадение отношений неотличимости
и слабой неотличимости для класса сильно связных автоматов.
8. Понятие r-неотличимости конечных автоматов. Теорема о существовании для любого натурального r двух автоматов, являющихся r-неотличимыми, но не r+1 - неотличимыми.
9. Неотличимость двух состояний множеством слов. Лемма о разбиениях множества состояний автомата на классы неотличимости множествами M и (M u AM).
Построение множества, отличающего любые два состояния автомата, на основе некоторого
исходного множества слов М.
10. Теорема Мура о длине слова, отличающего два состояния конечного автомата.
Длина слова, отличающего два состояния различных автоматов. Примеры, устанавливающие
неулучшаемость этих оценок длины.
11.Базис достижимости и базис отличимости для конечного автомата. Леммы о существовании этих базисов.
12. Построение множества слов, отличающего заданный инициальный автомат приведенного
вида от любого другого инициального автомата приведенного вида, имеющего не более n состояний (с помощью базисов отличимости и достижимости).
13. Кратные эксперименты с конечными автоматами. Простые и условные кратные эксперименты. Результат применения кратного эксперимента к автомату. Длина, кратность
и объем результата. Диагностические и тестовые кратные эксперименты. Простейшие оценки
длины кратных диагностических экспериментов.
14. Алгоритм нахождения диагностического кратного безусловного эксперимента, имеющего
наименьший объем.
15. Простые эксперименты с конечными автоматами. Безусловные и условные простые
эксперименты. Результат применения эксперимента к автомату. Диагностические и тестовые
простые эксперименты. Утверждение об отсутствии в общем случае тестового простого
эксперимента для инициального автомата в классе автоматов, отличающихся от него выбором
начального состояния.
16. Установочные эксперименты для конечного автомата. Теорема Мура-Карацубы.
17. События, представимые в конечном автомате. Операции над событиями. Регулярные события. Лемма о решении уравнения с итерацией. Лемма о решении системы уравнений с регулярными коэффициентами.
18. Регулярность событий, представимых в конечном автомате.
19. Обобщенные истичники. Событие, определяемое обобщенным источником. Существование
обобщенного источника, определяющего регулярное событие. Представимость события, определяемого обобщенным источником. Теорема Клини. Пример нерегулярного события.
20. Обычный источник. Задание регулярных событий источниками. Теорема Лупанова о числе состояний автомата, необходимом в худшем случае для педставления события, определяемого n-вершинным источником.
21. Регулярные выражения. Регулярность пересечения, разности и дополнения регулярного
события. Регулярность проекции регулярного события. Регулярность события, образованного
словами, все начала которых принадлежат заданному регулярному событию.
22. Сверхслова и сверхсобытия. Сверхсобытия, представимые в конечном автомате с помощью заданного семейства подмножеств выходного алфавита. Операции над сверхсобытиями. Общерегулярные сверхсобытия. Лемма о регулярности множества слов, переводящих автомат из заданного состояния в него же и определяющих заданную группу выходных символов.
23. Общерегулярность представимых сверхсобытий.
24. Сверхисточники и определяемые ими сверхсобытия. Существование сверхисточника, определяющего заданное общерегулярное сверхсобытие.
25. Представимость сверхсобытия, определяемого сверхисточником. Теорема Мак-Нотона.
26. Пример необщерегулярного сверхсобытия.

Редактировал vazelin (13.12.2005 11:06)