|
Termersetzungssysteme
(V3 + Ü2, WS 2015/16)
|
|
Studiengänge
- Master Informatik
- Master Software Systems Engineering
- Master Mathematik
- Bachelor Informatik
- Da es sich um eine "einführende Master-Veranstaltung" handelt, kann sie auch als
Bachelor-Wahlpflichtveranstaltung (Theorie) im Studiengang Bachelor Informatik gewählt werden.
- Ebenso ist es möglich, die Vorlesung bereits im Bachelor-Studiengang
zu hören und zu prüfen und sie sich später für den
Master-Studiengang
anerkennen zu lassen.
- Diese Vorlesung eignet sich insbesondere auch zur Kombination mit
"Funktionaler Programmierung" und "Logikprogrammierung" im Schwerpunktkolloquium
für Master Informatik und Master SSE.
Zuordnung
Wahlpflichtfach Theorie (für Bachelor),
Theoretische Informatik (für Master),
Theoretische Grundlagen von SSE (Master SSE)
Sprache
englisch
Skript
Das Skript zur Vorlesung ist hier erhältlich: Skript (Fassung vom 22.9.2011)
Inhalt
Termersetzungssysteme dienen zum Rechnen und automatischen Beweisen mit
Gleichungen. Außerdem sind Termersetzungssysteme die
Basis-Programmiersprache, die allen funktionalen Programmiersprachen
zugrunde liegt. Termersetzungssysteme werden daher in vielen Bereichen
wie der automatischen Programmverifikation, der Spezifikation von
Programmen und der deklarativen Programmierung eingesetzt. In der
Vorlesung werden Verfahren vorgestellt, um folgende Fragestellungen
rechnergestützt zu untersuchen:
- Ist das Resultat eines Programms immer eindeutig (Konfluenz)?
- Hält ein Programm immer nach endlich vielen Schritten an
(Terminierung)?
- Erfüllt ein Programm seine Spezifikation (Korrektheit)?
- Wie kann man ein unvollständiges Programm automatisch
vervollständigen?
Literatur
- J. Avenhaus. Reduktionssysteme. Springer-Verlag, 1995.
- F. Baader und T. Nipkow: Term Rewriting and All That, Cambridge
University Press, 1998.
- R. Bündgen: Termersetzungssysteme, Vieweg, 1998.
- N. Dershowitz and J.-P. Jouannaud. Rewrite Systems. Handbook of
Theoretical Computer Science, Vol. B, Chapter 6: Formal Methods and
Semantics, J. van Leeuwen (ed.), North-Holland, pp. 243-320, 1990.
-
E. Ohlebusch. Advanced Topic in Term Rewriting. Springer-Verlag, 2002.
- Terese. Term Rewriting Systems. Cambridge University Press, 2003.
Die Prüfung wird als schriftliche Klausur durchgeführt.
Sie findet am
22. Februar 2016 statt. Die zweite Klausur findet am
18. März 2016 statt.
