Detailansicht
Miracles of simplicity
cellular automata and selected applications
Matthias Danzinger
Art der Arbeit
Diplomarbeit
Universität
Universität Wien
Fakultät
Fakultät für Mathematik
Studiumsbezeichnung bzw. Universitätlehrgang (ULG)
Lehramtsstudium UF Mathematik UF Psychologie und Philosophie
Betreuer*in
Peter Raith
DOI
10.25365/thesis.47576
URN
urn:nbn:at:at-ubw:1-28782.26936.172664-8
Link zu u:search
(Print-Exemplar eventuell in Bibliothek verfügbar)
Abstracts
Abstract
(Deutsch)
Das Modell des zellulären Automaten ist sehr einfach: Basis ist eine d-dimensionale Anordnung von unendlich oder endlich vielen Zellen, die jeweils gewisse Zustände annehmen können. Die möglichen Zustände können als endliche Menge aufgefasst werden. Jedem Element des Zellularraumes wird ein Zustand, also ein Element aus der Zustandsmenge, zugewiesen, weshalb es sich hierbei um eine Funktion von der Menge der Zustände auf die Menge der Zellen handelt. Wir sprechen hierbei von der Konfiguration des Automaten zu einem gegebenen Zeitpunkt. In diskreten Zeitschritten verändern die Zellen ihre Zustände abhängig von den Zuständen der Zellen in einer vorab festgelegten Nachbarschaft basierend auf einfachen Regeln. Zu jedem Zeitpunkt erhält man so eine neue Konfiguration des Automaten. Die Funktion, die eine Konfiguration zum Zeitpunkt t in eine neue Konfiguration zum Zeitpunkt t+1 überführt, heißt die „globale Überführungsfunktion“ (global transition function) und bildet das zentrale Objekt in der Erforschung derartiger Systeme. Diese Funktionen können zum Beispiel hinsichtlich elementarer Eigenschaften von Abbildungen wie etwa Injektivität und Surjektivität untersucht werden. In weiterer Folge kann gefragt werden, ob die Funktion eine Inverse besitzt, der Automat also reversibel ist. Oder wir können uns fragen, ob diese oder jene Konfiguration jemals angenommen wird, oder welche genauen Bedingungen für ein bestimmtes Verhalten verantwortlich sind. Diese Fragen können natürlich auch bezüglich gewisser Teilmengen des Zellularraumes gestellt werden. Um derartige Fragen zu beantworten, können verschiedene mathematische Methoden zum Einsatz kommen. Neben allgemeinen Grundlagen spielt die Theorie diskreter dynamischer Systeme oder auch Methoden der theoretischen Informatik eine wichtige Rolle.
Abstract
(Englisch)
The concept of a cellular automaton is quite simple. The basis is a d-dimensional grid, consisting of a finite or infinite number of cells. Each cell can take one state out of a finite state set in each time step. Every element of the cell space is mapped onto an element of the state set. Mathematically, this is a function and we call this function the configuration of the automaton at a given time. In discrete time steps, each cell changes its state depending on the states of its neighbours in a predefined neighbourhood, according to a certain update function. The arguments of this update function are the states of the neighbouring cells, which might include the state of the cell itself as well. Through this mapping, we obtain a new configuration. The function that globally maps one configuration to another one is called the global transition function and constitutes the main object of interest when theoretically analysing these systems. By investigating the properties of this function, we can answer certain questions about the behaviour of the automaton. For example, it can be analysed with regards to basic mathematical properties like injectivity and surjectivity. By doing so, we may ask if the automaton is reversible, meaning that the global transition function has an inverse function. We can also ask questions like: Will the system ever reach a certain configuration? Similarly, we may ask such questions about the behaviour of certain subsets of the cell space as well.
Schlagwörter
Schlagwörter
(Englisch)
Cellular Automata Discrete Dynamical Systems Complexity Theory
Schlagwörter
(Deutsch)
Zelluläre Automaten Diskrete Dynamische Systeme Komplexitätstheorie
Autor*innen
Matthias Danzinger
Haupttitel (Englisch)
Miracles of simplicity
Hauptuntertitel (Englisch)
cellular automata and selected applications
Paralleltitel (Deutsch)
Einfache Wunder – Zelluläre Automaten und ausgewählte Anwendungen
Publikationsjahr
2017
Umfangsangabe
vii, 117 Seiten : Illustrationen, Diagramme
Sprache
Englisch
Beurteiler*in
Peter Raith
AC Nummer
AC14506910
Utheses ID
42108
Studienkennzahl
UA | 190 | 406 | 299 |