Файл для печти в MS Word   ( hw1.zip    43 KB)

Общая теория

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

Хорошим примером для ознакомления с принципами работы клеточного автомата является игра Джона Хортона Конвея "Жизнь".

Общие правила построения клеточных автоматов можно сформулировать следующим образом:

1. Состояние клеток дискретно (обычно 0 и 1, хотя могут быть автоматы и с большим числом состояний). 
2. Соседями являются ограниченное число клеток, часто это ближайшие клетки. 
3. Правила, задающие динамику развития клеточного автомата, обычно имеют простую функциональную форму и зависят от решаемой проблемы. 
4. Клеточный автомат является тактируемой системой, т.е. смена состояний клеток происходит одновременно. 

основе или решать с их помощью самые разнообразные задачи:

• моделирование химических и физических процессов, 
• проведение исследований по "Искусственной жизни" (Artificial Life) 
• исследование биологических процессов 
• моделирование распространения слухов 

(http://www.island-formoza.ru/tech_bred/index.html)
• и т.д. 

Клеточные автоматы различаются, в частности, количеством состояний клеток, размерностью сетки и правилом изменения состояний клеток. Мы рассмотрим некоторые разновидности автоматов с двумерной сеткой.

В двумерных автоматах соседями клеток обычно считаются 5 клеток – сама клетка и 4 ее непосредственных не диагональных соседа, или 9 клеток – сама клетка и 8 ее непосредственных соседей, включая диагональные клетки.

Представление состояния двумерного клеточного автомата

Состояние клеточного автомата может быть описано матрицей:

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

Конкретные примеры автоматов

Простейшие автоматы

Рассмотрим разновидности автоматов, задаваемые различными правилами изменения состояний и различным числом состояний клетки.

1. “Ортогональный автомат” 

Автомат с клетками, имеющими 2 состояния (0, 1).
Правило изменения – клетка становиться единицей, если один и только один из ее четырех непосредственных соседей единица. Клетка ставшая единицей никогда не становиться нулем (нет смерти).

= 1, если или = 1

2. “Ортогонально-диагональный автомат” 

Автомат с клетками, имеющими 2 состояния (0, 1).

Правило изменения – клетка “оживет” если:

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

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

или 

и затем, внеся “дефект” (инвертировав одну или несколько клеток), следить за преобразованием рисунка.
 
 

3. “Автомат Фредкина” 

Автомат с клетками, имеющими 2 состояния (0, 1).

Правило изменения – клетка “живет”, если сумма состояний соседей (+ свое) есть нечетное число.

, если , иначе

= 0

Данный автомат имеет интересное свойство – многократно копировать начальную конфигурацию через определенное число шагов.

Более сложные автоматы

4. Автоматы из серии “Поколения”. 

 

 
 
 

Автоматы с числом состояний более чем два.
Правила изменений состояния клетки записываются следующим образом

S/B/C

где:
S – набор цифр от 0 до 8, определяет число “живых” соседей, при котором клетка остается “в живых”,
B – набор цифр от 0 до 8, определяет число “живых” соседей при котором “рождается” новая клетка
С – число, определяет число ходов “умирания” клетки

Например - 23/3/14

Означает, что клетка живет, если у нее 2 или 3 соседа,
что при ровно трех соседях “рождается” новая клетка, и
что клетка умирает за четырнадцать ходов.

Если число “живых” соседей у клетки не равняется ни одной из цифр из набора S, клетка начинает “умирать” и ее состояние увеличивается с каждым ходом, пока не достигнет C, после чего клетка пропадает. “Умирающая” клетка не участвует в подсчете числа “живых” соседей при расчете следующего шага. При рождении клетка получает первое состояние.


---


 

“Фейерверк”
2/13/21

Пример конфигурации:

Требуется реализовать: два или три описанных простейших автомата (напр. ортогональный и Фредкина), либо один из сложных. Программа должна выводить на экран монохромное или цветное изображение состояния автомата. Необходимо, чтобы сетка автомата была достаточно велика, как минимум 200х200 клеток. Желательно, чтобы программа могла показать эволюцию автомата (особенно для сложных автоматов), но можно выводить и только n-ый (вводимый пользователем) шаг. Также желательно предоставить возможность пользователю задавать начальную конфигурацию автомата, или же просто предоставить набор нескольких начальных состояний. Удобство интерфейса и красота вывода данных учитываются.

Присылать задания по e-mail: assign1@graphics.cs.msu.su в следующем виде:
.zip файл с именем, построенным следующим образом:

имя начинается с цифры - это последняя цифра в номере вашей группы (например, если у вас 206 группа, то название файла будет начинаться с цифры 6), дальше первые три буквы вашей фамилии (латинским шрифтом), далее - знак подчеркивания и три первые буквы имени (латинским шрифтом)
Пример: Иванов Андрей из 202 группы должен прислать нам .zip файл с именем: 2iva_and.zip

Теперь о том, какие файлы должен содержать ваш .zip - файл

1. исходники 
2. *.exe 
3. файл readme (что работает, что не работает, что дополнительно реализовано и т.п., на какой платформе и на каком ПО программа написана и оттестирована) 

Работа оценивается, исходя из 7 баллов.
 

8 февраля 2000 года