Wróć do strony głównej.

Jednowymiarowe automaty komórkowe: diagramy kołowe

Wstęp: wszystko na tej stronie zainspirowane zostało tym projektem.

Założenie: Czytający tę stronę wie, czym jest elementarny automat komórkowy.

To, co napiszę teraz zabrzmi bardzo poważnie, ale tak naprawdę takie nie jest: przestrzeń stanów d-wymiarowego elementarnego automatu komórkowego (elementary cellular automaton, ECA) można interpretować jako podzbiór zbioru liczb naturalnych A = {1..2^d-1}. ECA przekształca A na samego siebie (w większości przykadów w siebie).

Takie przekształcenia można zaprezentować za pomocą swoistego diagramu kołowego — na obwodzie koła umieszczamy kolejne elementy zbioru A; przejście ze stanu a(t) = n, które jest liczbą naturalną, do stanu a(t+1) = m przedstawiane jest za pomocą wygiętej (bezierowsko) cięciwy. Poniżej widać przykładową „ewolucję” takiego diagramu.

Wraz z kolejnymi przekształceniami ECA na diagramie pojawiają się kolejne cięciwy.

Danie główne

Na niniejszym stronie — i jej podstronach — znajdziesz graficzne reprezentacje przejść między stanami dla każdej z 256 reguł ECA dla 1024-elementowej przestrzeni stanów. Stworzyłem trzy rodzaje diagramów, a na każdym umieściłem innego rodzaju informacje, o których parę słów w następnych akapitach.

Diagram „z”

Fragment diagramu z

Przestrzeń stanów automatu została podzielona na cztery części — czerwoną, niebieską, zieloną i pomarańczową. Na diagramie typu „z” kolor cięciwy-połączenia (1. na powyższym rysunku) odpowiada kolorowi ćwiartki, z której cięciwa wyszła w pierwszym pokoleniu (zatem kolor nie zmienia się podczas ewolucji automatu komórkowego — ćwiartka startowa pozostaje przecież taka sama). Kolor na pierścieniu 2. pozwala określić, do której ćwiartki zawędrował dany punkt z przestrzeni stanów po sześciu przekształceniach automatu, zaś heatmapa 3. obrazuje, jak często dany punkt z przestrzeni stanów był — znowu po sześciu przekształceniach — odwiedzany przez automat: im jaśniejszy prostokąt, tym częściej.

Diagram „do”

Fragment diagramu do

Diagram typu „do” zawiera podobne dane: tutaj jednak kolor połączenia odpowiada kolorowi ćwiartki, do której trafia dany element przestrzeni stanów automatu po sześciu pokoleniach. Z kolei heatmapy 5. pozwalają zorientować się, jak często dany punkt był odwiedzany z innych stanów początkowych (a mówiąc dokładniej: ćwiartek). Heatmapa 6. pokazuje dokładnie te same dane, co heatmapa 3. z diagramu „z”.

Diagram szary

Diagram szary zawiera dane prezentowane na obydwu powyższych typach diagramów. Połączenia rysowane są za pomocą koloru szarego (aczkolwiek: bardzo jasnego, czyt. prawie białego), stąd nazwa.

Tyle wstępu. Jeszcze tylko parę słów o narzędziach, za pomocą których stworzyłem diagramy.

Diagramy były generowane przez skrypt circos. Circos służy do wizualizacji danych (głównie genomu) za pomocą okręgu i cięciw, łączących dwa punkty z rzeczonego okręgu, o ile te punkty są ze sobą w jakiejś — wizualizowanej — relacji. Mnogość opcji narzędzia poraża, a jego autorem jest Marcin Krzywiński.

Do zasilenia Circos danymi wykorzystałem język programowaina Processing: napisany w nim program generował, dla każdej reguły ECA, pliki tekstowe, zawierające różne dane wejściowe. Trzy diagramy każdej reguły definiowany był za pomocą ośmiu plików tekstowych: pięciu heatmap i trzech plików z określonymi połączeniami (po jednym dla każdego rodzaju wykresu, miało to swoje uzasadnienie).

Samo generowanie diagramów było zautomatyzowane za pomocą pliku wsadowego BAT.

Ot, i tyle. Zapraszam do przeglądania wykresów:

Aha, gdyby ktoś był ciekawy i chciał wiedzieć, po co to wszystko — odpowiedź brzmi „bo mogłem” ;-)

Utworzone za pomocą txt2tags.

Ostatnia modyfikacja 26-09-2013.