Praktikum Diskrete Optimierung (SS 2001)

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.

Inhalt

	Minimale Spannbäme
	Kürzeste Pfade
	Matchings
	Netzwerkfluß
	Färbung planarer 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

Mit dem Praktikum werden mehrere Ziele verfolgt:

	Tieferes Verständnis der Methoden zur Diskreten Optimierung,
	Erfahrungen bei der Entwicklung hochoptimierter Software für rechenintensive Probleme.
	Spaß an der Herausforderung, die bestmögliche Leistung aus dem verfügbaren Rechensystem "herauszukitzeln".

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. Auf spezielle Fragen, welche die Implementierung betreffen und in den Vorlesungen nur knapp behandelt werden, wird in der Praktikumsbesprechung eingegangen.

Durchführung

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. Auch die Visualisierung von Graphenalgorithmen kann sehr komfortabel mittels der LEDA-Klasse GraphWin erfolgen.

Die Bearbeitung der Praktikumsaufgaben kann entweder auf unseren Lehrstuhl-Rechern (S 2237), in der Sun-Halle oder auch auf einem Linux-Rechner zu Hause erfolgen (in letzterem Fall muß dann LEDA auf dem Rechner installiert werden). Die Aufgaben sollen in Zweiergruppen bearbeitet werden, wobei wir dringend empfehlen, die Aufgaben nicht aufzuteilen, sondern wirklich in Zusammenarbeit zu lösen und zu implementieren. Bei der Prüfung am Ende des Praktikums wird erwartet, daß jede(r) Student(in) bei allen Praktikumsaufgaben auch zur Implementierung, die von seiner/ihrer Gruppe abgegeben wurde, Fragen beantworten kann.

Während des Praktikums findet einmal pro Woche eine zweistündige Besprechung statt, bei der die neuen Aufgaben und die zu implementierenden Algorithmen erläutert werden. Die Abgabe der Lösungen (Source-Codes) erfolgt per E-Mail an optprak@hpmayr1.informatik.tu-muenchen.de. Die Lösungen werden von einem Betreuer korrigiert, der seine Kommentare und die Bewertung der Lösung dann ebenfalls per E-Mail den Student(inn)en mitteilt. Fragen der Student(inn)en bezüglich Algorithmen und etwaigen Problemen bei der Implementierung können entweder in der Praktikumsvorlesung oder direkt mit den Betreuern besprochen werden.

Die abgegebenen Lösungen werden nach den folgenden Kriterien beurteilt:

1. Korrekte Berechnung der gewünschten Ergebnisse
2. Effiziente Implementierung, d.h. Einhaltung der angegebenen Worst-Case-Komplexität
3. Verständlichkeit und Strukturiertheit des Quelltexts

Um den unbenoteten Praktikums-Schein zu erhalten, müssen die folgenden Kriterien erfüllt werden:

• die Zweiergruppe muß zu allen Blättern zufriedenstellende Lösungen abgegeben haben
• die mündliche Prüfung am Semesterende muß bestanden werden

WICHTIG: Das Praktikum Diskrete Optimierung 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). Student(inn)en, die nach der neuen Prüfungsordnung DHP machen müssen, können den Schein nicht als Praktikumsschein zu Informatik I verwenden. Student(inn)en, 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

	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.