zur Kursübersicht

Theoretische Informatik 2 - Vorlesungsskript

Bachelor-Studium Informatik

Dominik Scheder, TU Chemnitz

  1. Einleitung
    1. Boolesche Schaltkreise (nicht im Sommersemester 2025)
      1. Fanin, Tiefe, Größe
      2. Wahrheitstabellen, CNF, DNF
      3. Binär-Addierer
      4. Monotone Schaltkreise
      5. Majority
      6. Untere und obere Schranken
    2. 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≉R
      5. Das Schröder-Bernstein-Theorem
      6. Der Trichotomiesatz
    3. Berechenbarkeit und natürliche Zahlen
      1. Primitive Rekursion. Motivation und Definition
      2. Primitive Rekursion: Konstruktionen, Tricks
      3. Primitive Rekursion kann nicht alles: die Ackermann-Funktion
      4. Ein Schritt weiter: while-Schleifen und μ-Rekursion
    4. Reguläre Sprachen
      1. Reguläre Grammatiken
      2. Endliche Automaten
      3. Nichtdeterministische endliche Automaten
      4. Von einer reguläre Grammatik zu einem endlichen Automaten an einem Beispiel
      5. Reguläre Ausdrücke
      6. Die Grenzen regulärer Sprachen
      7. Übungsaufgaben
    5. Kontextfreie Sprachen
      1. Ableitungen und Ableitungsbäume
      2. Pushdown-Automaten (nicht im Sommersemester 2025)
      3. Rechnerübung: gute kontextfreie Grammatik designen (nicht im Sommersemester 2025)
      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
    6. Allgemeine Grammatiken (nicht im Sommersemester 2025)
      1. Turingmaschinen
        1. Formale Definition
        2. Beispiele
        3. Varianten: Mehrband, Halbband, Oblivious, nichtdeterministisch
        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
      2. Komplexitätstheorie
        1. Das Zeithierarchietheorem
      3. Appendix - Manual für das Schreiben dieses Skripts