1 Automaty komórkowe Cellular Automata CA

2 automat komórkowy 1011 – liczba neuronów w organizmieliczba galaktyk we wszechświecie 6 * 1023 liczba Avogadra Otoczenie - duże zespoły wzajemnie oddziałujących elementów zmierzających do stanu równowagi Uproszczenia w symulacjach komputerowych charakter oddziaływań Ograniczenie oddziaływań do sąsiadów Gra w życie J.H. Conway 2D; periodyczne warunki brzegowe Elementy populacji – osobnicy – w węzłach siatki Reguły przetrwania, śmierci, generowania nowych osobników

3 CA Stanisław Ulam, lata 40 XX wStep Wolfram (twórca pakietu Mathematica) Struktura danych (tablica komórek) Algorytm Parametry: Typ komórki Stan początkowy Funkcja przejścia

4 Automat sprawiedliwy – niezależny od kierunku przeliczania komórek (kopia tablicy)sasiedztwo Sąsiedztwo Neumanna Sąsiedztwo Moore’a

5 Przykłady automatów komórkowychGra w życie Conway’s Game of Life prelokacja Ofiary i drapieżnicy Mrówka Langtona Symulacje fizyczne

6 Gra w życie - reguły Dla każdego elementu populacji:if ( 2<=liczba_sąsiadów<=3 ) element przeżywa 1 generację if ( liczba_sąsiadów >=4 ) element umiera //przeludnienie if ( liczba_sąsiadów <=1 ) element umiera //izolacja Dla każdego pustego pola: if ( liczba_sąsiadów = 3 ) tworzy się nowy element populacji w tym polu

7 Gra w życie reguły Życie i śmierć zachodzą równocześnie PrzesłankiNie istnieje konfiguracja pierwotna, dla której w prosty sposób można udowodnić, że rośnie ona w sposób nieograniczony Powinny istnieć konfiguracje pierwotne prowadzące do wzrostu bez granic znikające tworzące stabilną konfigurację wchodzące w nieskończone oscylacje

8 Gra w życie ak Efekt końcowy automatuStan stabilny Stan cyklicznie zmieniający się z niedużym okresem Stan chaotyczny Złożone, stabilne konfiguracje o długich okresach Życie – równoważne maszynie Turinga

9 Gra w życie reguły - zastosowaniaModel formowania opinii społecznej „warszawski” „wrocławski” Symulacja rozchodzenia się choroby zakaźnej Model Isinga CA + GA Badanie gęstości upakowania kulek w polach

10 Model formowania opinii społecznejStany: tak, nie si,j = -1 lub 1 Wartość początkowa – np. 80% populacji – tak; 20% - nie Opinie rozrzucone losowo Przeprowadzenie rund dyskusyjnych – wymiana z innymi członkami populacji (sąsiedzi –odległość emocjonalna), siła przekonywania fi,j – siła przekonywania Dynamika układu – opisana regułą większości S=f0,0s0,0(t) + f0,1s0,1(t) + f1,0s1,0(t) + f0,-1s0,-1(t) + f-1, 0s-1,0(t) 0,0 0,1 1,0 -1,0 0,-1 S0,0 = +1, jeśli S>=0 S0,0 = -1, jeśli S<0

11 Model formowania opinii społecznejInny sposób wyboru sąsiadów , np. losowy, dla zadanego zasięgu, proporcjonalny do odległości Szumy Znając dynamikę zmian pojedynczego osobnika – obserwacja zmian rozkładu opinii Tworzenie grup wokół przywódców (osoby o mocnym wpływie) Tworzenie wałów ochronnych (słabsi osobnicy za murem osobników silniejszych) Rozwój „grup oporu”

12 Model wrocławski Bazuje na obserwacji zachowań stadnychJedna silnie skorelowana (to samo zdanie na pewien temat) para potrafi narzucić swoje zdanie sąsiadom Jeśli para ma różne zdania – otoczenie nie zmienia poglądów

