IM ZOO DER AUTOMATEN

Publikum

Dieses Proseminar richtet sich an Studierende im 2.-6. Semester Bachelor Informatik, oder auch Mathematik, Bio-Informatik, CuK oder Computerlinguistik.


Überblick über das Seminar

Dieses Proseminar hat zwei Ziele: Erstens geht es darum die Technik und Kniffe des 'wissenschaftlichen Vortragens' zu erlernen, zu üben, und zu verfeinern. Außerdem geht es darum, in einem gemeinsamen Bummel durch den 'Zoo der Automaten' verschiedene theoretisch ansprechende und praktisch relevante Automatenmodelle kennenzulernen.

 

Automatenmodelle spielen eine große Rolle in der Informatik. Zum einen bilden sie die Grundlage für theoretische Fragen, wie das Berechenbarkeitsproblem oder die Chomskysche Sprachenhierarchie. Zum anderen bilden sie das Fundament für die Analyse von Softwaresystemen, von Hardware, von Geschäftsprozessen, Internetprotokollen und dratlosen Netzwerken. Insbesondere die automatische Überprüfung von Eigenschaften eines Systemes, das sogenannte Model-Checking basiert auf Automatenmodellen.

 

In diesem Seminar beschäftigen wir uns mit einigen Anwendungsfelder, die mit Hilfe der vorgestellten Automatenmodelle beschrieben werden können. Diese Anwendungen motivieren unsere Wanderung durch den Zoo der Automaten, in dem wir verschiedene Variationen von Automaten kennenlernen, die durch praktische Problemstellungen motiviert sind. Jedes dieser Automatenmodelle stellt eine Erweiterung der endlichen Automaten dar. So kann man etwa das zeitliche Verhalten von Systemen in Automaten nachbilden, oder mit Hilfe von Automaten Sprachen definieren, die nicht aus endlichen sondern unendlichen Wörtern bestehen. Wir werden verstehen, warum dies für die beschriebenen Anwendungsfelder wesentlich ist.

 


Grundlagen

Endliche Automaten
Differentialgleichungen
Markovketten
Boolsche Funktionen

Anwendungsgebiete

Hardware als Automaten
Software als Automaten
Geschäftsprozesse als Automaten
Produktionsanlagen als Automaten
Drahtlose Kommunikation als Automaten
TCP und IP als Automaten

Der Automatenzoo

Input/Output-Automaten
Zeit-Automaten
Probabilistische Automaten
Automaten auf unendlichen Wörtern
Hybride Automaten
Zelluläre Automaten
Keller-Automaten
Automatenspiele
Interface-Automaten
Statecharts
Petri-Netze
Warteschlangen
Minimierung von Automaten
Binäre Entscheidungsdiagramme

Dozent

Prof. Dr.-Ing. Holger Hermanns
Ernst Moritz Hahn, MsC

Eine erste Besprechung findet am Montag, 20.10.2008 um 17 Uhr in Raum 528 (E1 3) statt.


Wir treffen uns ab dem 3.11.2008 wöchentlich, vorraussichtlich jeweils Montag von 10-12 Uhr.


Die ersten beiden regulären Treffen dienen der Vorbereitung einer gemeinsamen Basis, es steht jedoch vor allem das Einüben von grundlegenden Präsentationstechniken im Vordergrund.

  • Am ersten regulären Termin (3.11.) sollen alle Teilnehmer in der Lage sein, einen 10-minütigen Vortrag über endliche Automaten und einen 10-minütigen Vortrag über Differentialgleichungen zu halten. Die zu verwendenden Folien erreichen uns spätestens am Sonntag davor. Wir werden jeweils einige daraus zur Präsentation auswählen.
  • Am zweiten regulären Termin (10.11.) sollen alle Teilnehmer in der Lage sein, einen 10-minütigen Vortrag über Boolsche Funktionen und einen 10-minütigen Vortrag über Markovketten zu halten. Die zu verwendenden Folien erreichen uns wiederum spätestens am Sonntag davor. Wir werden jeweils einige daraus zur Präsentation auswählen.

An den darauffolgenden Terminen werden je zwei Vorträge von je 30 Minuten Länge gehalten. Die Themen der Vorträge werden aus der obigen Themenliste individuell von uns an die Teilnehmer vergeben. Die Vergabe kann frühzeitig erfolgen. Jeder der Teilnehmer hält genau einen individuellen Vortrag. Hier geht es wiederum sowohl um die Wissensvermittlung, als auch die Präsentationstechnik. Die Folien zu den Vorträgen werden spätestens eine Woche vor dem Vortragstermin mit uns im Detail besprochen. Es empfiehlt sich in den meisten Fällen bereits vorab den roten Faden des geplanten Vortrages mit uns zu besprechen.


Anmeldung

Wenn Sie an diesem Seminar teilnehmen wollen, melden Sie sich bitte bei unserem Course-Managment-System an.


Literatur

Im folgenden finden Sie einige Literaturvorschläge zu den einzelnen Themen. Diese Vorschläge sind nicht binden, sie sollten durch eigene Recherchen ergänzt werden.

  • Input/Output-Automaten
  • Interface-Automaten
    • Luca de Alfaro, Thomas A. Henzinger: Interface Automata. Proceedings of the Ninth Annual Symposium on Foundations of Software Engineering (FSE), ACM Press, 2001, pp. 109-120.
  • Zeit-Automaten
  • Probabilistische Automaten
  • Automaten auf unendlichen Wörtern
  • Hybride Automaten
  • Zelluläre Automaten
    • J. L. Schiffer: Cellular Automata: A Discrete View of the World:. Wiley & Sons, Inc., 2007
  • Statecharts
  • Petri-Netze
  • Keller-Automaten
    • U. Schöning: Theoretische Informatik - kurzgefasst. Spektrum Akademischer Verlag, Heidelberg, Berlin, 2001, pp. 51-78
  • Automatenspiele
  • Minimierung von Automaten
    • C. Baier, J.-P. Katoen: Principles of Model Checking. The MIT Press, 2008, pp. 449-594
  • Binäre Entscheidungsdiagramme
  • Drahtlose Kommunikation als Automaten
  • Warteschlangen
  • Produktionsanlagen als Automaten

    		•