Praktikum Algorithmen-Entwurf (SS 97)

Dozent:	Prof. Dr. Ernst W. Mayr
Zeit:	6 SWS, Vorlesung Di 10:15 - 12:00
Raum:	S 2229
Bereich:	Informatik I (alte Prüfungsordnung) Informatik III (neue Prüfungsordnung) (Details hier)
Voraussetzungen:	bestandenes Vordiplom; Besuch der Veranstaltung Effiziente Algorithmen I ( EA II empfehlenswert)
Praktikumsleiter:	Stefan Bischof, Thomas Erlebach
Anmeldung:	zentrale Einschreibung in der HP-Halle
Scheinerwerb:	Lösen der Programmieraufgaben (unbenoteter Schein)

Hintergrund

Viele Probleme, die in der Praxis auftreten, lassen sich sehr gut mit Hilfe von Graphen modellieren und lösen. Aus diesem Grund beschäftigen sich seit mehreren Jahrzehnten Wissenschaftler aus den Bereichen Informatik und Mathematik intensiv mit der Entwicklung von Algorithmen zur effizienten Lösung typischer Problemstellungen für Graphen. Dabei hat sich gezeigt, daß es für viele Probleme, bei denen ein naiver Lösungsansatz zu exponentiellen Laufzeiten führt, doch sehr schnelle Algorithmen gibt.

Matching maximaler Kardinalität in einem bipartiten Graphen

Ein Beispiel sind sogenannte Matching-Algorithmen, die viele unterschiedliche Zuordnungsprobleme lösen können. Ein solches Problem könnte etwa darin bestehen, Dozenten und Kurse einander so zuzuordnen, daß möglichst viele Kurse gehalten werden können. Dabei soll jeder Dozent nur einen Kurs halten, und jeder Kurs soll nur von einem Dozenten gehalten werden. In diesem Fall läßt sich das Problem als bipartiter Graph modellieren (siehe Bild). Die obere Reihe von Knoten entspricht den Dozenten, die untere Reihe den Kursen. Eine Kante zwischen einem Dozent und einem Kurs bedeutet, daß der Dozent fähig ist, den Kurs zu halten. Eine unter diesen Bedingungen gültige Zuordnung von Dozenten zu Kursen entspricht genau einem Matching. Im Beispiel können maximal sechs der acht Kurse gehalten werden, und die fett dargestellten Kanten entsprechen einer solchen Zuordnung. Der Algorithmus von Hopcroft und Karp löst das Matching-Problem in bipartiten Graphen in Zeit O(sqrt(n)*m), wobei n die Anzahl der Knoten und m die Anzahl der Kanten des Graphen ist.

Neben ihrer Nützlichkeit für die Lösung praktischer Probleme sind Graphenalgorithmen vor allem auch aufgrund der eingesetzten algorithmischen Techniken und der verwendeten Datenstrukturen interessant. Studenten, die an dem Praktikum teilnehmen wollen, sollten daher die Bereitschaft haben, sich auch in kompliziertere Algorithmen hineinzudenken.

Inhalt

Im Rahmen des Praktikums sollen Studenten verschiedene Graphenalgorithmen effizient implementieren und dabei die Arbeitsweise der Algorithmen mit Hilfe des Programms xanimate auf dem Bildschirm visualisieren. Beispiele für im Praktikum zu lösende Probleme sind:

	Tiefensuche, Breitensuche
	Zusammenhangskomponenten
	Minimale Spannbäme
	Kürzeste Pfade
	Matchings
	Netzwekfluß
	Färbung planarer Graphen
	Approximation des Traveling Salesman Problem

Die meisten Algorithmen werden in den Vorlesungen "Effiziente Algorithmen und Datenstrukturen" und "Effiziente Algorithmen und Datenstrukturen II" besprochen. Der Besuch dieser Vorlesungen ist empfehlenswert, aber nicht unbedingt erforderlich. Das Praktikum soll ein tieferes Verständnis für die Arbeitsweise von Graphenalgorithmen vermitteln und den Studenten die für effiziente Implementierungen notwendigen höheren Datenstrukturen nahebringen.

Durchführung

Die Studenten erhalten Aufgabenblätter mit Programmieraufgaben, für deren Bearbeitung eine oder mehrere Wochen zur Verfügung stehen. Die Lösungen sollen in C++ unter Verwendung von LEDA (Library of Efficient Data Types and Algorithms) und xanimate programmiert werden.

LEDA ist eine Klassenbibliothek, die häufig verwendete Datenstrukturen wie Stacks, Queues, Priority-Queues, Listen, Graphen usw. zur Verfügung stellt und damit eine große Erleichterung für C++-Programmierer bringt.

xanimate ist ein Programm, mit dessen Hilfe Graphen editiert und gespeichert werden können. Außerdem bietet es Graphenalgorithmen die Möglichkeit, auf dem Bildschirm die Darstellung von Knoten und Kanten zu beeinflussen, um die Arbeitsweise des Algorithmus zu veranschaulichen.

Die Bearbeitung der Praktikumsaufgaben kann entweder auf unseren Lehrstuhl-Rechern (S 2221), in der HP-Halle oder auch auf einem Linux-Rechner zu Hause erfolgen (in letzterem Fall müssen dann xanimate und LEDA auf dem Rechner installiert werden). Abhängig von der Teilnehmerzahl des Praktikums können Aufgaben unter Umständen auch in kleinen Gruppen bearbeitet werden.

Während des Praktikums findet einmal pro Woche ein zweistündiges Treffen statt, bei dem ein Betreuer abgegebene Lösungen und neue Aufgaben bespricht. Außerdem werden die zur Bearbeitung der Aufgaben notwendigen Grundlagen vermittelt. Fragen der Studenten bezüglich Algorithmen und etwaigen Problemen bei der Implementierung können ebenfalls hier beantwortet werden.

Den Studenten, die alle Programmieraufgaben zufriedenstellend lösen, wird ein unbenoteter Schein ausgestellt. Falls die Teilnehmerzahl jedoch groß ist und die Aufgaben in Gruppen gelöst werden, ist zum Erhalt des Scheins zusätzlich die erfolgreiche Ablegung einer mündlichen Prüfung am Ende des Semesters nötig.

WICHTIG: Das Praktikum Algorithmen-Entwurf zählt nach der alten Prüfungsordnung als Wahlpflichtpraktikum im Bereich Informatik I (Praktische Informatik), nach der neuen Prüfungsordnung (gültig ab November 1996) aber im Bereich Informatik III (Theoretische Informatik). Studenten, die nach der neuen Prüfungsordnung DHP machen müssen, können den Schein nicht als Praktikumsschein zu Informatik I verwenden. Studenten, die zwischen alter und neuer Prüfungsordnung wählen dürfen, können den Schein wahlweise als Schein zu Informatik I oder zu Informatik III verwenden. Für Details hier clicken!

Literatur

Unter anderem enthalten folgende Bücher Beschreibungen der im Praktikum zu implementierenden Algorithmen:

	Turau. Algorithmische Graphentheorie. Addison Wesley, 1996
	Gibbons. Algorithmic Graph Theory. Cambridge University Press, 1985
	Mehlhorn. Data Structures and algorithms 2: Graph algorithms and NP-Completeness, Springer-Verlag, 1984
	Papadimitriou, Steiglitz. Combinatorial Optimization: Algorithms and complexity. Prentice-Hall, 1982
	Sedgewick. Algorithms. Addison-Wesley, 1988

Thomas Erlebach, 1995-10-25, 1996-01-12, 1996-08-01
Tobias Knopff, 1997-04-08