Studies

193
Compulsory

When a course instance has been created from a template, the course instance will be in this state

  • Data is usually still incomplete and everything can still be edited.
  • Lecturers or secretaries can move the state forward to Edited.

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/

The first class takes place on Friday, 22.04.2016.

Contents

  • Complexity classes: 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. + oracles
  • Theorems: Cook-Levin, Time- and Space-hierarchy, Ladner, Mahaney, Savitch, Immerman-Szelepcsényi, Karp-Lipton, Adleman, Sipser-Gács, Valiant-Vazirani, Baker-Gill-Solovay, Goldreich-Levin, PCP, parallel repetition, Goldwasser-Sipser, Nisan-Wigderson, Razborov-Smolensky, Razborov-Rudich, sum-check protocol, Håstad's switching lemma, expander mixin lemma, leftover hashing lemma, etc.
  • Concepts: time, space, nondeterminism, advice, interaction, diagonalization, alternation, relativization, algebrization, naturalization, pseudo-randomness, error-correction, expander-graphs, discrete Fourier-analysis, etc.

Target Audience

M.S.-sutdents in Competer Science, Mathematics or similar courses of study. Afterwards, you can obtain a topic for a Master thesis.

Recommended Background 

Basic knowledge in Mathematics and Theoretical Computer Science: discrete Mathemtics, discrete probability theory, linear algebra, simple algebra and number theory, theory of algorithms, NP-completeness theory. More concretely: Contents of Mathematics for Computer Science, Theory of Computation, Algorithms and Data Structures, Advanced Algorithms

Website

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

Cross-language

193 154
Compulsory

Expectant Mother

Not dangerous
Partly dangerous
Alternative Course
Dangerous
Show questionnaire

Nursing Mother

Not dangerous
Partly dangerous
Alternative Course
Dangerous
Show questionnaire

AncillaryCourses

Übung zu Komplexitätstheorie

Expectant Mother

Not dangerous
Partly dangerous
Alternative Course
Dangerous
Show questionnaire

Nursing Mother

Not dangerous
Partly dangerous
Alternative Course
Dangerous
Show questionnaire