FUBMI-WB : Grundlagen der theoretischen Informatik S21 : Syllabus

Syllabus

Syllabus

1. Vorlesung MontagMon Apr 12, 2021 10:15 AM - | 11:45 AM

Begrüßung, Überblick: Sprachen, Automaten, Berechenbarkeit, Entscheidbarkeit (Folie, Video 9 min, mit Smartplayer, MP4-Datei 15 MByte)
Ablauf der Vorlesung (Video 4 min, mit Smartplayer, MP4-Datei ohne Quizfrage 6 MByte)
Ablauf der Übungen (Video 2 min, mit Smartplayer, MP4-Datei 15 MByte)
Wörter über einem Alphabet (Folien,Video 9 min, mit Smartplayer, MP4-Datei ohne Quizfrage 11 MByte)
formale Sprachen (Video 12 min, mit Smartplayer, MP4-Datei 14 MByte)
Entscheidungsprobleme als formale Sprachen
Produkt (Verkettung) und *-Operation
reguläre Ausdrücke, Anwendungen, reguläre Sprachen (Video 14 min, mit Smartplayer, MP4-Datei ohne Quizfrage 19 MByte)

2. Vorlesung MittwochWed Apr 14, 2021 10:15 AM - | 11:45 AM

deterministischer endlicher Automat (DEA) A=(Q,Σ,q₀,δ,F) (Folien, Video 15 min, mit Smartplayer, MP4-Datei 18 MByte)
- Zustandsmenge Q
- Eingabealphabet Σ
- Startzustand q₀
- Übergangsfunktion δ: Q × Σ→Q
- akzeptierende Zustände F⊆Q
erweiterte Übergangsfunktion δ* (Video 13 min, mit Smartplayer, MP4-Datei ohne Quizfragen 15 MByte)
die vom Automaten A akzeptierte Sprache L(A)
Programmieren mit endliche Automaten (Video 22 min, mit Smartplayer, MP4-Datei ohne Quizfrage 27 MByte)

3. Vorlesung MontagMon Apr 19, 2021 10:15 AM - | 11:45 AM

Berechnungsweg eines Automaten (Folien, Video 19 min, mit Smartplayer, MP4-Datei ohne Quizfrage 23 MByte)
nichtdeterministischer endlicher Automat (NEA)
Übergangsrelation δ
Erzeugung von Wörtern durch einen NEA
Beispiele (Video 18 min, mit Smartplayer, MP4-Datei 22 MByte)
→ Netzdienst FLACI zum Herumspielen mit regulären Ausdrücken, Automaten, und Grammatiken
Übergangstabelle, alternative Definition eines NEA
Sprachkunde: der Automat, engl. the automaton, Plural automata (→ Die Automate, Erzählung von E. T. A. Hoffmann)
Simulation aller Berechnungsmöglichkeiten für einen NEA (Folien, Video 9 min, mit Smartplayer, MP4-Datei 11 MByte)
Hauptsatz über reguläre Sprachen (Video 24 min, mit Smartplayer, MP4-Datei 32 MByte)
äquivalente Automaten und äquivalende reguläre Ausdrücke
Potenzmengenkonstruktion

4. Vorlesung MittwochWed Apr 21, 2021 10:15 AM - | 11:45 AM

Syntaxdiagramm eines regulären Ausdrucks als graphische Darstellung (Folien, Video 14 min, mit Smartplayer, MP4-Datei 18 MByte)
NEA mit ε-Übergängen
induktiver Aufbau eines regulären Ausdrucks (Video 12 min, mit Smartplayer, MP4-Datei 14 MByte)
Konstruktion des NEA mit ε-Übergängen
Notwendigkeit der ε-Übergänge (Video 29 min, mit Smartplayer, MP4-Datei 37 MByte)
Elimination der ε-Übergänge
Automaten mit mehreren Startzuständen
Erreichbarkeitsalgorithmus

5. Vorlesung MontagMon Apr 26, 2021 10:15 AM - | 11:45 AM

Algorithmus von Kleene: Erzeugung eines regulären Audrucks für die von einem endlichen Automaten akzeptierte Sprache (Folien, Video 27 min, mit Smartplayer, MP4-Datei ohne Quizfragen 35 MByte)
verwandte Algorithmen: Algorithmus von Warshall zur Erreichbarkeit (transitive Hülle), Algorithmus von Floyd für kürzeste Wege. Dynamische Programmierung (Video 14 min, mit Smartplayer, MP4-Datei 21 MByte)

6. Vorlesung MittwochWed Apr 28, 2021 10:15 AM - | 11:45 AM

