Unter
effizienten Algorithmen verstehen wir Algorithmen,
die im Hinblick auf ihre Laufzeit und/oder ihren Speicherbedarf zu den
besten für die Lösung eines bestimmten Problems bekannten
Algorithmen zählen. 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,
dass es für viele Probleme, bei denen ein naiver
Lösungsansatz zu exponentiellen Laufzeiten führt, sehr
schnelle Algorithmen gibt.
Matching maximaler Kardinalität in einem bipartiten Graphen
Ein Beispiel sind so genannte Matching-Algorithmen, die viele
unterschiedliche Zuordnungsprobleme lösen können. Ein solches
Problem könnte etwa darin bestehen, Dozenten und Kurse einander so
zuzuordnen, dass 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ässt 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, dass 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. Die Studierenden sollten daher die Bereitschaft haben,
sich auch in kompliziertere Algorithmen hineinzudenken.
Im Rahmen des Praktikums sollen zu einem
großen Teil verschiedene Graphenalgorithmen effizient
implementieren werden und dabei die Arbeitsweise der Algorithmen auf dem
Bildschirm visualisiert werden. Beispiele für im Praktikum zu
lösende Graphenprobleme sind:
- Tiefensuche, Breitensuche
- Zusammenhangskomponenten
- Minimale Spannbäume
- Kürzeste Pfade
- Matchings
- Netzwerkfluss
- Färbung planarer Graphen
- Layout von Graphen
- Approximation des Traveling Salesman Problem
Neben diesen Graphenproblemen werden aber auch einige Probleme
behandelt, die aus einem anderen Anwendungsbereich kommen und nur
indirekt mit Graphen zu tun haben. Beispiele hierfür sind:
- Suchen von Strings in Texten
- Berechnung der Edit-Distance zweier Strings
- Primzahlen und das RSA-Verfahren
Viele der Algorithmen werden in den Vorlesungen "Effiziente
Algorithmen und Datenstrukturen" und "Effiziente Algorithmen und
Datenstrukturen II" besprochen. Die Vorkenntnisse aus diesem
Veranstaltungen sind nützlich, können aber auch parallel zum
Praktikum erworben werden. Im Rahmen einer speziellen
Praktikumsvorlesung werden die zum Verständnis der Funktionsweise
der Algorithmen und zur Implementierung notwendigen Grundlagen
erklärt. Hier wird auch auf spezielle Fragen, welche die
Implementierung betreffen und in den Vorlesungen nur knapp behandelt
werden, eingegangen.
Das Praktikum soll ein tieferes Verständnis für die
Arbeitsweise effizienter Algorithmen, insbesonders von
Graphenalgorithmen, vermitteln und den Studierenden die für
effiziente Implementierungen notwendigen höheren Datenstrukturen
nahebringen.
Unter anderem enthalten folgende Bücher Beschreibungen der im
Praktikum zu implementierenden Algorithmen:
- Cormen, Leiserson, Rivest. Introduction to Algorithms. MIT Press, 1990
- 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
- Tarjan. Data Structures and Network Algorithms. SIAM, 1983
- Reingold, Nievergelt, Deo. Combinatorial Algorithms. Prentice-Hall, 1977
- Ahuja, Magnanti, Orlin. Network Flows: Theory, Algorithms, and Applications. Prentice Hall, 1993
