VL Komplexitätstheorie und Approximation (WS '00/01)
LV-Nr.: 0350 L 260
Termine:
Die Vorlesung findet normalerweise donnerstags von 10:10 bis 11:40 Uhr
im Raum MA 741 statt. Dazu gibt es folgende Ausnahme:
- Die Vorlesung vom 7. Dezember wird auf Mittwoch,
13. Dezember, 16:00 bis 17:30 Uhr, MA741 vorverlegt.
Weitere Verlegungen werden rechtzeitig bekanntgegeben werden.
Zum Inhalt der Vorlesung:
Die Schwierigkeit eines Optimierungs- oder Entscheidungsproblems wird
in der Regel daran gemessen, wie gut bzw. schnell es algorithmisch
gelöst werden kann. Diese Intuition wird in der Komplexitätstheorie
aufgegriffen und formalisiert. Das ermöglicht insbesondere eine
Zuordnung der betrachteten Probleme zu verschiedenen
Komplexitätsklassen, so dass dann sowohl positive wie auch negative
Aussagen bezüglich ihrer effizienten Lösbarkeit getroffen werden
können. Anhand von anschaulichen Beispielen (hauptsächlich aus der
Kombinatorischen Optimierung) wird eine Einführung in dieses Gebiet
gegeben. Neben klassischen komplexitätstheoretischen Konzepten und
Fragestellungen beschäftigen wir uns auch damit, wie gut ein als
schwer erkanntes Optimierungsproblem in vertretbarer Zeit approximativ
gelöst werden kann.
Voraussetzungen:
Grundkenntnisse über Algorithmen (beispielsweise aus der Vorlesung COMA).
Hilfreich sind außerdem Grundkenntnisse aus der Vorlesung Graphen- und
Netzwerkalgorithmen (sie werden jedoch nicht vorausgesetzt).
Literatur:
- Computers and Intractability von Michael Garey und David Johnson (Freeman, 1979)
- Computational Complexity von Christos Papadimitriou (Addison-Wesley, 1994)
- Complexity and Approximation von Giorgio Ausiello et al. (Springer, 1999)
- Approximation Algorithms for NP-hard Problems von Dorit Hochbaum (PWS, 1995)
Übungen:
Gelegentlich werden Übungsaufgaben ausgegeben und im Rahmen der
Vorlesung besprochen werden.
Sonstige Angaben:
Veranstaltung im Studienschwerpunkt "Algorithmische Diskrete
Mathematik"; gleichermaßen für Mathematiker, sowie für Techno- und
Wirtschaftsmathematiker und Informatiker geeignet.
TU Berlin |
FB
Mathematik |
FTP
Last modified: Thu Nov 30 10:05:25 MET 2000
<skutella@math.tu-berlin.de>