Структура графа состояний клеточных автоматов определённого типа

Оглавление

§1 Введение

§1.1 Общие сведенья по клеточным автоматам

§2 Структура графа состояний для линейного оператора над Zp

§3 ACS-автомат

§3.1 Постановка задачи.

§3.2 Краткий обзор предыдущих результатов

§3.3 Структура Gj при p=2

§3.3.1 Исследование структуры

§3.3.2 Исследование высоты деревьев

§3.4 Структура Gj при p¹2

§4 Структура графа со

стояний оператора взятия разностей

§5 Перспективы исследования

§6 Резюме

Используемые источники. Список использованной литературы

§1 Введение

§1.1 Общие сведенья по клеточным автоматам

Клеточный автомат – это математический объект с дискретным пространством и временем. Каждое положение в пространстве представлено отдельной клеткой, а каждый момент времени – дискретным шагом или поколением. Состояние каждой клетки определяется некоторыми правилами взаимодействия. Эти правила предписывают изменения состояния каждой клетки в следующем такте времени в ответ на текущее состояние соседних клеток.

Общие правила построения клеточных автоматов:

1. Состояние клеток дискретно (0 или 1, но могут быть автоматы и с большим числом состояний).

2. Соседями является ограниченное число клеток.

3. Правила, задающие динамику развития клеточного автомата, имеют некоторую функциональную форму.

4. Клеточный автомат является тактируемой системой, т.е. смена клеток происходит одновременно.

Условные обозначения

Некоторые стандартные обозначения векторов из

Цели:

1. Исследовать структуру графа :

· определить количество и высоту деревьев, описать их структуру;

· определить количество и длину циклов графа ;

· описать множество висячих вершин графа .

2. Рассмотреть те же вопросы для случая произвольного линейного оператора.

§2 Структура графа состояний для линейного оператора над Zp

Введение

Рассмотрим множество и линейный оператор такое, что y – линейный оператор над полем Zp, в частности, этот оператор может задавать изменение состояния некоторого одномерного клеточного автомата с p состояниями.

Будем рассматривать граф состояний , для которого . Основной целью исследования является изучение структуры графа .

Одним из важных свойств оператора y, которое будет использоваться в дальнейшем, является его аддитивность:

Для исследования структуры графа Gy рассмотрим следующую нумерацию вершин нулевого дерева (см. рис. 2.1).

– вершина, находящаяся на m ярусе, при этом она входит в

(), смысл этих обозначений станет ясным позже. Важно то, что в этих обозначениях в вершину входят , при этом вершины входят в (в нашем случае.

Рис. 2.1

Теорема 2.1

Пусть задана цепь: тогда .

Доказательство:

Воспользуемся методом математической индукции.

База m=1:

, действительно причем различные вершины, ч.т.д.

Пусть теорема верна для m = l-1, т.е.

Докажем, что Тем, самым, по построению , мы покажем, что .

Действительно, в силу линейности:

Теорема 2.1 доказана.

Назовем дерево с корнем en = (0,0,…,0) – «нулевым» деревом, тогда для него верна следующая теорема.

 Скачать реферат