Algorithmen In Zellularautomaten
Algorithmen in Zellularautomaten13. ZA-Modelle mit wenigen ZuständenThomas WorschFakultät für InformatikInstitut für Theoretische InformatikSommersemester 2020
Zieleeinige (sehr) einfache ZA als Modelle realer Phänomene(Diffusion, Strömung, Magnetisierung, Verkehr)einige nützliche Techniken(Random Walks, Block-ZA, partitionierte ZA)Algorithmen in Zellularautomaten (T. Worsch, KIT-Fakultät für Informatik)2 / 29
ÜberblickPseudo-ZufallsbitsRandom WalksBlock- und partitionierte ZAVerkehrssimulationAlgorithmen in Zellularautomaten (T. Worsch, KIT-Fakultät für Informatik)3 / 29
Algorithmus: ein Pseudozufallsbit pro Zelle𝑁 𝐻1(2)𝑄 {0, 1}𝐶 (0, 0)𝑁 , 𝑂, 𝑆,𝑊 : die vier „Himmelsrichtungen“Überführungsfunktion:𝛿 (ℓ) ℓ (𝐶) · ℓ (𝑁 ) ℓ (𝑂) ℓ (𝑆) ℓ (𝑊 )Algorithmen in Zellularautomaten (T. Worsch, KIT-Fakultät für Informatik)4 / 29
Algorithmus: zwei Pseudozufallsbits pro ZelleZustand 𝑞 einer Zelle bestehe aus zwei Bits 𝑞[0] und 𝑞[1]:𝛿 (ℓ) [0] ℓ (𝐶) [0] · ℓ (𝑂) [0] ℓ (𝑁 ) [0] ℓ (𝑆) [0] ℓ (𝑊 ) [1]𝛿 (ℓ) [1] ℓ (𝐶) [1] · ℓ (𝑂) [1] ℓ (𝑁 ) [1] ℓ (𝑆) [1] ℓ (𝑊 ) [0]Algorithmen in Zellularautomaten (T. Worsch, KIT-Fakultät für Informatik)5 / 29
ÜberblickPseudo-ZufallsbitsRandom WalksBlock- und partitionierte ZAVerkehrssimulationAlgorithmen in Zellularautomaten (T. Worsch, KIT-Fakultät für Informatik)6 / 29
Random WalkObjekt bewegt sich in diskreten Schritten zufällig ︁𝑝𝑛 1)mit Wahrscheinlichkeit 𝑝𝑛 zu Nachbarzelle 𝑛 (mit𝑛 𝑁Zum Beispiel:𝑝 1 𝑝 1 1/4 und 𝑝 0 1/2𝑝 1 𝑝 1 1/2𝑝 2 1/9, 𝑝 1 2/9, 𝑝 0 2/9, 𝑝 1 4/9Wie könnte man das implementieren?Algorithmen in Zellularautomaten (T. Worsch, KIT-Fakultät für Informatik)7 / 29
Random WalkObjekt bewegt sich in diskreten Schritten zufällig ︁𝑝𝑛 1)mit Wahrscheinlichkeit 𝑝𝑛 zu Nachbarzelle 𝑛 (mit𝑛 𝑁Zum Beispiel:𝑝 1 𝑝 1 1/4 und 𝑝 0 1/2𝑝 1 𝑝 1 1/2𝑝 2 1/9, 𝑝 1 2/9, 𝑝 0 2/9, 𝑝 1 4/9Wie könnte man das implementieren?Algorithmen in Zellularautomaten (T. Worsch, KIT-Fakultät für Informatik)7 / 29
Ein Random Walker in einem eindimensionalen ZA Algorithmen in Zellularautomaten (T. Worsch, KIT-Fakultät für Informatik) 8 / 29
Rechnung (Random Walk im Eindimensionalen)nur ein Partikel𝑁 𝐻1(1)𝑝 (𝑡, 𝑥): Wahrscheinlichkeit, dass Partikel zum Zeitpunkt 𝑡 an Stelle 𝑥ein Schritt: Fortschreiten der Zeit um Δ𝑡Nachbarzellen Δ𝑥 entfernt𝑝 1 𝑝 1 𝛼 mit 0 𝛼 1/2dann:𝑝 (𝑡 Δ𝑡, 𝑥) 𝛼𝑝 (𝑡, 𝑥 Δ𝑥) 𝛼𝑝 (𝑡, 𝑥 Δ𝑥) (1 2𝛼)𝑝 (𝑡, 𝑥)Algorithmen in Zellularautomaten (T. Worsch, KIT-Fakultät für Informatik)9 / 29
Rechnung (2)Taylorentwicklung und (geeignetes) Abbrechen nach wenigen Summanden: 𝑝(𝑡, 𝑥) 𝑡 𝑝(Δ𝑥) 2 2𝑝𝑝 (𝑡, 𝑥 Δ𝑥) 𝑝 (𝑡, 𝑥) Δ𝑥 (𝑡, 𝑥) (𝑡, 𝑥) 𝑥2 𝑥 2 𝑝(Δ𝑥) 2 2𝑝𝑝 (𝑡, 𝑥 Δ𝑥) 𝑝 (𝑡, 𝑥) Δ𝑥 (𝑡, 𝑥) (𝑡, 𝑥) 𝑥2 𝑥 2𝑝 (𝑡 Δ𝑡, 𝑥) 𝑝 (𝑡, 𝑥) Δ𝑡Einsetzen in𝑝 (𝑡 Δ𝑡, 𝑥) 𝛼𝑝 (𝑡, 𝑥 Δ𝑥) 𝛼𝑝 (𝑡, 𝑥 Δ𝑥) (1 2𝛼)𝑝 (𝑡, 𝑥)liefert . . .Algorithmen in Zellularautomaten (T. Worsch, KIT-Fakultät für Informatik)10 / 29
Rechnung (3)𝑝 (𝑡, 𝑥) Δ𝑡 𝑝(𝑡, 𝑥) 𝑡 𝛼𝑝 (𝑡, 𝑥) 𝛼Δ𝑥 𝑝(Δ𝑥) 2 2𝑝(𝑡, 𝑥) 𝛼(𝑡, 𝑥) 𝑥2 𝑥 2 𝛼𝑝 (𝑡, 𝑥) 𝛼Δ𝑥 𝑝(Δ𝑥) 2 2𝑝(𝑡, 𝑥) 𝛼(𝑡, 𝑥) 𝑥2 𝑥 2 (1 2𝛼)𝑝 (𝑡, 𝑥)Also: 𝑝(Δ𝑥) 2 2𝑝(𝑡, 𝑥) 𝛼(𝑡, 𝑥) 𝑡Δ𝑡 𝑥 2Algorithmen in Zellularautomaten (T. Worsch, KIT-Fakultät für Informatik)11 / 29
Problem:Algorithmen in Zellularautomaten (T. Worsch, KIT-Fakultät für Informatik)12 / 29
Problem: mehrere „Random Walker“ ?Was tun?Algorithmen in Zellularautomaten (T. Worsch, KIT-Fakultät für Informatik)12 / 29
ÜberblickPseudo-ZufallsbitsRandom WalksBlock- und partitionierte ZAVerkehrssimulationAlgorithmen in Zellularautomaten (T. Worsch, KIT-Fakultät für Informatik)13 / 29
Blockzellularautomatenlokale Blocküberführungsfunktiondeterministisch: 𝛽 : 𝑄 𝑁 𝑄 𝑁𝑁probabilistisch: 𝛽 : 𝑄 𝑁 [0; 1] 𝑄legt für jede lokale Konfiguration ℓ : 𝑁 𝑄neue (Wahrscheinlichkeitsverteilungen von) Zuständenfür alle Zellen der Nachbarschaft festBenutzung: Parkettierung von 𝑅 mit Kacheln 𝑁 ,auf denen 𝛽 angewendet wirdAlgorithmen in Zellularautomaten (T. Worsch, KIT-Fakultät für Informatik)14 / 29
Beispiel𝑅 Z, 𝑁 {0, 1}.zwei Parkettierungen: 4 3 2 101234streng abwechselnd benutzenAlgorithmen in Zellularautomaten (T. Worsch, KIT-Fakultät für Informatik)15 / 29
Beispiel𝑅 Z, 𝑁 {0, 1}.zwei Parkettierungen: 4 3 2 101234streng abwechselnd benutzenAlgorithmen in Zellularautomaten (T. Worsch, KIT-Fakultät für Informatik)15 / 29
Odd-Even-Transposition-Sort als Block-ZABlockzellularautomat mit 𝑁 {0, 1}:([𝑎, 𝑏] falls 𝑎 𝑏 𝑎 # 𝑏 #𝛽 ( [𝑎, 𝑏]) [𝑏, 𝑎] falls 𝑎 𝑏#Algorithmen in Zellularautomaten (T. Worsch, KIT-Fakultät für Informatik)1746352#16 / 29
Odd-Even-Transposition-Sort als Block-ZABlockzellularautomat mit 𝑁 {0, 1}:([𝑎, 𝑏] falls 𝑎 𝑏 𝑎 # 𝑏 #𝛽 ( [𝑎, 𝑏]) [𝑏, 𝑎] falls 𝑎 𝑏#1746352##1473625#Algorithmen in Zellularautomaten (T. Worsch, KIT-Fakultät für Informatik)16 / 29
Odd-Even-Transposition-Sort als Block-ZABlockzellularautomat mit 𝑁 {0, 1}:([𝑎, 𝑏] falls 𝑎 𝑏 𝑎 # 𝑏 #𝛽 ( [𝑎, 𝑏]) [𝑏, 𝑎] falls 𝑎 𝑏#1746352##1473625#Algorithmen in Zellularautomaten (T. Worsch, KIT-Fakultät für Informatik)16 / 29
Odd-Even-Transposition-Sort als Block-ZABlockzellularautomat mit 𝑁 {0, 1}:([𝑎, 𝑏] falls 𝑎 𝑏 𝑎 # 𝑏 #𝛽 ( [𝑎, 𝑏]) [𝑏, 𝑎] falls 𝑎 𝑏#1746352##1473625##1437265#Algorithmen in Zellularautomaten (T. Worsch, KIT-Fakultät für Informatik)16 / 29
Odd-Even-Transposition-Sort als Block-ZABlockzellularautomat mit 𝑁 {0, 1}:([𝑎, 𝑏] falls 𝑎 𝑏 𝑎 # 𝑏 #𝛽 ( [𝑎, 𝑏]) [𝑏, 𝑎] falls 𝑎 𝑏#1746352##1473625##1437265#Algorithmen in Zellularautomaten (T. Worsch, KIT-Fakultät für Informatik)16 / 29
Odd-Even-Transposition-Sort als Block-ZABlockzellularautomat mit 𝑁 {0, 1}:([𝑎, 𝑏] falls 𝑎 𝑏 𝑎 # 𝑏 #𝛽 ( [𝑎, 𝑏]) [𝑏, 𝑎] falls 𝑎 n in Zellularautomaten (T. Worsch, KIT-Fakultät für Informatik)16 / 29
Odd-Even-Transposition-Sort als Block-ZABlockzellularautomat mit 𝑁 {0, 1}:([𝑎, 𝑏] falls 𝑎 𝑏 𝑎 # 𝑏 #𝛽 ( [𝑎, 𝑏]) [𝑏, 𝑎] falls 𝑎 n in Zellularautomaten (T. Worsch, KIT-Fakultät für Informatik)16 / 29
Odd-Even-Transposition-Sort als Block-ZABlockzellularautomat mit 𝑁 {0, 1}:([𝑎, 𝑏] falls 𝑎 𝑏 𝑎 # 𝑏 #𝛽 ( [𝑎, 𝑏]) [𝑏, 𝑎] falls 𝑎 lgorithmen in Zellularautomaten (T. Worsch, KIT-Fakultät für Informatik)16 / 29
Odd-Even-Transposition-Sort als Block-ZABlockzellularautomat mit 𝑁 {0, 1}:([𝑎, 𝑏] falls 𝑎 𝑏 𝑎 # 𝑏 #𝛽 ( [𝑎, 𝑏]) [𝑏, 𝑎] falls 𝑎 lgorithmen in Zellularautomaten (T. Worsch, KIT-Fakultät für Informatik)16 / 29
Odd-Even-Transposition-Sort als Block-ZABlockzellularautomat mit 𝑁 {0, 1}:([𝑎, 𝑏] falls 𝑎 𝑏 𝑎 # 𝑏 #𝛽 ( [𝑎, 𝑏]) [𝑏, 𝑎] falls 𝑎 1234567#Algorithmen in Zellularautomaten (T. Worsch, KIT-Fakultät für Informatik)16 / 29
Odd-Even-Transposition-Sort als Block-ZABlockzellularautomat mit 𝑁 {0, 1}:([𝑎, 𝑏] falls 𝑎 𝑏 𝑎 # 𝑏 #𝛽 ( [𝑎, 𝑏]) [𝑏, 𝑎] falls 𝑎 1234567#Algorithmen in Zellularautomaten (T. Worsch, KIT-Fakultät für Informatik)16 / 29
Margolus-Nachbarschaft im Zweidimensionalen2 2-Blöckeabwechselnde Benutzung diagonal versetzter ParkettierungenAlgorithmen in Zellularautomaten (T. Worsch, KIT-Fakultät für Informatik)17 / 29
Block-ZA versus «normale» ZALemmaJeder Block-Zellularautomat mit zyklisch durchlaufener Folge vonKachelungen kann von einem normalen ZA (mit gegebenenfallsgrößerer Zustandsmenge und Nachbarschaft) Schritt für Schrittmit einer Verlangsamung um konstanten Faktor simuliert werden.Beweis: ÜbungLemmaDie Umkehrung gilt auch.Beweis: ÜbungAlgorithmen in Zellularautomaten (T. Worsch, KIT-Fakultät für Informatik)18 / 29
Beispiel (Random Walk vieler n in Zellularautomaten (T. Worsch, KIT-Fakultät für Informatik)19 / 29
Beispiel (Random Walk vieler Teilchen)eindimensional: zum Beispielvertausche Zustände in Zweierblock oder nichtzweidimensional:Algorithmen in Zellularautomaten (T. Worsch, KIT-Fakultät für Informatik)19 / 29
Beispiel (Random Walk vieler Teilchen)eindimensional: zum Beispielvertausche Zustände in Zweierblock oder nichtzweidimensional: zum Beispielrotiere Teilchen in jeder Kachel zufälligim Uhrzeigersinn oder entgegen dem UhrzeigersinnAlgorithmen in Zellularautomaten (T. Worsch, KIT-Fakultät für Informatik)19 / 29
Gittergase (engl. lattice gases)Partikelmodelle für (manche) strömende Flüssigkeiten und Gase.einfachster Fall: in jeder Zelle nur ein Bit1: Partikel, das sich im nächsten Schritt zu einem Nachbarn bewegt.0: kein PartikelÜberführungsfunktion mit 2 Phasen1. Bewegungen der Partikel2. „Kollisionen“ mehrerer Partikelhäufig Überführungsfunktionen serhaltung“Algorithmen in Zellularautomaten (T. Worsch, KIT-Fakultät für Informatik)20 / 29
Beispiel: HPP (Hardy, de Pazzis, Pomeau)Beschreibung (einer Variante) von HPP-GAS als Block-ZA:Margolus-Nachbarschaft mit 2 2-Blöcken𝑄 {0, 1}Kollision: wenn genau zwei Partikel zusammentreffen, die ausentgegengesetzten Richtungen kommen; sie werden dann um 90 abgelenkt. Algorithmen in Zellularautomaten (T. Worsch, KIT-Fakultät für Informatik) 21 / 29
Definition: partitionierter ZellularautomatZustandsmenge 𝑄 𝑃 𝑁Arbeitsweise beschrieben durch 𝛿 0 : 𝑃 𝑁 𝑃 𝑁Für Bestimmung des neuen Zustandes einer Zelle 𝑖 wird von Zelle 𝑖 𝑛 nurdie Zustandskomponente 𝑐𝑖 𝑛 (𝑛) verwendet.Algorithmen in Zellularautomaten (T. Worsch, KIT-Fakultät für Informatik)22 / 29
Beispiel: FHP (Frisch, Hasslacher, Pomeau)hexagonales Gitterjede Zelle hat sechs Nachbarn𝑄 {0, 1}6Kollisionsregel: Wenn der „Gesamtimpuls“ der ankommenden Teilchen 0 istund nicht 4 Teilchen ankommen, dann werden alle Teilchen um 60 im Uhrzeigersinn oder entgegengesetzt dem Uhrzeigersinn (zufällige Wahl) abgelenkt.Algorithmen in Zellularautomaten (T. Worsch, KIT-Fakultät für Informatik)23 / 29
Beispiel: FHP IIIsiebtes Bit für ein „ruhendes Teilchen“ in jeder ZelleRegeln (bis auf Rotation):vorhernachherAlgorithmen in Zellularautomaten (T. Worsch, KIT-Fakultät für Informatik)vorhernachhervorhernachher24 / 29
Beispiel: Ising SystemeNachbarschaft: 𝐻1(2)Zustandsmenge: { , } „Spin“Vorstellung: „kleine (Elementar-)Magnete“benachbarte Spins antiparallel ( oder ): „Energie gespeichert“ benachbarteSpins parallel ( oder ): „keine Energie gespeichert“energieerhaltende Änderung möglichst vieler Spins:Algorithmen in Zellularautomaten (T. Worsch, KIT-Fakultät für Informatik)25 / 29
Beispiel: Ising SystemeNachbarschaft: 𝐻1(2)Zustandsmenge: { , } „Spin“Vorstellung: „kleine (Elementar-)Magnete“benachbarte Spins antiparallel ( oder ): „Energie gespeichert“ benachbarteSpins parallel ( oder ): „keine Energie gespeichert“energieerhaltende Änderung möglichst vieler Spins:mit Schachbrettmuster initialisiertes „Aktivitätsbit“,das in jeder Zelle hin- und herkipptSpin wird genau dann gewechselt, wenn Zelle aktiv und genau 2 der 4Nachbarzellen den gleichen Spin haben wie die Zelle selbst.Algorithmen in Zellularautomaten (T. Worsch, KIT-Fakultät für Informatik)25 / 29
ÜberblickPseudo-ZufallsbitsRandom WalksBlock- und partitionierte ZAVerkehrssimulationAlgorithmen in Zellularautomaten (T. Worsch, KIT-Fakultät für Informatik)26 / 29
Beispiel: Modell von Nagel und SchreckenbergZelle entspricht 7.5 𝑚 Straße.Zelle kann leer oder von einem Auto besetzt.„Geschwindigkeit“ 𝑣: ganze Zahl zwischen 0 und 𝑣 max 5.modellierte Höchstgeschwindigkeit:1Zelle𝑚5 · 7.5 · 3600 𝑘𝑚𝑘𝑚Schritt·5· 7.5 thmen in Zellularautomaten (T. Worsch, KIT-Fakultät für Informatik)27 / 29
Modell von Nagel und Schreckenberglokale Überführungsfunktion besteht aus drei Phasen:1. Beschleunigung: 𝑣 0 min(𝑣 1, 𝑣 max, 𝑔),wobei 𝑔 die Anzahl freier Zellen vor dem Auto ist.2. Trödeln: 𝑣 00 max(𝑣 0 1, 0)mit kleiner Wahrscheinlichkeit 𝑝.3. Fahren: Das Fahrzeug bewegt sich um 𝑣 00 Zellen weiter;𝑣 𝑣 00.ähnliche Ansätze für FußgängersimulationAlgorithmen in Zellularautomaten (T. Worsch, KIT-Fakultät für Informatik)28 / 29
ZusammenfassungManchmal genügen wenige Zustände pro Zellefür ein «gutes» Modell eines realen Phänomens.Konzepte, die dabei wichtig oder nützlich sein atenpartitionierte ZellularautomatenAlgorithmen in Zellularautomaten (T. Worsch, KIT-Fakultät für Informatik)29 / 29
Vorstellung: „kleine (Elementar-)Magnete“ benachbarte Spins antiparallel ("#oder #"): „Energie gespeichert“ benachbarte Spins parallel (##oder ""): „keine Energie gespeichert“ energieerhaltende Änderung möglichst vieler Spins: mit Schachbre muster i
Grundlagen der Informatik / Algorithmen und Datenstrukturen Aufgabe 132 zu Aufgabe 132a Idee: 1 Überprüfe, ob die Liste leer ist. Wenn ja ListEmptyException! 2 Merke Dir den Wert des ersten Knotens in einer Hilfsvariable. 3 Durchlaufe die Liste von Knoten zu Knoten bis zum Ende und überprüfe jeweils, ob der aktuelle
tion sind daher in der Informatik ebenso wichtige Grundbegriffe wie Automation, Mathematik, for-male Sprachen oder Algorithmen. Grundlagen der Informatik werden in den Fä-chern Mathematik, Kryptographie, Theoretische Informatik, Wirtschaft, Algorithmen und Program-mierung, Betri
Docusnap erzeugt aus den erfassten individuellen Daten direkt in Microsoft Visio eine Vielzahl von Plänen. Die in Docusnap erzeugte Darstellungsform der verschie-denen Pläne (Layout, Algorithmen) lässt sich anpassen. Die Pläne werden nach dem jeweils vorgegeben
Grundlagen Theoretische Informatik Algorithmen und Datenstrukturen Objektorientierte Programmierung Wirtschaftseng-lisch für Wirt-schaftsinform. Produktion und Material-wirtschaft 1 Grundlagen der Mathematik für Informatiker Logik und diskrete Strukturen Mensch-Computer-Interaktion Einführung in die Pr
modernen Computersystemen, Informationsdarstellung im Computer, Programmiersprachen, Algorithmen. Eine Einführung in die Program-mierung erfolgt am Beispiel einer prozeduralen Sprache: Datenstruktu-ren, Kontrollstrukturen, Abstraktionsprinzipien, Software-Technik. Die Veranstalt
1.1 The Retail Banking sector performs a vital role in the economy. There are around 73 million current accounts and 4 million business accounts in the UK, and retail deposits – including current accounts, savings accounts and SME accounts – total around 1.5 trillion. Retail lending is a key driver of economic activity; UK households owe around 1.4 trillion in mortgages and 198 .
Library of Congress Cataloging-in-Publication Data Bosco, Giovanni, Saint, 1815-1888. [Memorie dell'Oratorio di S. Francesco di Sales dal 1815 al 1855. English] Memoirs of the Oratory of Saint Francis de Sales from 1815 to 1855: the autobiography of Saint John Bosco / translated by Daniel Lyons; with notes and commentary by Eugenio Ceria, Lawrence Castelvecchi, and Michael Mendl. Includes .
ST JOHN BOSCO ARTS COLLEGE Publication Scheme on information available under the Freedom of Information Act 2000. The Governing Body is responsible for maintenance of this scheme which will be reviewed bi-annually. Introduction The purpose of a publication scheme is and why it has been developed. One of the aims of the Freedom of Information Act 2000 (which is referred to as FOIA in the rest .
