Zellul ä re Automaten

11

Zelluläre AutomatenZelluläre Automaten

Wo,YaoliangWo,Yaoliang

IMTIMT

99208369920836

2

GliederungGliederung

► EinführungEinführung

► Bausteine eines Zellulären AutomatenBausteine eines Zellulären Automaten

► Eindimensionale Zelluläre AutomatenEindimensionale Zelluläre Automaten

► ZusammenfassungZusammenfassung

3

EinführungEinführung

► Zelluläre Automaten sind mathematische Systeme, die durch einfache Regeln Zelluläre Automaten sind mathematische Systeme, die durch einfache Regeln beschrieben werden und hochkomplexes Verhalten zeigenbeschrieben werden und hochkomplexes Verhalten zeigen..

► Die Die erste Simulationerste Simulation von Zellpopulationen: von Zellpopulationen: -- in den 50er Jahren -- in den 50er Jahren John von NeumannJohn von Neumann► ""GAME OF LIFEGAME OF LIFE":": --1968 John Horton Conway --1968 John Horton Conway -- der berühmteste zelluläre Automat.-- der berühmteste zelluläre Automat.► eindimensionale zelluläre Automaten:eindimensionale zelluläre Automaten: -- Systematisierung in den 80er Jahren durch Wolfram -- Systematisierung in den 80er Jahren durch Wolfram -- mit vollkommen deterministischen Regeln und -- mit vollkommen deterministischen Regeln und Betrachtung der Raum- und Zeitdimension durch Betrachtung der Raum- und Zeitdimension durch

dasdas Aneinanderreihen der räumlichen Zustände in Aneinanderreihen der räumlichen Zustände in

ihremihrem zeitlichen Verlauf.zeitlichen Verlauf.

4

Die Grundcharakteristika eines zellulären AutomatenDie Grundcharakteristika eines zellulären Automaten

nach nach Gerhard und SchusterGerhard und Schuster ( (19951995, S. 18f.):, S. 18f.): ► Seine Entwicklung findet in Raum und Zeit statt. Seine Entwicklung findet in Raum und Zeit statt. ► Sein Raum ist eine diskrete Menge zahlreicher Zellen. Sein Raum ist eine diskrete Menge zahlreicher Zellen. ► Jede dieser Zellen hat nur eine endliche Anzahl möglicher Zustände.Jede dieser Zellen hat nur eine endliche Anzahl möglicher Zustände.► Die Zustände der Zellen verändern sich in diskreten Zeitschritten. Die Zustände der Zellen verändern sich in diskreten Zeitschritten. ► Alle Zellen sind identisch und verhalten sich nach den gleichen Alle Zellen sind identisch und verhalten sich nach den gleichen

Entwicklungsregeln.Entwicklungsregeln.

► Die Entwicklung einer Zelle hängt nur von ihrem Zustand und dem Die Entwicklung einer Zelle hängt nur von ihrem Zustand und dem ihrer lokal umgebenden Nachbarzellen ab.ihrer lokal umgebenden Nachbarzellen ab.

5

Bausteine eines zellulären AutomatenBausteine eines zellulären Automaten ► ZellraumZellraum

1. Diskrete Struktur1. Diskrete Struktur

2. unterschiedliche Dimension (ein-, zwei- oder dreidimensional)2. unterschiedliche Dimension (ein-, zwei- oder dreidimensional)

3. Unterschiedliche Geometrie der Zellen (3. Unterschiedliche Geometrie der Zellen (z. B. rechteckig,z. B. rechteckig,

hexagonal, dreieckighexagonal, dreieckig) )

4. Die Größe (4. Die Größe (z. Bz. B ein zweidimensionaler zellulärer ein zweidimensionaler zellulärer Automat mit Automat mit

10*10 rechteckigen Zellen ) 10*10 rechteckigen Zellen )

6

Bausteine eines zellulären AutomatenBausteine eines zellulären Automaten

