Ruhr-Universität Bochum zum Inhalt Startseite der RUB pix
Startseite Uni Startseite
Überblick Uni Überblick
A-Z Uni A-Z
Suche Uni Suche
Kontakt Uni Kontakt

pix
 
Das Siegel
Naturwissenschaften Ingenieurwissenschaften Geisteswissenschaften Medizinische Einrichtungen Zentrale Einrichtungen
pix
 
pix Lehrstuhl Mathematik & Informatik
Komplexitätstheorie SS 08
 
 
 
Unser Angebot: Mitarbeiter | Forschung | Lehre | Abschlussarbeiten   
pix
Startseite » Lehre » 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

 
 
Zum Seitenanfang   Seitenanfang | Diese Seite drucken
Letzte Änderung: 09.04.2008 | Ansprechpartner: Webmaster