Download Algorithmen in Zellularautomaten: Eine Einführung by Roland Vollmar PDF

By Roland Vollmar

Dieses Buch basiert auf Vorlesungen, die ich in den letzten Jahren an der Technischen Universitat Braunschweig hielt. Es soll dazu dienen, die Eigenschaften von (uberwiegend) nichtnu merischen parallelen Algorithmen, die in Zellularautomaten imple mentierbar sind, anhand von charakteristischen Beispielen deutlich zu machen und dabei die hauptsachlich verwandten der bisher ent wickelten Methoden aufzuzeigen. Es wird dabei weder versucht, Voll standigkeit zu erreichen, noch wird der Anspruch erhoben, eine aus gearbeitete Theorie vorzustellen. Auch auf Aufwandsfragen (Zeit und Zustandskomplexitat) wird nur gelegentlich eingegangen. Bedingt durch die aUsserordentlich schnelle Entwicklung der Mikroprozessor technik ruckt m.E. der breite Einsatz von Arraycomputern naher; da Zellularautomaten als 1-1odelle von ihnen aufgefasst werden konnen, hoffe ich, mit dieser Zusammenstellung auf die sich ergebenden Mog lichkeiten aufmerksam zu machen. Vor der Darstellung der parallelen Algorithmen werden in einem Ka pitel einige Methoden der Standardisierung zellularer Raume be schrieben; dies soll dem mit dem Gebiet nicht vertrauten Leser ein Gefuhl fur Grenzen und Fahigkeiten zellularer Automaten vermitteln und ihn in die Arbeitsweise tiefer einfuhren. Die relativ zahlreichen Hinweise auf weiterfuhrende Arbeiten und auf in diesem Rahmen nicht behandelte Themen sollen eine Einord nung der angegebenen Resultate in das Gesamtgebiet erleichtern hel fen und Anreize zur weiteren Beschaftigung damit gebe

Show description

Read Online or Download Algorithmen in Zellularautomaten: Eine Einführung PDF

Similar german_4 books

Maschinen- und Konstruktionselemente 1: Grundlagen der Berechnung und Gestaltung

Die B? nde der Maschinen- und Konstruktionselemente haben sich als Standard-Lehrb? cher an Technischen Hochschulen f? r die Konstruktionstechnischen Vorlesungen durchgesetzt. Gem? ? dem Grundlagencharakter der Vorlesung wird der Schwerpunkt auf ableitbares, systematisiertes Wissen gelegt und das Gelernte an zahlreichen Berechnungsbeispielen einge?

Extra info for Algorithmen in Zellularautomaten: Eine Einführung

Example text

H. B. kennzeichnet 6 (110)2 ~ die Situation, in der der Automat und sein nördlicher Nachbar im Zustand im Zustand 0 sind. B. als 1 , der südliche (x, 1, x) aufge- faßt werden) . 6 einander gegenübergestellt (alle außerhalb gelegenen Automaten befinden sich zum Zeitpunkt t 0 im Ruhezustand) • Die Asymmetrie der Raster Hk könnte zur Uberzeugung führen, daß Zellularräume mit entsprechenden Rastern in ihren Fähigkeiten gegenüber solchen mit allgemeinen Rastern -wobei, wie wir oben sahen, das H1 -Raster ausreicht- beschränkt sind.

Dieses Problem und insbesondere die zweidimensionale Variante wird in der Literatur unter dem Aspekt einer geringen Zustandszahl erstaunlich häufig behandelt. Wenn die entsprechenden Betrachtungen für iterative Arrays einbezogen werden, so sind -ohne Anspruch auf Vollständigkeit- die Arbeiten [Col] , [Sm1], [Harn], [Ku1] , [But] und [Höl] zu nennen. In den beiden letzteren wird die bisher niedrigste bekannte Zustandszahl (nämlich IA' I = IAI 4 ) erreicht, nach einer Wahl von h , die der aus obigem Beispiel entspricht.

Die Existenz einer entsprechenden überführungsfunktion, gibt das sog. C o I e sche Lemma ([CoI]) , das ursprüng- lich für iterative Arrays formuliert wurde, aber, leicht modifiziert, auch für Zellularräume anwendbar ist ([Sm1]). ES muß ein gewisser Homomorphismus h und eine Menge K gefunden werden, die festlegen, wie die Codierung der Information in a' erfolgen muß. allg. h. in a' wird eine starke Informationsredundanz zu beobachten sein. 1: Seien Zellularräume. Gruppe (Z2, +) h (A, 2, N, F) und a' a' = K ist ent- klein zu halten.

Download PDF sample

Rated 4.41 of 5 – based on 26 votes