Abschlusseigenschaften regulärer Sprachen (Folien, Video 11 min, mit Smartplayer, MP4-Datei 14 MByte)
strukturelle Induktion (Video 35 min, mit Smartplayer, MP4-Datei 45 MByte)
Homomorphismen (Video 12 min, mit Smartplayer, MP4-Datei 15 MByte)
inverse Homomorphismen (Video 12 min, mit Smartplayer, MP4-Datei 15 MByte)

7. Vorlesung MontagMon May 03, 2021 10:15 AM - | 11:45 AM

Das Pumping-Lemma für reguläre Sprachen (Folien, Video 15 min, mit Smartplayer (NUN AUCH MIT Quizfragen), MP4-Datei ohne Quizfragen 19 MByte)
Kontraposition der Pumpinglemmas (Video 17 min, mit Smartplayer, MP4-Datei 20 MByte)
Anwendung des Pumpinglemmas (Video 11 min, mit Smartplayer, MP4-Datei 13 MByte)
Beweis des Pumpinglemmas
Anwendung der Abschlusseigenschaften (Folie, Video 16 min, mit Smartplayer (NUN AUCH MIT Quizfragen), MP4-Datei ohne Quizfragen 19 MByte)

8. Vorlesung MittwochWed May 05, 2021 10:15 AM - | 11:45 AM

die Nerode-Relation ~_L (Folien, Video 14 min, mit Smartplayer, MP4-Datei 18 MByte)
Satz von Myhill-Nerode (Video 9 min, mit Smartplayer, MP4-Datei 12 MByte)
Beweis (Video 12 min, mit Smartplayer, MP4-Datei ohne Quizfrage 15 MByte)
Konstruktion des Automaten aus den Nerode-Klassen (Video 25 min, mit Smartplayer, MP4-Datei 33 MByte)

9. Vorlesung MontagMon May 10, 2021 10:15 AM - | 11:45 AM

Konstruktion des Minimalautomaten mit dem Verfeinerungsalgorithmus (Folien. Nachtrag 10.5. 14:30 Uhr: Auf Seite 3 wurde die Aufspaltung in Unterklassen übersichtlicher dargestellt.)
- Grundidee (Video 13 min, mit Smartplayer, MP4-Datei 17 MByte)
- Beispiel (Video 21 min, mit Smartplayer, MP4-Datei 27 MByte)
- Formulierung des Verfeinerungsalgorithmus
- Korrektheit (Video 23 min, mit Smartplayer, MP4-Datei 30 MByte)
- Laufzeit (Video 13 min, mit Smartplayer, MP4-Datei 18 MByte)
Minimierung nichtdeterministischer Automaten? (Video 4:30 min, mit Smartplayer, MP4-Datei 5 MByte)
Nachtrag 12.5. Beweis, dass der Minimalautomat eindeutig ist (Folien, Video 15 min, mit Smartplayer, MP4-Datei 20 MByte)
- Ergänzung: Startzustand und akzeptierende Zustände (Video 2 min, mit Smartplayer, MP4-Datei 3 MByte)

10. Vorlesung MittwochWed May 12, 2021 10:15 AM - | 11:45 AM

Entscheidungsfragen für reguläre Sprachen (Folien, Video 17 min, mit Smartplayer, MP4-Datei 23 MByte)
Zusammenfassung über reguläre Sprachen
Anwendung: lexikalische Analyse mit flex und JFlex
- Beispieldateien summe.lex beziehungsweise summeJ.lex (Java)
- flex: https://github.com/westes/flex, JFlex: https://jflex.de/
- kurze Übersicht über das Format der wichtigsten Muster (regulären Ausdrücke) in flex. (Auszug aus der Dokumentation, nicht ganz auf dem neuesten Stand)
verwandte Konzepte: Automaten mit Ausgabe, probabilistische Automaten, Markoffketten
Turingmaschinen, Einführung und Beispiel (Folien, Video 25 min, mit Smartplayer, MP4-Datei 32 MByte)
Church-Turing'sche These
formale Definition einer Turingmaschine (Video 25 min, mit Smartplayer, MP4-Datei 31 MByte)
Beispiel ausgearbeitet: Addition von zwei Binärzahlen
Konfiguration, Übergang zwischen Konfigurationen

11. Vorlesung MontagMon May 17, 2021 10:15 AM - | 11:45 AM

