zur KursübersichtKapitel 1 >>

Theoretische Informatik 2 - Vorlesungsskript

Bachelor-Studium Informatik
Dominik Scheder, TU Chemnitz,
  1. Einleitung
  2. Boolesche Schaltkreise (nicht im Sommersemester 2025)
    1. Fanin, Tiefe, Größe
    2. Wahrheitstabellen, CNF, DNF
    3. Binär-Addierer
    4. Monotone Funktionen und monotone Schaltkreise
    5. Majority
    6. Untere und obere Schranken
  3. Unendliche Mengen
    1. Wer ist größer?
    2. Beispiele abzählbar unendlicher Mengen
    3. Mengen, die so groß wie $\R$ sind
    4. Die Cantorsche Diagonalisation: $\N \not \approx \R$
    5. Das Schröder-Bernstein-Theorem
    6. Der Trichotomiesatz
  4. Berechenbarkeit und natürliche Zahlen
    1. Primitive Rekursion: Motivation und Definitionen
    2. Primitive Rekursion: Konstruktionen und Tricks
    3. Primitive Rekursion kann nicht alles: die Péter-Ackermann-Funktion
    4. Ein Schritt weiter: while-Schleifen und $\mu$-Rekursion
  5. Reguläre Sprachen
    1. Reguläre Grammatiken
    2. Endliche Automaten
    3. Nichtdeterministische Endliche Automaten
    4. Von einer regulären Grammatik zu einem endlichen Automaten an einem Beispiel
    5. Reguläre Ausdrücke
    6. Die Grenzen regulärer Sprachen
    7. Übungsaufgaben
  6. Kontextfreie Sprachen
    1. Ableitungen und Ableitungsbäume
    2. Kontextfreie Grammatiken und Kellerautomaten
    3. Rechnerübung: Gute kontextfreie Grammatiken entwerfen
    4. LL($k$)-Grammatiken (nicht im Sommersemester 2025)
    5. LR-Parser per Hand entwerfen
    6. Einen Parser in Java implementieren
    7. LR-Grammatiken
    8. Linker Rand, Blüten und die DK-Grammatik
    9. Der DK-Automat
    10. Allgemeines Parsing
    11. Die Grenzen kontextfreier Sprachen
  7. Allgemeine Grammatiken
  8. Turingmaschinen
    1. Turingmaschinen: Formale Definition und Beispiele
    2. Beispiele
    3. Variationen: Mehrband-Maschinen, nichtdeterministische Maschinen
    4. Turing-Maschinen codieren
    5. Turing-Maschinen simulieren Turing-Maschinen: die universelle Turing-Maschine
    6. Unentscheidbarkeit
    7. Mehr über Unentscheidbarkeit: Das Postsche Korrespondenzproblem
    8. Anwendungen des Postschen Korrespondenzproblems
  9. Complexity Theory
    1. Das Zeithierarchietheorem
    2. Turing-Maschinen zu Schaltkreisen!
    3. Nichtdeterministische Zeit
    4. Viele Beispiele aus NP
    5. Reduktionen
    6. Ganz NP reduziert auf SAT: das Cook-Levin-Theorem
    7. Beschränkter Speicherplatz
    8. Savitch's Theorem: $\textrm{Reachability} \in \textrm{Space}(\log(n))$