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

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

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

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

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

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

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

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

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

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

  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