• Syllabus

Print View

1. VorlesungFri Apr 25, 2025 12:15 PM -  | 01:45 PM

  • Fleißige Biber
  • LOOP-berechenbare Funktionen
  • nicht (LOOP-) berechenbare Funktionen

2. VorlesungFri May 02, 2025 12:15 PM -  | 01:45 PM

  • primitiv-rekursive Funktionen
  • Primzahlkodierung (Gödelnummern)
  • LOOP-berechenbare Funktionen sind primitiv-rekursiv

3. VorlesungFri May 09, 2025 12:15 PM -  | 01:45 PM

  • primitiv-rekursive Funktionen sind LOOP-berechenbar
  • WHILE und GOTO
  • Registermaschinen (Zählerautomaten)
    • endliche Anzahl an Registern mit unendlichem Wertebereich
    • Gegensatz: Turingmaschinen mit unendlichem Band und endlichem Alphabet
  • Registermaschinen mit 2 Registern (Zählerautomaten) können Turingmaschinen simulieren

4. VorlesungFri May 16, 2025 11:45 AM -  | 01:15 PM

  • Zählerautomaten mit 1 Zähler: Entscheidbarkeit des Halteproblems
  • Minimierung (μ-Rekursion)
  • Partielle Funktionen, berechenbare (partielle) Funktionen
  • Algorithmen, die Programme bearbeiten: Editor, Präprozessor, Makros erweitern, Compiler, Analysewerkzeuge
  • Begriffe/Programme verwenden und erwähnen
  • Selbstdruckende Programme (in Python)

5. VorlesungFri May 23, 2025 12:15 PM -  | 01:45 PM

6. VorlesungFri May 30, 2025 12:15 PM -  | 01:45 PM

  • Beweis der Rekursionssatzes für Turingmaschinen
  • Verstecken von Hintereingängen
  • Satz von Rice
  • Kontextfreie Grammatiken

7. VorlesungFri Jun 06, 2025 12:15 PM -  | 01:45 PM

  • Nichtdeterministische Kellerautomaten: Definition
  • Kontextfreie Sprachen und Kellerautomaten

8. VorlesungFri Jun 13, 2025 12:15 PM -  | 01:45 PM

  • Gültige Konfigurationsfolge für Turingmaschinen
  • Entscheidbare und unentscheidbare Probleme für kontextfreie Sprachen
    • Schnitt zweier Sprachen
    • Ist das Komplement leer?
  • Ist das Komplement eines regulären Ausdrucks leer?

9. Vorlesung - per VideoFri Jun 20, 2025 12:15 PM -  | 01:45 PM

  • deterministische 2-Wege-Kellerautomaten und das Teilwortproblem (Folien)
    Achtung: Der Keller in den Videos und in den Folien ist von links nach rechts als v1v2…vm dargestellt mit vm als oberstem Kellersymbol, im Gegensatz zur sonst verwendeten Konvention.
    • direkte Simulation (Video 13:30 min, mit Smartplayer, MP4-Datei 17 MByte)
      Videoinhalt
      Nachtrag zum Teilwortproblem 0:00
      Überblick 0:56
      deterministischer 2-Wege-Kellerautomat 1:38
      Eingabeband (nur zum Lesen) 1:43
      Zustandsmenge Q 2:53
      Startzustand q0 3:00
      Kelleralphabet Γ 3:06
      Stapelgrundsymbol Z0 3:36
      Eingabealphabet Σ 4:17
      Übergangsfunktion δ 4:49
      Startkonfiguration 6:05
      Beendung 6:20
      akzeptierende Zustandsmenge F 6:51
      unendliche Schleife 7:21
      Lösung des Teilwortproblems 7:30
      Programmzähler 8:40
      Laufzeit 9:14
      exponentielle Laufzeit: Binärzähler 9:30
      Simulation in linearer Zeit 10:06
      direkte Simulation 10:32
      Abbruchbedingung 10:57
      Ausführung eines Schrittes 11:21
      Beendigung nur mit leerem Stapel 12:44
    • gegliederte Simulation, Abkürzung durch Merken (Video 18 min, mit Smartplayer, MP4-Datei 21 MByte)
      Videoinhalt
      gegliederte Simulation 0:00
      Veränderung des Stapels 1:19
      Ergebnis der Simulationsfunktion 2:31
      rekursive Simulationsfunktion 2:56
      Akzeptieren der Eingabe 5:48
      Vergleich mit der direkten Simulation 6:53
      Vorteil 7:31
      Systematische Reihenfolge der Teilprobleme? 8:27
      Merken der Ergebnisse 8:56
      Unendliche Rekursion 10:27
      Unendliche Schleife im Kellerautomaten 11:15
      Statusabfrage zu Beginn 12:44
      Statusänderung am Ende 13:40
      lineare Laufzeit 13:50
      Zählen der Aufrufe 14:31
      Zusammenfassung und Rückblick 16:06
  • Nachtrag: Hintergrund und Entstehung des Algorithmus von Knuth-Morris-Pratt (1977) zur Teilwortsuche (Video 8 min, mit Smartplayer, MP4-Datei 8 MByte)

10. Vorlesung - per VideoFri Jun 27, 2025 12:15 PM -  | 01:45 PM

Vorlesung - 11Fri Jul 04, 2025 12:15 PM -  | 01:45 PM

Vorlesung - 12Fri Jul 11, 2025 12:15 PM -  | 01:45 PM

Vorlesung - 13Fri Jul 18, 2025 12:15 PM -  | 01:45 PM

Vorlesung - 14 FERIEN!Fri Jul 25, 2025 12:15 PM -  | 01:45 PM