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


Скачать 214.88 Kb.
Название1 Общие сведенья по клеточным автоматам
страница1/3
Дата публикации13.10.2013
Размер214.88 Kb.
ТипДокументы
referatdb.ru > Математика > Документы
  1   2   3
Управление образования Московского района г. Минска

Государственное учреждение образования «СШ № 41 г. Минска»

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


Автор:

Учащийся 9’ класса

ГУО «СШ №41 г. Минска»

Иванин Алексей

Научный руководитель:

Студент 1 курса ФПМИ БГУ

Глущенко Михаил Сергеевич

Минск, 2009 г

Оглавление


Оглавление 2

§1 Введение 3

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

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

§3 ACS-автомат 7

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

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

§3.3 Структура G при p=2 8

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

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

§3.4 Структура G при p2 12

§4 Структура графа состояний оператора взятия разностей 15

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

§6 Резюме 17

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


^

§1 Введение

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



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

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

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

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

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


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

V(G)

Множество вершин графа G

E(G)

Множество ребер графа G



Поддерево g с корнем v



Множество вершин полного корневого поддерева g с корнем v дерева G, находящихся на m-том ярусе, относительно корня v.

D()

Множество висячих вершин графа



Поле вычетов по mod p (p – простое), т.е. {1,2,..,p-1}





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

(0,0,0,…,0)=

en

(1,0,1,1,0,1,…,0,1)=

rn для n=2k+1

(1,0,0,…,0)=

dn

(1,1,0,1,1,0,…,1,1)=

sn для n=3k+2

Цели:

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

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

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

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

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

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



Введение

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

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

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



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

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

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


Рис. 2.1
Теорема 2.1

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

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

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

База m=1:

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

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

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

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



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

Теорема 2.2

«Нулевое» дерево – p-нарное дерево с точностью до петли в корне (0,0..,0).

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

По теореме 2.1 единственная цепь из висячей вершины в (0,0,..0) однозначным образом определяет все элементы дерева (различность определяемых вершин очевидна, и следует из простоты p).
Теорема 2.3

Каждое дерево притягиваемого каждой точкой каждого цикла графа G изоморфно нулевому» дереву.

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

Для любых последовательностей k и l, находящихся на одном ярусе какого-то дерева, для которых выполняется условие:



верно равенство:

, где ―одна из последовательностей «нулевого» дерева на n-ном ярусе (сумма в поле ) (Следует из теоремы 2.1).

Используя полученное соотношение можно достроить любое дерево до дерева изоморфного «нулевому».
^

§3 ACS-автомат

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


В данной работе рассматривается клеточный автомат (одномерный), функционирование которого осуществляется по следующим правилам:

Дана полоска 1n (сам автомат), все клетки, которой находятся в состояниях «0» и «1». Изменение состояния клетки определяется следующим образом: данная клетка переходит в состояние «1», если её соседи находятся в разных состояниях, и в «0»,если её соседи находятся в одинаковых состояниях. Клетки, находящиеся по краям переходят в то же состояние, которое было у единственной соседней клетки в предыдущий момент времени.

По полоске длины n будем определять вектор , где :



Рассмотрим множество и отображение такое, что



(здесь и ниже – операция сложения по mod p=2, т.е. операция сложения в поле Z2).

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

Для начала рассмотрим некоторые определения и обозначения, которые будут использоваться в дальнейшем в работе:

  • ^ Ориентированное дерево — это ориентированный граф без циклов, в котором из каждой вершины, кроме одной, называемой корнем ориентированного дерева, выходит ровно одно ребро (более подробно структуры дерева будет определена позже).

  • m-й ярус – множество вершин дерева, находящихся на расстоянии m от корня.

  • Частичный порядок на вершинах: , если вершины u и v различны и вершина u лежит на единственном элементарном пути, соединяющем вершиной v с корнем дерева.

  • Корневое поддерево с корнем v — подграф .

  • Множество назовем множеством висячих вершин графа .
^

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



В прошлом году на ряде конференций (см. Используемые источники) была представлена работа по клеточным автоматам, в которой был исследован частный случай линейного оператора и найдены высоты деревьев для последовательностей, состоящих из 2n-1 элементов. В ней были представлены следующие утверждения, которые будут использоваться в дальнейшем:
Утверждение 3.2.1

.
Утверждение 3.2.2

1. ;

2. , причем

3. ;

4. .

Утверждение 3.2.3

; и .
Предисловие

В параграфе будет рассказано о свойствах графа состояний оператора , а именно будет описана его структура.
^

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

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


Пользуясь утверждением 3.2.2, мы получаем, что среди всех последовательностей можно выделить следующие:

  1. которые невозможно получить не из каких других, например: (1,0,0) (они будут образовывать висячие вершины графа);

2.  которые, спустя несколько итераций возвращаются в начальное положение, например:

(1,0,0,0)  (0,1,0,0)  (1,0,1,0)  (0,0,0,1)  (0,0,1,0)  (0,1,0,1)  (1,0,0,0)

(такие последовательности в графе будут соответствовать вершинам цикла)



Используя утверждение 3.2.2, можно сделать вывод:

Теорема 3.3.1.1

Каждая компонента связности графа является циклом (возможно длины 1), каждый элемент которого притягивает дерево (т.е. является корнем ориентированного дерева) (см. рис. 3.2.1).
Наша основная задача определить длины циклов и высоты деревьев, описать их структуру и найти их количество.


Рис. 3.3.1

Теорема 3.3.1.2

Для любых последовательностей k и l, находящихся на одном ярусе какого-то дерева, для которых выполняется условие: верно равенство:

, где ―одна из последовательностей «нулевого» дерева на n-ном ярусе.

Более точно это можно сформулировать так:

