Notizen

Theoretische Informatik

aliasesTI

1. Übersicht und Einführung

  1. Administrativa
  2. Warum Theorie

2. Formale Sprachen und Automaten

  1. Endliche Automaten
  2. Reguläre Sprachen
  3. Worterzeugung und Grammatiken
  4. Chomsky-Hierachie
  5. Reguläre Sprachen und endliche Automaten
  6. Nicht-Deterministische endliche Automaten
  7. Grammatiken und NEAs
  8. Äquivalenz von NEAs und DEAs
  9. Reguläre Ausdrücke
  10. Das Pumping-Lemma
  11. Automatenminimierung
  12. Abschlusseigenschaften regulärer Sprachen
  13. Kontextfreie Sprachen
  14. Kellerautomaten
  15. CYK-Algorithmus

3. Berechenbarkeitstheorie

  1. Turing-Maschinen
  2. LBAs und der Satz von Kuroda
  3. Berechenbarkeit und die Church-Turing-These
  4. Varianten von Turing-Maschinen
  5. Berechnungskomplexität
  6. Alternative Berechnungsmodelle
  7. Universelle Turing-Maschinen
  8. Das Halteproblem

4. Komplexitätstheorie

  1. Definitionen
  2. Komplexitätsklassen
  3. Struktur von NP

Backlinks