zur Kursübersicht

Theoretische Informatik 2 - Vorlesungsskript

Bachelor-Studium Informatik

Dominik Scheder, TU Chemnitz

  1. Boolesche Schaltkreise
    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
    3. Rechnerübung: gute kontextfreie Grammatik designen
    4. LL(k)-Grammatiken
    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
    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