Modulcode:	MS0403
Englische Bezeichnung:	Relational Methods in Computer Science
Modulverantwortliche(r):	Prof. Dr. Rudolf Berghammer
Turnus:	unregelmäßig (WS07/08 SS10)
Präsenzzeiten:	4V 2Ü
ECTS:	8
Workload:	240 Std.
Dauer:	ein Semester
Modulkategorien:	TG (MSc Inf) MV (MSc Inf)
Lehrsprache:	Deutsch
Voraussetzungen:

Kurzfassung:

In den letzten Jahren wurden Verbandstheorie und der sich auf sie stützende bzw. sie in eine spezielle Richtung erweiternde Kalkül der binären Relationen als geeignete Formalismen zur Beschreibung von grundlegenden Konzepten der Informatik -- insbesondere im Bereich der Programmiersprachen und -methodik und der Algorithmik -- in größerem Rahmen genutzt.

Die Vorlesung baut auf die Vorlesung über Ordnungen und Verbände (MS0402) auf. Sie gibt eine grundlegende Einführung in den algebraischen Kalkül der binären Relationen, die sogenannte Relationenalgebra, und demonstriert die Nützlichkeit des algebraischen Vorgehens anhand von vielen Beispielen aus der Informatik.

Lernziele:

Aufbauend auf ordnungs-und verbandstheoretische Grundlagen ist ein wesentliche Lernziel die Einführung in die algebraische Auffassung von Relationen und die sich dabei ergebenden speziellen Denk- und Schlußweisen. Weiterhin ist es ein Ziel der Vorlesung zu demonstrieren, daß eine algebraische Vorgehensweise eine Reihe von Vorzügen besitzt. Einer davon ist die relativ einfache Mechanisierung. Es ist deshalb auch geplant, auf die maschinelle Unterstützung beim Arbeiten im Relationenkalkül einzugehen und ein an der CAU entwickeltes Programmsysteme zur relationalen Programmieren und zur Visualisierung relationaler Berechnungen zu verwenden

Lehrinhalte:

Zuerst werden hier die grundlegenden Begriffe von konkreten, also mengentheoretischen, Relationen eingeführt und dann im Rahmen von abstrakten Relationenalgebren algebraisiert. Ein Teil der Axiome einer Relationenalgebra ist rein verbandstheoretischer Natur; hierdurch wird die Brücke zur Vorlesung über Ordnungen und Verbände hergestellt. Die algebraische Behandlung von Relationen beinhaltet insbesondere die algebraische Definition von bestimmten Klassen von Relationen bzw. von relationalen Operationen und den Beweis von wichtigen Eigenschaften. Nach dieser Einführung in die Algebra der Relationen und das Rechnen in ihr befaßt sich die Vorlesungmit den strukturerhaltenden Funktionen zwischen Relationen. Dies ist nsbesondere wichtig, um die "`Eindeutigkeit"' von axiomatisch definierten relationalen Strukturen festzulegen, welche später bei gewissen Anwendungen eine Rolle spielen.

Der zweite Teil der Vorlesung konzentriert sich auf Anwendungen von Relationen beim Algorithmenentwurf. Zuerst wird gezeigt, wie man Datenstrukturen -- insbesondere Mengen und einige der in der universellen Algebra bzw. der Semantik von Programmiersprachen wichtigen sogenannten Bereichskonstruktionen -- mit relationenalgebraischen Mitteln beschreiben kann. Dann wird anhand von vielen Fallstudien demonstriert, wie man konkrete Probleme durch relationale Programme löst, also durch Programme, die sich im wesentlichen nur auf einen Datentyp für Relationen stützen. Viele der Beispiele sind graphentheoretischer Natur, wie etwa die Bestimmung der erreichbaren Knoten, das Testen von Kreisfreiheit oder die Berechnung von Kernen. Es werden aber auch Probleme aus anderen Bereichen betrachtet, beispielsweise kombinatorische 2-Personen-Spiele und das Erfüllbarkeitsproblem von Booleschen Formeln. Durch die relationale Behandlung von ordnungs- und verbandstheoretischen Problemen wird schließlich der Bogen wieder zurück zur Vorlesung ueber Ordnungen und Verbände geschlagen.

Weitere Voraussetzungen:

Vorteilhaft ist MS0402 (Ordnungen und Verbände). Man kann die dort eingeführten Begriffe aber auch anhand der ersten Kapitel des Buchs von R. Berghammer nacharbeiten. (Das Buch deckt MS0402 und MS0403 ab.) Soweit die Begriffe tieferliegend sind (etwa Fixpunkte oder Hüllenbildungen- und -systeme), werden sie aber auch kurz wiederholt, um die Vorlesung möglichst abgeschlossen zu halten.

Prüfungsleistung:

Mündliche Prüfung am Vorlesungsende

Lehr- und Lernmethoden:

Verwendbarkeit:

Literatur:

• G. Schmidt, T. Str"ohlein, Relationen und Graphen, Springer Verlag, 1989.
• C. Brink, W. Kahl, G. Schmidt (Herausgeber): Relational Methods in Computer Science, Springer Verlag, 1997.
• R. Berghammer, Ordnungen, Verbände und Relationen mit Anwendungen, Vieweg-Teubner Verlag, 2008.

Verweise:

Kommentar: