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.

9 thoughts on “ONA – Zadanie 1 – Automaty komórkowe”

  1. Jak wyglądałby przykładowy input dla naszego programu?
    Czy program może przyjmować parametry przez funkcję input(), czy powinno się to odbywać z linii komend?

  2. Raczej zniechęcałbym do użycia input().
    Najlepiej podawać argumenty przy pomocy modułu argparse jako pliki do wczytania.

      1. Podstawowa wersja to Macierze M, S, E wplikach wejsciowych i liczba kroków. Wyjście może być do jakiegoś domyślnego pliku, ale oczywiście może być podane. Można też rozważyć opcję, że zamiast macierzy M podajemy rozmiar tej macierzy i prawdopodobieństwo żywej komórki i program generuje nam losowy stan początkowy.

  3. Ja też mam pytania do inputu:

    1. Macierz M podana jest jako macierz (tak wynika z komentarza), a nie jako dwa osobne argumenty – wektor i wymiary (tak wynika z tekstu zadania)?

    2. Jak wygląda ‘plik z macierzą’? Dla takiej na przykład macierzy sąsiedztwa opisanej w treści w zawartości pliku jest:

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

    b) np.array([[1,1,1],[1,10,1],[1,1,1]])

    c) [[1,1,1],[1,10,1],[1,1,1]]

    czy jeszcze coś innego?

    1. O zapisywaniu i wczytywaniu macierzy było na wykładzie 2. są metody np.load() i np.save(). Co do macierzy M, domyślnie powinni Państwo obsłużyć macierz w postaci pliku do załadowania przy pomocy np.load(). Ale jeśli ktoś chce, to może także podać wymiary i wylosować sobie macierz M o takich wymiarach. Nie jest to obowiązkowe, ale pewnie urozmaici Państwu pracę.

  4. Mam pytanie do zapisu macierzy i obrazka do pliku.
    Czy mamy zapisywać jedynie obrazek i macierz opisującą stan końcowy, czy włącznie z macierzami przedstawiające stany pośrednie programu?

    1. Obie opcje są OK. Nie było to wyszczególnione w opisie, więc mogą Państwo zadecydować wedle uznania.

Leave a Reply

Your email address will not be published. Required fields are marked *