19315401 Vorlesung

SoSe 16: Komplexitätstheorie

Wolfgang Mulzer

Kommentar

Die erste Vorlesung findet statt am Freitag, den 22.04.2016.

Inhalt

  • Klassen: P, NP, coNP, PH, L, SL, NL, coNL, PSPACE, NPSPACE, BPP, PP, ZPP, RP, #P, PARITY P, IP, AM, MA, EXP, NEXP, P/Poly, NC, ACC, BQP, PCP, MIP, etc. + Orakel
  • Sätze: Cook-Levin, Band- und Zeit-Hierarchie, Ladner, Mahaney, Savitch, Immerman-Szelepcsényi, Karp-Lipton, Adleman, Sipser-Gács, Valiant-Vazirani, Baker-Gill-Solovay, Goldreich-Levin, PCP, parallele Wiederholung, Goldwasser-Sipser, Nisan-Wigderson, Razborov-Smolensky, Razborov-Rudich, Summenüberprüfungsprotokoll, Håstads Umschaltlemma, Expander-Vermischungslemma, Lemma vom Restehack, etc.
  • Konzepte: Zeit, Platz, Nichtdeterminismus, Ratschläge, Interaktion, Diagonalisierung, Alternierung, Relativierung, Algebraisierung, Naturalisierung, Pseudozufall, Fehlerkorrektur, Expander-Graphen, diskrete Fourier-Analyse, etc.

Zielgruppe

M.S.-Studenten in Informatik, Mathematik o.ä., Die Vergabe von Masterarbeiten im Anschluss an die Vorlesung ist möglich.

Empfohlene Vorkenntnisse 

Grundkenntnisse in Mathematik und theoretischer Informatik: diskrete Mathematik, diskrete Wahrscheinlichkeitstheorie, lineare Algebra, einfache Algebra und Zahlentheorie, Algorithmik, NP-Vollständigkeitstheorie Konkreter: MafI I-III, Grundlagen der theoretischen Informatik, AlP III, Höhere Algorithmik

Website

http://www.inf.fu-berlin.de/lehre/SS16/CCT/

Schließen

Literaturhinweise

  • S. Arora und B. Barak. Computational Complexity: A Modern Approach. Cambridge University Press, 2009.
  • O. Goldreich. Computational Complexity: A Conceptual Perspective. Cambridge University Press, 2008.
  • C. Papadimitriou. Computational Complexity. Addison Wesley, 1994.
  • M. Sipser. Introduction to the Theory of Computation. Thomson Press, 2005.
  • I. Wegener. Komplexitätstheorie: Grenzen der Effizienz von Algorithmen. Springer Verlag, 2003.
Schließen

26 Termine

Regelmäßige Termine der Lehrveranstaltung

Fr, 22.04.2016 10:00 - 12:00

Dozenten:
Univ.-Prof. Wolfgang Mulzer

Räume:
T9/SR 006 Seminarraum (Takustr. 9)

Fr, 29.04.2016 10:00 - 12:00

Dozenten:
Univ.-Prof. Wolfgang Mulzer

Räume:
T9/SR 006 Seminarraum (Takustr. 9)

Fr, 06.05.2016 10:00 - 12:00

Dozenten:
Univ.-Prof. Wolfgang Mulzer

Räume:
T9/SR 006 Seminarraum (Takustr. 9)

Fr, 13.05.2016 10:00 - 12:00

Dozenten:
Univ.-Prof. Wolfgang Mulzer

Räume:
T9/SR 006 Seminarraum (Takustr. 9)

Fr, 20.05.2016 10:00 - 12:00

Dozenten:
Univ.-Prof. Wolfgang Mulzer

Räume:
T9/SR 006 Seminarraum (Takustr. 9)

Fr, 27.05.2016 10:00 - 12:00

Dozenten:
Univ.-Prof. Wolfgang Mulzer

Räume:
T9/SR 006 Seminarraum (Takustr. 9)

Fr, 03.06.2016 10:00 - 12:00