Die Church-Turingsche These: Ein Algorithmus ist das, was von einer Turingmaschine berechnet werden kann (Folien, Video 12 min, mit Smartplayer, MP4-Datei ohne Quizfrage 15 MByte)
Programmiertechniken für Turingmaschinen: Unterprogramme, mehrere Spuren auf dem Band, Statusvariablen (Video 15 min, mit Smartplayer, MP4-Datei 20 MByte)
Turingmaschinen mit mehreren Bändern
Einschränkungen: binäres Alphabet, Gruppieren von Bandsymbolen (Video 8 min, mit Smartplayer, MP4-Datei 9 MByte)
fleißige Biber
Berechenbarkeit, Entscheidbarkeit (Folien, Video 23 min, mit Smartplayer, MP4-Datei ohne Quizfragen 30 MByte)
Entscheidungsprobleme und Sprachen
die von einer Turingmaschine akzeptierte Sprache
rekursiv aufzählbare Sprachen
das Halteproblem H
binäre Kodierung einer Turingmaschine
Simulationsprogramm für Turingmaschinen
universelle Turingmaschinen, die universelle Sprache U

12. Vorlesung MittwochWed May 19, 2021 10:15 AM - | 11:45 AM

Die Diagonalsprache D (Folien, Video 18 min, mit Smartplayer, MP4-Datei 21 MByte)
Programme als Daten
Selbstbezüglichkeit
unentscheidbare Probleme, rekursiv aufzählbare Probleme
Computer können nicht alles lösen! (Video 12 min, mit Smartplayer, MP4-Datei ohne Quizfrage 15 MByte)
Untentscheidbarkeit des Halteproblems H
Reduktion von Problem A auf Problem B: A≤B
Abschluss bezüglich Komplement, rekursiv aufzählbar, entscheidbar (Video 19 min, mit Smartplayer, MP4-Datei ohne Quizfrage 26 MByte)
Abschluss gegenüber Mengenoperationen, ˙, * (Video 10 min, mit Smartplayer, MP4-Datei 12 MByte)
Aufzählen der Wörter einer Sprache

13. Vorlesung MittwochWed May 26, 2021 10:15 AM - | 11:45 AM

Unentscheidbare Probleme
- Pflasterung der Ebene (Folien, Video 32 min, mit Smartplayer, MP4-Datei 42 MByte)
- - Wang-Kacheln
- Das Postsche Korrespondenzproblem (Folien, Video 28 min, mit Smartplayer, MP4-Datei 35 MByte)
- nicht berechenbare Funktionen, fleißige Biber (Video 7 min, mit Smartplayer, MP4-Datei 8 MByte)
- diophantische Gleichungen (Video 6 min, mit Smartplayer, MP4-Datei 7 MByte)
- Erkennen von Schadsoftware
Entscheidungsprobleme für L(M) (Folien, Video 17 min, mit Smartplayer, MP4-Datei 21 MByte)
- nichttriviale Eigenschaften von Sprachen
- Ist L(M) leer?
- Satz von Rice, Beweis (Video 11 min, mit Smartplayer, MP4-Datei 13 MByte)

14. Vorlesung MontagMon May 31, 2021 10:15 AM - | 11:45 AM

Unentscheidbarkeit: Folgerungen (Folie, Video 7 min, mit Smartplayer, MP4-Datei 9 MByte)
kontextfreie Grammatiken (Folien)
- Struktur von Sprache (Video 11 min, mit Smartplayer, MP4-Datei 14 MByte)
- Beispiel einer kontextfreien Grammatik für einfache deutsche Sätze
- Regeln (Produktionen)
- Ableitung
- Variablen (Nichtterminalsymbole)
- Terminalsymbole
- Startsymbol
- Definition einer kontextfreien Grammatik G=(Σ,V,P,S), (Video 17 min, mit Smartplayer, MP4-Datei ohne Quizfragen 24 MByte)
- Von einer Grammatik G erzeugte Sprache L(G)
- Ableitungsbaum, Linksableitung
- Beispiele kontextfreier Sprachen: 0ⁿ1ⁿ (Video 22 min, mit Smartplayer, MP4-Datei 27 MByte)
- Beispiel: Palindrome
- Beispiel: ausgeglichene Wörter mit gleich vielen Nullen und Einsen

15. Vorlesung MittwochWed Jun 02, 2021 10:15 AM - | 11:45 AM

