Algorithmen in Zellularautomaten

Zellularautomaten sind ein wichtiges Modell für feinkörnigen Parallelismus, das ursprünglich von John von Neumann auf Vorschlag S. Ulams entwickelt wurde.

Im Rahmen der Vorlesung werden wichtige Grundalgorithmen (z.B. für Synchronisation) und Techniken für den Entwurf effizienter feinkörniger Algorithmen vorgestellt. Die Anwendung solcher Algorithmen in verschiedenen Problembereichen wird vorgestellt. Dazu gehören neben von Neumanns Motivation 'Selbstreproduktion' Mustertransformationen, Problemstellung wie Sortieren, die aus dem Sequenziellen bekannt sind, typisch parallele Aufgabenstellungen wie Anführerauswahl und Modellierung realer Phänomene.

Themen:

• Berechnungsmächtigkeit
• Mustererkennung
• Selbstreproduktion
• Sortieren
• Synchronisation
• Anführerauswahl
• Diskretisierung kontinuierlicher Systeme
• Sandhaufenmodell