Informatik-Logo
Fakultät für Informatik - Technische Universität München

Lehrstuhl für Effiziente Algorithmen

TUM-Logo

Praktikum Algorithmen-Entwurf (WS 2007/2008)


Dozent: Prof. Dr. Ernst W. Mayr
Zeit:
jeweils Mo 14:15 - 15:45 Uhr (Raum 03.11.018)
Praktikumsbegin:
22.10.2007
Bereich: Informatik III (Theoretische Informatik)
Voraussetzungen: bestandenes Vordiplom; Besuch der Vorlesung Effiziente Algorithmen I in früherem Semester oder gleichzeitig zum Praktikum ist verpflichtend; Vorlesung Effiziente Algorithmen II empfehlenswert, Kenntnisse in C/C++
Praktikumsleiter: Dmytro Chibisov
Hanjo Täubig
Anmeldung: per email an algoprak*att*in.tum.de
Scheinerwerb: Schein für das Lösen aller Programmieraufgaben und mündliche Prüfung am Semesterende

Aufgabenblätter, Skripten, Beispieleingaben
Abgabe-Status



Prüfungseinteilung



Hintergrund

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.

Bild Matching
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. Student(inn)en, die an dem Praktikum teilnehmen wollen, sollten daher die Bereitschaft haben, sich auch in kompliziertere Algorithmen hineinzudenken.


Inhalt

Im Rahmen des Praktikums sollen Student(inn)en zu einem großen Teil verschiedene Graphenalgorithmen effizient implementieren und dabei die Arbeitsweise der Algorithmen auf dem Bildschirm visualisieren. Beispiele für im Praktikum zu lösende Graphenprobleme sind:

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:

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 Student(inn)en die für effiziente Implementierungen notwendigen höheren Datenstrukturen nahebringen.


Literatur

Unter anderem enthalten folgende Bücher Beschreibungen der im Praktikum zu implementierenden Algorithmen:
Hanjo Täubig
Last modified: 6. August 2007