19537
Vorlesung
WiSe 12/13: Ausgewählte Themen der Algorithmik: Komplexitätstheorie
Wolfgang Mulzer
Zusätzl. Angaben / Voraussetzungen
4
Kommentar
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 Diplom- oder Masterarbeiten im Anschluss an die Vorlesung ist möglich. If desired, the class can be held in English. Voraussetzungen 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 Literatur - 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. Homepage http://www.inf.fu-berlin.de/lehre/WS12/CCT/ Schließen
32 Termine
Regelmäßige Termine der Lehrveranstaltung
Mo, 15.10.2012 10:00 - 12:00
Mo, 22.10.2012 10:00 - 12:00
Mo, 29.10.2012 10:00 - 12:00
Mo, 05.11.2012 10:00 - 12:00
Mo, 12.11.2012 10:00 - 12:00
Mo, 19.11.2012 10:00 - 12:00
Mo, 26.11.2012 10:00 - 12:00
Mo, 03.12.2012 10:00 - 12:00
Mo, 10.12.2012 10:00 - 12:00
Mo, 17.12.2012 10:00 - 12:00
Mo, 07.01.2013 10:00 - 12:00
Mo, 14.01.2013 10:00 - 12:00
Mo, 21.01.2013 10:00 - 12:00
Mo, 28.01.2013 10:00 - 12:00
Mo, 04.02.2013 10:00 - 12:00
Mo, 11.02.2013 10:00 - 12:00
Fr, 19.10.2012 12:00 - 14:00
Fr, 26.10.2012 12:00 - 14:00
Fr, 02.11.2012 12:00 - 14:00
Fr, 09.11.2012 12:00 - 14:00
Fr, 16.11.2012 12:00 - 14:00
Fr, 23.11.2012 12:00 - 14:00
Fr, 30.11.2012 12:00 - 14:00
Fr, 07.12.2012 12:00 - 14:00
Fr, 14.12.2012 12:00 - 14:00
Fr, 21.12.2012 12:00 - 14:00
Fr, 11.01.2013 12:00 - 14:00
Fr, 18.01.2013 12:00 - 14:00
Fr, 25.01.2013 12:00 - 14:00
Fr, 01.02.2013 12:00 - 14:00
Fr, 08.02.2013 12:00 - 14:00
Fr, 15.02.2013 12:00 - 14:00