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

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

Спецкурс "Теория обратимых клеточных автоматов"

 

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

  1. Понятие клеточного автомата (КА). Классы конечных и периодических конфигураций. Отображения, реализуемые клеточными автоматами.
  2. Блоки ячеек в клеточном автомате. Определение ограничения на блок глобальной функции переходов. Неконструируемые конфигурации блока. Взаимно-стираемые кон
  3. Лемма об отсутствии неконструируемых конфигураций для сюръективных КА.
  4. Лемма об отсутствии взаимно-стираемых конфигураций для КА, инъективных на конечных конфигурациях.
  5. Лемма о существовании неконструируемых конфигураций при наличии взаимно-стираемых конфигураций (теорема Мура).
  6. Лемма о существовании взаимно-стираемых конфигураций при наличии неконструируемых конфигураций (теорема Майхилла).
  7. Теорема Мура-Майхилла в терминах отображений. Простейшая иерархия классов обратимых КА.
  8. Пример нетривиального биективного КА.
  9. Пример КА сюръективного, но не биективного.
  10. Блочные перестановки. Теорема J. Durand-Lose о представлении биективного КА суперпозицией блочных перестановок (без доказательства).
  11. Теорема о балансировке числа прообразов конфигураций блоков в сюръективных КА.
  12. Теорема о верхней оценке числа сюръективных КА.
  13. Класс гранично-перестановочных КА. Теорема о нижней оценке числа сюръективных КА.
  14. Понятие Б-графа для одномерных КА.
  15. Построение "квадрата" Б-графа.
  16. Алгоритм проверки сюръективности одномерных КА как алгоритм поиска на квадрате Б-графа.
  17. Алгоритм проверки биективности одномерных КА как алгоритм поиска на квадрате Б-графа.
  18. Понятие машины Тьюринга (МТ). Отображения, вычисляемые МТ. Тезис Тьюринга.
  19. Алгоритмически неразрешимые проблемы. Проблемы самоприменимости, остановки на слове, остановке на пустом слове.
  20. График вычисления МТ. Табличное задание графиков.
  21. Переформулировка алгоритмически неразрешимых проблем для МТ в проблемы существования локально-корректных графиков.
  22. Лемма о "циклических" системах линейных уравнений над Z_2.
  23. Понятие клеточного автомата с переменной структурой (КАПС).
  24. Лемма об "укладке" СЛАУ над Z_2 на график в рамках КАПС.
  25. Теорема Кари о неразрешимости проблемы распознавания свойства сюръективности для двумерных КА.
  26. Лемма о циклических компонентах для бесконечных конфигураций "графического" КАПС.
  27. Теорема Кари о неразрешимости проблемы распознавания свойства биективности для двумерных КА.
  28. Структуризация класса клеточных автоматов с точки зрения распознавания свойства обратимости (без доказательства).
  29. .

Наверх

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