Ознакомительный урок на тему "Одномерные клеточные автоматы"

Реализация одномерных клеточных автоматов

Выполнил:

Афанасьева.С.Д.

Улан-Удэ

2015

Содержание

ВВЕДЕНИЕ 3

1 Понятие клеточных автоматов 4

1.1 Основные свойства классической модели клеточных автоматов 4

1.2 Классификация клеточных автоматов 5

2 Одномерные клеточные автоматы 6

3 Двумерные клеточные автоматы 7

4 Применение клеточных автоматов 9

4.1 Влияние на развитие наук 9

4.2 Применение клеточных автоматов для математического моделирования динамических процессов 11

Заключение 13

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

Введение

Идея клеточных автоматов зародилась в 1940 - е годы. Ее независимо друг от друга разработали венгерско-американский математик Джон Фон Нейман и немецкий инженер Конрад Цусе. Сформулирована она была как универсальная вычислительная среда для построения, анализа и сравнения характеристик алгоритмов. Область применения клеточных автоматов огромна. Поэтому тема клеточных автоматов является очень актуальной, так как может помочь в разгадке многих вопросов окружающего мира. Создатель игры «Жизнь» Конуэй, считал, что нашу вселенную можно представить клеточным автоматом, который управляет движением элементарных частиц в соответствии с некоторыми правилами.

Задача исследования – реализация одномерных клеточных автоматов в среде разработки приложений на языке С++.

Предмет исследования – динамика поведения дискретных динамических систем на примере клеточных автоматов.

1. Понятие клеточных автоматов.

Автоматом называют устройство (или совокупность устройств), которое без непосредственного участия человека выполняет процессы приема, преобразования и передачи энергии, материалов или информации в соответствии с заложенной в него программой.

Клеточные автоматы являются частным случаем конечных автоматов, используемых для моделирования динамического поведения однородных сред. При этом пространство и время считаются дискретными, а физические величины в каждой точке моделируемой среды могут принимать конечное множество дискретных значений. Клеточные автоматы активно используются для моделирования сложных динамических систем.

1.1. Основные свойства классической модели клеточных автоматов:

• Локальность правил. На новое состояние клетки могут влиять  только элементы её окрестности и, возможно, она сама;

• Однородность системы. Вся область решетки построена по одному правилу. Однако на практике  решетка оказывается конечным множеством клеток (ведь невозможно выделить неограниченный объем данных). В результате могут иметь место краевые эффекты. Клетки, стоящие на границе решетки будут отличны от остальных по числу соседей. Во избежание этого можно ввести периодические краевые условия;

• Множество возможных состояний клетки — конечно. Это условие служит для того что бы проводилось конечное число операций.  Отметим, что оно не мешает использовать клетки для хранения чисел с плавающей точкой при решении прикладных задач.

• Значения во всех клетках изменяются одновременно в каждой итерации. Иначе порядок перебора клеток в итерации приводил бы к значительному изменению результата.  Необходимо отметить, что на практике, при решении определённых задач, возникает потребностьв том, чтобы отказаться от последних трёх свойств.

1. 2. Классификация клеточных автоматов

Классификация по типам поведения.

Стивен Вольфрам в своей книге A New Kind of Science предложил 4 класса, на которые все клеточные автоматы могут быть разделены в зависимости от типа их эволюции. Классификация Вольфрама была первой попыткой классифицировать сами правила, а не типы поведения правил по отдельности. В порядке возрастания сложности классы выглядят следующим образом:

Класс 1: Развитие происходит с конечным числом итераций до уникального однородного состояния, то есть до определенной точки.

Класс 2: Генерируются регулярные, периодические узоры, переходящие в предельный цикл.

Класс 3: структуры изменяются с определенным периодом, зависят от начальной конфигурации, их траектории лежат на хаотическом аттракторе.

Класс 4: В этот класс входят все клеточные автоматы, которые развиваются по сложным траекториям. Такие автоматы имеют возможность универсальных вычислений.

По утверждению Вольфрама эта классификация не совершенна, хотя и является основной и наиболее распространенной. Задача классификации правил по-прежнему остается открытой, о чем свидетельствуют проводимые исследования в динамических системах.

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

2. Одномерные клеточные автоматы.

В одномерном (линейном) клеточном автомате решетка это последовательность клеток, то есть одномерный массив, в котором для каждой из них, кроме крайних, имеется по два «соседа». Три клетки (центральная, предыдущая, следующая) порождают  комбинаций состояний этих трёх клеток. Всего существует  возможных правил. Эти 256 правил кодируются в соответствии с кодом Вольфрама — стандартному соглашению, правилу, которое было предложено Вольфрамом. Для устранения краевых эффектов решетка «заворачивается» в тор. Это позволяет использовать следующее соотношение для всех клеток автомата:

y'[i] = f(y[i-1], y[i], y[i+1]),

где f – функция переходов клетки;

y'[i] – состояние i-й клетки в следующий момент времени;

y[i-1] – состояние (i-1)-й клетки в данный момент времени;

y[i] – состояние i-й клетки в данный момент времени;

