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

Lehrstuhl für Effiziente Algorithmen

TUM-Logo

Praktikum Diskrete Optimierung (SS 04)

Dozent: Prof. Dr. Ernst W. Mayr
Zeit: Praktikumsbesprechung jeweils Montags 14:00 (c.t) - 16:00 Uhr (2 SWS),
4 Stunden Lösen der Programmieraufgaben (6 SWS)
Raum: Praktikumsbesprechung im Seminarraum MI 03.11.018,
Lösen der Programmieraufgaben im Rechnerraum MI 03.09.034
Bereich: Informatik III
Voraussetzungen: bestandenes Vordiplom; Grundkenntnisse über Entwurf und Implementierung von Algorithmen, Motivation und Kreativität
Praktikumsleiter: Jan Griebsch, Stefan Pfingstl
Sprechstunden: Jan Griebsch:  Di. 16:00 Uhr und Mi. 16:00 Uhr
Stefan Pfingstl: Di. 14:00 Uhr und Do. 10:00 Uhr
Anmeldung: Ab sofort bis 05. Februar 2004
Verbindliche Bewerbungen per e-mail an optprak@in.tum.de

Bitte geben Sie in der Mail folgende Daten an:

  • Name, Vorname
  • Matrikalnummer
  • Studienrichtung, Nebenfach und Fachsemester
  • Kurze(!) Begründung des Interesses am Praktikum
  • Kenntnisse in den Programmiersprache C/C++
  • Wenn vorhanden, Wunschpartner für 2er Gruppe

Alle Bewerber erhalten bis spätestens 09. Februar per e-mail Bescheid, ob Sie am Praktikum teilnehmen können.

Scheinerwerb: Schein für Lösen aller Programmieraufgaben (in Zweiergruppen) und mündliche Prüfung am Semesterende

Aufgabenblätter, Beispieleingaben
Abgabe-Status
Prüfungseinteilung

Hintergrund

Unter Diskreter Optimierung versteht man die Suche nach einer optimalen Lösung zu einem Problem mit diskretem Suchraum. Solche Probleme treten in der Praxis an vielen Stellen auf. Als Beispiele seien genannt: Viele Diskrete Optimierungsprobleme, 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. Doch was ist ein effizienter Algorithmus? Gewöhnlich lassen sich die bei der Diskreten Optimierung betrachteten Probleme dadurch charakterisieren, daß der Suchraum endlich ist und somit eine optimale Lösung durch vollständige Suche gefunden werden könnte. Da der Suchraum jedoch meistens zwar endlich aber riesig ist (und die exakte Lösung der Probleme nicht selten NP-schwer ist), muß man in der Praxis auf andere Methoden ausweichen. Hierbei gilt es, die Struktur der zugrundeliegenden Probleme bzw. Graphen bestmöglich auszunutzen. Oft führt nämlich ein naiver Lösungsansatz zu einem Algorithmus mit exponentieller Laufzeit oder zumindest einer Laufzeit, die um einen großen Faktor langsamer ist als bei Einsatz geschickterer Methoden. Tatsächlich 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.

Bild Matching
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

Im Rahmen des Praktikums sollen Student(inn)en zu einem großen Teil verschiedene Graphenalgorithmen effizient implementieren. Während Probleme mit kleinen Eingabegrößen in der Regel auch mit naiven ad hoc Ansätzen gelöst werden können, zeigen sich die Grenzen derartiger Verfahren bei steigender Problemgröße und besonders bei praxisrelevanten Eingabedaten recht schnell. Der Fokus im Praktikum Diskrete Optimierung liegt daher auf der Lösung von Problemen mit großen oder sogar riesigen Eingabeinstanzen. Beispiele für im Praktikum zu lösende Optimierungsprobleme 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:

Mit dem Praktikum werden mehrere Ziele verfolgt:

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

Die Student(inn)en erhalten Aufgabenblätter mit Programmieraufgaben, für deren Bearbeitung eine oder mehrere Wochen zur Verfügung stehen. Die Lösungen sollen in C++ zunächst ohne Verwendung zusätzlicher Bibliotheken programmiert werden.

Die Bearbeitung der Praktikumsaufgaben kann entweder auf unseren Lehrstuhl-Rechern (MI 03.09.034), 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@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:

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

Unter anderem enthalten folgende Bücher Beschreibungen der im Praktikum zu implementierenden Algorithmen:
Letzte Änderung: Arno Buchner am 26.01.2004