Grundstudiumsvorlesung im SoSe 2005
18.007 Formale Grundlagen der Informatik 4 (F4)

   Daniel Moldt, Rüdiger Valk

2st. Mo 10 - 12 ESA B
Lernziel:
Wie der ganze Zyklus "Formale Grundlagen der Informatik" beschäftigt sich diese Vorlesung auf mathematischer Basis mit Abstraktionen, Modellbildungen und Verfahren zur Beschreibung und Analyse von Algorithmen und Prozessen. Formale Methoden spielen in der Informatik die Rolle eines "Denkzeugs", mit dem der (abstrakte) Kern einer Sache knapp und präzise beschrieben werden kann. Erst auf der Basis eines sauberen theoretischen Fundaments wird es möglich, solche Beschreibungen zu formulieren und deren Analysen vorzunehmen. Parallele und nebenläufige Programme und Prozesse sind aufgrund ihrer Komplexität besonders anfällig für fehlerhafte Behandlung aufgrund unpräziser Methoden. Es ist daher kein Zufall, dass "formal methods" in diesem Gebiet fester Bestandteil der Forschung und Entwicklung sind. Die Vorlesung führt in die wichtigsten Phänomene und Beschreibungstechniken ein. Sie werden z.T. an realen Programmen illustriert.
Inhalt:
  • Einfache formale Modelle (zustandsorientiert: Transitionssysteme, programmsprachlich: die prozessorientierte Sprache P, graphisch: Petrinetze) sowie relevante Begriffe und Erscheinungen (z.B.: Zustand, Aktion, Erreichbarkeit, Semantiken der Nebenläufigkeit, Verklemmungsfreiheit, Lebendigkeit und Fairness, Prinzipien der Spezifikation, Invarianten)
  • Nichtsequentielle Programme: Modellierung, Synchronisations- und Kommunikationsprinzipien, Speicher- und Rendezvous-Synchronisation, klassische Fallbeispiele, Funktionalität, Modellierung von realen Prozessen in Organisationen (workflow)
  • Parallele Algorithmen: synchrone parallele Algorithmen, Zeit- und Prozessor-Komplexität
  • Verteilte Algorithmen: Grundannahmen und Darstellungsformen, wichtige Problemklassen, Auswahlalgorithmen, verteilter wechselseitiger Ausschluss.
Stell. im Studienplan:
Grundstudium
Voraussetzungen:
F1, F2, F3 und P3
Vorgehen:
Vorlesung mit Hörsaalübungen
Literatur:
  1. J. Magee, J. Kramer: Concurrency - State Models & Java Programs (John Wiley, Chichester, 1999)
  2. W. Reisig: Petrinetze (Springer Berlin, 1985)
  3. E. Jessen, R. Valk: Rechensysteme - Grundlagen der Modellbildung (Springer, Berlin, 1986)
  4. C. Girault, R. Valk: Petri Nets for Systems Engineering - A Guide to Modelling, Verification, and Applications (Springer, Berlin, 2003)
Periodizität:
jährlich zum SS
Eignung:
Geeignet für Lehramtsstudierende, Nebenfachstudierende, Bioinformatikstudierende, Wirtschaftsinformatikstudierende.
Stichworte:
Zustand, Aktion, Nebenläufigkeit, Atomizität, Funktionalität, Fairness, prozessorientierte Sprache, parallele u. verteilte Algorithmen, Petrinetz, Synchronisation, Verklemmung, Lebendigkeit, Transitionssystem, Kommunikation