|
|
|
 |
Lehrstuhl
Mathematik & Informatik
Komplexitätstheorie
SS
08 |
|
| |
| |
|
 |
|
|
| LV-NR |
150 262 |
| Veranstaltung |
Komplexitätstheorie
| 4.0 std. |
NA 1/64 Di
12.00-14.00
NA 5/64 Do 12.00-14.00
|
|
| Dozent(inn)en |
Simon, H. U. |
| Übung |
Kallweit, M. |
(150 263)
|
2.0 std.
|
NA 2/24 Do 08.00-10:00
|
|
| |
|
Voraussetzungen |
| |
|
Elementare Grundkenntnisse zu der Thematik, wie sie etwa in der Vorlesung "Theoretische Informatik" vermittelt werden,
werden weitgehend vorausgesetzt. (Diese Voraussetzungen sind aber von mathematisch gebildeten Studierenden relativ
rasch im Selbststudium herstellbar.)
|
| |
|
Kommentar |
| |
|
Die Vorlesung beschäftigt sich mit der Theorie der lokalen Optimierung
bei kombinatorischen Problemen. Dabei gibt es drei zentrale Themen.
Erstens gehen wir der Frage nach, inwieweit mathematisch garantiert
werden kann, dass ein aufgespürtes lokales Optimum nicht wesentlich
schlechter ist als ein globales Optimum. Zweitens analysieren wir
die Zeitkomplexität lokaler Optimierungprobleme: wieviele lokale
Verbesserungen sind erforderlich, bis wir zu einem lokalen Optimum
gelangen? Drittens untersuchen wir Heuristiken, die unter Umständen
auf dem Weg zu einem lokalen Optimum auch Verschlechterungen der
aktuellen Lösung in Kauf nehmen (wie zum Beispiel "Simulated
Annealing". Bei den ersten beiden Themen werden zur Illustration
der Analysetechniken konkrete Optimierungsprobleme (wie zum
Beispiel "Problem des Handelsreisenden", "Balancierte
Graphenpartition" oder Scheduling-Probleme "nach allen Regeln
der Kunst" behandelt.
|
| |
|
Literatur
|
| |
|
In der Vorlesung wird das Buch "Theoretical Aspects of Local Search" von Wil Michiels, Emile Aarts und Jan Korst (Springer Verlag) besprochen.
Zur Theorie der NP-Vollständigkeit empfehle ich den
Klassiker: Garey and Johnson, "Computers and Intractability. (A Guide to the Theorie of NP-Completeness)", Freeman and Company.
|
| |
|
Prüfungstermine
|
| |
|
- Mdl. Prüfung: 29.7.2009 (150262a) (Anmeldungen: 15.6. - 15.7.2009, 12 Uhr)
- Mdl. Prüfung: 1.10.2009 (150262b) (Anmeldungen: 3.8. - 17.9.2009, 12 Uhr)
Die genauen Uhrzeiten bitte mit Michael Kallweit bis spätestens zum jeweiligen Anmeldeschluss absprechen.
|
|
|
Materialien
|
|
|
Übungsaufgaben
|
|
Blatt 01:
PDF
|
|
Blatt 02:
PDF
|
|
Blatt 03:
PDF
|
|
Blatt 04:
PDF
|
|
Blatt 05:
PDF
|
|
Blatt 06:
PDF
|
|
Blatt 07:
PDF
|
|
Blatt 08:
PDF
|
|
Blatt 09:
PDF
|
|
Blatt 10:
PDF
|
|
Blatt 11:
PDF
|
|
Blatt 12:
PDF
|
|
|
| |
|
|
