ca.pdf

(10716 KB) Pobierz
lima_malarz3a.eps
Automaty komórkowe
v. 2.7182818284590452353
Krzysztof Malarz
Niniejsze opracowanie “Notatek do wykładu z automatów komórkowych” jest prywatną wła
snościąKrzysztofaMalarzaiwykorzystywanejest wyłączniedla celów dydaktycznych . Publi
kowanie bądź dalsza jego dystrybucja naruszy prawa autorskie osób trzecich.
Wszelkie uwagi, pytania czy informacje o zauważonych błędach proszę kierować na adres
<malarz@agh.edu.pl>.
Podziękowania. ChciałbympodziękowaćKrzysztofowiKułakowskiemuzawprowadzeniemnie
wtematykębędącąprzedmiotemniniejszegowykładuinieustannąpomocwjegoprzygotowaniu
i prowadzeniu oraz udostępnienie prywatnych notatek.
Podziękowania należą się również moim Koleżankom i Kolegom z ZIS WFiIS AGH: Mał
gorzacie Krawczyk, Pawłowi Paściakowi, Tomaszowi Sitkowskiemu i Maciejowi Wołoszynowi,
którzy udostępnili wyniki swoich prac oraz rysunki do rozdziałów 11, 15 i 17.
Dziękuję również B. Jagodzie i P. Bialicowi z Instytutu Chemii UJ za udostępnieniu swoich
prac magisterskich wykorzystanychw rozdziale 18.
Skład komputerowy systemem L A T E X2 ε .
Spis treści
I Teoria
7
1 Wstęp 8
1.1 Czym są automaty komórkowe (AK)? . . . . . . . . . . . . . . . . . . . 8
1.2 Trochę historii . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
1.3 Literatura . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
2 Skala trudności 10
2.1 Maszyna Turinga . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
2.2 Twierdzenie Godla . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
3 Definicje i inne kłamstwa 12
3.1 Life Conwaya . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
3.2 Najprostsza notacja . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
3.3 Elementarne AK . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
3.3.1 Legalne AK . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
3.3.2 Automaty głosujące . . . . . . . . . . . . . . . . . . . . . . . . . 16
4 Klasyfikacja AK 17
4.1 Klasyfikacja na podstawie obserwacji . . . . . . . . . . . . . . . . . . . . 17
4.1.1 Klasyfikacja Wolframa . . . . . . . . . . . . . . . . . . . . . . . . 21
4.1.2 Diagramy de Bruijna . . . . . . . . . . . . . . . . . . . . . . . . . 23
4.2 Klasyfikacja na podstawie reguł . . . . . . . . . . . . . . . . . . . . . . . 25
4.2.1 Metody średniego pola . . . . . . . . . . . . . . . . . . . . . . . . 26
4.2.1.1 Aktywność AK . . . . . . . . . . . . . . . . . . . . . . . 26
4.2.1.2 Stabilność rozwiązań równania iteracyjnego . . . . . . . 26
4.2.1.3 Równania ewolucji . . . . . . . . . . . . . . . . . . . . . 27
4.3 Teoria struktury lokalnej . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
4.4 Szybkość rozprzestrzeniania się różnic . . . . . . . . . . . . . . . . . . . 32
5 Odwracalność 35
5.1 Przykład: (2,1/2) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
5.2 Rajski ogród . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
5.2.1 Przykład: Life . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
5.3 Symetria T . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
6 Liniowość i iniektywność AK 39
6.1 Iniektywność . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
6.2 Sekwencje aperiodyczne . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
2
http://www.zis.agh.edu.pl/ak/
7 Pochodna dyskretna 42
7.1 Zapis odwzorowań na zbiorach skończonych . . . . . . . . . . . . . . . . 42
7.2 Boole’owska odległość wektorowa . . . . . . . . . . . . . . . . . . . . . . 45
7.3 Pochodna Boole’a . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
8 Model odwzorowań przypadkowych 48
8.1 Średnia długość cyklu . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48
8.2 Model Kauffmana . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49
9 Samozorganizowany stan krytyczny 51
9.1 SOC w piasku . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51
9.2 SOC w Life . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52
II Zastosowania
55
10 AK w biofizyce: model Penny 56
10.1 Parametry kontrolne modelu . . . . . . . . . . . . . . . . . . . . . . . . 56
10.2 Algorytm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57
10.3 Charakterystyka populacji . . . . . . . . . . . . . . . . . . . . . . . . . . 58
10.4 Kilka (o‘kay — kilkanaście) przykładów zastosowań . . . . . . . . . . . . 59
10.4.1 Wpływ parametrów modelu na liczebność populacji . . . . . . . 59
10.4.2 Groźba wyginięcia . . . . . . . . . . . . . . . . . . . . . . . . . . 63
10.4.3 Ciśnienie ewolucyjne . . . . . . . . . . . . . . . . . . . . . . . . . 66
10.4.4 “Katastrofa dojrzałości” . . . . . . . . . . . . . . . . . . . . . . . 67
10.4.5 Polowanie/odławianie/wojny . . . . . . . . . . . . . . . . . . . . 68
10.4.6 Poza partenogenezę . . . . . . . . . . . . . . . . . . . . . . . . . 69
10.4.7 Dlaczego Natura wynalazła płeć? . . . . . . . . . . . . . . . . . . 70
10.4.8 Dlaczego kobiety żyją dłużej? . . . . . . . . . . . . . . . . . . . . 72
10.4.9 Dlaczego wśród niektórych gatunków ssaków pojawia się meno
pauza u samic? . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75
10.4.10 Wierność czy rozwiązłość? . . . . . . . . . . . . . . . . . . . . . . 75
10.4.11 Czy długowieczność jest dziedziczna? . . . . . . . . . . . . . . . . 76
10.4.12 Współzawodnictwo: ofiara (1) i drapieżnik (2) . . . . . . . . . . 77
10.4.13 Dlaczego drzewa żyją dłużej? . . . . . . . . . . . . . . . . . . . . 78
10.4.14 Inne próby zastosowania . . . . . . . . . . . . . . . . . . . . . . . 79
11 AK w fizyce magnetyzmu: model Isinga 80
11.1 Dowód Derridy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81
11.2 Metody Monte Carlo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82
11.2.1 Metody obliczeń . . . . . . . . . . . . . . . . . . . . . . . . . . . 82
11.2.1.1 Schemat Metropolisa . . . . . . . . . . . . . . . . . . . 82
11.2.1.2 Dynamika Glaubera . . . . . . . . . . . . . . . . . . . . 83
11.2.1.3 Kąpiel cieplna . . . . . . . . . . . . . . . . . . . . . . . 83
11.2.2 Kilka uwag natury technicznej . . . . . . . . . . . . . . . . . . . 84
11.3 Rozprzestrzenianie się uszkodzeń . . . . . . . . . . . . . . . . . . . . . . 85
11.4 Ergodyczność . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 86
11.5 Przykład zastosowania . . . . . . . . . . . . . . . . . . . . . . . . . . . . 87
11.5.1 Temperatura Curie na sieciach regularnych z dodatkowymi sąsia
dami . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 87
11.5.2 Temperatura Curie na sieciach Archimedesa . . . . . . . . . . . . 87
Spis treści
3
256275214.001.png
http://www.zis.agh.edu.pl/ak/
11.5.3 Dygresja: Oznaki SOC w antyferromagnetykach J =−1 na sie
ciach rosnących? . . . . . . . . . . . . . . . . . . . . . . . . . . . 89
11.5.4 Efektywny algorytm obliczania sumy statystycznej . . . . . . . . 95
11.6 Dynamiczny diagram fazowy . . . . . . . . . . . . . . . . . . . . . . . . 97
11.6.1 Sieć kwadratowa z oddziaływaniem jak w modelu Isinga . . . . . 97
11.6.1.1 Konstrukcja DDF . . . . . . . . . . . . . . . . . . . . . 97
11.6.1.2 Magnetoelastyczne przejście fazowe w YMn 2 . . . . . . 98
12 AK w socjofizyce: formowanie opinii społecznej 99
12.1 Model Nowaka–Szamreja–Latan´ego . . . . . . . . . . . . . . . . . . . . . 99
12.1.1 Przejścia fazowe w obecności guru . . . . . . . . . . . . . . . . . 100
12.2 Sieci króla Salomona . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101
12.3 Model Sznajdów . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 102
12.4 Sieć Barabasiego–Alberta–Isinga . . . . . . . . . . . . . . . . . . . . . . 103
12.5 Zastosowanie: przewidywanie wyników wyborów . . . . . . . . . . . . . 104
12.5.1 Histogram liczby głosów . . . . . . . . . . . . . . . . . . . . . . . 104
12.5.2 Do której partii i kiedy się zapisać? . . . . . . . . . . . . . . . . . 104
13 AK w fizyce powierzchni: modelowanie wzrostu warstw i ich powierz
chni 107
13.1 Podstawowe procesy w skali atomowej . . . . . . . . . . . . . . . . . . . 107
13.2 Charakterystyka powierzchni i dynamiki jej wzrostu . . . . . . . . . . . 107
13.3 Deterministyczne modele SOS . . . . . . . . . . . . . . . . . . . . . . . . 108
13.3.1 Model nanoszenie przypadkowego (MNP) . . . . . . . . . . . . . 108
13.3.2 Model Family’ego . . . . . . . . . . . . . . . . . . . . . . . . . . . 109
13.3.3 Model Wolfa–Villaina . . . . . . . . . . . . . . . . . . . . . . . . 109
13.3.4 Model Das Sarmy–Tamborenea . . . . . . . . . . . . . . . . . . . 109
13.4 Probabilistyczne modele SOS . . . . . . . . . . . . . . . . . . . . . . . . 110
13.4.1 Model 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 110
13.4.2 Model 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 112
13.5 Przykłady zastosowania . . . . . . . . . . . . . . . . . . . . . . . . . . . 113
13.5.1 Początkowe stadia wzrostu . . . . . . . . . . . . . . . . . . . . . 113
13.5.2 Samoafiniczność powierzchni . . . . . . . . . . . . . . . . . . . . 117
14 Problemy transportu 121
14.1 Hydrodynamika . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 121
14.1.1 Model HPP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 122
14.1.2 Model FHP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 122
14.1.3 Gaz siatkowy Boltzmanna . . . . . . . . . . . . . . . . . . . . . . 125
14.1.4 Inne przykłady zastosowań . . . . . . . . . . . . . . . . . . . . . 125
14.1.5 Symulacja przepływów lepkich . . . . . . . . . . . . . . . . . . . 126
14.2 Korki . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 126
14.2.1 Podstawowy model jednowymiarowy . . . . . . . . . . . . . . . . 126
14.2.2 Model Nagela–Schreckenberga . . . . . . . . . . . . . . . . . . . . 127
14.2.3 Model Chowdhuryego–Schadschneidera . . . . . . . . . . . . . . 128
14.3 Materiały granulowane . . . . . . . . . . . . . . . . . . . . . . . . . . . . 129
Spis treści
4
256275214.002.png
http://www.zis.agh.edu.pl/ak/
15 Fraktale: na granicy fizyki i geometrii 131
15.1 Wymiar fraktalny . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 131
15.2 Skalowanie i podobieństwo . . . . . . . . . . . . . . . . . . . . . . . . . . 132
15.3 Skalowanie skończonych rozmiarów . . . . . . . . . . . . . . . . . . . . . 132
15.3.1 Wykładniki krytyczne dla modelu Isinga . . . . . . . . . . . . . . 133
15.4 Perkolacja . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 134
15.4.1 Algorytm Hoshena–Kopelmana . . . . . . . . . . . . . . . . . . 136
15.4.2 Rekonstrukcja przejścia perkolacjnego po przypadkowym uszko
dzeniu sieci . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 137
15.4.3 Pożary lasów . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 137
15.4.3.1 Klasyczne podejście bazujące na technice AK . . . . . . 137
15.4.3.2 Podejście średniopolowe . . . . . . . . . . . . . . . . . . 141
15.4.3.3 The model . . . . . . . . . . . . . . . . . . . . . . . . . 141
15.4.3.4 Numerical approach . . . . . . . . . . . . . . . . . . . . 142
15.4.3.5 The map . . . . . . . . . . . . . . . . . . . . . . . . . . 142
15.4.3.6 The bifurcation diagram . . . . . . . . . . . . . . . . . 144
15.4.3.7 The Lyapunov exponent . . . . . . . . . . . . . . . . . . 145
15.4.3.8 Fire size distribution . . . . . . . . . . . . . . . . . . . . 148
15.4.3.9 Comparison with experimental data . . . . . . . . . . . 150
15.4.3.10 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . 153
15.5 Analiza Hursta . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 154
15.6 Swobodne błądzenie przypadkowe . . . . . . . . . . . . . . . . . . . . . . 154
16 AK w fizyce medycznej: elektroforeza żelowa 156
16.1 DNA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 156
16.2 Elektroforeza . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 156
16.3 Model reptonowy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 157
16.3.1 Zastosowanie modelu do opisu elektroforezy . . . . . . . . . . . . 157
16.3.2 Obliczenia analityczne (dla E = 0) . . . . . . . . . . . . . . . . . 158
16.3.3 Symulacja komputerowa — zastosowanie metod Monte Carlo . . 159
16.3.3.1 Przypadek bez pola . . . . . . . . . . . . . . . . . . . . 159
16.3.3.2 Przypadek z polem . . . . . . . . . . . . . . . . . . . . 159
16.3.3.3 Ulepszanie algorytmu . . . . . . . . . . . . . . . . . . . 159
16.3.3.4 Dalsze poprawki . . . . . . . . . . . . . . . . . . . . . . 160
16.3.4 Wyniki . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 161
16.3.4.1 Symulacja dla E = 0 . . . . . . . . . . . . . . . . . . . . 161
16.3.4.2 Symulacja dla E = 0 . . . . . . . . . . . . . . . . . . . . 161
16.3.4.3 Różne koncentracje żelu . . . . . . . . . . . . . . . . . . 161
16.3.5 Model reptonowy jako model cząstkowy . . . . . . . . . . . . . . 162
16.4 Podsumowanie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 162
17 AK w chemii: modelowanie reakcji katalitycznych 163
17.1 Reakcja katalityczna . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 163
17.2 Symulacjakinetykiprocesudesorpcjitermicznejzpowierzchniciałastałego 164
17.2.1 Wyniki symulacji dla powierzchni SiO 2 /Si(110) z zaadsorbowa
nym potasem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 165
17.3 Symulacja reakcji katalitycznego utleniania tlenku węgla . . . . . . . . . 165
Spis treści
5
256275214.003.png

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika:

Zgłoś jeśli naruszono regulamin