13 Rozchodzenie się choroby zakaźnejObszar N x N; rozmieszczenie osobników w polach Periodyczne warunki brzegowe lub nie Szczepienie – wśród losowo wybranej grupy 1 losowo wybrany niezaszczepiony osobnik – źródłem choroby V=liczba_osób_zaszczepionych/liczność_populacji Nz – liczba osób niezaszczepionych Zk- liczba osób zakażonych (spośród Nz) I – wskaźnik infekcji I=Zk/Nz < 1 I(V) – funkcja malejąca Istnieje Vc – wskaźnik infekcji gwałtownie maleje

14 Model Isinga Badanie magnetycznych własności ciałN spinów w węzłach siatki 2D Spiny oddziałują z sąsiadami i zewnętrznym polem magnetycznym Stany spinów: dół -1; góra 1 Cel – minimum energii układu Metoda Metropolisa

15 prelokacja Symulacja pożaru lasuSzybkość i kierunek wiatru Wilgotność powietrza i poszycia Odległość między drzewami Istnienie i rozmiary przecinek Rozmieszczenie ognisk zapalnych Pudełko z kulkami przewodnikami i izolatorami umieszczonymi w dwóch przeciwnych ściankach; po przyłożeniu napięcia – prąd popłynie jeśli utworzy się prelokujący klaster (przy powolnym wzroście liczby przewodników - gwałtowne przejście do stanu przewodnictwa) Poszukiwanie ropy naftowej, wody – cechy porowatych skał

