19315401
Vorlesung
WiSe 21/22: Komplexitätstheorie
Wolfgang Mulzer
Zusätzl. Angaben / Voraussetzungen
Zielgruppe
M.S.-Studierende 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
SchließenKommentar
Achtung Terminhinweis: Die erste Vorlesung findet statt am Dienstag, den 02.11.2021.
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.
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.
28 Termine
Zusätzliche Termine
Mi, 06.04.2022 10:00 - 12:00Mundliche Prüfung Komplexitätstheorie
Regelmäßige Termine der Lehrveranstaltung
Di, 02.11.2021 10:00 - 12:00
Komplexitätstheorie
Di, 09.11.2021 10:00 - 12:00
Komplexitätstheorie
Di, 16.11.2021 10:00 - 12:00
Komplexitätstheorie
Di, 23.11.2021 10:00 - 12:00
Komplexitätstheorie
Di, 30.11.2021 10:00 - 12:00
Komplexitätstheorie
Di, 07.12.2021 10:00 - 12:00
Komplexitätstheorie
Di, 14.12.2021 10:00 - 12:00
Komplexitätstheorie
Di, 04.01.2022 10:00 - 12:00
Komplexitätstheorie
Di, 11.01.2022 10:00 - 12:00
Komplexitätstheorie
Di, 18.01.2022 10:00 - 12:00
Komplexitätstheorie
Di, 25.01.2022 10:00 - 12:00
Komplexitätstheorie
Di, 01.02.2022 10:00 - 12:00
Komplexitätstheorie
Di, 08.02.2022 10:00 - 12:00
Komplexitätstheorie
Di, 15.02.2022 10:00 - 12:00
Komplexitätstheorie
Do, 04.11.2021 10:00 - 12:00
Komplexitätstheorie
Do, 11.11.2021 10:00 - 12:00
Komplexitätstheorie
Do, 18.11.2021 10:00 - 12:00
Komplexitätstheorie
Do, 25.11.2021 10:00 - 12:00
Komplexitätstheorie
Do, 02.12.2021 10:00 - 12:00
Komplexitätstheorie
Do, 09.12.2021 10:00 - 12:00
Komplexitätstheorie
Do, 16.12.2021 10:00 - 12:00
Komplexitätstheorie
Do, 06.01.2022 10:00 - 12:00
Komplexitätstheorie
Do, 13.01.2022 10:00 - 12:00
Komplexitätstheorie
Do, 20.01.2022 10:00 - 12:00
Komplexitätstheorie
Do, 27.01.2022 10:00 - 12:00
Komplexitätstheorie
Do, 03.02.2022 10:00 - 12:00
Komplexitätstheorie
Do, 10.02.2022 10:00 - 12:00
Komplexitätstheorie
Do, 17.02.2022 10:00 - 12:00
Komplexitätstheorie
Inhalt
Klassen: P, NP, coNP, PH, L, SL, NL, coNL, PSPACE, NPSPACE, ... Lesen Sie weiter