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