►Die NachbarschaftDie Nachbarschaft

1.1. abhängig von der Dimension und Geometrie des zellulären Automatenabhängig von der Dimension und Geometrie des zellulären Automaten

2.2. der Radiusder Radius

3.3. ob „Eck-Zellen“ als Nachbarn gezählt werdenob „Eck-Zellen“ als Nachbarn gezählt werden

7


► RandbedingungenRandbedingungen1.1. ProblemeProbleme

①① diskreter Zellraumdiskreter Zellraum

②② die andere lokale Umgebung an den Ränderndie andere lokale Umgebung an den Rändern

③③ ein großes Gewicht von einem kleinen Zellraumein großes Gewicht von einem kleinen Zellraum

8


22.. StrategienStrategien

①① Die periodische RandbedingungDie periodische Randbedingung

─ die Ränder des Zellraums sind miteinander zu verklebendie Ränder des Zellraums sind miteinander zu verkleben

─ Aus einem eindimensionalen Zellulären Automaten wird ein Aus einem eindimensionalen Zellulären Automaten wird ein

„Ring“, in dem die Zelle am rechten Rand zu der am linken „Ring“, in dem die Zelle am rechten Rand zu der am linken

benachbart ist. benachbart ist.

②② Die symmetrische Randbedingung Die symmetrische Randbedingung entspricht einer entspricht einer

Spiegelung der RandzellenSpiegelung der Randzellen

9


► ZustandsmengeZustandsmenge

1.1. nur wenige Zustände (oft nur 2 Zustände 0 und 1)nur wenige Zustände (oft nur 2 Zustände 0 und 1)

2.2. die Definition muss genau festgelegt werdendie Definition muss genau festgelegt werden

3.3. Anzahl der Zustände des Automaten beträgt kAnzahl der Zustände des Automaten beträgt kNN (k (k

Zellzustände, N ZellenZellzustände, N Zellen))

► ZustandensentwicklungZustandensentwicklung

1.1. Abhängig nur von dem Selbstzustand und den Zuständen der Abhängig nur von dem Selbstzustand und den Zuständen der

Zellen derZellen der NachbarschaftNachbarschaft

2.2. Die Anzahl der möglichen Spielregeln beträgt Die Anzahl der möglichen Spielregeln beträgt KKkknn . Abhängig . Abhängig

nur von der Anzahl der Zellzustände nur von der Anzahl der Zellzustände kk und der Größe der und der Größe der

Nachbarschaft n.Nachbarschaft n.

10

Eindimensionale zelluläre AutomatenEindimensionale zelluläre Automaten ((WolframWolfram--AutomatenAutomaten))

Eindimensionale zelluläre AutomatenEindimensionale zelluläre Automaten

► In der 80er Jahren untersuchte und systematisierte Wolfram In der 80er Jahren untersuchte und systematisierte Wolfram

die Eigenschaften von zellulären Automaten. Um die Eigenschaften von zellulären Automaten. Um

Systematisierung zu erreichen, beschränkte er sich auf Systematisierung zu erreichen, beschränkte er sich auf

eindimensionale zelluläre Automaten mit vollkommen eindimensionale zelluläre Automaten mit vollkommen

deterministischen Regeln und betrachtete die Raum- und deterministischen Regeln und betrachtete die Raum- und

Zeitdimension durch das Aneinanderreihen der räumlichen Zeitdimension durch das Aneinanderreihen der räumlichen

Zustände in ihrem zeitlichen Verlauf.Zustände in ihrem zeitlichen Verlauf.

► Eine Zelle hat nur 2 Zustände (Wert 0 oder 1).Eine Zelle hat nur 2 Zustände (Wert 0 oder 1).

11

Eindimensionale zelluläre AutomatenEindimensionale zelluläre Automaten ((WolframWolfram--AutomatenAutomaten))

