18.600  Vorlesung F 4 - Parallelität und Nebenläufigkeit

letztmalige Durchführung

Lehrende: Dr. rer. nat. Daniel Moldt

Veranstaltungsart: Vorlesung

Semester-Wochenstunden: 2

Termine: Montags 10-12

Ort: F-132

Unterrichtssprache: Deutsch

Min. | max. Teilnehmerzahl: - | -

Kommentare/ Inhalte:
Stichworte:
Funktionalität, Fairness, prozessorientierte Sprache, parallele u. verteilte Algorithmen, Petrinetz, Synchronisation, Verklemmung, Lebendigkeit, Nebenläufigkeit, Atomizität, Transitionssystem, Kommunikation, Workflow, Zustand, Aktion

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.
  

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.

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)
   
   Weitere Informationen befinden sich auf den lokalen Webseiten von TGI.
   

[Forschung] [TGI] [Informatik]