ONA – Zadanie 1 – Automaty komórkowe

Naszym pierwszym zadaniem zaliczeniowym będzie napisanie programu umożliwiającego symulację automatów komórkowych, czyli pewnych obiektów matematycznych, które wymyślił w latach 40tych XX wieku Stanisław Ulam.

Automat komórkowy będzie dla nas strukturą macierzową (najczęsciej opartą na dwuwymiarowych macierzach), która składa się ze:

• stanu automatu, t.j. macierzy o zadanych wymiarach i wartościach całkowitych (zwykle tylko 0,1)
• regułach ewolucji stanu automatu, t.j określenie sąsiedztwa w macierzy oraz zależności wartości w komórce w kroku t+1 od wartości sąsiadów w kroku t.

Dobrym przykładem automatu komórkowego jest gra w życie pomysłu Johna Conway’a. Reguły gry są następujące:

• Rozważamy automaty mające wartości 0 (martwa komórka) lub 1 (żywa komórka) w każdej z komórek macierzy prostokątnej MxN
• Rozważamy sąsiedztwo Moore’a, czyli każda komórka (poza brzegowymi) ma 8 sąsiadów.
• Mamy następujące reguły ewolucji automatu:
  – Jeśli komórka jest żywa w kroku t, to pozostaje żywa w kroku t+1, jeśli ma 2 lub 3 żywych sąsiadów (w p.p. umiera w kroku t+1)
  – jeśli komórka jest martwa w kroku t, to pozostaje martwa w kroku t+1, chyba, że ma dokładnie 3 żywych sąsiadów.

Całkiem ładną symulację takich systemów można zobaczyć na tej stronie internetowej

W naszym przypadku będziemy reprezentować sąsiedztwo jako macierze wag, czyli macierze kwadratowe nieparzystego rozmiaru (najczęściej 3×3). A reguły ewolucji jako wektory. Np. dla naszego przykładu gry w życie możemy rozważyć macierz sąsiedztwa:

S=np.array([[1,1,1],[1,10,1],[1,1,1]])

a regułę ewolucji zapisać jako:

E= np.zeros((18,),dtype=int8)
E[3]=1
E[12]=1
E[13]=1

Wtedy możemy wyliczyć nową wartość stanu w macierzy na pozycji M[i,j] (dla wszystkich “wewnętrznych” i,j, jako:

N[i,j]=E[np.sum(M[i-1:i+2,j-1:j+2]*S)]

Nasze zadanie będzie następujące:

Napisać program, który pobiera jako parametry:

• rozmiar stanu automatu w postaci wektora
• macierz wag w postaci macierzy do załadowania przez np.load()
• wektor reguł ewolucji
• Inicjalny stan macierzy stanu
• liczbę kroków symulacji do wykonania.

Następnie program wykonuje taką symulację i zapisuje wyniki jako macierze, obrazki lub animację.

Punktacja:

• Wczytywanie parametrów i wykonywanie symulacji, zapis macierzy i/lub obrazka do pliku – 6 pkt
• Przedstawienie wyników w animacji matplotlib (4 pkt) (API animacji tutaj)
• rozważenie automatów więcej niż 2 wymiarowych (2 pkt) (Przykład np. na youtube)

Zadania trzeba wysłać (w postaci jednego, nieskompresowanego, pliku .py ze źródłami programu wyposażonymi w komentarze umożliwiające zrozumienie kodu) na mój adres e-mail, z dopiskiem [ONA-1-2019] w tytule maila. Zadania przyjmuję do 25. marca do 8:00 rano. Potem można oddać z 50% bonifikatą punktów do początku sesji egzaminacyjnej.