► Wird eine Zelle an der Position i im Zellraum zum Zeitpunkt t mit Wird eine Zelle an der Position i im Zellraum zum Zeitpunkt t mit

ZZii(t) beschrieben, dann ist eine mögliche Formel für eine (t) beschrieben, dann ist eine mögliche Formel für eine

Entwicklungsregel: Entwicklungsregel:

ZZii(t+1)=(Z(t+1)=(Zi-1i-1(t)+ Z(t)+ Zi+1i+1(t)) mod 2.(t)) mod 2.

Der Wert der Zelle ZDer Wert der Zelle Zii(t+1) ergibt sich aus der Summe der Werte (t+1) ergibt sich aus der Summe der Werte

ihrer beiden Nachbarzellen im vorherigen Zeitschritt modulo 2.ihrer beiden Nachbarzellen im vorherigen Zeitschritt modulo 2.

ZZii(t+1)= 0, wenn (t+1)= 0, wenn (Z(Zi-1i-1(t)+ Z(t)+ Zi+1i+1(t)) gerade(t)) gerade

1, wenn 1, wenn (Z(Zi-1i-1(t)+ Z(t)+ Zi+1i+1(t)) ungerade(t)) ungerade

► Anzahl möglicher Spielregeln: KAnzahl möglicher Spielregeln: Kkknn

12

Eindimensionale zelluläre Eindimensionale zelluläre AutomatenAutomaten

((WolframWolfram--Automaten)Automaten)Das Verhalten der grünen Zelle wird durch die benachbarten blauen Das Verhalten der grünen Zelle wird durch die benachbarten blauen

Zellen bestimmt.Zellen bestimmt. Das Pascalsche DreieckDas Pascalsche Dreieck

NB: Anzahl der NachbarnNB: Anzahl der NachbarnK: Anzahl der möglichen Zustände jeder ZelleK: Anzahl der möglichen Zustände jeder Zelle

Das Pascalsche DreieckDas Pascalsche Dreieck

NR.NR. 11 22 33 44 55 66 77 88

NachbarschaftNachbarschaft 000000 000011 001100 001111 110000 110011 111100 111111

FolgezustandFolgezustand 00 11 00 00 11 00 00 00

13


((WolframWolfram--Automaten)Automaten)Z.B für k = 2 heißt dies, jede Zelle hat 2 Zustände (entweder 0 oder 1).Z.B für k = 2 heißt dies, jede Zelle hat 2 Zustände (entweder 0 oder 1).

1 ist durch schwarzen Gitterplatz gekennzeichnet.1 ist durch schwarzen Gitterplatz gekennzeichnet.

0 ist durch weißen Gitterplatz gekennzeichnet0 ist durch weißen Gitterplatz gekennzeichnet

RuleHex:12 (Wolfram's Hexadezimal-Code)RuleHex:12 (Wolfram's Hexadezimal-Code)

RuleBinary: 00010010 = (RuleBinary: 00010010 = (000100010010)0010)2 2 = (= (112)2)1616

Mögliche Spielregeln: KMögliche Spielregeln: Kkknn = 2^2^3=256. Das heißt, dass es außer dieser Spielregel = 2^2^3=256. Das heißt, dass es außer dieser Spielregel

noch 255 mögliche Spielregeln gibt.noch 255 mögliche Spielregeln gibt.

14


((WolframWolfram--Automaten)Automaten)Bermuda Triangle RuleBermuda Triangle Rule

NB=5 (R=2) NB=5 (R=2) K=2K=2

Bermuda Triangle RuleBermuda Triangle Rule

RuleBinary = 00111000111001000100000100111101, RuleHex = BC82271CRuleBinary = 00111000111001000100000100111101, RuleHex = BC82271C

NR.NR. 11 22 33 44 55 66 77 88



NR.NR. 99 1010 1111 1212 1313 1414 1515 1616



15


((WolframWolfram--Automaten)Automaten)

mögliche Spielregeln sind 2mögliche Spielregeln sind 22255 = 4,294,967,296 = 4,294,967,296