y[i+1] – состояние (i+1)-й клетки в данный момент времени.

В качестве примера показан результат работы клеточного автомата, реализованный по правилу 161 (10100001). Мы получили фрактал с последовательно вложенной структурой – ковер Серпинского. Правило определяет, что клетка становится черной, когда левая, либо правая, но не обе вместе окрашены в черный цвет.

Рис1.

Именно простейшие клеточные автоматы будут реализованы для исследования динамики поведения дискретных динамических систем. Глядя только на правило, кажется невозможным предугадать поведение каждого клеточного автомата. Но, проводя соответствующий компьютерный эксперимент, можно увидеть то, что происходит на самом деле – и в результате открывается путь исследования целого мира отмеченного феномена, связанного с простыми программами эволюции.

3. Двумерные клеточные автоматы.

В двумерном (плоскостном) клеточном автомате решетка реализуется двумерным массивом. В ней каждая клетка имеет восемь «соседей» (окрестность из восьми клеток). Для устранения краевых эффектов решетка так же, «заворачивается» в тор. Это позволяет использовать следующее соотношение для всех клеток автомата:

y'[i][j] = f(y[i][j], y[i-1][j], y[i-1][j+1], y[i][j+1], y[i+1][j+1], y[i+1][j], y[i+1][j-1], y[i][j-1], y[i-1][j-1]).

Наиболее известным из двумерных клеточных автоматов является автомат, моделирующий игру «Жизнь». В этом автомате, как и во всех, рассмотренных выше, клетки могут находиться в двух состояниях. Функция переходов клеток реализует следующие условия:

• если данная клетка мертва (находится в состоянии «ноль»), то она оживет (перейдет в состояние «единица») при условии, что у нее имеется ровно три живых соседа;

• если данная клетка жива, то она останется живой только при условии, что у нее есть два или три живых соседа и умрет в противном случае. В этой игре интерес представляет наблюдение за развитием популяции клеток при различных начальных условиях.

«Планер» был выбран в качества примера, так как является наиболее простым из «летающих» объектов. Он «летает» в том смысле, что перемещается за счет самовоспроизведения, происходящего с периодом в четыре шага.

Рис.2

Аналогичные игры можно вести и на бесконечных досках, клетки которых имеют форму равносторонних треугольников и правильных шестиугольников. Несмотря на сильное внешнее отличие, по существу эти игры не вносят ничего нового, и с помощью подходящего определения «соседних» клеток их всегда можно свести к эквивалентным играм на обычной доске с клетками в форме квадратов. Соседними могут быть не только клетки, имеющие общие стороны или вершины. Как заметил Беркс, такие игры, как шахматы, шашки и го, допустимо рассматривать как клеточные автоматы со сложными окрестностями каждой клетки (окрестностью называется совокупность соседей) и правилами перехода. Противники, делая очередной ход, выбирают среди множества допустимых состояний то, которое должно привести их к определённому конечному состоянию — выигрышу.

4. Применение клеточных автоматов.

Теория клеточных автоматов, связанная с именами фон Неймана и Конрада Цузе, имеет огромное значение для всей науки и многообразное прикладное применение. Клеточные автоматы с 80-х гг. используются в моделях физико-химических процессов, с 90-х гг. в гуманитарных науках, таких как урбанистика (толпа, транспортная пробка). Обзорная статья В. Ванага по вероятностным клеточным автоматам еще раз узаконила для отечественных исследователей клеточные автоматы как метод математического моделирования. Последнее десятилетие ознаменовалось бумом публикаций в самых разных разделах науки, связанных с клеточными автоматами; одновременно с этим продолжает развиваться и математическая теория клеточных автоматов. Теория клеточных автоматов имеет широкое применение, рассмотрим некоторые из них.

4.1.Влияние на развитие наук.

Игра, состоящая всего из двух простых правил, уже многие годы привлекает внимание ученых в самых различных областях. Игра «Жизнь» и ее модификации повлияла (в ряде случаев взаимно) на многие разделы таких точных наук как математика, информатика, физика. Это, в частности:

• Теория автоматов,

• Теория алгоритмов,

• Теория игр и математическое программирование,

• Алгебра и теория чисел,

• Теория вероятностей и математическая статистика,

• Комбинаторика и теория графов,

• Фрактальная геометрия,

• Вычислительная математика,

• Теория принятия решений,

• Математическое моделирование.

Кроме того, многие закономерности, обнаруженные в игре, имеют свои аналогии в других, подчас совершенно «нематематических» дисциплинах. Вот список наук, теории которых имеют интересные точки соприкосновения с феноменами «Жизни»:

• Кибернетика. Сама игра является удачной попыткой Конвея доказать существование простых самовоспроизводящихся систем.

• Биология. Внешнее сходство с развитием популяций примитивных организмов.

• Физиология. Рождение и смерть клеток аналогичны процессу возникновения и исчезновения нейронных импульсов, которые и формируют процесс мышления, а также аналогичны созданию импульсов в нервной системе многоклеточных организмов.

• Астрономия. Эволюции некоторых сложных колоний удивительным образом схематично повторяют этапы развития спиралевидных галактик.