16 Algorytm prelokacji węzłowejTablica zajętości Wypełniona losowo z prawdopodobieństwem p „1” lub „0” Wektor pamięci ME Etykiety – kolejne liczby całkowite (numer klastra) Przeglądanie tablicy zajętości wierszami, nadając etykiety elementom zajętym; elementowi, który ma sąsiadów (po lewej stronie i powyżej (i-1,j); (i,j-1) przyporządkowana jest najniższa z etykiet sąsiadów (y) Ustawienie wektora pamięci ME(x)=y; x,y – etykiety; x>y Uzgadnianie kilkustopniowe – zastąpienie etykiet z wektora ME ( od największej wartości ) x->y

17 Etykietowanie elementów -sąsiedztwo1 2 3 Element badany sąsiedzi

18 prelokacja 1 1 2 3 4 5 6 7 8 ME(3)=2 ME(6)=4 ME(4)=3 6 -> 43 -> 2 4 -> 3 1 2 5 7 8 1 2 3 4 5 7 8 1 2 3 5 7 8

19 Kropla spadająca na wietrzeKropla przesuwa się między węzłami sieci pod wpływem siły ciężkości i wiatru Cel – określenie średniej wartości dryftu (xk-x0) Parametry symulacji: x0, y0 – punkt początkowy δ x = δy – odległości między współrzędnymi węzłów p1, p2, p3, p4 - prawdopodobieństwa ruchu w 4 kierunkach p1+ p2+ p3+ p4 = 1 Liczba symulacji Kryterium stopu pojedynczej symulacji – yk= 0

20 Kropla spadająca na wietrzeReguły poruszania się po sieci (xi,yi) : Wylosuj r rzeczywiste є(0,1) if (r <= p1) (xi,yj) -> (xi+1,yi) → if (r >= p1 && r < p1+p2 ) (xi,yi) -> (xi,yi-1) ↑ if (r >= p1+p2 && r < p1+p2 +p3 ) (xi,yj) -> (xi-1,yi) ← if (r >= p1+p2+p3 && r < 1 ) (xi,yj) -> (xi,yi+1) ↓

21 Kropla spadająca na wietrze→ ↑ ← ↓ y0 yk =0 x0 xk

22 Ruchy Browna Brown 1827, Einstein 1905, Smoluchowski 1906Ruchy małych cząstek zawiesiny w sieci Wyznaczenie położenia cząstki zawiesiny w chwili t=0, Δt, 2Δt, 3Δt,…. oraz Δxi, Δyi Badanie średniej wartości kwadratu przesunięcia wraz z upływem czasu (liczba kroków)

23 Ruchy Browna śr_wartość_kwadratu_x(liczba kroków)- zależność liniowaśr_wartość_kwadratu_y(liczba kroków)- zależność liniowa

24 Ruchy Browna Nachylenie prostejDla gazów - 2D; D – współczynnik dyfuzji D=kT/(6πηr) k - stała Boltzmanna T – temperatura η współczynnik lepkości r – promień cząstki

25 Mrówka Langtona Langton’s Ant Pamiętane parametry:Bieżąca pozycja (x, y) Kierunek ( 1 z 8 lub 1 z 4 ) W każdej iteracji przeliczana jedna komórka Modyfikacja komórki (P(x,y)=T/F) Modyfikacja kierunku przesunięcie o jedno pole Np.: if (P(x,y)) zmień kierunek o 900 w lewo; else zmień kierunek o 900 w prawo; P(x,y)=~P(x,y); Move (o 1 pole w zadanym kierunku) Po kroków – tablica nieuporządkowana ak

26 Wyliczanie kolejnych wierszy tablicy na podstawie poprzednich – generacja fraktaliSierpińskiego Zaznaczenie nieparzystych liczb w trójkącie Pascala Stan komórki – na podstawie dwóch komórek powyżej ( p + p -> p; p +np. -> np.; np. +np. ->p) ak

27 Symulacje fizyczne Komórki – wycinek zdyskretyzowanej przestrzeniIteracje – dyskretny czas Nowa wartość komórki zależy od poprzedniej i sąsiadujących Rozkład ciśnienia Rozchodzenie się fal na wodzie Wiatr Podobne wyniki przy sąsiedztwie 4, 8, 12 AK-fale, wiatr plamy piasek gaz

28 L-systemy (systemy Lindenmayera)1986 r – biolog, Aristid Lindenmayer Modelowanie biologicznego wzrostu Tworzenie grafiki komputerowej przedstawiającej rośliny, krzewy, drzewa Technika przepisywania: zastępowanie części początkowego ciągu znaków (aksjomatu) zgodnie z ustalonymi regułami (produkcjami)

29 Rodzaje L-systemów Deterministyczne bezkontekstowe Stochastyczneparametryczne

30 L-systemy deterministyczne, bezkontekstoweUstalone słowo początkowe (aksjomat) Zbiór reguł (produkcji) a→א א – słowo Przykład: ω: b p1: a→ab p2: b→a b→a→ab→aba→abaab→abaababa→abaababaabaab

31 L-systemy stochastyczneProdukcje z pewnym prawdopodobieństwem a→(P)א Przykład: ω: F p1: F→(0.33) F [+F] F [-F] F p2: F→(0.33) F [+F] F p3: F→(0.34) F [-F] F F – krok do przodu + rysowanie linii [ - zapisz na stosie stan ] – zdejmij stan z stosu

32 L-systemy kontekstoweProdukcja stosowana, gdy zgadza się kontekst (prawy, lewy lub oba) 2L-systemy al. ar → א 1L-systemy al. a> ar → א Przykład: ω: baaaa p1: b< a → b p2: b → a baaaa → abaaa → aabaa → aaaba → aaaab →aaaaa

33 L-systemy parametryczneProdukcja: A(t) : t > 5 → B(t+1)CD(t*0.5, t-2) Symbol A ma 1 parametr – t if ( t>5 ) A zamienione jest na …… Domyślna produkcja: a → a Przykład: ω: B(2)A(4,4) p1: A(x,y) : y<=3 → A(x*2,x+y) p2: A(x,y) : y>3 → B(x)A(x/y,0) p3: B(x) : x<1 → C p4: B(x) : x>=1 → B(x-1) B(2)A(4,4) → B(1)B(4)A(1,0) → B(0)B(3)A(2,1) → CB(2)A(4,3) → CB(1)A(8,7) → CB(0)B(8)A(8/7,0) → CCB(7)A(16/7,8/7) → ….

34 Interpretacja ciągów znaków - żółwStan żółwia: (x,y,C) x,y –położenie α – kierunek Dane: krok = d zmiana kąta = β Ciąg znaków – komenda: F – krok do przodu o d w kierunku α z rysowaniem linii f – krok do przodu bez rysowania linii + – skręt w lewo o β - – skręt w prawo o β

35

36 Kwadratowa wyspa Kochaω: F-F-F-F p1: F → F – F + F + FF – F – F + F F – krok do przodu o d + – skręt w lewo o 900 - – skręt w prawo o 900 n=0 n=1

37 Wyspy Kocha

38 F – krok do przodu + rysowanie linii[ - zapisz na stosie stan ] – zdejmij stan z stosu

39

40 liście

41