NR.NR. 1717 1818 1919 2020 2121 2222 2323 2424



NR.NR. 2525 2626 2727 2828 2929 3030 3131 3232



16


((WolframWolfram--Automaten)Automaten)4 Klassen4 Klassen► Nach einer großen Anzahl von Computersimulationen fanden Wolfram und Nach einer großen Anzahl von Computersimulationen fanden Wolfram und

seine Mitarbeiter heraus, dass man die eindimensionalen Automaten in 4 seine Mitarbeiter heraus, dass man die eindimensionalen Automaten in 4 Klassen unterteilen kann.Klassen unterteilen kann.

17


((WolframWolfram--Automaten)Automaten)1. 1. In der ersten Klasse befinden sich alle Automaten, die sich aus In der ersten Klasse befinden sich alle Automaten, die sich aus

fast allen möglichen Anfangszuständen nach kurzer Zeit zu einem fast allen möglichen Anfangszuständen nach kurzer Zeit zu einem unveränderlichen Endzustand entwickeln werden.unveränderlichen Endzustand entwickeln werden.

18


((WolframWolfram--Automaten)Automaten)2.2. Klasse 2 enthält alle Automaten, welche periodische Muster Klasse 2 enthält alle Automaten, welche periodische Muster

ausbilden. Anders als in der ersten Klasse überleben nur ausbilden. Anders als in der ersten Klasse überleben nur einzelne mehr oder weniger breite Stränge von Zellen. Diese einzelne mehr oder weniger breite Stränge von Zellen. Diese sehen am Schluss wie ein Strichcode aus. sehen am Schluss wie ein Strichcode aus.

19


((WolframWolfram--Automaten)Automaten)3. 3. Klasse 3: Automaten mit diesen Regeln zeigen ständige Klasse 3: Automaten mit diesen Regeln zeigen ständige

Veränderungen ohne eindeutigen Endzustand, Eigenschaften Veränderungen ohne eindeutigen Endzustand, Eigenschaften chaotischen Verhaltens.chaotischen Verhaltens.

20


((WolframWolfram--Automaten)Automaten)4.4. Klasse 4: Automaten entwickeln komplizierte, räumlich Klasse 4: Automaten entwickeln komplizierte, räumlich

voneinander getrennte Muster, die sich im Laufe der Zeit voneinander getrennte Muster, die sich im Laufe der Zeit durch den Zellraum bewegen.durch den Zellraum bewegen.

21


((WolframWolfram--Automaten)Automaten)► Unterschiede zwischen den vier Klassen durchUnterschiede zwischen den vier Klassen durch

1.1. Aussehen und Gestalt der letztlich entstehenden Musterbildungen Aussehen und Gestalt der letztlich entstehenden Musterbildungen undund

2.2. jeweils einen eigenen Grad der Vorhersagbarkeitjeweils einen eigenen Grad der Vorhersagbarkeit

Klasse 1 : das gesamte Verhalten ist ohne genaue Kenntnis Klasse 1 : das gesamte Verhalten ist ohne genaue Kenntnis eines Anfangszustands vorhersagbareines Anfangszustands vorhersagbar

Klasse 2 : im Anfangszustand sind nur kleine, begrenzte Klasse 2 : im Anfangszustand sind nur kleine, begrenzte Bereiche relevant, um den Zustand einer bestimmten Zelle im Bereiche relevant, um den Zustand einer bestimmten Zelle im Endzustand vorherzusagenEndzustand vorherzusagen

Klasse 3 und Klasse 4 : die gesamte Musterbildung kann durch Klasse 3 und Klasse 4 : die gesamte Musterbildung kann durch die Änderung eines einzelnen Zellenzustands beeinflusst die Änderung eines einzelnen Zellenzustands beeinflusst werden. werden.

22


((WolframWolfram--Automaten)Automaten)► "Magische Parameter""Magische Parameter"

