Q3 · Konzepte und Anwendungen der theoretischen Informatik

Die Themenfelder Q3.1 und Q3.2 bilden den verbindlichen Kern des Kurshalbjahres. In Q3.1 werden Alphabete, Wörter und Sprachen formal beschrieben. Die Lernenden entwickeln und untersuchen Grammatiken, leiten Wörter schrittweise ab, prüfen ihre Ableitbarkeit mit Ableitungsbäumen und übertragen zwischen Grammatiken und Syntaxdiagrammen. Die Einordnung von Grammatiktypen, Sprachklassen und zugehörigen Maschinenmodellen stellt diese Beschreibungsformen in den Zusammenhang der Chomsky-Hierarchie.

Q3.2 führt von der erzeugenden Beschreibung formaler Sprachen zu erkennenden und verarbeitenden Automaten. Zustandsbasierte Systeme werden mit endlichen Automaten modelliert und durch Zustandsdiagramme sowie Übergangstabellen dargestellt. Die Lernenden untersuchen deterministische und nichtdeterministische Automaten, verwenden sie als Akzeptoren und Transduktoren, simulieren die Verarbeitung von Eingaben und beziehen reguläre Ausdrücke, reguläre Grammatiken und endliche Automaten als unterschiedliche Beschreibungen regulärer Sprachen aufeinander. An geeigneten Sprachen werden zugleich die Grenzen endlicher Automaten sichtbar.

In zwei der drei Kurshalbjahre Q1 bis Q3 wird durch den jeweils geltenden Erlass ein weiteres Themenfeld aus den Themenfeldern 3 bis 5 festgelegt. Gehört Q3 zu diesen beiden Kurshalbjahren, ist eines der Themenfelder Q3.3 bis Q3.5 zusätzlich verbindlich. Q3.3 erweitert endliche Automaten um einen Keller und untersucht damit die Verarbeitung geschachtelter sowie kontextfreier Strukturen. Q3.4 behandelt die Turingmaschine als allgemeines Berechnungsmodell und führt zur Frage, welche Probleme algorithmisch lösbar sind; das Halteproblem macht eine prinzipielle Grenze der Berechenbarkeit sichtbar. Q3.5 erschließt mit der Registermaschine ein maschinennahes, programmgesteuertes Berechnungsmodell und verbindet Berechenbarkeit mit elementaren Befehlen, Registern, Sprüngen und Ablaufsteuerung. Innerhalb der verbindlichen Themenfelder kann der Erlass weitere Schwerpunkte und Konkretisierungen ausweisen.

Das D-Book stellt die Inhalte aller fünf Themenfelder bereit. Inhaltsseiten, Aufgabenmodule und Werkzeuge verbinden die Tätigkeiten Beschreiben, Ableiten, Darstellen, Modellieren, Simulieren, Prüfen, Vergleichen und Einordnen. Im Werkzeug für formale Sprachen können Grammatiken und Ableitungen untersucht werden; das Automaten-Werkzeug verbindet Zustandsmodelle, Übergangstabellen, Eingabeverarbeitung und Simulation. Die Seiten zu Keller-, Turing- und Registermaschinen machen Speicherformen und Berechnungsabläufe schrittweise nachvollziehbar. Welche zusätzlichen Themenfelder und Schwerpunkte im jeweiligen Kurs verbindlich sind, richtet sich nach dem geltenden Erlass.

Maßgeblich sind im Kurshalbjahr insbesondere die Kompetenzbereiche Algorithmen, Formale Sprachen und Automaten sowie Informatik, Mensch und Gesellschaft.