EBNF zur Beschreibung der Syntax von Programmiersprachen (Folien, Video 8 min, mit Smartplayer, MP4-Datei 11 MByte)
Nachtrag vom 20. Juni: kontextfreie Datenformate (Video 6 min, mit Smartplayer, MP4-Datei 11 MByte)
- HTML
- XML, Beispiel NEA.xml einer XML-Datei
eindeutige und mehrdeutige Grammatiken (Video 16 min, mit Smartplayer, MP4-Datei 21 MByte)
andere Typen von Grammatiken: die Chomsky-Hierarchie (Folien, Video 12 min, mit Smartplayer, MP4-Datei 16 MByte)
- Typ-0-Sprachen: beliebige Grammatiken
- Typ-1-Sprachen: kontextsensitive Grammatiken
- Typ-2-Sprachen: kontextfreie Sprachen
- Typ-3-Sprachen: reguläre Sprachen
kontextsensitive Sprachen
- Beispiel (Video 8 min, mit Smartplayer, MP4-Datei 9 MByte)
- kontextsensitive Sprachen sind entscheidbar (Video 5:30 min, mit Smartplayer, MP4-Datei 7 MByte)
Typ-0-Sprachen und rekursiv aufzählbare Sprachen (Video 11:30 min, mit Smartplayer, MP4-Datei ohne Quizfrage 14 MByte)

16. Vorlesung MontagMon Jun 07, 2021 10:15 AM - | 11:45 AM

Chomsky-Normalform (CNF) für kontextfreie Sprachen (Folien, Video 27 min, mit Smartplayer, MP4-Datei 34 MByte)
Jede kontextfreie Sprache ist auch kontextsensitiv.
Transformation der Grammatik in CNF
- Schritt 1: Trennung von Variablen und Terminalsymbolen
- Schritt 2: Elimination zu langer Regeln
- Schritt 3: Elimination der ε-Regeln
- Schritt 4: Elimination der Einheitsregeln (Video 10 min, mit Smartplayer, MP4-Datei 12 MByte)
Beispiel 1 (Video 13 min, mit Smartplayer, MP4-Datei 16 MByte)
Beispiel 2: eindeutige Grammatik für arithmetische Ausdrücke (Video 12 min, mit Smartplayer, MP4-Datei 14 MByte)

17. Vorlesung MittwochWed Jun 09, 2021 10:15 AM - | 11:45 AM

Nachtrag: Turing-Reduktion und Karp-Reduktion (Folie, Video 11 min, mit Smartplayer, MP4-Datei 15 MByte)
Das Wortproblem für kontextfreie Sprachen (Folien, Video 14 min, mit Smartplayer, MP4-Datei 17 MByte)
CYK-Algorithmus von Cocke, Younger, Kasami
- Beispiel (Video 20 min, mit Smartplayer, MP4-Datei 27 MByte)
- Laufzeit
das Pumpinglemma für kontextfreie Sprachen (Folien, Video 22 min, mit Smartplayer, MP4-Datei 27 MByte)
- Beweis

18. Vorlesung MontagMon Jun 14, 2021 10:15 AM - | 11:45 AM

Anwendung des Pumpinglemmas (Folien, Video 22 min, mit Smartplayer, MP4-Datei 26 MByte)
Abschlusseigenschaften kontextfreier Sprachen (Folien, Video 9 min, mit Smartplayer, MP4-Datei 11 MByte)
Entscheidungsfragen über kontextfreie Sprachen (Video 10 min, mit Smartplayer, MP4-Datei 13 MByte)
Die Dyck-Sprache der ausgeglichenen Klammerausdrücke (Video 5 min, mit Smartplayer, MP4-Datei 5 MByte)

19. Vorlesung MittwochWed Jun 16, 2021 10:15 AM - | 11:45 AM

Kellerautomaten K=(Σ,Γ,Q,Z₀,q₀,δ,F) (Folien, Video 29 min, mit Smartplayer, MP4-Datei 36 MByte)
- Eingabealphabet Σ
- Kelleralphabet Γ
- Zustandsmenge Q
- Kellergrundsymbol Z₀
- Startzustand q₀∈Q
- Übergangsrelation δ ⊆ Q × Σ × Γ × Q × Γ^*
- akzeptierende Zustände F⊆Q
Konfigurationen (q,w,γ) (Folien, Video 22 min, mit Smartplayer, MP4-Datei 28 MByte)
Akzeptieren durch Endzustand L(K)
Akzeptieren durch leeren Keller N(K)
Kellerautomaten akzeptieren genau die kontextfreien Sprachen (Folien)
- Grammatik G → Kellerautomat K (Video 12 min, mit Smartplayer, MP4-Datei 17 MByte)
- Kellerautomat K → Grammatik G
  - Elimination der Zustände (Video 26 min, mit Smartplayer, MP4-Datei 33 MByte)
  - Konstruktion der Grammatik G (Video 4 min, mit Smartplayer, MP4-Datei 6 MByte)

