Lehrveranstaltung

Vorlesung, 4 SWS, ECTS-Studium, ECTS-Credits: 8,0, Modul: MS0403; Fachgebiet: Theoretische Informatik, Informatiknahe Mathematik
Zeit und Ort: Di 12:00 - 14:00, LMS2 - R.Ü3; Do 12:00 - 14:00, LMS2 - R.Ü1
vom 14.4.2009 bis zum 16.7.2009

Voraussetzungen / Organisatorisches

Die vierstündige Vorlesung wendet sich in erster Linie an die Studierenden der Informatik im Haupt- und Nebenfach, aber auch an Studierende der Mathematik mit Interesse an theoretischen Fragestellungen. Vorausgesetzt werden Kenntnisse, wie sie im Diplom-Grundstudium oder einen Bachelor-Studiums eines der eben erwähnten Fächer erworben werden. Der vorherige Besuch der Vorlesung "Ordnung und Verbände" ist hilfreich, aber nicht zwingend notwendig, da sowohl ein Buch zum Nachschlagen zur Verfügung steht und auch die erforderlichen Grundlagen noch jeweils wiederholt werden.

Inhalt

Im ersten Teil werden die grundlegenden Begriffe von konkreten, also mengentheoretischen, Relationen eingeführt und dann im Rahmen von abstrakten Relationenalgebren algebraisiert. Nach dieser Einführung in die Algebra der Relationen und das Rechnen in ihr befassen wir uns noch mit den strukturerhaltenden Funktionen zwischen Relationen. Dies ist insbesondere wichtig, um die Eindeutigkeit von axiomatisch definierten relationalen Strukturen festzulegen, welche später bei Anwendungen in der Algorithmik eine großse Rolle spielen.

Im zweiten Teil konzentrieren wir uns dann auf Anwendungen von Relationen beim Algorithmenentwurf. Zuerst zeigen wir, wie man Datenstrukturen - insbesondere Mengen und einige der in der universellen Algebra bzw. der Semantik von Programmiersprachen wichtigen sogenannten Bereichskonstruktionen - mit relationalen Mitteln beschreiben kann. Dann demonstrieren wir anhand von vielen Fallstudien, wie man konkrete Probleme durch relationale Programme lösen kann, also durch Programme, die sich im Wesentlichen nur auf einen Datentyp für Relationen stützen. Viele der Beispiele sind graphentheoretischer Natur; wir betrachten aber auch Probleme aus anderen Bereichen, etwa kombinatorische Spiele, das bekannte SAT-Problem der Booleschen Formeln und Probleme auf Qrdnungen und Verbänden.

Bei den die Vorlesung der begleitenden Übungen werden wir oftmals RelView einsetzen, ein an der Christian-Albrechts-Universität zu Kiel entwickeltes Computersystem zur Manipulation und Visualisierung von konkreten Relationen und zum relationalen Programmieren.

Die Vorlesung orientiert sich am zweiten Teil des Buches "Ordnungen, Verbände und Relationen mit Anwendungen", das 2008 beim Teubner-Verlag erschienen ist.

Empfohlene Literatur

R. Berghammer: Ordnungen, Verbände und Relationen mit Anwendungen, Teubner Verlag, 2008

G. Schmidt, T. Ströhlein: Relationen und Graphen, Springer Verlag, 1989.

C. Brink, W. Kahl, G. Schmidt (Herausgeber): Relational Methods in Computer Science, Springer Verlag, 1997.

Zusätzliche Informationen

Schlagwörter: Relationen, Graphen, Algorithmen
Erwartete Teilnehmerzahl: 25

Zugeordnete Lehrveranstaltungen

UE: Übungen zu: Relationale Methoden in der Informatik (080063): Dozent/in: Prof. Dr. Rudolf Berghammer
Zeit und Ort: Do 14:00 - 16:00, CAP4 - R.715



	UnivIS ist ein Produkt der Config eG, Buckenhof