ЛР. Клеточные автоматы

Post date: Sep 14, 2010 6:56:35 AM

Спасибо Валентине Кустиковой за идею :)

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

Описание клеточных автоматов: Г.Б. Астафьев, А.А. Короновский, А.Е. Храмов. Клеточные автоматы.

Достаточно подробное описание клеточного автомата: Л. Наумов, А. Шалыто. Клеточные автоматы. Реализация и эксперименты.

Продолжении предыдущей статьи: Л. Наумов, А. Шалыто. «Цветные» клеточные автоматы, или клонирование Мона Лизы.

Описание игры "Жизнь", правила и примеры: В. Скляр. "Жизнь" Конвея.

Применимость и примеры клеточных автоматов (последняя ссылка особенно интересна :) ):

• А. Б. Беланков, В. Ю. Столбов. Применение клеточных автоматов для моделирования микроструктуры материала при кристаллизации.
• Моделирование мембраны:
  • Simple membranes;
  • Mobile membranes;
  • Spiney membranes.
• Cамовоспроизводящиеся клеточные автоматы:
  • HAL;
  • Crystal 1D;
  • Crystal 2D.
• Картина интерференции.
• Эволюция размножения.
• Т. Мисютина. Гидродинамика сперматозоида морского ежа.

Постановка задачи:

1. Реализовать визуальное приложение, представляющее клеточный автомат. Поле для игры - прямоугольник, замкнутый на себе (по вертикали и горизонтали).
2. Программа должна позволять задавать размер поля (значение по умолчанию: 20x20), время задержки между итерациями в мс (значение по умолчанию: 1000), тип клеточного автомата (значение по умолчанию: игра "Жизнь").
3. Программа должна выводить количество выполненных итераций и текущее состояние автомата.
4. Программа должна позволять генерировать начальную конфигурацию случайным образом и задавать конфигурацию с помощью мыши (конфигурация по умолчанию должна быть такой).
5. В программе должны быть реализованы следующие типы клеточных автоматов:
   • Игра "Жизнь".
   • Автомат с окрестностью фон Неймана (ищите свою фамилию в списке, порядковый номер - соответствует формуле ниже):
6. y*[i,j] = y[i,j] ^ y[i-1,j] ^ y[i+1,j] ^ y[i,j-1] ^ y[i,j+1]
7. y*[i,j] = y[i,j] ^ ( y[i-1,j] & y[i+1,j] ) ^ ( y[i,j-1] & y[i,j+1] )
8. y*[i,j] = y[i,j] ^ ( ( y[i-1,j] & y[i+1,j] ) | ( y[i,j-1] & y[i,j+1] ) )
9. y*[i,j] = y[i,j] ^ ( ( y[i-1,j] ^ y[i+1,j] ) | ( y[i,j-1] ^ y[i,j+1] ) )
10. y*[i,j] = y[i,j] | ( y[i-1,j] ^ y[i+1,j] ^ y[i,j-1] ^ y[i,j+1] )
11. y*[i,j] = y[i,j] ^ ( y[i-1,j] | y[i+1,j] ) ^ ( y[i,j-1] | y[i,j+1] )
12. y*[i,j] = y[i,j] ^ ( ( y[i-1,j] | y[i+1,j] ) & ( y[i,j-1] | y[i,j+1] ) )
13. y*[i,j] = y[i,j] ^ ( ( y[i-1,j] ^ y[i+1,j] ) & ( y[i,j-1] ^ y[i,j+1] ) )
14. y*[i,j] = y[i-1,j] ^ y[i+1,j] ^ y[i,j-1] ^ y[i,j+1]
15. y*[i,j] = ( y[i-1,j] & y[i+1,j] ) ^ ( y[i,j-1] & y[i,j+1] )
16. y*[i,j] = ( ( y[i-1,j] & y[i+1,j] ) | ( y[i,j-1] & y[i,j+1] ) )
17. y*[i,j] = ( ( y[i-1,j] ^ y[i+1,j] ) | ( y[i,j-1] ^ y[i,j+1] ) )
    • Автомат с окрестностью Мура:

y**[i,j] = y*[i,j] ^ y[i+1,j+1] ^ y[i+1,j-1] ^ y[i-1,j+1] ^ y[i-1,j-1], где y*[i,j] - формула из предыдущего пункта.

• Автомат с окрестностью Мвона:

y***[i,j] = y**[i,j] ^ y[i+2,j] ^ y[i-2,j] ^ y[i,j+2] ^ y[i,j-2], где y**[i,j] - формула из предыдущего пункта.

Например, для студента, соответствующего 7-ому номеру в списке, необходимо реализовать автоматы со следующими формулами:

y*[i,j] = y[i,j] ^ ( ( y[i-1,j] | y[i+1,j] ) & ( y[i,j-1] | y[i,j+1] ) )

y**[i,j] = y[i,j] ^ ( ( y[i-1,j] | y[i+1,j] ) & ( y[i,j-1] | y[i,j+1] ) ) ^ y[i+1,j+1] ^ y[i+1,j-1] ^ y[i-1,j+1] ^ y[i-1,j-1]

y***[i,j] = y[i,j] ^ ( ( y[i-1,j] | y[i+1,j] ) & ( y[i,j-1] | y[i,j+1] ) ) ^ y[i+1,j+1] ^ y[i+1,j-1] ^ y[i-1,j+1] ^ y[i-1,j-1] ^ y[i+2,j] ^ y[i-2,j] ^ y[i,j+2] ^ y[i,j-2]

На выполнение лабораторной работы отводится 4 недели.

Dead Line: 23:59 11.10.2010