Seminar "Algorithmen für NP-harte
Probleme"
Wintersemester 2001/2002
| Veranstalter: |
Detlef Sieling
(GB IV, R. 331, Tel. 2067, Email:  ) |
| Anmeldung: |
Ab dem 5.11.2001 beim Veranstalter. Die Vortragsliste ist als
Postscript-File
und als PDF-File verfügbar;
Ausdrucke
der Vortragsliste liegen in GB IV im 2.OG zwischen den Räumen 335
und 336 aus. |
|
| Termin: |
18.-21. Februar 2002 (d.h. in der ersten Woche nach
der Vorlesungszeit
des Wintersemesters 2001/2002) |
Zusammenfassung
Wenn man für ein Problem bewiesen hat, dass es NP-vollständig
ist, oder auch in der Situation, dass man keinen effizienten
Algorithmus
für ein Problem findet, stellt sich die Frage, wie man weiter
vorgehen
soll. Die erste Idee sollte sein, zu überprüfen, ob man
überhaupt das "richtige" Problem untersucht, d.h., ob man eine
eingeschränkte
Variante des Problems finden kann, die für die benötigte
Anwendung
ausreicht und die vielleicht effizienter lösbar ist als die
ursprünglich
betrachtete allgemeine Variante. Z.B. sind manche Probleme auf Graphen
NP-hart, während die eingeschränkte Variante für planare
Graphen effizient lösbar ist. Eine weitere Frage ist, ob man eine
exakte Lösung des Problems braucht, oder ob Näherungen der
exakten
Lösung auch ausreichen. Falls dies der Fall ist, sollte man nach
Approximationsalgorithmen
suchen. In manchen Fällen helfen auch randomisierte
(Approximations-)Algorithmen
weiter. Falls alle diese Versuche erfolglos sind, kann man
schließlich
noch Heuristiken untersuchen. Heuristiken sind Algorithmen, die
häufig,
d.h. für viele praktisch wichtige Eingaben, gute Lösungen
berechnen.
In dem Seminar sollen für einige wichtige Probleme, z.B. das
Traveling
Salesman Problem oder das Erfüllbarkeitsproblem,
Approximationsalgorithmen,
randomisierte Algorithmen und Heuristiken vorgestellt werden.
Die Liste der geplanten Vorträge ist als Postscript-File
und als PDF-File verfügbar. Die
Vorträge
werden ab Montag, dem 5.11.2001, beim Veranstalter vergeben. Der
weitere
Ablauf ist der folgende:
- Selbstständige Einarbeitung in die vorgeschlagene und bei
Bedarf
auch
weitere Literatur. Selbstständig heißt hier, dass es nicht
im
Rahmen einer Vorlesung o.Ä. stattfindet; der Veranstalter steht
aber
für inhaltliche Fragen und Fragen zur Vortragsgestaltung zur
Verfügung.
- Bis zum 4. Februar 2001: Abgabe einer Zusammenfassung des
Vortragsthemas
(ca. 3 Seiten) beim Veranstalter. Die Zusammenfassungen werden
anschließend
an alle Seminarteilnehmerinnen und -teilnehmer verteilt.
- 18. bis 21. Februar: Vorträge.
9.10.2001 - Detlef
Sieling