Введение

Тема 1. Основные понятия и задачи теории автоматов

• 1.1. Понятие автомата (168мин.)
• 1.2. Основные задачи теории автоматов (273мин.)
• Тест:  Основные понятия и задачи теории автоматов (26мин.)

Тема 2. Автоматы как преобразователи информации

• 2.1. Теорема Мура о единственности автомата приведенного вида (63мин.)
• 2.2. Теорема об автомате как преобразователе периодических сверхслов (42мин.)
• 2.3. Теоремы Мура о длине слов, отличающих состояния автоматов (147мин.)
• Тест:  Автоматы как преобразователи информации (18мин.)

Тема 3. Эксперименты с автоматами-преобразователями

• 3.1. Теорема Мура об отсутствии простого тестового эксперимента (63мин.)
• 3.2. Теорема Мура о существовании простого установочного эксперимента (63мин.)
• 3.3. Теорема Карацубы о неулучшаемости оценки Мура длины простого установочного эксперимента (63мин.)
• 3.4. Кратные эксперименты с автоматами (42мин.)
• Тест:  Эксперименты с автоматами-преобразователями (16мин.)

Тема 4. Автоматы как акцепторы

• 4.1. Регулярные выражения и события (63мин.)
• 4.2. Теорема Клини о представлении событий автоматами (105мин.)
• 4.3. Лемма о накачке (63мин.)
• Тест:  Автоматы как акцепторы (18мин.)

Тема 5. Автоматы как сверхакцепторы

• 5.1. Общерегулярные выражения и события (42мин.)
• 5.2. Теорема Мак-Нотона о представление сверхсобытий автоматами (189мин.)
• Тест:  Автоматы как сверхакцепторы (14мин.)

Тема 6. Автоматы как предсказатели

• 6.1. Прогнозирование сверхсобытий автоматами (42мин.)
• 6.2. Теоремы Вереникина и Гасанова о прогнозировании периодических сверхсобытий (168мин.)
• 6.3. Теоремы Мастихиной о частичном прогнозировании общерегулярных сверхсобытий (377мин.)
• Тест:  Автоматы как предсказатели (24мин.)

Тема 7. Клеточные автоматы

• 7.1. Понятие клеточного автомата (168мин.)
• 7.2. Теорема Мура - Майхилла о райском саде (126мин.)
• 7.3. Теорема Подколзина о существовании универсального клеточного автомата (273мин.)
• 7.4. Теоремы Титовой о конструировании изображений клеточными автоматами (587мин.)
• • 7.4.1. Теорема о существовании универсального элементарного автомата (126мин.)
  • 7.4.2. Оценки времени конструирования изображений (105мин.)
  • 7.4.3. Конструирование движущихся изображений (336мин.)
• Тест:  Клеточные автоматы (48мин.)

Тема 8. Распознавание полноты для автоматов

• 8.1. Автоматные функции многих переменных (63мин.)
• 8.2. Операции над автоматными функциями и схемами (231мин.)
• 8.3. Замыкание. Выразимость. Задача о полноте (63мин.)
• 8.4. Конечные K-полные системы (147мин.)
• 8.5. Неконечная порожденность классов автоматов с операциями суперпозиции (21мин.)
• 8.6. Теорема Кудрявцева о числе предполных классов для автоматов (105мин.)
• 8.7. Теорема Кратко об алгоритмической неразрешимости проблемы распознавания полноты для автоматов (147мин.)
• Тест:  Распознавание полноты для автоматов (38мин.)

Рекомендуемая литература

Завершение курса

• Тест:  Итоговое тестирование (48мин.)