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

Управление образованияМосковского района г. Минска

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

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

Минск, 2009 г

Оглавление

§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.               Клеточныйавтомат является тактируемой системой, т.е. смена клеток происходитодновременно.

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

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

Введение

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

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

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

/>

Для исследованияструктуры графа Gy<sub/>рассмотримследующую нумерацию вершин нулевого дерева (см. рис. 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

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

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

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

/>

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

/>,

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

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

§3 ACS-автомат§3.1Постановка задачи

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

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

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

/>

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

/>

(здесь и ниже /> – операция сложения по modp=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

 

/>; /> и />.

Предисловие

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

 §3.3 Структура Gjпри 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).

Нашаосновная задача определить длины циклов и высоты деревьев, описать их структуруи найти их количество.

/> <td/>

Рис. 3.3.1

   

Теорема3.3.1.2

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

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

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

/>

Рис.3.2.2

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

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

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

1.               m = 1:

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

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

3.               Докажемтеорему для 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.

2.               Пустьутверждение верно для 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=3×2n-1-1.

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

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

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

Введение

Впараграфе 2 мы рассматривали структуру графа состояний для произвольноголинейного оператора над Zp.В данном параграфе пойдет речь о структуре графа Gjопределенного в параграфе 3.1. По аналогии со случаем p=2,по состоянию числовой полоски длины n(т.е. самого автомата с состояниями 0,1,..p-1)будем определять вектор/>, ирассматривать /> такое, что:

/>

Всеостальные основные определения вводятся аналогичным образом, как и в случае p=2,основным предметом исследования является структура графа Gj.

Однимиз важных свойств оператора j является его аддитивность:

/>

котораяследует из линейности оператора j.

Впредыдущем параграфе было доказано утверждение о том, что для произвольноголинейного оператора y «нулевое» дерево – p-нарноедерево с точностью до петли в корне (0,0..,0) (теорема 2.2). В данном параграфебудет определена высота нулевого дерева, тем самым будут определена высотадерева притягиваемого каждой точкой каждого цикла графа Gj(теорема 2.3).

Теорема3.4.0

Вершина/> является висячей тогда итолько тогда, когда n – нечётное ивыполняется условие:

/>

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

Пустьу нас есть последовательности /> и />

Тогда/> Но тогда />.

Нопо условию />, т.е. для тогочтобы вершина /> была висячейнеобходимо и достаточно, чтобы />, т.е.

/>

Теоремаполностью доказана.

Теорема3.4.1

Еслидлина последовательности кратна двум, то граф Gφ ―дизъюнктное объединение циклов.

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

Воспользуемсятем, что дерево, притягиваемое каждой точкой каждого цикла, изоморфно нулевомудереву. Рассмотрим нулевое дерево. Его высота при n=2kравна нулю. Это следует из того, что />, но m=2s+1,противоречие. Теорема полностью доказана.

Теорема3.4.2

Еслидлину последовательности представить в виде pk(2l)-1, (p,l)=1, тогдаpk есть высота «нулевого» дерева.

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

Дляначала докажем следующие леммы.

Лемма 1

/> – висячая вершинапричем, />.

/>

Рис. 3.4.1 Пример для p= 5.

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

Для начала рассмотримшахматную раскраску таблицы (2pk-1)(pk+1),строки которой есть последовательности />, />, …, /> (см. рис.).Тогда числа, стоящие на закрашенных позициях равны 0.

Остальные координатыобразуют треугольник Паскаля с вершиной в 1 (см. пример на рис. 3.4.1 для p= 5). Тогда т.к. />, то:

/>,

при этом /> (все значениябиноминальных коэффициентов берутся по модулю p,так как мы рассматриваем вектор в пространстве />)

Замечание:

Здесь и ниже, всемногочлены рассматриваются над полем />

Докажем, что /> 

Действительно, т.к./> (т.к./>), то: />.

Откуда />, ч.т.д.

Замечание

Висячесть вершины /> следует изтеоремы 3.4.0

Следствие

/> – висячая вершина /> причем, />.

Для доказательствадомножим элементы рассмотренного выше треугольник Паскаля на iи в силу простоты p получимтребуемое.

Лемма 2

Вершина н вида:

/>

является висячей приусловии, что число последовательностей вида />, где />не кратно p,причем />.

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

Из теоремы 3.4.0,вершина /> является висячейпри n нечётном и выполненииусловия:

/>.

Таким образом, приподстановке соответствующих значений получим:

/>.

/>, где />.

Таким образом, вершинавида:

/>

является висячей приусловии, что число конструкций вида />, где m=1либо (p-1), не кратно p.Вторая часть леммы следует из следствия леммы 1, причем, как и в лемме 1, /> Лемма доказана.

Приступим теперь кдоказательству основной теоремы. Из леммы 1 следует, что высота дерева при /> равна pk,из леммы 2 следует, что если высота дерева при /> равна высоте деревапри />и, при условии,что (l,p)=1.

Теорема полностьюдоказана.

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

Введение

Вданном параграфе рассматривается структура графа состояний Gwоператора взятия разностей /> (см.[1]), который определяется следующим образом:

/>

В([1]) wбыл рассмотрен только над Z2,в этом параграфе оператор взятия разностей будет рассмотрен над полем Zp.Оператор взятия разностей используется для анализа сложности функций (см. [1]).

Наоснове результатов параграфа 2 (теоремы 2.2, 2.3), для анализа структуры графасостояний оператора w достаточно определить высоту нулевогодерева, тем самым будут определена высота дерева притягиваемого каждой точкойкаждого цикла графа Gw(теорема 2.3).

Теорема4.1

Если/>, то наименьшийпериод функции /> (modp) по iравен pk.

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

Проверимсначала, что число pkявляется периодом при />:

/>

Действительно,т.к.:/>

/>,

то/>, ч.т.д.

Теперьпокажем, что это наименьший период, если />, наименьший периоддолжен быть делителем числа pk,поэтому мы проверим, что pk-1– не период.

Докажем,что при /> число сочетаний />, действительно,пусть j= i-(p-1)pk-1,тогда />. Тогда, т.к.:

/>,

откудат.к. /> и/>, то />, т.е. />, ч.т.д.

Сдругой стороны />, поэтому число pk-1не является периодом функции

/> (modp) по переменной i,когда />, при этомусловии />.

Теорема4.2

Еслидлину последовательности представить в виде: /> где /> />,/>, тогда pk естьвысота «нулевого» дерева.

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

Проведем явноеинтегрирование функции />периодаn, т.е. определим a,такое, что j(a) = (1,1,…,1) (строгое определениеинтегрирования см. в [1])

/>

Рис. 4.1

Легко видеть, что всеинтегрированные «интегралы» (с начальным условием /> при t=1)– это приведенные по модулю pкосые линии треугольника Паскаля, на которых   j= 0 для исходной функции />, а затем, по мереповторного «интегрирования», ответы доставляют косые линии с j= 0,1,2… (см рис. 4.1)

Следовательно, длявыяснения того, сколько раз удастся «проинтегрировать» функцию /> (т.е.определить высоту нулевого дерева) в классе n-периодическихфункций (т.е. в классе n-периодическихпоследовательностей) остается выяснить, при каких значениях jфункция /> аргумента iбудет иметь период n.

Всилу теоремы 4.1, если n=/>/>, то построение «нулевого» дерева, описанного выше,будет успешным до тех пор, пока «j-кратныеинтегралы» /> от функции /> будутоставаться n-периодическимифункциями аргумента i. Но наименьшийпериод указанной функции переменной iравен prпри />. Чтобы эта функция была n-периодической,необходимо, чтобы число n=/>  делилось на наименьший период,т.е. чтобы />. Откуда следует, что если длинупоследовательности представить в виде: n=/>/>, тогда pk есть высота «нулевого» дерева,ч.т.д.

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

1.               Более подробноисследовать структуру />, аименно:

·                  Определитьколичество циклов и их длину;

·                  Описать множествокорней деревьев  и т.д.

2.               Рассмотретьдвумерный вариант клеточного автомата (на клеточном прямоугольнике />) с теми же вопросами, т.е.описать структуру графа состояний.

3.               Более подробнорассмотреть матричную интерпретацию.

4.               В связи сиспользованием одномерных клеточных автоматов, а также линейных операторов, втеории кодирования, найти количественные и качественные характеристики автомата(например, определить коллизии и т.д.).

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

§6Резюме

Основнымпредметом исследования являлась рассмотрение структуры графа />, более подробное изучение которой,является одним из наиболее перспективных направлений дальнейшего исследования.В общем случае получена следующая характеристика структуры графа />:

1.Каждая компонента связности графа /> является циклом (возможно длины1), каждая вершина которого притягивает дерево (возможно нулевой высоты).

2./> и /> />;

3./>;

4.«Нулевое» дерево ― p-нарноедерево с точностью до петли в корне en(0,0..0), причем его высота равна

·                  /> (для оператора />, описывающего функционирование ACS-автоматаи />), если длинупоследовательности представить в виде /> где />, />;

·                  /> (для оператора />, описывающего функционирование ACS-автоматаи />) если длинупоследовательности представить в виде: /> где />, />.

5.«Нулевое» дерево ― p-нарноедерево с точностью до петли в корне en(0,0..0), причем его высота равна /> (для оператора взятия разности), если длину последовательностипредставить в виде: /> где /> />,/>;

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

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

Используемыеисточники

1.          М.С.Глущенко, П.С. Пересторонин, Почти центральная симметрия (доклад на IVБалтийском научно–инженерном конкурсе, Санкт-Петербург, 2008 г.)

2.          М.С.Глущенко, П.С. Пересторонин, Почти центральная симметрия (доклад на XIIБелорусской республиканской конференции учащихся общеобразовательныхучреждений, Минск, 2008 г.)

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

1.          В.И.Арнольд, Сложность конечных последовательностей нулей и единиц и геометрияконечных функциональных пространств (из доклада Московскому математическомуОбществу 22 ноября 2005 г.)

2.          В.И.Арнольд, Топология и статистика арифметических и алгебраических формул, Успехиматематических наук 58(2003), №4, 3-28