1.2.2 Algorithmische Lösungen für konkrete Problemstellungen entwickeln
Unterrichtsmaterial zum Lernziel: Die Maturandinnen und Maturanden können algorithmische Lösungen für konkrete Problemstellungen entwickeln.
Graphentheorie und Algorithmen: Tiefensuche, Breitensuche und Dijkstra
Das Lehrmaterial behandelt grundlegende Konzepte der Graphentheorie wie Adjazenzlisten und Graphendarstellungen. Es führt praxisnah durch wichtige Algorithmen wie Tiefensuche (DFS), Breitensuche (BFS) und Dijkstras Algorithmus zur Bestimmung kürzester Wege.
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.
Advent of Code - Day 6: Lanternfish
Eine klassische Programmieraufgabe aus dem Advent of Code, bei der das exponentielle Bevölkerungswachstum von Laternenfischen simuliert werden muss. Die Aufgabe eignet sich hervorragend zur praktischen Problemlösung und dem effizienten Design von Algorithmen in der Informatik.
Übungen zur Rekursion und Programmentwicklung in Python
Eine Sammlung von Programmieraufgaben und Übungen, bei denen rekursive Algorithmen in Python analysiert, angewendet, schrittweise entwickelt und getestet werden. Die Lernenden nutzen problemreduzierende Ansätze und visualisierende Hilfsmittel wie Aufrufbäume, um rekursive Funktionen für Listenoperationen zu verstehen und zu programmieren.
Der Turm von Hanoi: Strategien und Implementierung
Dieses Unterrichtsmaterial führt Lernende durch die Analyse und algorithmische Lösung des Klassikers 'Turm von Hanoi'. Die Schülerinnen und Schüler erarbeiten rekursive und generalisierte Strategien für mehrere Scheiben und implementieren diese in Code.
Swiss Olympiad in Informatics 2024 - Second Round Tasks
Eine Sammlung von fortgeschrittenen algorithmischen Programmieraufgaben und Rätseln aus der zweiten Runde der Schweizer Informatik-Olympiade, die sich mit Themen wie Graphentheorie, dynamischer Programmierung und Datenstrukturen befassen.
Dijkstra-Algorithmus und Dictionaries in Python
Eine vertiefende Programmier-Challenge, bei der Schülerinnen und Schüler den Dijkstra-Algorithmus und die Verwendung von Python-Dictionaries zur effizienten Repräsentation von Graphen schrittweise implementieren.
Endliche Automaten und Zustände in Python programmieren
Dieses Unterrichtsmaterial führt in die praktische Programmierung von endlichen Automaten in Python ein. Anhand von Beispielen wie einer Lichtschaltung, einem Getränkeautomaten und einem E-Mail-Checker (Akzeptor) lernen die Lernenden den Einsatz von Enums, Variablen und Kontrollstrukturen zur Zustandsverwaltung.
Implementierung des Amb-Operators in verschiedenen Programmiersprachen
Das Material präsentiert Code-Beispiele und Erklärungen zur Implementierung des nicht-deterministischen Amb-Operators (ambiguous) in verschiedenen Programmiersprachen wie C#, C++, Ada und Pseudocode. Anhand eines Wortketten-Rätsels wird demonstriert, wie Such- und Backtracking-Probleme elegant gelöst werden können.
15 Puzzle Solver
Dieses Material präsentiert Implementierungen in ARM-Assembler und einer weiteren Programmiersprache zur automatischen Lösung des klassischen 15-Puzzles mittels Suchalgorithmen. Es demonstriert fortgeschrittene Programmierkonzepte und Algorithmik anhand eines konkreten Problembeispiels.
Advent of Code: No Such Thing as Too Much
Eine programmierbasierte Programmieraufgabe, bei der Kombinationen von Behaeltern gefunden und zaehlen muessen, um genau eine bestimmte Literzahl Erfrischungsgetraenk zu fuellen. Das Material eignet sich hervorragend zur praktischen Anwendung von algorithmischen Lösungsstrategien und Rekursion.
Internet Protocol Version 7 (Advent of Code Puzzle)
Ein Programmier- und Logikrätsel im Stil von Advent of Code, bei dem IP-Adressen nach bestimmten Mustern (ABBA-Sequenzen innerhalb und ausserhalb von Klammern) gefiltert werden müssen. Das Material eignet sich hervorragend zur Schulung von String-Manipulation und algorithmischem Denken.
Advent of Code: An Elephant Named Joseph
Eine klassische Programmier- und Logikaufgabe (bekannt aus dem Advent of Code), bei der ein mathematisch-algorithmisches Problem im Kreis angeordneter Personen gelöst werden muss. Die Lernenden müssen einen effizienten Algorithmus zur Bestimmung des Gewinners entwickeln und implementieren.
Air Duct Spelunking (Advent of Code)
Eine Programmieraufgabe im Stil von Advent of Code, bei der ein Roboter auf einer Karte gesteuert wird, um den kürzesten Weg zu finden, der alle Zielpunkte mindestens einmal besucht (Traveling Salesperson Problem).
Advent of Code: Recursive Circus
Eine Programmieraufgabe, bei der eine Baumstruktur bzw. hierarchische Anordnung von Programmen analysiert werden muss, um das unterste Element zu finden. Dies fördert das Verständnis von rekursiven Datenstrukturen und Datenparsing.
Advent of Code: Assembly-Interpreter (Duet)
Eine Programmieraufgabe im Rahmen des Advent of Code, bei der ein kleiner Assembler-Interpreter für Register und Instruktionen entwickelt werden muss. Die Lernenden analysieren eine unbekannte Befehlssatzarchitektur und implementieren die Logik, um Programme auszuführen.
Advent of Code: Electromagnetic Moat
Eine Programmieraufgabe, bei der eine Brücke aus magnetischen Komponenten gebaut und maximiert werden muss. Dabei werden rekursive Suchalgorithmen und Graphen- oder Baumstrukturen angewendet, um die stärkste Kombination zu finden.
Advent of Code: Memory Maneuver (Baumstrukturen und Rekursion)
Eine Programmieraufgabe im Rahmen von Advent of Code, bei der ein hierarchischer Baum aus Zahlen eingelesen, repräsentiert und rekursiv ausgewertet werden muss. Das Material eignet sich hervorragend, um fortgeschrittene Programmierkonzepte wie rekursive Datenstrukturen und Baum-Traversierung praktisch anzuwenden.
The Stars Align (Advent of Code)
Eine Programmieraufgabe zur Simulation der Bewegung von Punkten mit bekannten Positionen und Geschwindigkeiten über die Zeit, bis sie ein lesbares Wort bilden. Die Schülerinnen und Schüler müssen einen Algorithmus implementieren, um die Positionen iterativ zu berechnen und den Zeitpunkt der minimalen Ausdehnung zu finden.
Advent of Code: Subterranean Sustainability (Zellautomat)
Eine Programmieraufgabe im Stil von Advent of Code, bei der die zeitliche Entwicklung eines eindimensionalen zellulären Automaten über mehrere Generationen hinweg simuliert werden muss.
Advent of Code: Mine Cart Madness
Eine Programmieraufgabe zur Simulation sich bewegender Loren auf einem komplexen Schienensystem, bei der Kollisionen und Wegfindungsregeln implementiert werden müssen.
Advent of Code: Reservoir Research
Eine Programmieraufgabe, bei der die Ausbreitung von Wasser in einem zweidimensionalen Gitternetz aus Sand und Ton simuliert werden muss. Lernende entwerfen einen Algorithmus zur Simulation von Wasserströmen und zählen die erreichbaren Felder.
Advent of Code: A Regular Map (Graph- und Pfadsuche)
Eine Programmieraufgabe aus dem Advent of Code, bei der aus regulären Ausdrücken ein Raum-Labyrinth generiert und mittels Breitensuche der am weitesten entfernte Raum bestimmt werden muss. Es fördert das algorithmische Denken sowie die Anwendung von Graphen und Suchalgorithmen.
Advent of Code: Experimental Emergency Teleportation
Eine Programmieraufgabe zur Berechnung von Manhattan-Distanzen in einem 3D-Koordinatensystem. Es wird die Position von Nanobots und deren Signalradius analysiert, um zu ermitteln, welche Bots in Reichweite des stärksten Bots liegen.
Advent of Code: Four-Dimensional Adventure (Graph-Algorithmen und Distanzen)
Eine Programmieraufgabe im Rahmen des Advent of Code, bei der vierdimensionale Koordinaten eingelesen und mithilfe der Manhattan-Distanz in Konstellationen gruppiert werden müssen. Dies erfordert algorithmisches Denken, Datenstrukturen und typischerweise Graphen-Traversierungsalgorithmen wie Breitensuche oder Tiefensuche.
Advent of Code: Crossed Wires
Eine Programmieraufgabe, bei der Pfade von zwei Drähten auf einem Gitternetz analysiert werden müssen, um Schnittpunkte zu finden und die Manhattan-Distanz zu berechnen. Die Lernenden setzen algorithmische Problemlösungen praktisch um, indem sie Koordinaten und Pfadüberschneidungen auswerten.
Advent of Code: Monitoring Station
Eine Programmieraufgabe zur Bestimmung des optimalen Standorts für eine Überwachungsstation auf einer Asteroidenkarte basierend auf Sichtlinien. Die Schülerinnen und Schüler entwickeln einen Algorithmus, um Koordinaten zu verarbeiten und die Sichtbarkeit zwischen Punkten zu berechnen.
Advent of Code: Labyrinth-Suche mit Schlüsseln und Türen
Eine klassische Programmier- und Algorithmusaufgabe, bei der auf einem Gitterkarten-Labyrinth der kürzeste Pfad zum Einsammeln aller Schlüssel unter Berücksichtigung von verschlossenen Türen gefunden werden muss. Dies fördert algorithmisches Denken und die Anwendung von Graphensuche oder Suchalgorithmen.
Advent of Code: Labyrinth mit Portalen und kürzesten Wegen
Eine Programmieraufgabe, bei der ein Labyrinth mit raumfaltenden Portalen analysiert werden muss, um den kürzesten Weg von Start zu Ziel mithilfe von Graph-Algorithmen (wie Breitensuche) zu finden.
Advent of Code: Springdroid Adventure
Eine Programmieraufgabe, bei der eine Robotersteuerung (Springdroid) mittels einer minimalistischen Assemblersprache (Springscript) und boolescher Logik implementiert werden muss, um Hindernisse zu überwinden. Die Lernenden müssen algorithmisch über Bedingungen nachdenken und Programme mit begrenzten Instruktionen entwerfen.
Advent of Code: Allergen Assessment
Eine Programmieraufgabe, bei der anhand von Lebensmittellisten und bekannten Allergenen ermittelt werden muss, welche Zutaten bestimmte Allergene enthalten können und welche völlig allergenfrei sind. Die Schülerinnen und Schüler müssen algorithmische Logik anwenden, um die Daten auszuwerten.
Advent of Code: Rambunctious Recitation
Eine Programmieraufgabe im Rahmen des Advent of Code, bei der ein algorithmisches Gedächtnisspiel simuliert und das Resultat nach einer grossen Anzahl Runden berechnet werden muss. Die Lernenden müssen die Regeln verstehen und in Code umsetzen, um effizient das 2020. gesprochene Wort zu ermitteln.
Advent of Code: Amphipod-Rätsel
Eine Programmieraufgabe im Rahmen des Advent of Code, bei der ein Suchproblem zur optimalen Sortierung von Kreaturen in einem Gitter unter Energieaufwand gelöst werden muss.
Reactor Reboot
Eine programmiertechnische Aufgabe, bei der ein dreidimensionales Gitter von Würfeln anhand von Anweisungen manipuliert und ausgewertet werden muss. Das Material eignet sich hervorragend für algorithmisches Problemlösen und das effiziente Verarbeiten von Bereichsdaten.
Advent of Code: Dirac Dice
Eine Programmieraufgabe aus dem Advent of Code, bei der ein Würfelspiel simuliert und ausgewertet werden muss. Schülerinnen und Schüler können dabei algorithmisches Denken und Problemlösungskompetenzen anwenden.
Advent of Code: Beacon Scanner
In dieser Programmieraufgabe müssen 3D-Scans von Baken und Scannern verglichen und zusammengesetzt werden, um eine globale Karte zu erstellen. Dabei müssen räumliche Überlappungen und unbekannte Orientierungen durch Koordinatentransformationen gelöst werden.
Advent of Code: Kürzester Pfad (Chiton)
Eine Programmieraufgabe im Rahmen von Advent of Code, bei der ein Pfad mit minimalem Gesamtrisiko auf einem Gitter (Matrix) gefunden werden muss. Dies eignet sich hervorragend zur praktischen Anwendung und Vertiefung von Graph-Algorithmen wie Dijkstra zur Wegfindung.
Advent of Code 2021, Tag 12: Passage Pathing
Eine algorithmische Programmieraufgabe, bei der alle möglichen Pfade durch ein Höhlensystem unter bestimmten Bedingungen gefunden und gezählt werden müssen. Die Problemstellung fördert das Entwerfen von Suchalgorithmen, wie beispielsweise Tiefensuche (DFS), auf Graphen.
Advent of Code: Dumbo Octopus
Eine Programmieraufgabe, bei der die Simulation von Energiezuständen und Kettenreaktionen in einem zweidimensionalen Oktopussen-Gitter über mehrere Schritte implementiert werden muss.
Seven Segment Search
Eine Programmieraufgabe im Rahmen des Advent of Code, bei der durch die Analyse von Signalschemata eines beschädigten Siebensegmentanzeigers Logik- und Suchprobleme gelöst werden müssen. Die Schülerinnen und Schüler entwickeln Algorithmen, um gemischte Verdrahtungen zu rekonstruieren und bestimmte Ziffern zu zählen.
Advent of Code: Hydrothermal Venture (Tag 5)
Eine Programmieraufgabe, bei der Linienkoordinaten eingelesen und horizontale sowie vertikale Schnittpunkte ermittelt werden müssen. Ideal zur praktischen Vertiefung von zweidimensionalen Datenstrukturen und Koordinatenberechnungen.
Advent of Code: Giant Squid
Eine Programmieraufgabe aus dem Advent of Code, bei der ein Bingo-Spiel simuliert und das Gewinnerbrett ermittelt werden muss. Dabei wird algorithmisches Denken und die Verarbeitung von strukturierten Eingabedaten trainiert.
Parsing von Firefox user.js mit Raku Grammars
Das Material zeigt Schritt für Schritt, wie man mit der Programmiersprache Raku und sogenannten Grammars eine Konfigurationsdatei (user.js von Firefox) parsen kann. Dabei werden reguläre Muster, Regeln und das Debugging von Grammars praktisch erläutert.
Regexes and Grammars
Dieses Unterrichtsmaterial bietet eine strukturierte Übungsreihe zu regulären Ausdrücken (Regex) und Grammatiken. Lernende können anhand verschiedener Aufgaben Textmuster abgleichen, Grammatiken entwickeln und strukturierte Eingaben verarbeiten.
Rekursion und Iteration
Dieses Unterrichtsmaterial erklärt die grundlegenden Konzepte von Rekursion und Iteration als Modellierungswerkzeuge für wiederholte Berechnungen. Es zeigt die Vorzüge beider Ansätze auf und thematisiert die systematische Umwandlung zwischen rekursiven und iterativen Algorithmen.
Übungen zu rekursiven Algorithmen mit dem RecursionTutor
Dieses Unterrichtsmaterial enthält praktische Programmier- und Analyseaufgaben zur Rekursion anhand konkreter Anwendungsbeispiele wie Zinseszins, Medikamentenabbau und geometrischen Wachstumsprozessen. Lernende nutzen einen interaktiven Tutor zur Visualisierung von Aufrufbäumen, um rekursive Algorithmen zu entwickeln, zu testen und zu verstehen.
Wege im Galton-Brett
Dieses Unterrichtsmaterial führt anhand des Galton-Bretts in die mathematisch-informatische Modellierung und Untersuchung von Rekursionen ein. Die Lernenden bestimmen Anzahl von Wegen, analysieren Eigenschaften der entsprechenden Funktion und vergleichen verschiedene rekursive Implementierungen.
Liste als rekursive Datenstruktur
Dieses Unterrichtsmaterial erklärt die rekursive Definition von Listen und zeigt anhand eines konkreten Beispiels, wie rekursive Algorithmen zur Verarbeitung von Listen entwickelt, in Python implementiert und getestet werden.
Rekursive Algorithmen für selbstähnliche Figuren und Fraktale in Python
Das Unterrichtsmaterial enthält praktische Programmierübungen zu rekursiven Algorithmen und Selbstähnlichkeit. Die Lernenden sollen geometrische Figuren wie das Sierpinski-Dreieck oder den Pythagoras-Baum in Teilprobleme zerlegen, entsprechende Algorithmen entwickeln und diese in Python implementieren.
Fallstudie - Selbstähnliche Figuren
Dieses Material behandelt die rekursive Problemreduktion am Beispiel von selbstähnlichen Figuren. Lernende entwerfen rekursive Algorithmen und setzen diese mithilfe von Turtlegrafik praktisch um.