• Физика твёрдого тела. Теория автоматов вообще и игра «Жизнь» в частности используются для анализа «явлений переноса» — диффузии, вязкости и теплопроводности.

• Наномеханика. Стационарные и пульсирующие колонии являются показательным примером простейших устройств, созданных на основе нанотехнологий.

• Электротехника. Правила игры используются для моделирования самовосстанавливающихся электрических цепей.

• Социология. Процессы доминации, вытеснения, поглощения, сосуществования, слияния и уничтожения популяций во многих аспектах схожи с явлениями, происходящими при взаимодействии больших, средних и малых социальных групп.

• Философия. Приведённый список примеров снова наводит на мысль, что всё во Вселенной развивается по одним и тем же нескольким фундаментальным законам, пока ещё не познанным человеком.

Вероятно, игра «Жизнь» и ее модификации связаны и с иными научными явлениями, даже возможно еще не известными в современное время. Также возможно, что не открытые на сегодня законы Природы и Общества станут более понятными благодаря данной игре.

1. 2. Применение клеточных автоматов для математического моделирования динамических процессов.

Наиболее частое и развитое направление применения клеточных автоматов — это математическое моделирование динамических процессов. При математическом моделировании физических явлений часто возникает ситуация, когда рассматриваемую задачу нельзя решить аналитически, а расчет ее в виде разностной схемы приводит к появлению различного рода неустойчивостей.

В процессе описания физического явления при помощи совокупности дифференциальных уравнений происходит замена физической реальности, часто носящей дискретный характер (молекулы в газодинамике, элементарные заряды в электричества и т. д.), непрерывной моделью. При переходе к разностным схемам пространство и время в этой непрерывной модели делаются вновь дискретными, а после реализации их на компьютере все величины рассматриваются с ограниченной точностью.

Заключение

В данной работе проведен обзор одномерных клеточных автоматов, а также разработка и реализация программы в среде разработки приложений на языке С++, при визуализации которой можно наблюдать динамику поведения дискретных динамических систем. В качестве примера приведены результаты реализации программы по правилам 161 и 250.

Таким образом, клеточные автоматы нашли и находят широкое применение во многих сферах человеческой деятельности, многие задачи которых стало возможным решить только с помощью компьютера. Они стали активно использоваться в сфере криптографии для получения новых алгоритмов шифрования информации. Автоматы введены в некоторых географических информационных системах (ГИС). С помощью них можно описывать поведение социальных групп, химических и физических процессов, применять клеточные автоматы в экологическом моделировании.

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

1. Тоффоли Т., Марголус Н. Машины клеточных автоматов. М.:Мир, 1991.280 с.

2. Астафьев Г., Короновский А. Клеточные автоматы. М.: Изд-во ГосУНЦ, 2003.24 с.

3. Антонова Л., Бурзалова Т., Данеев А. О моделировании клеточных автоматов в системе "MATHEMATICA" // Геометрия многообразий и ее приложения: материалы научной конференции с международным участием, Улан-Удэ - оз. Байкал, 18-21 июня 2014 г. - 2014. - С. 44-50.

4. Фон Нейман Дж. Теория самовоспроизводящихся автоматов.М.: Мир,1971.

5. Малинецкий Г., Степанцев М., Моделирование движения толпы при помощи клеточных автоматов.М.: Известия ВУЗов. 1997г.75с.

Текст программы:

#include <stdio.h>

#include

#include

const int count=61;

inline int TorIt(int x)

{

if (x<0) return x+count; else return x%count;

}

int f(int y1,int y2, int y3,int a1,int a2,int a3,int a4,int a5,int a6,int a7,int a8)

{

if (y1==1&&y2==1&&y3==1)

return a1;

if (y1==1&&y2==1&&y3==0)

return a2;

if (y1==1&&y2==0&&y3==1)

return a3;

if (y1==1&&y2==0&&y3==0)

return a4;

if (y1==0&&y2==1&&y3==1)

return a5;

if (y1==0&&y2==1&&y3==0)

return a6;

if (y1==0&&y2==0&&y3==1)

return a7;

if (y1==0&&y2==0&&y3==0)

return a8;

}

using namespace std;

int main()

{

setlocale(LC_ALL,"Russian");

int y[count],y1[count],i,a1,a2,a3,a4,a5,a6,a7,a8,j;

char c;

cout << "Введите правило:"<< endl;

cin >> a1>>a2>>a3>>a4>>a5>>a6>>a7>>a8;

for (i=0; i

{

y[i]=0;

}

y[30]=1;

for (i=0; i

{

for (i=0; i

cout << y[i];

cout<

for (j=0; j

{

for (i=0; i

{

y1[i]=f(y[TorIt(i-1)],y[TorIt(i)],y[TorIt(i+1)],a1,a2,a3,a4,a5,a6,a7,a8);

}

for (i=0; i

{

y[i]=y1[i];

cout << y[i];

}

cout <

}

}

system ("pause");

return 0;

}

Пример работы программы:

Правило 161(10100001)

Правило 250(11111010)

Правило 254(11111110)