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

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

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

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. Структуризация класса клеточных автоматов с точки зрения распознавания свойства обратимости (без доказательства).
.

Наверх