LEA
Fakultät für Informatik der Technischen Universität München
Lehrstuhl für Effiziente Algorithmen
Postadresse: 80290 München; Hausadresse: Arcisstr.21, 80333 München
english

Komplexitätstheorie (SS 99)


* Dozent:
Prof. Dr. Angelika Steger

* Bereich:
4 SWS Vorlesung im Bereich Informatik III (Theoretische Informatik)
Wahlpflichtvorlesung im Gebiet Komplexität

* Zeit und Ort:
Di. 8:30 - 10:00 (S1128)
Fr. 9:15 - 11:00 (1100)
Beginn: 4.5.99

* Übung:
2 SWS Übung zur Vorlesung
Termin: Mo 12:15 - 13:45, Raum S2229 *
Übungsleitung: Jens Ernst

Übungsschein: Einen Schein erhält, wer mindestens 40% der Punkte zu den Hausaufgaben erreicht und erfolgreich an der Semestralprüfung teilnimmt.

* Hörerkreis:
Studierende im Hauptstudium der Informatik
Studierende mit Nebenfach Informatik

* Voraussetzungen:
Stoff des Informatik Grundstudiums
Vorlesung Effiziente Algorithmen und Datenstrukturen I vorteilhaft, aber nicht notwendig.

* Empfehlenswert für:
Erweiterte Kenntnisse im Bereich Komplexität

* Inhalt:
In der Vorlesung wird im wesentlichen der Stoff des Buches Introduction to the Theory of Complexity von Bovet und Crescenzi behandelt.

* Weiterführende bzw. verwandte Vorlesungen:

* Skript:
Kein Skript. Aber einige Slides, die in der Vorlesung aufgelegt wurden:
Optimierungsprobleme I
Optimierungsprobleme II
Probabilistisch verifizierbare Beweise

* Literatur:
Balczar, Daz, Gabarr:
Structural Complexity I
EATCS Monographs, Springer-Verlag.
Daniel Pierre Bovet, Pierluigi Crescenzi:
Introduction to the Theory of Complexity
Prentice Hall Verlag.
Rüdiger Reischuk:
Einführung in die Komplexitätstheorie
Teubner-Verlag.

* Sprechstunde:
siehe hier


steger@informatik.tu-muenchen.de