Q3 – Theoretische Informatik

Lernvideos

1. Registermaschinen
   • 1.1 Aufbau und Funktion (4 min)
   • 1.2 Registermaschinenprogramme (8 min)
   • 1.3 Befehlssatz und Beispiele (12 min)
2. Formale Sprachen
   • 2.1 Aphabet, Wort, Sprache, Grammatik
   • 2.2 Reguläre und kontextfreie Sprachen
   • 2.3 Die Chomsky-Hierarchie (nur LK) (6 min)
   • 2.4 Syntax-Diagramme
3. Endliche Automaten
   • 3.1 Akzeptoren (8 min)
   • 3.2 Grenzen endlicher Automaten (6 min)
   • 3.3 Nicht-Determinismus und Potenzmengenkonstruktion (nur LK) (10 min)
   • 3.4 Schreibende Automaten (Mealy-Automaten) (4 min)
   • 3.5 Beschreibung realer Automaten (2 min)
     • Bonus-Video: Endliche Automaten in Videospielen
   • 3.6 Reguläre Ausdrücke (12 min)
4. Kellerautomaten (nur LK)
5. Berechenbarkeit
   • 5.1 Computer, Probleme, Algorithmen und Berechenbarkeit
   • 5.2 Turingmaschinen
   • 5.3 Die Hypothese von Church
   • 5.4 Die universelle Turingmaschine
   • 5.5 Probleme als partielle Funktionen
   • 5.6 Nicht-berechenbare Probleme
   • 5.7 Das Halteproblem
6. Grundlagen der Komplexitätstheorie
   • 6.1 Laufzeit und O-Notation
   • 6.2 Klassifizierung von Problemen
   • 6.3 P=NP?

Materialien

• YouTube: „Wie der erste Compiler die Programmierung revolutionierte“
• Automat-Simulator: Simuliert endliche Automaten und Kellerautomaten
• Turing-Maschinen-Simulator: von Anthony Morphett
• Turing-Maschinen-Simulator: von mir 🙂
• Registermaschinen-Simulator: von einem Darmstädter Schüler!
• Registermaschinen-Simulator: von mir 🙂
• Grammatik-Playground: Hier kann man kontextfreie Grammatiken testen.
• RegExp-Tester: Dient zum Testen regulärer Ausdrücke.
• Railroad-Diagram-Generator: Generiert Syntax-Diagramme.
• DrawDiagram: Generiert Syntax-Diagramme. Um eine passable Auflösung zu erreichen, muss man die Font- und Rule-Sizes erhöhen.
  Beispiel für eine Zahl mit optionalem Komma:
  Zahl = ('0' | '1' | '…' | '9'), { ('0' | '1' | '…' | '9') }, (',', ('0' | '1' | '…' | '9'), { ('0' | '1' | '…' | '9') }|);

Arbeitsblätter

• AB 1: Formale Sprachen und Grammatiken
• AB 2: Syntaxdiagramme, reguläre und kontextfreie Sprachen
• AB 3: Endliche Automaten
• AB 4: Reguläre Ausdrücke
• AB 5: Nicht-Determinusmus und Potenzmengenkonstruktion
• AB 5: Turingmaschinen
• AB 6: Turing-Vollständigkeit (nur LK)
• AB 7: Berechenbarkeit
• AB 8: Komplexitätstheorie
• AB 9: Abschluss