Roland Vollmar's Algorithmen in Zellularautomaten: Eine Einführung PDF

By Roland Vollmar

ISBN-10: 3322966712

ISBN-13: 9783322966711

ISBN-10: 3519023504

ISBN-13: 9783519023500

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

Best german_4 books

Download e-book for iPad: Der Stahlskelettbau mit Berücksichtigung der Hoch- und by Alfred Hawranek

Dieser Buchtitel ist Teil des Digitalisierungsprojekts Springer publication information mit Publikationen, die seit den Anfängen des Verlags von 1842 erschienen sind. Der Verlag stellt mit diesem Archiv Quellen für die historische wie auch die disziplingeschichtliche Forschung zur Verfügung, die jeweils im historischen Kontext betrachtet werden müssen.

Download e-book for iPad: Einführung in die Empirische Literaturwissenschaft by Helmut Hauptmeier, Siegfried J. Schmidt

Die vorliegende Einfiihrung in die Empirische Literaturwissenschaft ist eine Gemeinschaftsarbeit, die wir 1983 realisiert haben. Bei dieser Arbeit haben wir von verschiedenen Seiten Hilfe gefunden: N. Groeben hat selbstlos philosophische und methodologische Probleme zu lasen geholfen und unsere erste Fassung ebenso kritisch wie wohl wollend kommentiert.

Extra info for Algorithmen in Zellularautomaten: Eine Einführung

Example text

Wird darüber ( A 1 a d y e v nennt sie nichtkonstruierbare Konfigurationen) und über Modifikationen davon ausführlich referiert. ) Entscheidbarkeitsfragen für Garten-Eden-Konfigurationen werden im Detail in [G01] diskutiert. Variationen des Garten-Eden-Problems werden in Mosaikräurnen als sog. Vollständigkeitsprobleme behandelt. Es geht dabei, grob gesprochen, darum, zu klären, ob für gegebene Mosaikräurne die Menge aller endlichen Konfigurationen bzw. genauer ihrer Äquivalenzklassen bez. Translationen aus gewissen primitivsten Konfigurationen durch Anwendungen der jeweiligen globalen Transformationen erhalten werden kann.

Legt man um die so entstehenden Rasterelemente jeweilS die Elemente aus um den Faktor k fache Raster in Da K K, so reicht es für eine Beschleunigung aus, wenn diese Menge das um a kN + K überdeckt. K erweiterte k- eine endliche Menge ist, kann die Zustandsmenge von q' so ausgelegt werden, daß diese zusätzliche Information speicherbar wird. h. , wenn die Anzahl der Zustände möglichst klein bleibt. - 44 Eine solche Wahl hängt vom Geschick des damit Arbeitenden ab. 3: Sei einen Zellularraum Zellularraum.

Dabei wird allerdings von der Zweidimensionalität nicht eigentlich Ge- - 55 brauch gemacht, sondern lediglich ein Streifen benutzt, in dem jede Zelle ein Feld des Bandes darstellt, während im "benachbarten" Streifen jeweils nur genau eine Zelle nicht im Ruhezustand ist; diese Zelle repräsentiert den Kopf in dem entsprechenden Zustand. Die relativ niedrige Zustandszahl wird mit dem relativ großen Raster erkauft: Mit einem H1-Raster ergibt sich lAI = max(2m + 2, 2n + 2) und eine Verlangsamung der Berechnung um einen Faktor ~ 3 • Sieht man für den zu simulierenden Kopf an der entsprechen- den Stelle eine eigene Zelle zwischen zwei, Felder repräsentierenden, Zellen vor, so läßt sich eine Turingmaschine auch in einem lAI = 2n + m eindimensionalen Zellularraum mit H 1-Raster und in höchstens doppelter Realzeit R-simulieren.

Download PDF sample

Algorithmen in Zellularautomaten: Eine Einführung by Roland Vollmar


by Thomas
4.5

Rated 4.53 of 5 – based on 43 votes