V O R L E S U N G

Komplexitätstheorie (WS 2003/2004)

Prof. Dr. H. Veith

Folien:
Für "Platz Klassen und Spiele" und "Approximation" gibt es nun
in schwarz-weiss gehaltene Folien!
Die Folien folgen dem Aufbau der Vorlesung, und enthalten deshalb Wiederholungen
und keine Tafelbeweise. Eine edierte Version ist in Vorbereitung.
Einführung
Turing Maschinen
NP-Vollständigkeit
NP-Vollständigkeit
Strukturelle Komplexitätstheorie
Strukturelle Komplexitätstheorie
Platz Klassen und Spiele (sw)
Deskrpitive Komplexitätstheorie und Datenbanken
Kryptographie
Interactive Protocols
Approximation (sw)
Sollten Sie in den neuen Folien Fehler finden, so informieren Sie uns bitte unter
complexity@tiki.informatik.tu-muenchen.de


Bereich:
4 SWS Vorlesung im Bereich Informatik III (Theoretische Informatik)
Wahlpflichtvorlesung im Gebiet Informatik III

Zeit und Ort:
Mittwoch, 10.15-12.00, Raum MI-00.04.011 (HS2)
Freitag, 11.15-12.45, Raum MI-00.04.011 (HS2)

Übung: 2 SWS Übung zur Vorlesung
Die Anmeldung erfolgt durch eine email an complexity@tiki.informatik.tu-muenchen.de
mit dem Subject "Schein".
Im Rahmen der Übung sind zu drei Übungsblättern schriftliche Ausarbeitungen in
LaTex o.a. zu erstellen. Die Angaben werden per email verschickt und in der nächsten
Vorlesung besprochen. Bitte schicken Sie Ihre Ausarbeitungen als .ps oder .pdf an
complexity@tiki.informatik.tu-muenchen.de.
Die drei Termine:

Die Nachbesprechung der Beispiele erfolgt n.V.

Es werden Zusatzpunkte für schriftliche Ausarbeitungen der Tafelvorträge vergeben!

Literatur:

Hörerkreis:
Studierende im Hauptstudium der Informatik

Voraussetzungen:
Stoff des Informatik-Grundstudiums

Inhalt:
Übersicht