20. (letzte) Vorlesung MontagMon Jun 21, 2021 10:15 AM - | 11:45 AM

Schnitt einer kontextfreien Sprache mit einer regulären Sprache (Folien)
- Beweis 1: Kellerautomat, Video 10 min, mit Smartplayer, MP4-Datei 12 MByte)
- Beweis 2: Tripelkonstruktion, Video 9 min, mit Smartplayer, MP4-Datei 11 MByte)
deterministische kontextfreie Sprachen (Folien, Video 17 min, mit Smartplayer, MP4-Datei 21 MByte)
- deterministische Kellerautomaten
- Zusammenhang zu eindeutigen Grammatiken
- spezielle kontextfreie Grammatiken für Programmiersprachen
- Werkzeuge: bison (yacc) in Zusammenarbeit mit flex
Ergänzung: deterministische 2-Wege-Kellerautomaten und das Teilwortproblem (Folie, Video 6 min, mit Smartplayer, MP4-Datei 7,5 MByte)
- aus der Vorlesung Algorithmen, Datenstrukturen, Datenabstraktion vom Wintersemester 2020/2021:
  - Hintergrund und Entstehung des Algorithmus von Knuth-Morris-Pratt (1977) für das Teilwortproblem (Video 8 min, mit Smartplayer, MP4-Datei 8 MByte, aus der 10. Vorlesung vom 3. 12. 2020)
  - deterministische 2-Wege-Kellerautomaten (Folien, aus der 25. Vorlesung vom 9. 2. 2021, siehe auch Inhaltsverzeichnisse der Videos)
    - direkte Simulation (Video 13:30 min, mit Smartplayer, MP4-Datei 17 MByte)
    - gegliederte Simulation, Abkürzung durch Merken (Video 18 min, mit Smartplayer, MP4-Datei 21 MByte)
Nachtrag: kontextfreie Datenformate (Folie, Video 6 min, mit Smartplayer, MP4-Datei 11 MByte)
- HTML
- XML, Beispiel NEA.xml einer XML-Datei
Zusammenfassung und Ausblick (Folien, Video 15 min, mit Smartplayer, MP4-Datei 18 MByte)

Montag: Technischer Testlauf zur OnlineklausurMon Jun 28, 2021 10:15 AM - | 11:45 AM

KlausurWed Jul 07, 2021 10:15 AM - | 11:45 AM

Tools list begins here

Content begins here

1. Vorlesung MontagMon Apr 12, 2021 10:15 AM - | 11:45 AM

2. Vorlesung MittwochWed Apr 14, 2021 10:15 AM - | 11:45 AM

3. Vorlesung MontagMon Apr 19, 2021 10:15 AM - | 11:45 AM

4. Vorlesung MittwochWed Apr 21, 2021 10:15 AM - | 11:45 AM

5. Vorlesung MontagMon Apr 26, 2021 10:15 AM - | 11:45 AM

6. Vorlesung MittwochWed Apr 28, 2021 10:15 AM - | 11:45 AM

7. Vorlesung MontagMon May 03, 2021 10:15 AM - | 11:45 AM

8. Vorlesung MittwochWed May 05, 2021 10:15 AM - | 11:45 AM

9. Vorlesung MontagMon May 10, 2021 10:15 AM - | 11:45 AM

10. Vorlesung MittwochWed May 12, 2021 10:15 AM - | 11:45 AM

11. Vorlesung MontagMon May 17, 2021 10:15 AM - | 11:45 AM

12. Vorlesung MittwochWed May 19, 2021 10:15 AM - | 11:45 AM

13. Vorlesung MittwochWed May 26, 2021 10:15 AM - | 11:45 AM

14. Vorlesung MontagMon May 31, 2021 10:15 AM - | 11:45 AM

15. Vorlesung MittwochWed Jun 02, 2021 10:15 AM - | 11:45 AM

16. Vorlesung MontagMon Jun 07, 2021 10:15 AM - | 11:45 AM

17. Vorlesung MittwochWed Jun 09, 2021 10:15 AM - | 11:45 AM

18. Vorlesung MontagMon Jun 14, 2021 10:15 AM - | 11:45 AM

19. Vorlesung MittwochWed Jun 16, 2021 10:15 AM - | 11:45 AM

20. (letzte) Vorlesung MontagMon Jun 21, 2021 10:15 AM - | 11:45 AM

Montag: Technischer Testlauf zur OnlineklausurMon Jun 28, 2021 10:15 AM - | 11:45 AM

KlausurWed Jul 07, 2021 10:15 AM - | 11:45 AM