1.3.2 Grenzen der Automatisierung auf Basis grundlegender Konzepte der Berechenbarkeitstheorie (z.B. Turingmaschine, endliche Automaten, formale Sprachen) einschätzen
Unterrichtsmaterial zum Lernziel: Die Maturandinnen und Maturanden können Grenzen der Automatisierung auf Basis grundlegender Konzepte der Berechenbarkeitstheorie (z.B. Turingmaschine, endliche Automaten, formale Sprachen) einschätzen.
Theoretische Informatik: P, NP und Komplexität
Das Unterrichtsmaterial führt in die theoretische Informatik ein, behandelt polynomiale und exponentielle Laufzeiten sowie die Komplexitätsklassen P und NP. Anhand von Beispielen wie der Faktorisierung, dem Erfüllbarkeitsproblem (SAT) und dem Travelling Salesman Problem (TSP) wird das fundamentale P-NP-Problem veranschaulicht.
Rechnerarchitektur und Von-Neumann-Rechner
Dieses Unterrichtsmaterial behandelt fundierte Konzepte der Technischen Informatik wie Turingmaschinen, den Aufbau und die Funktionsweise des Von-Neumann-Rechners, logische Schaltungen sowie Assembler-Programmierung mit LMC. Es richtet sich an fortgeschrittene Lerngruppen im Schwerpunktfach oder im Grundlagenfach.
Zustandsmaschinen und endliche Automaten
Dieses Unterrichtsmaterial erklärt das Konzept von Zustandsmaschinen und endlichen Automaten am Beispiel einer Liftsteuerung. Es behandelt Zustände, Ereignisse, State-Event-Tabellen, Zustandsdiagramme sowie die konkrete Implementierung in Python.
Esoterisch Programmieren - Brainfuck
Dieses Unterrichtsmaterial führt in die esoterische Programmiersprache Brainfuck ein und behandelt dabei grundlegende Konzepte der theoretischen Informatik und Turing-Vollständigkeit. Die Lernenden analysieren und verwenden Programme, die mit nur acht Befehlen auskommen.
Kara – Programmieren mit endlichen Automaten
Das Lehrmittel führt Schülerinnen und Schüler ohne Vorkenntnisse spielerisch in die Grundlagen des Programmierens und endliche Automaten ein. Mithilfe des programmierbaren Marienkäfers 'Kara' in einer grafischen Umgebung werden elementare algorithmische Abläufe und logische Bedingungen vermittelt.
TuringKara – zweidimensionale Turing-Maschinen
Das Material stellt die Lernumgebung TuringKara zur Verfügung, mit der das Berechnungsmodell der Turing-Maschine anhand eines zweidimensionalen Ansatzes spielerisch und praktisch ausprobiert werden kann. Es bietet eine breite Palette an Aufgaben wie Invertieren von Bitstrings, Addition von Binärzahlen oder die Universelle Turing-Maschine.
Exorciser: Plattform für Aufgaben zur Theoretischen Informatik
Die Seite beschreibt eine Aufgabensammlung namens Exorciser, die gezielt Übungen zu regulären Sprachen, kontextfreien Grammatiken und Markov-Algorithmen bereitstellt. Sie dient Lehrpersonen und Lernenden zur Vertiefung von Konzepten der theoretischen Informatik wie endlichen Automaten und Grammatiken.
Computation: Berechenbarkeit und reguläre Sprachen
Dieses Unterrichtsmaterial behandelt theoretische Grundlagen der Informatik wie Berechenbarkeit, Berechnungsmodelle und endliche Automaten. Es enthält spielerische Einstiege durch Puzzles sowie praktische Aufgaben zur Mustererkennung mit der Programmierumgebung Kara.
Tutorial Turingmaschine
Dieses Unterrichtsmaterial leitet die Lernenden dazu an, sich das Konzept der Turingmaschine mithilfe eines externen Tutorials selbstständig zu erarbeiten. Dabei werden auch Übungsaufgaben bearbeitet und Fragen für den anschliessenden Unterrichtsdiskurs festgehalten.
Algorithmisch lösbare und algorithmisch unlösbare Probleme: Aufgaben zur Reduktion
Dieses Unterrichtsmaterial stellt zwei Aufgaben zum Thema Reduktion vor. Es ermöglicht Schülerinnen und Schülern an Gymnasien, sich mit der Lösbarkeit von Problemen auseinanderzusetzen, ohne dafür formale Grundlagen der Berechenbarkeitstheorie vorauszusetzen.
Kara – Programmieren mit endlichen Automaten
Das Material stellt fortgeschrittene Anwendungen des Programmierlernsystems Kara vor, darunter den Labyrinth-Besuch mittels Backtracking, die Simulation von Langtons Ameise und den fleissigen Biber zur Veranschaulichung von Turing-Maschinen.
TuringKara: zweidimensionale Turing-Maschinen
Das Material stellt die Programmierumgebung TuringKara vor, die zweidimensionale Turing-Maschinen spielerisch und visuell erfahrbar macht. Es enthält Hinweise auf Programmieraufgaben, Musterlösungen sowie eine Bedienungsanleitung.