Конструирование изображений клеточными автоматами

• Автор: Титова, Елена Евгеньевна
• Шифр специальности: 01.01.09
• Научная степень: Кандидатская
• Год защиты: 2015
• Место защиты: Москва
• Количество страниц: 92 с. : ил.

Оглавление
Введение
1 Общая характеристика работы
2 Краткое содержание работы
1 Конструирование изображений клеточными автоматами
1 Точная оценка числа состояний элементарного автомата
2 Точное значение времени построения изображения при неограниченном числе
состояний элементарного автомата
3 Линейная оценка времени построения изображения при ограниченном числе
состояний элементарного автомата
4 Оценка времени конструирования изображения при растущем числе состояний
элементарного автомата
5 Верхняя оценка времени построения изображения на экране с одним входом
при ограниченном числе состояний элементарного автомата
6 Построение изображений на многомерных экранах
2 Сложность управляющего автомата для построения изображений на универсальном экране
1 Предобработка кода изображения
2 Сложность управляющего автомата
3 Конструирование движущихся изображений клеточными автоматами
1 Движение точки на конечном экране
2 Движение многоточечных изображений на конечном экране
3 Движущиеся изображения на бесконечном экране
4 Движение с ограниченной скоростью на бесконечном экране
5 Автономно движущиеся изображения на бесконечном экране
Заключение

Введение
1 Общая характеристика работы
Актуальность темы и степень ее разработанности
Клеточный автомат — это математический объект с дискретными пространством и временем. Каждое положение в пространстве представлено отдельной клеткой, а каждый момент времени — дискретным временным шагом или поколением. Состояние каждой пространственной клетки определяется очень простыми правилами взаимодействия. Эти правила предписывают изменения состояния каждой клетки в следующем такте времени в ответ на текущее состояние соседних клеток. При этом для разных клеток правила изменения состояний могут быть разными.
Частным случаем клеточных автоматов являются однородные структуры, которые представляют собой дискретную математическую модель широкого класса реальных систем вместе с протекающими в них процессами, таких как физические среды, в которых реализуются тепловые и волновые явления, химические растворы с реакциями в них, биологические ткани, в которых происходит обмен веществ, технические схемы управления, производящие переработку механических и электрических сигналов, вычислительные схемы и т.п.
Понятие однородной структуры возникает при выборе в качестве преобразователя информации, стоящего в клетке пространства, конечного автомата — простейшей управляющей системы. Если задать начальные состояния автома-

одну клетку в каждом направлении. Это означает, что если ненулевое значение появилось на каком-то из свободных входов экрана, то клетки с координатами (п, т) оно достигнет не раньше чем в тт(те, т) + 1-й такт. ■
Лемма 4. Если п,тбК, то
Т(п,т) < тт(те,т7г) + 1.
Доказательство. Построим генератор, который конструирует любое изображение за время тт(п, т)+1. Без ограничения общности считаем, что т> п.
Построим элементарный автомат. Будем считать, что состояние элементарного автомата состоит из двух компонент: первая — счетчик (от 0 до п), а вторая — метка (0 или 1). В начальный момент времени счетчик автомата и метка равны нулю. Существенным входом элементарного автомата является только состояние верхнего автомата. Если значение счетчика автомата равно нулю, автомат выдает метку. В каждый момент времени автомат берет значение счетчика и метку у верхнего автомата. Если значение счетчика больше нуля, автомат уменьшает его на единицу, присваивает это значение своему счетчику и берет у верхнего автомата новое значение метки. Таким образом определяется новое состояние элементарного автомата. Если значение счетчика верхнего автомата равно нулю, автомат не меняет значение своего счетчика и своей метки. Таким образом, элементарные автоматы имеют по 2п + 2 состояния, А — В = (3 = Е2П+2 — {0,1,..., 2п + 1}. Для состояний 0 и 1 значения счетчика равны нулю, значения метки равны 0 и 1 соответственно. Для состояний с 2-го по (п + 1)-е значение метки равно 0 и значения счетчика равно 1,2,... ,п соответственно. Для состояний с {п + 2)-го по (2п + 1 )-е значение метки равно 1 и значения счетчика равно 1, 2,..., п соответственно. Переходы состояний описаны выше.
Построим внешний автомат, соответствующий заданному двоичному коду К. В начальном (нулевом) состоянии автомат подает на верхнюю горизонталь п-ю