English version of this page
На главную страницу
Официальный сайт кафедры Математической теории интеллектуальных систем и
лаборатории Проблем теоретической кибернетики
механико-математического факультета МГУ им. М. В. Ломоносова
На первую страницу сервера Новости Кафедра Сотрудники Учеба Наука Исследования Журнал Культура Полнотекстовый поиск по серверу
 ТДФ Теория дискретных функций – лекции и семинары для студентов 1 курса (II поток)
 Ташкентский филиал Ташкентский филиал МГУ им. М.В. Ломоносова
 Семинары расписание специальных семинаров кафедры МаТИС
 Курсы расписание специальных курсов кафедры, программа курсов
 Практикум cпециальный математический практикум кафедры МаТИС, III курс
 Студенты список студентов кафедры по курсам и группам, расписание занятий, выпускники
 Магистратура информация для поступающих в магистратуру
 Аспирантура информация для аспирантов и поступающих в аспирантуру; списки аспирантов

Перейти к полному списку специальных курсов кафедры

Программа экзамена по спецкурсу "Теория автоматов"

Спецкурс расчитан на один год или полгода, возможен зачет.

 

Программа курса, 2013 г.

 

1. Понятие конечного автомата, основные определения. Обобщения понятия конечного автомата. Примеры автоматов, описывающих сложение n-разрядных чисел и деление n-разрядных чисел на фиксированное число. Способы задания автомата, канонические уравнения, диаграмма Мура.

2. Автоматная функция. Детерминированная функция, понятие о.д.-функции. Эквивалентность состояний автомата, сильная и слабая эквивалентность автоматов. Пример несовпадения сильной и слабой эквивалентности. Изоморфизм автоматов, приведенный автомат. Теорема о единственности приведенного автомата, эквивалентного данному.

3. Абстрактные автоматы. Проверка эквивалентности состояний автомата, теорема Мура о длине слова, проверяющего эквивалентность состояний автомата и ее следствия. Проверка эквивалентности конечных автоматов. Теорема Мура о длине слова, отличающего конечные автоматы. Достижимость оценки длины слова отличающего конечные автоматы.

4. Эксперименты с автоматами. Простые, кратные и условные эксперименты. Невозможность определения с помощью экспериментов числа состояний автомата и начального состояния автомата. Установочный эксперимент. Теорема об оценке длины установочного эксперимента.

5. Конечные автоматы как акцепторы. Регулярные множества и регулярные выражения. Теорема Клини.

6. Конечные автоматы как сверхакцепторы. Теорема Мак-Нотона.

7. Структурные автоматы, операции суперпозиции и композиции. Схемы в базисе из булевых функций и <задержки>. Оператор замыкания. Проблема полноты и выразимости. Мощность полных систем автоматов. Класс автоматов с безусловными переходами, полные системы в этом классе.

8. Системы автоматов с операцией суперпозиции, имеющих ограниченное число входов. Полнота системы одноместных автоматов и булевых функций. Полугруппа автомата, связь операций над автоматами с операциями над их полугруппами. Вербальные операции над автоматами. Неполнота системы одноместных групповых автоматов и булевых функций в классе групповых автоматов.

9. Линейные автоматы. Проблема полноты для линейных автоматов относительно суперпозиции.

10. Алгоритмическая неразрешимость проблемы полноты конечных систем автоматов относительно композиции.

11. О мощности множества предполных классов автоматов.

12. Системы автоматов с операцией композиции, содержащие истинностные функции. Разрешимость проблемы полноты таких систем.

 

Литература.

1. Кудрявцев В.Б., Алешин С.В.,Подколзин А.С. "Введение в теорию конечных автоматов".- М.: Наука, 1985 г.

2. Яблонский С.В. Введение в дискретную математику. – М.: Наука, 1985 г.

3. Автоматы, Сборник статей под редакцией Маккарти и Шеннона, ИЛ, Москва, 1956

4. Кудрявцев В.Б., О мощностях множеств предполных классов некоторых функциональных систем, связанных с автоматами, ДАН СССР т.151,N3,1963, c.493-496.

5. Бабин Д.Н., Вербальные подавтоматы и задача полноты, Вестник МГУ, Математика и механика, 1985, N 3, с.82-85.

6. Летичевский А.А., Условия полноты для конечных автоматов, Вычислительная математика и математическая физика, N 4,1961, с.702-710.

7. Бабин Д.Н., Разрешимый случай задачи о полноте автоматных функций, Дискретная математика, том 4, 1992, выпуск 4, с.41-56, Наука, Москва.

8. Бабин Д.Н. О полноте двухместных о.д.-функций относительно суперпозиции, Дискретная математика, том 1, 1989, вып. 4, с. 86-91, Наука, Москва.

Наверх

   © 2001-2015 г. Кафедра Математической теории интеллектуальных систем, лаборатория Проблем теоретической кибернетики Написать вебмастеру   
XWare
 Полнотекстовый поиск
 
Только точная форма слов      Выводить по результатов на странице
Rambler's Top100 Рейтинг@Mail.ru