Д
ля любого «полного» корневого поддерева g с корнем v дерева G (с корнем в ): , где и – подмножество такое, что: , при этом (см. рис. 3.2.2).


Рисунок 3.3.2

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

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

  1. m = 1:

Пусть , тогда . Тогда, учитывая утверждение 1.1, и , получим требуемое.

  1. Пусть утверждение леммы верно для m = k, тогда:

  2. Докажем теорему для m = k+1.

Мы имеем: , тогда:

Если и , то:

Из утверждения 3.2.1:

, но , т.е. , откуда , ч.т.д.




Теорема 3.3.1.3


«Нулевое» дерево ― бинарное дерево с точностью до петли в корне en.

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

П
Рис. 3.3.3
усть и, тогда мы можем достроить его, пользуясь теоремой 3.3.1.2 до бинарного дерева с точностью до петли в корне en (см. рис. 3.3.3) Заметим, что n+1-го яруса быть не может т.к. тогда мы достраиваем этот ярус и получаем такое, что но – противоречие.

Теорема 3.3.1.4

Все деревья (в том числе и примыкающие к каждой вершине произвольного цикла) будут иметь столько ярусов, сколько и «нулевое», причем будут иметь такую же структуру.

Более точно: дерево, притягиваемое каждой точкой каждого цикла графа состояний, изоморфно дереву, притягиваемому точкой en.

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

Предположим «нулевое» дерево состоит из n ярусов тогда:

  1. Если наше дерево состоит менее чем из n ярусов, то, пользуясь теоремой 3.3.1.2, мы восстанавливаем его до дерева изоморфного «нулевому».

  2. Если дерево имеет m ярусов, где n<m тогда , получается, что «нулевое» дерево состоит из m ярусов ― противоречие.



^

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



Теорема 3.3.2.1

Если длина последовательности равна 2k-1, то высота деревьев будет равна 2k-1.

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

Пример для k=1 и k=2 строятся довольно просто:

k=1 k=2

0 (1) 0 0 (1,0,0) 0

0 (0) 0 0 (0,1,0) 0

0 (1,0,1) 0

0 (0,0,0) 0

Докажем по индукции

  1. База индукции:

Пусть k=3, тогда:

0 (1,0,0,0,0,0,0) 0

0 (0,1,0,0,0,0,0) 0

0 (1,0,1,0,0,0,0) 0

0 (0,0,0,1,0,0,0) 0

0 (0,0,1,0,1,0,0) 0

0 (0,1,0,0,0,1,0) 0

0 (1,0,1,0,1,0,1) 0

0 (0,0,0,0,0,0,0) 0

Высота дерева равна 2k=7.

  1. Пусть утверждение верно для n=k, тогда докажем его для n=k+1:

;

тогда:





Так как -й элемент равен «0» и остальные элементы симметричны относительно его, то в каждом последующем поколении этот элемент будет равен «0», следовательно, правая и левая части перейдут в состояние (0,0,…,0) через 2k поколений. Таким образом, высота дерева будет 2k +2k-1=2k+1-1=2n-1 ч.т.д.

Теорема 3.3.2.2

Если длину последовательности представить в виде  где , тогда 2k-1 ― высота «нулевого» дерева.

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


По теореме 3.3.2.1 , где с корнем .

Возьмем последовательность длиной ; 

 заметим, что тогда:

 (в связи с симметрией относительно )

Но тогда:

Высота дерева при n=2n-1 равна высоте дерева при n=32n-1. В связи с симметрией относительно  , мы получаем:

Высота дерева при n=2n+1+2n-1-1 равна высоте дерева при n=32n-1-1.

Таким образом, мы получаем, что если представить длины последовательности в виде: , то 2-1k ― высота дерева.

Теорема доказана.
  1   2   3

Похожие рефераты:

Инструкция: один ответ правильный (1 10 вопрос 10 баллов) Так как...
Ответы к заданиям 3 тура областной заочной школы олимпийского резерва рнпц «Ертіс дарыны» 2012-2013 учебный год
Коммерческое предложение
Установка и обслуживание автоматов по приготовлению горячих напитков. Дополнительно к автоматам по продаже кофе мы готовы установить...
Общие правила промышленной безопасности часть 2 Глава Оборудование Параграф Общие требования
Конструкция оборудования соответствует гост 12 003 «Оборудование производственное. Общие требования безопасности» и гост 12 007....
Общие требования промышленной безопасности часть 1 Глава Общие положения
Настоящие Требования устанавливают общие требования промышленной безопасности для опасных производственных объектов
План: Взаимосвязь обменов веществ: Образование углеводов из белков и белков из углеводов
Пути взаимосвязи обменов белков, углеводов и липидов. Общие источники энергии и общие промежуточные продукты. Общие пути распада....
Общие требования промышленной безопасности часть 2 Глава Оборудование Параграф
Конструкция оборудования соответствует гост 12 003 «Оборудование производственное. Общие требования безопасности» и гост 12 007....
1 общие положения 3
В настоящем документе представлены общие требования, предъявляемые к кптс автоматизированной системы контроля, управления и защиты...
Общие положения
Межотраслевые общие правила по охране труда (далее – Правила) распространяются на всех нанимателей независимо от их организационно-правовых...
Дипломные проекты (работы) общие требования стп 01-2013
Настоящий стандарт устанавливает общие требования к организации дипломного проектирования, построению, содержанию, оформлению и порядку...
Темы практических и/или семинарских занятий раздел Общие вопросы...
Какие общие задачи решаются при обучении математики учащихся вспомогательной школы?

Вы можете разместить ссылку на наш сайт:
Школьные материалы


При копировании материала укажите ссылку © 2013
контакты
referatdb.ru
referatdb.ru
Рефераты ДатаБаза