Ein wichtiger Parameter Ein wichtiger Parameter λ λ wurde von Christopher Langton gefunden, wurde von Christopher Langton gefunden, damit man einen Automaten nur nach seiner Produktionsregel in damit man einen Automaten nur nach seiner Produktionsregel in eine der Klassen einteilen kann. Dieser Parameter drückt die eine der Klassen einteilen kann. Dieser Parameter drückt die Wahrscheinlichkeit aus, mit welcher eine Zelle mit Zustand 1 Wahrscheinlichkeit aus, mit welcher eine Zelle mit Zustand 1 ("lebend") in der nächsten Runde überlebt oder nicht. ("lebend") in der nächsten Runde überlebt oder nicht.

Klasse 1: Klasse 1: λλ=0, alles Leben wird sofort aussterben; mit =0, alles Leben wird sofort aussterben; mit λλ=1 sind alle =1 sind alle Zellen auf Dauer am Leben.Zellen auf Dauer am Leben.

Klasse 3: z.B. bei Klasse 3: z.B. bei λλ=0,5; das ergibt ein großes Wirrwarr von toten =0,5; das ergibt ein großes Wirrwarr von toten und lebendigen Zellen.und lebendigen Zellen.

23


((WolframWolfram--Automaten)Automaten) Klasse 2Klasse 2: Teil der Bereiche 0<: Teil der Bereiche 0<λλ<0,5 bzw. 0,5<<0,5 bzw. 0,5<λλ<1. (Die Werte <1. (Die Werte

von toten und lebendigen Zellen können einfach vertauscht von toten und lebendigen Zellen können einfach vertauscht werden.) Das Gebiet der Automaten zweiter Klasse entspricht werden.) Das Gebiet der Automaten zweiter Klasse entspricht Werten von Werten von λλ zwischen den Grenzen 0 und 0,3 zwischen den Grenzen 0 und 0,3

Klasse 4Klasse 4: die magische Schwelle, wo die viertklassigen : die magische Schwelle, wo die viertklassigen Automaten angesiedelt sind, findet sich etwa bei Automaten angesiedelt sind, findet sich etwa bei λλ=0,273 =0,273

Begrenzung der 4 Klassen durch Begrenzung der 4 Klassen durch λλ..

24

AusblickAusblick

Man kann trotz der einfachen Regeln der Zellulären Man kann trotz der einfachen Regeln der Zellulären Automaten vieles mit ihnen simulieren.Automaten vieles mit ihnen simulieren. Zelluläre Automaten Zelluläre Automaten eignen sich besonders gut für Modelle, bei denen die eignen sich besonders gut für Modelle, bei denen die räumliche Komponente wichtig ist. Viele Forscher nennen räumliche Komponente wichtig ist. Viele Forscher nennen Zelluläre Automaten “Software der Natur“, und man geht Zelluläre Automaten “Software der Natur“, und man geht davon aus, dass diese Modellierungsmethode insbesondere davon aus, dass diese Modellierungsmethode insbesondere in den Geowissenschaften und in der Ökologie immer mehr in den Geowissenschaften und in der Ökologie immer mehr angewendet wird.angewendet wird.

25

Literatur Literatur

► Martin Gerhardt, Heike Schuster: Das digitale Universum. Martin Gerhardt, Heike Schuster: Das digitale Universum. Zelluläre Automaten als Modelle der Natur. Vieweg, Zelluläre Automaten als Modelle der Natur. Vieweg, Braunschweig 1995. Braunschweig 1995.

► Stephen Wolfram: Celluar Automata and Complexity. Stephen Wolfram: Celluar Automata and Complexity. Collected Papers. Addison-Wesley, Reading 1994.Collected Papers. Addison-Wesley, Reading 1994.

Date post:	04-Jan-2016
Category:	Documents
Upload:	kennan
View:	37 times
Download:	0 times

Zellul ä re Automaten

Documents