|
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: |
|
- J. Magee, J. Kramer: Concurrency - State Models & Java Programs, John Wiley, Chichester, 1999
- W. Reisig: Petrinetze, Springer Berlin, 1985
- E. Jessen, R. Valk: Rechensysteme - Grundlagen der Modellbildung, Springer, Berlin, 1986
- 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, Wirtschaftsinformatikstudierende. |
|
Stichworte: |
|
Petrinetz, Synchronisation, Verklemmung, Lebendigkeit, Transitionssystem, Kommunikation, Zustand, Aktion, Nebenläufigkeit, Atomizität,
Funktionalität, Fairness, prozessorientierte Sprache, parallele u. verteilte Algorithmen |
Matthias Jantzen