WS 2010/2011 » Komplexitätstheorie
Ziegler

ÜbersichtMaterialien

Aktuelles

21.12.2010Aus dienstlichen Gründen muss die Veranstaltung am 2.2. und am 4.2. leider ausfallen.
12.11.2010Übungsaufgabe 10 (Blatt 3) aktualisiert
27.09.2010Am 29.10. muss die Veranstaltung wegen einer Dienstreise leider ausfallen; dafür finden bereits in der ersten Vorlesungswoche beide Termine statt.

 

Veranstalter

Name Raum Tel.
Martin Ziegler

 

Vorlesung

TagUhrzeitin Raum
Mittwochs11:40 - 13:20S2|15-201

 

Literatur

  • Papadimitriou: Computational Complexity (HeBIS, Amazon)

 

Übung

Nr.Zeitin Raum
1Freitags, 9:50 - 11:30S2|15-201

 

Formalien

Für Bachelor im dritten Studienjahr
V2Ü2, 6 ECTS Punkte
auch geeignet für den Studiengang Informatik, vgl. MHB 432

 

Inhalt

  • Asymptotik, Rechenmodelle, Ressourcen
  • Turingmaschinen und ihre Programmierung
  • polynomielle Zeit und Platz
  • Beispielprobleme SAT, 3SAT, IS, Clique
  • Beziehungen zwischen ihnen, Reduktion
  • Klasse NP, Satz von Cook-Levin
  • weitere NP-vollständige Probleme
  • Approximationsalgorithmen und Güte
  • Beispiele: VC, metr. TSP, Knapsack
  • Nichtapproximierbarkeit
  • PSPACE und QBF
  • Gewinnstrategie auf Graphen
  • Satz von Savitch
  • Erreichbarkeit und NL
  • Immerman-Szelepcsényi
  • parallele Komplexität und Schaltkreise
  • P-Vollständigkeit
  • Kryptographie und UP
  • randomisierte Komplexität
  • polynomielle Hierarchie
  • Sipser-Gács-Lautemann

 

Skript

von Prof. Blömer

 

Aktuelles

Achtung: Vom 23.10.2017 bis 25.10.2017 ist das Studienbüro wegen Semestervorbereitung geschlossen! Die Sprechstunden entfallen!


Ordnungen, Formulare, etc.

Dokumente wie Prüfungsplan-formulare, Studien- und Prüfungspläne oder Modulhandbücher finden Sie im Downloadbereich

Sabine Bartsch
Iryna Bysaha
Meike Mühlhäußer
Alexandra Neutsch
Bettina Plutz (in Elternzeit)

Sprechzeiten:
Mo13:30-15:30
Mi, Do10:30-12:30

studienbuero(at)mathematik.tu-darmstadt.de

Studienberatung

 Albrun Knof

Sprechzeiten:
Mo13:30-15:00
Mi10:30-12:00

Die Sprechstunden finden in Raum S2|15 241 statt. Es ist keine Terminvereinbarung notwendig.

Weitere Fragen bitte per Mail an:

studienberatung(at)mathematik.tu-darmstadt.de

 

 

A A A | Print Drucken | Impressum Impressum | Contact Kontakt
    zum Seitenanfangzum Seitenanfang