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