Harte Nüsse
Proseminar im Sommersemester 02
PD Dr. Thomas Thierauf
und
Dr. Jochen Messner
Abteilung Theoretische Informatik
Inhalt
Immer wieder stößt man auf algorithmische Problemstellungen,
an denen man sich die Zähne ausbeißt (harte Nüsse eben):
selbst bei ausgefuchsten Programmen dauert es manchmal Stunden oder gar Tage
bis ein Computer die Lösung ausgibt.
Beispiele für solche harten Nüsse sind
-
das Travelling Salesman Problem,
bei dem man für einen Handelsvertreter eine kürzeste Rundreise
durch eine Reihe von Städten finden muss,
-
das Erfüllbarkeitsproblem,
bei dem man für eine boolesche Formel eine Belegung
der Variablen finden soll, die die Formel wahr macht
(falls es eine gibt),
-
das Fußball Bundesliga Meisterschaftsproblem,
bei dem man während der Spielsaison herausfinden soll,
ob ein bestimmter Verein jetzt noch Meister werden kann.
Im Seminar sollen diese und weitere harte Nüsse vorgestellt werden.
Wir gehen der Frage nach,
warum diese Problem so schwer zu lösen sind
und wollen Möglichkeiten aufzeigen,
wie man damit in der Praxis umgehen kann:
-
Bei Optimierungsproblemen kann man beispielsweise
statt der optimalen Lösung
eine näherungsweise optimale Lösung berechnen
(Approximation).
-
Manchmal kann man unter Verwendung von Zufallszahlen
Algorithmen entwickeln, die schneller sind als
"normale" Algorithmen (Randomisierung).
-
Manchmal gelingt es Algorithmen zu entwickeln,
die zwar bei manchen Eingaben sehr langsam sind,
aber bei den meisten Eingaben schnell sind,
die in der Praxis auftreten.
Literatur
Thomas Corman, Charles Leiserson, and Ronald Rivest.
Introduction to Algorithms.
The MIT Press, 1990.
Rajeev Motwani and Prabhakar Raghavan.
Randomized Algorithms.
Cambridge University Press, 1995.
Christos Papadimitriou.
Computational Complexity.
Addison-Wesley, 1994.
Uwe Schöning.
Algorithmik.
Spektrum Akademischer Verlag, 2001.
Michael Sipser.
Introduction to the Theory of Computation.
PWS Publishing Company, 1997.