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

Программа курса:

1. Понятие конечного автомата, основные определения. Способы задания автомата, канонические уравнения, диаграмма Мура.
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, Наука, Москва.

Наверх

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

Cпецкурс "Дополнительные главы теории автоматов"

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