1.3 Theoretische Informatik – Unterrichtsmaterial
Algorithmen und Datenstrukturen: Sortieren und Suchbäume
Ausführliche Vorlesungsnotizen und Erklärungen zu klassischen Sortieralgorithmen wie Bubblesort, Selection Sort, Insertion Sort und Heapsort sowie zu binären Suchbäumen und deren Traversierung. Das Material vermittelt die theoretischen Grundlagen und Laufzeitanalysen (O-Notation) für effiziente Datenverarbeitung.
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.
Aufwandsanalyse von Sortieralgorithmen
Das Unterrichtsmaterial führt in die Aufwandsanalyse von klassischen Sortieralgorithmen wie Selectionsort, Insertionsort, Bubblesort und Quicksort ein. Die Lernenden zählen Vergleiche, betrachten Best- und Worst-Case-Szenarien und analysieren die Kostenfunktionen in Abhängigkeit von der Problemgröße.
Laufzeitverhalten von Sortieralgorithmen
Das Material führt experimentell in die Laufzeitanalyse verschiedener Sortieralgorithmen (wie Selection Sort, Insertion Sort, Bubble Sort und Quicksort) mithilfe von Python ein. Die Lernenden messen systematisch Rechenzeiten, analysieren Gesetzmäßigkeiten und untersuchen den Einfluss verschiedener Implementierungen.
Der Graham-Scan-Algorithmus zur Bestimmung der konvexen Hülle
Dieses Unterrichtsmaterial erklärt detailliert den Graham-Scan-Algorithmus zur Berechnung der konvexen Hülle einer Punktmenge in der Computergeometrie. Es behandelt den theoretischen Hintergrund, die mathematische Korrektheit, eine vollständige Implementierung in C++ sowie eine Laufzeit- und Speicheranalyse.
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.
Laufzeit- und Speicherkomplexität (Big-O-Notation) in Perl
Der Artikel erklärt praxisnah anhand von Codebeispielen in Perl verschiedene Stufen der Zeit- und Speicherkomplexität (von O(1) bis O(n!) und O(2^n)). Dabei werden grundlegende algorithmische Muster wie Suchen, Sortieren, Rekursion und Backtracking beleuchtet.
Aufwandsanalyse von Suchalgorithmen (Linear und Binär)
Dieses Unterrichtsmaterial behandelt die Aufwandsanalyse von Algorithmen am Beispiel der linearen und binären Suche. Anhand von Aufgaben analysieren die Lernenden den Best-Case und Worst-Case sowie die Laufzeitkomplexität in Abhängigkeit von der Listenlänge.
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.
Exkurs: Rekursive Berechnungen mit hohem Aufwand
Das Material behandelt rekursive Funktionen in Python anhand des Galtonbretts und der Ackermann-Funktion. Es analysiert die Ineffizienz kaskadenartiger und verschachtelter Rekursionen durch Beobachtung der Funktionsaufrufe und Reduktionsketten.
Übungen zur Untersuchung und Verbesserung der Algorithmischen Effizienz in Python
Das Material enthält Übungsaufgaben zur Analyse und Steigerung der Effizienz von Algorithmen anhand von Python-Code. Die Lernenden untersuchen verschiedene Implementierungen von Potenzierungs- und Primzahltests und vergleichen deren Leistungsfähigkeit.
Effizienz von Algorithmen am Beispiel des Euklidischen Algorithmus
Das Material vergleicht zwei Algorithmen zur Bestimmung des grössten gemeinsamen Teilers (Wechselwegnahme und Euklidischer Algorithmus) hinsichtlich ihrer Effizienz und des Laufzeitverhaltens. Es führt grundlegende Begriffe wie die Äquivalenz und Ressourceneinsparung von Algorithmen ein.
Aktionen zählen mit Python
Dieses Unterrichtsmaterial zeigt anhand eines Python-Programms zum Euklidischen Algorithmus, wie durch den Einsatz von Zählvariablen die Anzahl der Schleifendurchläufe bestimmt werden kann. Die Lernenden führen das Programm aus und untersuchen die Laufzeitunterschiede bei unterschiedlichen Eingabewerten.
Swiss Olympiad in Informatics - First Round Tasks
Eine Sammlung von fortgeschrittenen algorithmischen Programmieraufgaben und theoretischen Fragestellungen aus der ersten Runde der Schweizer Informatik-Olympiade, die sich mit Graphentheorie, dynamischer Programmierung und Datenstrukturen befassen.
Swiss Olympiad in Informatics (SOI) Aufgaben und Material
Das Material enthaelt verschiedene anspruchsvolle Programmier- und Algorithmenaufgaben im Rahmen der Schweizer Informatik-Olympiade (SOI). Die Aufgaben decken Themen wie Graphentheorie, dynamische Programmierung, String-Verarbeitung und Komplexitätsanalyse ab.
Backtracking and the N-Queens Problem
Dieses Unterrichtsmaterial erklärt die algorithmische Strategie des Backtrackings anhand des klassischen Damenproblems. Es enthält eine theoretische Einführung, eine Beschreibung des Algorithmus sowie eine vollständige Implementation in C++ inklusive Laufzeitanalyse.
Convex Hull Trick und optimierte Dynamische Programmierung
Das Lehrmittel behandelt fortgeschrittene Techniken zur Optimierung von dynamischer Programmierung (DP) mittels des Convex Hull Tricks und der verallgemeinerten Deque-Optimierung. Es enthält mathematische Herleitungen sowie vollständige Implementierungen in C++.
Fenwick Trees (Binary Indexed Trees) in C++
Dieses fortgeschrittene Dokument behandelt die Theorie und Implementierung von Fenwick-Bäumen (Binary Indexed Trees) in C++. Es werden verschiedene Aspekte wie dynamische Prefix-Summen, multidimensionale Varianten, Bereichsabfragen sowie Koordinatenkompression detailliert erläutert.
Divide and Conquer on Ranges and Segment Trees
Der Text erklärt detailliert die theoretischen Grundlagen und die Implementierung von Segmentbäumen (Segment Trees) in C++. Dabei werden Divide-and-Conquer-Algorithmen, Bereichsanfragen (Range Queries) und effiziente Array-Updates behandelt.
Binäre Suche: Algorithmus, Implementation und Analyse
Dieses Unterrichtsmaterial erklärt das Prinzip der binären Suche für sortierte Arrays. Es enthält eine mathematisch begründete Problemstellung, eine Java-Implementierung sowie eine Analyse von Speicher- und Laufzeitkomplexität.
Einführung in Algorithmen und O-Notation
Das Material bietet eine verständliche Einführung in den Begriff des Algorithmus, die O-Notation zur Laufzeitanalyse sowie klassische Probleme wie das Rucksackproblem, das Travelling-Salesperson-Problem, das Finden eines Stars und das Maximum Subarray Problem. Es behandelt zudem verschiedene Entwurfsstrategien wie Teile-und-Herrsche und dynamische Ansätze.
The Cost of Computation: Algorithmische Komplexität und Big-O-Notation
Dieses Lehrmaterial führt in die Grundlagen der algorithmischen Analyse und die Big-O-Notation ein. Anhand von Beispielen zu Rekursion und Laufzeitvergleichen wird gezeigt, wie die Effizienz von Programmen gemessen und formal beschrieben wird.
Laufzeit von Algorithmen
Das Material führt in die Analyse der Zeitkomplexität von Algorithmen ein. Es erklärt die Unterscheidung zwischen Best-, Worst- und Average-Case sowie die Klassifizierung von Laufzeiten mithilfe der O-Notation.
Effizienz und Komplexität
Der Text führt in die Grundlagen der Analyse von Algorithmen ein. Es werden die zentralen Begriffe Effizienz und Komplexität im Hinblick auf Laufzeit und Speicherbedarf erläutert.
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.
Fibonacci numbers via recursion
Eine Programmieraufgabe, bei der die n-te Fibonacci-Zahl mittels Rekursion in Python implementiert werden soll. Zudem wird die Reflexion über die Laufzeit im Vergleich zu iterativen Lösungen angeregt.
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.
Komplexität von Algorithmen und Problemen
Dieses Unterrichtsmaterial führt systematisch in die Analyse des Laufzeitverhaltens und den Ressourcenverbrauch von Algorithmen ein. Anhand von Fallstudien werden verschiedene Problemlösungen und deren Effizienz untersucht.
Randomisierte Algorithmen
Diese mentorierten Unterrichtsmaterialien führen in das Konzept der randomisierten Algorithmen ein. Anhand von Beispielen wie Quicksort und der Verifikation von Matrixmultiplikationen wird analysiert, wie gezielter Zufall zur Lösung von Problemen eingesetzt werden kann.
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.
Das Entscheidungsproblem der Knotenüberdeckung
Diese leitprogrammartigen Unterrichtsunterlagen behandeln das Knotenüberdeckungsproblem als Entscheidungs- und Optimierungsproblem. Die Schülerinnen und Schüler befassen sich mit Formalismen der theoretischen Informatik, betrachten die algorithmische Komplexität und schulen ihr algorithmisches Denken anhand graphentheoretischer Beispiele.
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.
Rekursion und Aufwand
Dieses Unterrichtsmaterial beleuchtet die Eigenschaft von rekursiven Algorithmen, einen besonders hohen Rechenaufwand zu erzeugen. Anhand konkreter Beispiele, wie der Ackermann-Funktion, wird diese Problematik veranschaulicht.
Laufzeit messen mit Python
Dieses Unterrichtsmaterial demonstriert anhand eines Python-Programms für den Euklidischen Algorithmus und den Wechselwegnahme-Algorithmus, wie die Ausführungszeit von Programmen gemessen werden kann. Die Lernenden führen das Programm selbst aus und vergleichen die Rechenzeiten bei unterschiedlichen Eingabewerten.
Effizienz von Algorithmen
Dieses Material führt in das Konzept der algorithmischen Effizienz ein und zeigt Lernenden, wie sich die benötigten Ressourcen wie Rechenzeit und Speicherbedarf von Algorithmen unterscheiden. Zudem wird thematisiert, wie die Laufzeit von implementierten Algorithmen gemessen werden kann.
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.