04-00-0220-vu Advanced Complexity Theory

Veranstaltungsdetails

Lehrende: Prof. Dr. Martin Ziegler

Veranstaltungsart: Vorlesung und Übung

Orga-Einheit: FB04 Mathematik

Anzeige im Stundenplan: 04-00-0220-vu

Fach:

Anrechenbar für:

Semesterwochenstunden: 3

Credits: 4,5

Unterrichtssprache: Englisch

Min. | Max. Teilnehmerzahl: - | -

Lehrinhalte:

Diagonalisierungstechniken:
Hierarchiesätze,
Satz von Robert Ladner,
Friedberg-Muchnik,
Baker-Gill-Solovay;
algorithmische Informationstheorie und Kolmogorov Komplexität;
Time-versus-Space;
untere Schranken für Schaltkreise;
Zählkomplexität


Literatur:

Christos Papadimitriou: Computational Complexity

Voraussetzungen:

Komplexitätstheorie oder Einführung in die Berechenbarkeitstheorie oder Einführung in die mathematische Logik und ein Bachelorseminar in Logik

Erwartete Teilnehmerzahl:



Weitere Informationen:



Offizielle Kursbeschreibung:
Kleingruppe(n)
Die Veranstaltung ist in die folgenden Kleingruppen aufgeteilt:

  • Advanced Complexity Theory Übung 1

    Prof. Dr. Martin Ziegler

    Do, 14. Apr. 2011 [09:50]-Do, 14. Jul. 2011 [10:35]

    Kleingruppe anzeigen
Literatur
Termine
Datum Von Bis Raum Lehrende
1 Do, 14. Apr. 2011 10:45 12:25 S215/201 Prof. Dr. Martin Ziegler
2 Do, 21. Apr. 2011 10:45 12:25 S215/201 Prof. Dr. Martin Ziegler
3 Do, 28. Apr. 2011 10:45 12:25 S215/201 Prof. Dr. Martin Ziegler
4 Do, 5. Mai 2011 10:45 12:25 S215/201 Prof. Dr. Martin Ziegler
5 Do, 12. Mai 2011 10:45 12:25 S215/201 Prof. Dr. Martin Ziegler
6 Do, 19. Mai 2011 10:45 12:25 S215/201 Prof. Dr. Martin Ziegler
7 Do, 26. Mai 2011 10:45 12:25 S215/201 Prof. Dr. Martin Ziegler
8 Do, 9. Jun. 2011 10:45 12:25 S215/201 Prof. Dr. Martin Ziegler
9 Do, 16. Jun. 2011 10:45 12:25 S215/201 Prof. Dr. Martin Ziegler
10 Do, 30. Jun. 2011 10:45 12:25 S215/201 Prof. Dr. Martin Ziegler
11 Do, 7. Jul. 2011 10:45 12:25 S215/201 Prof. Dr. Martin Ziegler
12 Do, 14. Jul. 2011 10:45 12:25 S215/201 Prof. Dr. Martin Ziegler
Übersicht der Kurstermine
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  •  
  •  
  •  
Lehrende
Prof. Dr. Martin Ziegler