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.
Automaten und Sprachen
Dieses umfassende Unterrichtsportal behandelt zustandsbasierte Modellierung, formale Sprachen, reguläre Ausdrücke, Automaten wie Kellerautomaten und Turingmaschinen sowie die Entwicklung von Compilern und Interpretern. Es bietet tiefgehende theoretische und praktische Inhalte speziell für das Informatik-Schwerpunktfach am Gymnasium.
Advent of Code: Monster Messages (Formale Grammatiken und Parsing)
In dieser Programmieraufgabe sollen Nachrichten anhand einer kontextfreien Grammatik validiert werden. Das Material eignet sich hervorragend, um fortgeschrittene Programmierkonzepte sowie theoretische Grundlagen wie formale Sprachen und Grammatiken praktisch anzuwenden.
Einführung in Kara den Marienkäfer
Dieses Unterrichtsmaterial führt in die Programmierumgebung von Kara dem Marienkäfer ein, welcher als endlicher Automat grafisch programmiert werden kann. Es enthält Installationshinweise, eine Kurzanleitung zur Bedienung und verweist auf integrierte Programmieraufgaben.
Endliche Automaten
Das Material führt anhand alltäglicher Beispiele wie Lichtschalter und Getränkeautomaten in das Konzept endlicher Automaten ein. Es behandelt sowohl Zustandsübergangsdiagramme als auch -tabellen und bietet integrierte Aufgaben für Schülerinnen und Schüler.
Probe zu Endlichen Automaten, Kara und Regulären Ausdrücken
Eine schriftliche Leistungsüberprüfung (Probe auf Papier) für den Informatikunterricht. Die Lernenden werden zu endlichen Automaten, Kara-Programmen und regulären Ausdrücken geprüft.
Advent of Code: The Halting Problem (Turing-Maschine)
Eine Programmieraufgabe im Rahmen von Advent of Code, bei der eine einfache Turing-Maschine simuliert werden muss, um einen Zustand nach einer bestimmten Anzahl von Schritten zu berechnen. Das Material eignet sich gut für fortgeschrittene Schülerinnen und Schüler, um theoretische Grundlagen der Informatik praktisch anzuwenden.
Exkurs: Grenzen der rekursiven Verarbeitung bei realen Systemen an der Leibniz-Reihe
Das Material behandelt die Annäherung der Kreiszahl Pi mithilfe der Leibniz-Reihe. Anhand von Codebeispielen in Python werden iterative und rekursive Lösungsansätze verglichen und die Grenzen der Rekursionstiefe bei realen Systemen thematisiert.
Die Turingmaschine
Der Text erklärt das theoretische Modell der Turingmaschine, ihren Aufbau mit Band und Lese-/Schreibkopf sowie ihre Funktionsweise anhand von Zuständen und Übergangstabellen. Zudem wird auf die Churchsche These und die Grenzen der Automatisierung eingegangen.
Einführung in endliche Automaten
Dieses Unterrichtsmaterial führt in das Konzept der endlichen Automaten als Modell für einfache Berechnungen und Spracherkennung ein. Es erklärt, wie Automaten Wörter anhand von Zustandsübergängen verarbeiten und akzeptieren.
Endliche Automaten
Dieses Unterrichtsmaterial führt in das Konzept der endlichen Automaten als grundlegendes Berechnungsmodell der theoretischen Informatik ein. Es behandelt formale Definitionen, die Eigenschaften von Akzeptoren sowie Anwendungsgebiete in der Spracherkennung.
Klassifizierung von Grammatiken und die Chomsky-Hierarchie
Dieses Material erklärt die Chomsky-Hierarchie formaler Grammatiken und Sprachen, von Typ 0 bis Typ 3. Es geht auf die Unterscheidung zwischen kontextfreien und kontextsensitiven Grammatiken ein und liefert mathematische Definitionen sowie Beispiele.
Einführung in die Grammatiken
Dieses Unterrichtsmaterial führt formal in den Begriff und den Aufbau von formalen Grammatiken ein. Es definiert die Bestandteile eines 4-Tupels inklusive Variablen, Alphabet, Produktionsregeln und Startsymbol.
Wörter und Sprachen in der theoretischen Informatik
Das Material führt formal in die Grundbegriffe der theoretischen Informatik ein und definiert präzise, was unter Wörtern, Alphabeten und formalen Sprachen verstanden wird.
Was sind Sprachen - Alphabete und formale Grundlagen
Das Material führt formale Grundlagen für die Arbeit mit Texten in der Informatik ein. Es definiert den Begriff des Alphabets und nennt gängige Beispiele wie das boolesche oder das lateinische Alphabet.
Beispiele formaler Sprachen
Das Unterrichtsmaterial erläutert das Konzept formaler Sprachen an Hand von Beispielen wie der Relationenalgebra, SQL, Python und römischen Zahlen. Es zeigt auf, wie Alphabete, Wörter und gültige Sprachmengen mathematisch-formal definiert werden.
Sprachen und Automaten
Dieses Unterrichtsmaterial führt in die theoretischen Grundlagen formaler Sprachen in der Informatik ein und erklärt deren Bedeutung für die automatisierte Datenverarbeitung sowie Programmiersprachen. Es werden verschiedene Konzepte zur präzisen Sprachfestlegung vorgestellt.
Berechenbarkeit und algorithmische Lösbarkeit
Dieses Unterrichtsmaterial führt in die theoretischen Grundlagen der Berechenbarkeit und die Grenzen der Automatisierung ein. Es behandelt thematisch das Halteproblem sowie die theoretische Fundierung und Reichweite algorithmischer Methoden.
Exorciser: Interaktive Übungen zur theoretischen Informatik
Exorciser ist eine interaktive Lernplattform zur automatischen Generierung und Korrektur von Aufgaben aus der theoretischen Informatik. Das Material deckt Themen wie reguläre Sprachen, endliche Automaten, kontextfreie Grammatiken und Markov-Algorithmen ab und bietet sofortiges individuelles Feedback.
Einführung in endliche Automaten
Dieses Unterrichtsmaterial führt in das Konzept endlicher Automaten ein. Die Lernenden lernen, Automaten als Zustandsübergangsdiagramme darzustellen, einfache Probleme damit zu lösen und verstehen das Grundprinzip regulärer Ausdrücke.
Einführung in endliche Automaten
Ein Unterrichtstipp für Lehrpersonen zur Vermittlung endlicher Automaten (Finite State Automata). Anhand eines anschaulichen Beispiels mit Zügen und Stationen entdecken Lernende die Notwendigkeit von Zuständen, Übergängen (Transitions) und akzeptierenden Endzuständen.
Treasure Island: Endliche Automaten
Dieses Material bietet druckbare Arbeitsblätter für die 'Treasure Island'-Aktivität, bei der Schülerinnen und Schüler auf spielerische Weise endliche Automaten kennenlernen. Es enthält eine Karte für jeden Teilnehmenden sowie einen Satz Insel-Poster zur Durchführung der Aktivität im Unterricht.
Einführung in die Berechenbarkeit und Turingmaschinen
Das Material führt theoretische Grundlagen der Informatik ein, indem es den Begriff der Berechenbarkeit definiert und die Notwendigkeit mathematisch exakter Algorithmusbegriffe wie Turingmaschinen erläutert.
Nichtdeterministische Endliche Automaten (NEA)
Das Unterrichtsmaterial erklärt die Definition und Funktionsweise von nichtdeterministischen endlichen Automaten (NEA) im Vergleich zu deterministischen endlichen Automaten (DEA). Anhand mathematischer Formalismen und konkreter Beispiele wird aufgezeigt, wie Übergänge und Zustandsfolgen bei NEAs funktionieren.
Der Getränkeautomat als endlicher Automat
Dieses Unterrichtsmaterial erklärt anhand eines Cola-Automaten anschaulich die formale Definition und die Bestandteile eines endlichen Automaten. Es werden Zustände, das Alphabet, der Startzustand, die Überführungsfunktion und der Endzustand mathematisch-formal hergeleitet.
Einführung in Grammatiken und formale Sprachen
Das Material vermittelt die theoretischen Grundlagen von Grammatiken und formalen Sprachen im Kontext der theoretischen Informatik. Es behandelt die Chomsky-Hierarchie, reguläre und kontextfreie Grammatiken sowie deren Bedeutung für den Compilerbau und den Bezug zu endlichen Automaten.
Termersetzung und formale Grammatiken
Das Material erklärt anhand eines konkreten Beispiels, wie Wörter einer formalen Sprache durch schrittweise Termersetzung und Produktionsregeln ausgehend von einem Startsymbol abgeleitet werden. Dabei wird die Anwendung von Grammatiken und Ableitungen nachvollziehbar dargestellt.
EBNF-Syntaxdefinition von Wirth
Das Material beschreibt die formale Syntax der Erweiterten Backus-Naur-Form (EBNF) anhand von präzisen Grammatikregeln. Es dient als theoretische und formale Grundlage für das Verständnis von Programmiersprachen und Grammatiken.
Anwendungen formaler Sprachen
Der Text führt in die praktischen Anwendungen formaler Sprachen ein, wie etwa die Eingabevalidierung mittels regulärer Ausdrücke bei Webformularen. Zudem werden die grundlegenden Funktionen von Compilern und Interpretern als Übersetzungsprogramme für Hochsprachen wie Python erläutert.
Einführung in den untypisierten Lambda-Kalkül und Church-Booleans
Das Material erklärt anhand eines Beispiels den untypisierten Lambda-Kalkül, die Darstellung von Wahrheitswerten als Church-Booleans und den Aufbau von Ausdrücken mittels Bäumen, Abstraktionen und Applikationen.
Scottish Country Dance und Theoretische Informatik
Dieses Unterrichtsmaterial verbindet Scottish Country Dance visuell und musikalisch mit Konzepten der Theoretischen Informatik wie formellen Sprachen und Automaten. Es ist als anschauliches Projekt konzipiert, das theoretische Informatikkonzepte greifbar macht.
Einführung in die Programmierung und endliche Automaten mit Kara
Dieser Kurs führt anhand des programmierbaren Marienkäfers Kara in endliche Automaten und das Programmieren ein. Die Lernenden erarbeiten sich schrittweise und eigenständig Programmierkonzepte durch eine Reihe von Aufgaben mit ansteigendem Schwierigkeitsgrad. Das Material enthält Folien, Aufgaben mit Lösungen sowie Zusatzmaterial.
TuringKara: Zweidimensionale Turing-Maschinen
Das Material stellt TuringKara vor, eine zweidimensionale Erweiterung der Turing-Maschine, die mit Aufgaben, Musterlösungen und einer Bedienungsanleitung für den spielerischen und praktischen Einstieg in die theoretische Informatik und Programmierkonzepte genutzt werden kann.
TuringKara – zweidimensionale Turing-Maschinen
TuringKara ist eine interaktive Lernumgebung, die das Berechnungsmodell der Turing-Maschine auf einem zweidimensionalen Blatt anschaulich macht. Das Material enthält ausführliche Programme, Aufgabenstellungen und Anleitungen zur praktischen Auseinandersetzung mit theoretischer Informatik.
Kara - Programmieren mit endlichen Automaten
Das Material stellt den Marienkäfer Kara vor, eine Programmierumgebung zur spielerischen Steuerung mittels endlicher Automaten und Sensoren. Integrierte Aufgaben mit Lösungen und eine Bedienungsanleitung erleichtern den direkten Einstieg im Unterricht.
Kara – Programmieren mit endlichen Automaten
Das Material stellt die Programmierumgebung Kara vor, in welcher ein Marienkäfer mittels endlicher Automaten gesteuert wird. Es bietet einen spielerischen und intuitiven Einstieg in grundlegende Programmierkonzepte und Berechnungsmodelle für Einsteigerinnen und Einsteiger.
Computation: Berechenbarkeit, reguläre Sprachen und endliche Automaten
Dieses Unterrichtsmaterial führt spielerisch und theoretisch in die theoretische Informatik ein. Es behandelt Berechenbarkeit, kombinatorische Explosion anhand eines Puzzles und die Mustererkennung mit dem Lernprogramm Kara.
Esoterisch Programmieren - Brainfuck
Dieses Unterrichtsmaterial bietet eine Einführung in die esoterische Programmiersprache Brainfuck und behandelt theoretische Informatikkonzepte wie Turing-Vollständigkeit. Es enthält Unterlagen für Schülerinnen und Schüler, Lehrpersonen sowie die dazugehörigen Lösungen und Programmquellen.
Exorciser: Interaktives Übungswerkzeug zur theoretischen Informatik
Das Material stellt den «Exorciser» vor, ein Java-basiertes und interaktives Werkzeug zur automatischen Generierung und Bewertung von strukturierten Übungen in der theoretischen Informatik. Es bietet Studierenden die Möglichkeit, ihr Wissen zu überprüfen und sofortiges, feingranulares Feedback zu erhalten.
Kara für Profis: Endliche Automaten und Turing-Maschinen
Der Text präsentiert fortgeschrittene Aufgaben und theoretische Konzepte für die Programmierumgebung Kara, darunter Labyrinth-Besuche durch endliche Automaten, Langtons Ameise und die Simulation von Turing-Maschinen als fleissige Biber.
Einführung in formale Sprachen und Grammatiken
Das Material bietet einen kurzen theoretischen Überblick über formale Sprachen in der Informatik. Es erklärt den Unterschied zu natürlichen Sprachen und beschreibt die Bedeutung von Syntax, Semantik und formalen Grammatiken.
Algorithmisch lösbare und unlösbare Probleme: Aufgaben zur Reduktion
Das Unterrichtsmaterial stellt zwei Aufgaben zum Thema Reduktion vor, die für Gymnasien konzipiert sind. Es wird auf formale Grundlagen der Berechenbarkeit und Komplexität verzichtet.
Tutorial Turingmaschine
Die Schülerinnen und Schüler erarbeiten sich das Thema Turingmaschinen anhand eines externen Tutorials der Seite Matheprisma. Sie lösen dazu Übungsaufgaben mit Lösungen und bereiten offene Fragen für den Unterricht vor.
Einführung in die Komplexitätstheorie und das P-NP-Problem
Der Text behandelt grundlegende Konzepte der theoretischen Informatik wie Laufzeitkomplexität, die Komplexitätsklassen P und NP sowie das berühmte P-NP-Problem. Anhand von Beispielen wie der Primfaktorzerlegung, dem Erfüllbarkeitsproblem SAT und dem Travelling Salesman Problem werden diese theoretischen Konzepte greifbar gemacht.
Einführung in die Programmiersprache BlooP
Der Text stellt die theoretische Programmiersprache BlooP vor, die von Douglas Hofstadter entwickelt wurde, um das Halteproblem und Bounded Loops zu veranschaulichen. Anhand von Beispielen wie einer Fakultätsberechnung und einem Nim-Spiel werden grundlegende algorithmische Strukturen erläutert.
Reguläre Ausdrücke
Der Text führt kurz in das Thema der regulären Ausdrücke und deren formale Definition als Typ-3-Sprachen der Chomsky-Hierarchie ein. Am Ende ist eine leere Übungssektion angehängt, wodurch der Inhalt eher rudimentär bleibt.
Schatzinselaktivität zu endlichen Automaten
Dieses Material bietet Ausdrucke und Inselposter für eine spielerische Aktivität, um das Konzept endlicher Automaten zu erkunden. Die Ressource ist für den praktischen Einsatz im Unterricht konzipiert.