Ознакомительный урок на тему Двумерные клеточные автоматы
Реализация двумерных клеточных автоматов
Выполнил:
Афанасьева.С.Д.
.
Улан-Удэ
2015
Содержание
ВВЕДЕНИЕ3
1 Понятие клеточных автоматов4
1.1 Основные свойства классической модели клеточных автоматов4
1.2 Классификация клеточных автоматов5
2 Одномерные клеточные автоматы6
3 Двумерные клеточные автоматы9
4 Применение клеточных автоматов11
4.1 Влияние на развитие наук11
4.2 Применение клеточных автоматов для математического моделирования динамических процессов12
Заключение14
Список использованной литературы15
Введение
Идея клеточных автоматов зародилась в 1940 - е годы. Ее независимо друг от друга разработали венгерско-американский математик Джон Фон Нейман и немецкий инженер Конрад Цусе. Сформулирована она была как универсальная вычислительная среда для построения, анализа и сравнения характеристик алгоритмов. Область применения клеточных автоматов огромна. Поэтому тема клеточных автоматов является очень актуальной, так как может помочь в разгадке многих вопросов окружающего мира.
Задача исследования – реализация двумерных клеточных автоматов в среде разработки приложений Visual Studio 2013 на языке С++.
Методы исследования. В работе применяются такие общенаучные методы исследования, как наблюдение, описание, анализ, эксперимент, индукция, дедукция и некоторые другие.
Понятие клеточных автоматов.
Автоматом называют устройство (или совокупность устройств), которое без непосредственного участия человека выполняет процессы приема, преобразования и передачи энергии, материалов или информации в соответствии с заложенной в него программой.
Клеточные автоматы являются частным случаем конечных автоматов, используемых для моделирования динамического поведения однородных сред. При этом пространство и время считаются дискретными, а физические величины в каждой точке моделируемой среды могут принимать конечное множество дискретных значений. Клеточные автоматы активно используются для моделирования сложных динамических систем.
1.1. Основные свойства классической модели клеточных автоматов:
Локальность правил. На новое состояние клетки могут влиять только элементы её окрестности и, возможно, она сама;
Однородность системы. Вся область решетки построена по одному правилу. Однако на практике решетка оказывается конечным множеством клеток (ведь невозможно выделить неограниченный объем данных). В результате могут иметь место краевые эффекты. Клетки, стоящие на границе решетки будут отличны от остальных по числу соседей;
Множество возможных состояний клетки — конечно. Это условие служит для того что бы проводилось конечное число операций.
Значения во всех клетках изменяются одновременно в каждой итерации. Иначе порядок перебора клеток в итерации приводил бы к значительному изменению результата.
Классификация клеточных автоматов
Классификация по типам поведения.
Стивен Вольфрам в своей книге «A New Kind of Science» предложил 4 класса, на которые все клеточные автоматы могут быть разделены в зависимости от типа их эволюции. Классификация Вольфрама была первой попыткой классифицировать сами правила, а не типы поведения правил по отдельности. В порядке возрастания сложности классы выглядят следующим образом:
Класс 1: Развитие происходит с конечным числом итераций до уникального однородного состояния, то есть до определенной точки.
Класс 2: Генерируются регулярные, периодические узоры, переходящие в предельный цикл.
Класс 3: структуры изменяются с определенным периодом, зависят от начальной конфигурации, их траектории лежат на хаотическом аттракторе.
Класс 4: В этот класс входят все клеточные автоматы, которые развиваются по сложным траекториям. Такие автоматы имеют возможность универсальных вычислений.
По утверждению Вольфрама эта классификация не совершенна, хотя и является основной и наиболее распространенной. Задача классификации правил по-прежнему остается открытой, о чем свидетельствуют проводимые исследования в динамических системах.
Существует много других типов клеточных автоматов: одномерные, двумерные и автоматы больших размерностей, детерминированные и стохастические, локальные и автоматы с глобальным параметром, статичные и подвижные и т.д.
Одномерные клеточные автоматы.
В одномерном (линейном) клеточном автомате решетка это последовательность клеток, то есть одномерный массив, в котором для каждой из них, кроме крайних, имеется по два «соседа». Три клетки (центральная, предыдущая, следующая) порождают 23 =8 комбинаций состояний этих трёх клеток. Всего существует 28 =256 возможных правил. Эти 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.
Правило 250(11111010)
Клеточный автомат выполняет правило: если хотя бы один из соседей клетки черный, то клетка становится черной, иначе клетка становится белой.
Рис.2
Правило 254(11111110)
Для этого автомата правило определяет, что клетка должна быть черной во всех случаях, когда она сама или хотя бы один из ее соседей окрашены в черный цвет.
Рис.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
Применение клеточных автоматов.
Теория клеточных автоматов, связанная с именами фон Неймана и Конрада Цузе, имеет огромное значение для всей науки и многообразное прикладное применение. Клеточные автоматы с 80-х гг. используются в моделях физико-химических процессов, с 90-х гг. в гуманитарных науках, таких как урбанистика (толпа, транспортная пробка). Обзорная статья В. Ванага по вероятностным клеточным автоматам еще раз узаконила для отечественных исследователей клеточные автоматы как метод математического моделирования. Теория клеточных автоматов имеет широкое применение, рассмотрим некоторые из них.
4.1.Влияние на развитие наук.
Игра, состоящая всего из двух простых правил, уже многие годы привлекает внимание ученых в самых различных областях. Игра «Жизнь» и ее модификации повлияла (в ряде случаев взаимно) на многие разделы таких точных наук как математика, информатика, физика. Это, в частности:
Теория автоматов,
Теория алгоритмов,
Теория игр и математическое программирование,
Теория вероятностей и математическая статистика,
Комбинаторика и теория графов,
Вычислительная математика,
Теория принятия решений,
Математическое моделирование.
Кроме того, многие закономерности, обнаруженные в игре, имеют свои аналогии в других, подчас совершенно «нематематических» дисциплинах. Вот список наук, теории которых имеют интересные точки соприкосновения с феноменами «Жизни»:
Кибернетика.
Биология.
Физиология.
Астрономия.
Физика твёрдого тела.
Наномеханика.
Электротехника.
Социология.
Вероятно, игра «Жизнь» и ее модификации связаны и с иными научными явлениями, даже возможно еще не известными в современное время. Также возможно, что не открытые на сегодня законы Природы и Общества станут более понятными благодаря данной игре.
Применение клеточных автоматов для математического моделирования динамических процессов.
Наиболее частое и развитое направление применения клеточных автоматов — это математическое моделирование динамических процессов. При математическом моделировании физических явлений часто возникает ситуация, когда рассматриваемую задачу нельзя решить аналитически, а расчет ее в виде разностной схемы приводит к появлению различного рода неустойчивостей.
В процессе описания физического явления при помощи совокупности дифференциальных уравнений происходит замена физической реальности, часто носящей дискретный характер (молекулы в газодинамике, элементарные заряды в электричества и т. д.), непрерывной моделью. При переходе к разностным схемам пространство и время в этой непрерывной модели делаются вновь дискретными, а после реализации их на компьютере все величины рассматриваются с ограниченной точностью.
Заключение
В данной работе проведен обзор двумерных клеточных автоматов, а также разработка и реализация программы в среде разработки приложений Visual Studio 2013 на языке С++. В качестве примера приведены результаты реализации программы «Жизнь» и реализация двумерного клеточного автомата с окрестностями Мура и Фон Неймана.
Таким образом, клеточные автоматы нашли и находят широкое применение во многих сферах человеческой деятельности, многие задачи которых стало возможным решить только с помощью компьютера. Они стали активно использоваться в сфере криптографии для получения новых алгоритмов шифрования информации. Автоматы введены в некоторых географических информационных системах (ГИС). С помощью них можно описывать поведение социальных групп, химических и физических процессов, применять клеточные автоматы в экологическом моделировании.
Список использованной литературы
Тоффоли Т., Марголус Н. Машины клеточных автоматов. М.:Мир, 1991.280 с.
Астафьев Г., Короновский А. Клеточные автоматы. М.: Изд-во ГосУНЦ, 2003.24 с.
Антонова Л., Бурзалова Т., Данеев А. О моделировании клеточных автоматов в системе "MATHEMATICA" // Геометрия многообразий и ее приложения: материалы научной конференции с международным участием, Улан-Удэ - оз. Байкал, 18-21 июня 2014 г. - 2014. - С. 44-50.
Фон Нейман Дж. Теория самовоспроизводящихся автоматов.М.: Мир,1971.
Малинецкий Г., Степанцев М., Моделирование движения толпы при помощи клеточных автоматов.М.: Известия ВУЗов. 1997г.75с.
Текст программы реализованного ранее одномерного клеточного автомата.
#include <stdio.h>
#include <clocale>
#include <iostream>
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<count; i++)
{
y[i]=0;
}
y[30]=1;
for (i=0; i<count; i++)
{
for (i=0; i<count; i++)
cout << y[i];
cout<<endl;
for (j=0; j<count; j++)
{
for (i=0; i<count; 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<count; i++)
{
y[i]=y1[i];
cout << y[i];
}
cout <<endl;
}
}
system ("pause");
return 0;
}
Текст программы:
Игра жизнь на примере «Планера»
#include <stdio.h>
#include <clocale>
#include <iostream>
const int count=23;
inline int TorIt(int x)
{
if (x<0) return x+count;
else return x%count;
}
int f(int y, int yU, int yUR, int yR, int yDR, int yD, int yDL, int yL, int yUL)
{
int i=yU+yUR+yR+yDR+yD+yDL+yL+yUL;
if (y==0 && i==3) return 1;
if (y==1 && (i==2 || i==3)) return 1;
return 0;
}
using namespace std;
int main()
{
setlocale(LC_ALL,"Russian");
int y[count][count],y1[count][count],i,j,iter=0,kol;
cout << "Игра жизнь на примере «Планера»:" << endl << "Введите количество итераций=";
cin >> kol;
cout << endl;
for (int i=0; i<count; i++)
for (int j=0; j<count; j++)
{
y[i][j]=0;
}
y[11][11]=1;
y[10][11]=1;
y[ 9][11]=1;
y[11][12]=1;
y[10][13]=1;
while(iter!=kol+1)
{
cout << endl << "Итерация:"<< iter << endl;
for(i=0; i<count; i++)
{
for (j=0; j<count; j++)
cout << y[i][j];
cout << "\n";
}
for (i=0; i<count; i++)
for (int j=0; j<count; j++)
{
y1[i][j]=f(y[TorIt(i)][TorIt(j)],
y[TorIt(i-1)][TorIt(j)],y[TorIt(i-1)][TorIt(j+1)],
y[TorIt(i)][TorIt(j+1)],y[TorIt(i+1)][TorIt(j+1)],
y[TorIt(i+1)][TorIt(j)],y[TorIt(i+1)][TorIt(j-1)],
y[TorIt(i)][TorIt(j-1)],y[TorIt(i-1)][TorIt(j-1)]);
}
for (i=0; i<count; i++)
for (int j=0; j<count; j++)
y[i][j]=y1[i][j];
iter++;
}
system ("pause");
return 0;
}
Текст программы:
Реализация двумерного клеточного автомата с окрестностью Мура
(пример фрактального поведения)
#include <stdio.h>
#include <clocale>
#include <iostream>
const int count=23;
inline int TorIt(int x)
{
if (x<0) return x+count;
else return x%count;
}
int f(int y, int yU, int yUR, int yR, int yDR, int yD, int yDL, int yL, int yUL)
{
int i=y^yU^yUR^yR^yDR^yD^yDL^yL^yUL;
return i;
}
using namespace std;
int main()
{
setlocale(LC_ALL,"Russian");
int y[count][count],y1[count][count],i,j,iter=0,kol;
cout << "Правило: сумма по модулю два от состояний всех соседей и самой клетки" << endl << "Введите количество итераций=";
cin >> kol;
cout << endl;
for (int i=0; i<count; i++)
for (int j=0; j<count; j++)
{
y[i][j]=0;
}
y[10][12]=1;
y[10][10]=1;
y[ 9][11]=1;
y[11][11]=1;
y[12][10]=1;
y[12][12]=1;
y[13][11]=1;
while(iter!=kol+1)
{
cout << endl << "Итерация:"<< iter << endl;
for(i=0; i<count; i++)
{
for (j=0; j<count; j++)
cout << y[i][j];
cout << "\n";
}
for (i=0; i<count; i++)
for (int j=0; j<count; j++)
{
y1[i][j]=f(y[TorIt(i)][TorIt(j)],
y[TorIt(i-1)][TorIt(j)],y[TorIt(i-1)][TorIt(j+1)],
y[TorIt(i)][TorIt(j+1)],y[TorIt(i+1)][TorIt(j+1)],
y[TorIt(i+1)][TorIt(j)],y[TorIt(i+1)][TorIt(j-1)],
y[TorIt(i)][TorIt(j-1)],y[TorIt(i-1)][TorIt(j-1)]);
}
for (i=0; i<count; i++)
for (int j=0; j<count; j++)
y[i][j]=y1[i][j];
iter++;
}
system ("pause");
return 0;
}
Текст программы:
Реализация двумерного клеточного автомата с окрестностью Фон Неймана
(пример фрактального поведения)
#include <stdio.h>
#include <clocale>
#include <iostream>
const int count=23;
inline int TorIt(int x)
{
if (x<0) return x+count;
else return x%count;
}
int f(int y, int yU, int yR, int yD, int yL)
{
int i=y^yU^yR^yD^yL;
return i;
}
using namespace std;
int main()
{
setlocale(LC_ALL,"Russian");
int y[count][count],y1[count][count],i,j,iter=0,kol;
cout << "Правило: сумма по модулю два от состояний всех соседей и самой клетки" << endl << "Введите количество итераций=";
cin >> kol;
cout << endl;
for (int i=0; i<count; i++)
for (int j=0; j<count; j++)
{
y[i][j]=0;
}
y[10][12]=1;
y[10][10]=1;
y[ 9][11]=1;
y[11][11]=1;
y[12][10]=1;
y[12][12]=1;
y[13][11]=1;
while(iter!=kol+1)
{
cout << endl << "Итерация:"<< iter << endl;
for(i=0; i<count; i++)
{
for (j=0; j<count; j++)
cout << y[i][j];
cout << "\n";
}
for (i=0; i<count; i++)
for (int j=0; j<count; j++)
{
y1[i][j]=f(y[TorIt(i)][TorIt(j)],
y[TorIt(i-1)][TorIt(j)],
y[TorIt(i)][TorIt(j+1)],
y[TorIt(i+1)][TorIt(j)],
y[TorIt(i)][TorIt(j-1)]);
}
for (i=0; i<count; i++)
for (int j=0; j<count; j++)
y[i][j]=y1[i][j];
iter++;
}
system ("pause");
return 0;
}
Реализация двумерного клеточного автомата с окрестностью Фон Неймана.
Сохранив функцию переходов предыдущего примера и выбрав в качестве начальной конфигурации одну клетку.