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 or Download Algorithmen in Zellularautomaten: Eine Einführung PDF

Best german_4 books

Kommerzielle Nutzung des Internet: Unterstützung von Marketing, Produktion, Logistik und Querschnittsfunktionen durch Internet, Intranet und kommerzielle Online-Dienste

Das grundsätzliche power des net ist inzwischen von den meisten Firmen, Regierungen, kommunalen Verwaltungen, Schulen und anderen Institutionen erkannt worden. Von der Realisierung dieses Potentials sind die meisten Organisationen jedoch noch weit entfernt, weil ihr Planungshorizont, soweit es beim Einsatz des net überhaupt zu einer strategischen Planung kommt, zu sehr von den bestehenden Geschäftspraktiken eingegrenzt ist.

Extra info for Algorithmen in Zellularautomaten: Eine Einführung

Example text

Sie läßt sich natürlich nur dann sinnvoll beantworten, wenn die Aufgaben, die von Zellularräumen bearbeitet werden sollen, näher spezifiziert werden. Naheliegend ist es, zu verlangen, daß Berechnungsuniversalität erreicht werden muß. E. anschaulicheren eingehen wollen, um im Anschluß daran den anderen kurz zu skizzieren. S mit h [Sm3} wählt den "direkten Weg" und betrachtet die Simulation von -etwas anders als hier definierten- Turingmaschinen durch Zellularräume, wobei er teilweise von R-Simulationen Gebrauch macht (um die Zustandszahlen klein zu halten): Die Einzelautomaten werden so ausgelegt, daß sie Bandsymbole und/oder Zustandssymbole aufnehmen können.

Genauer ihrer Äquivalenzklassen bez. Translationen aus gewissen primitivsten Konfigurationen durch Anwendungen der jeweiligen globalen Transformationen erhalten werden kann. Die Untersuchungen wurden in Abhängigkeit von der Dimension, der Zustandszahl, der Rastergröße und gelegentlich der Rasterform durchgeführt. Wichtige Ergebnisse sind in [MK3] und [NaH] [YA2],[MK1], enthalten. Dabei ist bisher nur ein Fall bekannt, für den der Mosaikraurn nicht vollständig ist. In [ACP] wird auf den Zusammenhang zwischen dem Garten-Eden-Pro- blem und injektiven und surjektiven globalen Transformationen eingegangen.

Ausgehend von off-line 1-Bandm Bandsymbolen und n Zuständen, wird die lAI = max(m + 1, Konstruktion eines Zellularraumes mit d=2 und Turingmaschinen mit n + 1) und einem M1 -Raster ohne die beiden "oberen Ecken" beschrieben, das die Turingmaschine in Realzeit R-simuliert. 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.

Download PDF sample

Rated 4.90 of 5 – based on 49 votes