Grundlagen der Theoretische Informatik

Slides

ANMERKUNG: Alle Links in den Folien sind anklickbar

  • 14.04.2021: Einführung [introduction.pdf]
  • Audio-kommentierte Folien (Online 11.04.2021)
  • 15.04.2021: Terminologie (I) [terminologie1.pdf]
  • Audio-kommentierte Folien (Ordner: "2021-04-15: Terminologie I"; 3 Dateien)
  • Grundlegende Beweisstrategien 1 (Logik für Informatiker)
  • 21.04.2021: Terminologie (II) [terminologie2.pdf] --!>
  • Dycksprache -- Beweis: L(G)= Dk: [Beweis-Dycksprache.pdf]
  • Audio-kommentierte Folien (Ordner: "2021-04-21: Terminologie II"; 3 Dateien)
  • 22.04.2021: Terminologie (III) [terminologie3.pdf]
  • Abzählbarkeit: Beweis [Beweis-abzaehlbar.pdf]
  • Audio-kommentierte Folien (Ordner: "2021-04-22: Terminologie III"; 3 Dateien).
  • 28.04.2021: Terminologie (IV) [terminologie4.pdf]
  • 28.04.2021: Endliche Automaten (I) [endliche-automaten1.pdf]
  • Üerabzählbarkeit [ueberabzaehlbar.pdf]
  • Audio-kommentierte Folien (Ordner: "2021-04-28: Terminologie IV & Endliche Automaten"; 2 Dateien).
  • 29.04.2021: Endliche Automaten (II) [endliche-automaten2.pdf]
  • Beispiel [ndea-to-dea.pdf]
  • Audio-kommentierte Folien (Ordner: "2021-04-29: Endliche Automaten, Teil 2"; 2 Dateien).
  • 5.05.2021: Endliche Automaten (III) [endliche-automaten3.pdf]
  • Audio-kommentierte Folien (Ordner: "2021-05-05: Endliche Automaten, Teil 3"; 2 Dateien).
  • 6.05.2021: Endliche Automaten (IV) [endliche-automaten4.pdf]
  • Beweis: Zu jedem reg. Ausdruck r gibt es Ar eps-NDEA mit L(Ar)=I(r) [REGtoEPS-NDEA.pdf]

  • Beispiel: Berechnung eines regulären Ausdrucks für L(A) [beispiel1.pdf]
  • Beispiel: Berechnung eines Automaten mit L(A) = I(r) [beispiel2.pdf]

  • Audio-kommentierte Folien (Ordner: "2021-05-06: Endliche Automaten, Teil 4"; 6 Dateien).
  • 11.05.2021: Kellerautomaten (I) [keller-automaten1.pdf]
  • Beispiel: Berechnung der co-erreichbaren Variablen; Berechnung der erreichbaren Symbole
    [erreichbar-co-erreichbar.pdf]
  • Audio-kommentierte Folien (Ordner: "2021-05-12: Kellerautomaten und kontextfreie Sprachen, Teil 1"; 2 Dateien).
  • 19.05.2021: Kellerautomaten (II) [keller-automaten2.pdf] (Version: 15.05.2021)
  • Audio-kommentierte Folien (Ordner: "2021-05-19: Kellerautomaten und kontextfreie Sprachen, Teil 2"; 4 Dateien).
  • 20.05.2021: Kellerautomaten (III) [keller-automaten3.pdf] (Online: 15.05.2021)
  • Audio-kommentierte Folien (Ordner: "2021-05-20: Kellerautomaten und kontextfreie Sprachen, Teil 3"; 3 Dateien).
  • 2.06.2021: Kellerautomaten (IV) [keller-automaten4.pdf]

  • Hopcroft, Motwani, Ullman: Enführung in Automatentheorie, Formale Sprachen und Berechenbarkeit:
  • Seiten 272-275: [leeren-Stack->Endzustand.pdf]
  • Seiten 276-277: [Endzustand->leeren-Stack.pdf]

  • [PDA-to-Grammatik.pdf]

  • Audio-kommentierte Folien (Ordner: "2021-06-2: Kellerautomaten und kontextfreie Sprachen, Teil 4"; 2 Dateien).
  • 9.06.2021: Kellerautomaten (V) [keller-automaten5.pdf]
  • Example CYK-Algorithmus [example-CYK.pdf]
  • Audio-kommentierte Folien (Ordner: "2021-06-09: Kellerautomaten und kontextfreie Sprachen, Teil 5"; 3 Dateien).
  • 10.06.2021: Turing Maschinen (I) [turing-maschinen1.pdf]
  • Beispiele TM: tm-replace-a-b.pdf, tm-left-blank.pdf, tm-copy.pdf
  • Audio-kommentierte Folien (Ordner: "2021-06-10: Turing-Maschinen, Teil 1"; 3 Dateien).
  • 16.06.2021: Turing Maschinen (II) [turing-maschinen2.pdf] (Online: 12.06.2021)
  • Audio-kommentierte Folien (Ordner: "2021-06-16: Turing-Maschinen, Teil 2").
  • 17.06.2021: Turing Maschinen (III) [turing-maschinen3.pdf] (Online: 12.06.2021)
  • Audio-kommentierte Folien (Ordner: "2021-06-17: Turing-Maschinen, Teil 3").
  • 23.06.2021: Turing Maschinen (IV) [turing-maschinen4.pdf] (Online 19.06.2021)
  • Audio-kommentierte Folien (Ordner: "2021-06-23: Turing-Maschinen, Teil 4").
  • 24.06.2021: Q&A Turing Machinen und Entscheidbarkeit
  • 30.06.2021: Komplexität (I) [komplexitaet1.pdf] (Online: 19.06.2021)
  • [komplexitaet1-big-o-notation.pdf] (Online:26.06.2021)
  • Audio-kommentierte Folien (Ordner: "2021-06-30: Komplexität, Teil 1").
  • 1.07.2021: Komplexität (II) [komplexitaet2.pdf]
  • Audio-kommentierte Folien (Ordner: "2021-07-01: Komplexität, Teil 2").
  • 7.07.2021: Komplexität (III) [komplexitaet3.pdf]
  • Audio-kommentierte Folien (Ordner: "2021-07-07: Komplexität, Teil 3").

  • 8.07.2021: Themen; Question/Answer Session
  • Liste mit Themen [themen-gti.pdf]