|
Dozent:
Prof. Dr. Angelika Steger
|
|
|
Bereich:
2 SWS Vorlesung im Bereich Informatik III (Theoretische Informatik)
Sonstige prüfbare Vorlesung
|
|
|
Zeit und Ort:
Mi 10:15 - 11:45, Hörsaal S2229
Beginn: 7. Mai
|
|
|
Übung:
Keine Übung
|
|
|
Hörerkreis:
Studierende im Hauptstudium der Informatik
Studierende im Hauptstudium der Mathematik mit Nebenfach Informatik
|
|
|
Voraussetzungen:
Solide Grundkenntnisse der Theoretischen Informatik
|
|
|
Empfehlenswert für:
Vertiefung im Bereich Algorithmen/Komplexität
|
|
|
Inhalt:
Eine der spektakulärsten Fortschritte der theoretischen Informatik
in den letzten Jahren ist eine neue Charakterisierung der Klasse NP
durch probabilistisch verifizierbarer Beweise und die dadurch initierten
rasanten Fortschritte bei der Klassifizierung der Approximierbarkeit
kombinatorischer Optimierungsprobleme.
In dieser Vorlesung wollen wir die mit diesem Thema
zusammenhängenden Aussagen und Ergebnisse vorstellen. Einen
einführenden Artikel hierzu finden Sie
hier
(aus: Highlights der Informatik, Ingo Wegener (Ed.),
Springer-Verlag, 1996).
|
|
|
Skript:
Kein Skript, aber so etwas ähnliches. Details in der Vorlesung.
|
|
|
Literatur:
Genaue Referenzen werden in der Vorlesung bekannt
gegeben.
|
|
|
Sprechstunde:
siehe hier!
|