Dozenten:
Univ.-Prof. Wolfgang Mulzer

Räume:
T9/SR 006 Seminarraum (Takustr. 9)

Fr, 10.06.2016 10:00 - 12:00

Dozenten:
Univ.-Prof. Wolfgang Mulzer

Räume:
T9/SR 006 Seminarraum (Takustr. 9)

Fr, 17.06.2016 10:00 - 12:00

Dozenten:
Univ.-Prof. Wolfgang Mulzer

Räume:
T9/SR 006 Seminarraum (Takustr. 9)

Fr, 24.06.2016 10:00 - 12:00

Dozenten:
Univ.-Prof. Wolfgang Mulzer

Räume:
T9/SR 006 Seminarraum (Takustr. 9)

Fr, 01.07.2016 10:00 - 12:00

Dozenten:
Univ.-Prof. Wolfgang Mulzer

Räume:
T9/SR 006 Seminarraum (Takustr. 9)

Fr, 08.07.2016 10:00 - 12:00

Dozenten:
Univ.-Prof. Wolfgang Mulzer

Räume:
T9/SR 006 Seminarraum (Takustr. 9)

Fr, 15.07.2016 10:00 - 12:00

Dozenten:
Univ.-Prof. Wolfgang Mulzer

Räume:
T9/SR 006 Seminarraum (Takustr. 9)

Fr, 22.07.2016 10:00 - 12:00

Dozenten:
Univ.-Prof. Wolfgang Mulzer

Räume:
T9/SR 006 Seminarraum (Takustr. 9)

Mo, 25.04.2016 10:00 - 12:00

Dozenten:
Univ.-Prof. Wolfgang Mulzer

Räume:
T9/SR 005 Übungsraum (Takustr. 9)

Mo, 02.05.2016 10:00 - 12:00

Dozenten:
Univ.-Prof. Wolfgang Mulzer

Räume:
T9/SR 005 Übungsraum (Takustr. 9)

Mo, 09.05.2016 10:00 - 12:00

Dozenten:
Univ.-Prof. Wolfgang Mulzer

Räume:
T9/SR 005 Übungsraum (Takustr. 9)

Mo, 23.05.2016 10:00 - 12:00

Dozenten:
Univ.-Prof. Wolfgang Mulzer

Räume:
T9/SR 005 Übungsraum (Takustr. 9)

Mo, 30.05.2016 10:00 - 12:00

Dozenten:
Univ.-Prof. Wolfgang Mulzer

Räume:
T9/SR 005 Übungsraum (Takustr. 9)

Mo, 06.06.2016 10:00 - 12:00

Dozenten:
Univ.-Prof. Wolfgang Mulzer

Räume:
T9/SR 005 Übungsraum (Takustr. 9)

Mo, 13.06.2016 10:00 - 12:00

Dozenten:
Univ.-Prof. Wolfgang Mulzer

Räume:
T9/SR 005 Übungsraum (Takustr. 9)

Mo, 20.06.2016 10:00 - 12:00

Dozenten:
Univ.-Prof. Wolfgang Mulzer

Räume:
T9/SR 005 Übungsraum (Takustr. 9)

Mo, 27.06.2016 10:00 - 12:00

Dozenten:
Univ.-Prof. Wolfgang Mulzer

Räume:
T9/SR 005 Übungsraum (Takustr. 9)

Mo, 04.07.2016 10:00 - 12:00

Dozenten:
Univ.-Prof. Wolfgang Mulzer

Räume:
T9/SR 005 Übungsraum (Takustr. 9)

Mo, 11.07.2016 10:00 - 12:00

Dozenten:
Univ.-Prof. Wolfgang Mulzer

Räume:
T9/SR 005 Übungsraum (Takustr. 9)

Mo, 18.07.2016 10:00 - 12:00

Dozenten:
Univ.-Prof. Wolfgang Mulzer

Räume:
T9/SR 005 Übungsraum (Takustr. 9)

Studienfächer A-Z