1.2.3 Klassische Algorithmen (z.B. für Sortieren oder Suchen) zur Lösung eines Problems beschreiben, anwenden und vergleichen
Unterrichtsmaterial zum Lernziel: Die Maturandinnen und Maturanden können klassische Algorithmen (z.B. für Sortieren oder Suchen) zur Lösung eines Problems beschreiben, anwenden und vergleichen.
Sorting Networks (Netzwerk-Sortieren) – Unplugged Informatikunterricht
Eine klassische Unplugged-Unterrichtseinheit zum Thema Sortiernetzwerke und parallele Algorithmen, bei der Schülerinnen und Schüler physisch auf einem mit Kreide gezeichneten Netzwerk Algorithmen ausführen. Dabei werden grundlegende Konzepte wie algorithmisches Denken, Abstraktion, Zerlegung und parallele Verarbeitung anschaulich vermittelt.
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.
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.
Sortieren durch Zerlegen / Quicksort
Das Unterrichtsmaterial führt den Quicksort-Algorithmus schrittweise ein, beginnend mit einem kooperativen Rollenspiel über die formale Beschreibung als informeller Algorithmus bis hin zur Implementierung und Analyse.
Sortieren durch Aufsteigen / Bubblesort
Das Unterrichtsmaterial führt in das klassische Sortierverfahren Bubblesort ein. Die Lernenden analysieren die Grundidee anhand von Beispielen, beschreiben den Algorithmus, erstellen ein Struktogramm und implementieren den Algorithmus schliesslich selbst.
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.
Sortiernetzwerke als unplugged Parallelaralgoritmus
Dieses Unterrichtsmaterial führt Schülerinnen und Schüler spielerisch und ohne Computer an das Konzept von Sortiernetzwerken und paralleler Algorithmen herankommen. Durch das physische Durchlaufen eines auf den Boden gezeichneten Netzwerks erleben sie algorithmisches Denken, Abstraktion und Deaktivierung hautnah.
Parallel Sorting Networks Unterrichtseinheit
Dieses Unterrichtsmaterial beschreibt eine anschauliche, körperliche Aktivität zur Erkundung von parallelen Algorithmen und Sortiernetzwerken. Die Schülerinnen und Schüler lernen dabei spielerisch und ohne Computer, wie durch gleichzeitige Vergleiche von Werten die Effizienz von Datenverarbeitung gesteigert werden kann.
Binary Search unplugged
Dieses Unterrichtsmaterial beschreibt ein interaktives, physisches Spiel (Unplugged-Aktivität) zum Kennenlernen der binären Suche und der Strategie 'Teile und Herrsche' (Divide and Conquer). Schülerinnen und Schüler lernen durch das Suchen von Zahlen auf Karten, wie man durch Halbierung des Suchraums effizient vorgeht.
Binäre Suche spielerisch entdecken
Dieses Unterrichtsmaterial für eine spielerische Unplugged-Aktivität führt Schülerinnen und Schüler an die binäre Suche und das Prinzip von 'Teile und Herrsche' heran. Anhand von sortierten Karten lernen sie, wie durch geschicktes Halbieren des Suchraums Probleme effizient gelöst werden können.
Sequenziellen Suchalgorithmus spielerisch entdecken
Dieses Unterrichtsmaterial führt Schülerinnen und Schüler anhand eines physischen Suchspiels mit verdeckten Karten in das Konzept der sequenziellen Suche ein. Dabei werden grundlegende Aspekte des algorithmischen Denkens wie Abstraktion, Dekomposition und die Analyse des Worst-Case-Verhaltens erarbeitet.
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.
Accumulators in Recursive Function Design (HtDP)
Dieses Lehrmaterial behandelt das Konzept von Akkumulatoren zur Optimierung und Ermöglichung rekursiver Funktionen. Es zeigt anhand von Beispielen wie Distanzberechnungen und Graphentraversierung, wie der Verlust von Kontextwissen vermieden und die Leistung gesteigert werden kann.
Backtracking mit Heuristiken
Dieses Unterrichtsmaterial führt anhand eines alltäglichen Beispiels (Websuchen) in das Konzept des Backtrackings ein und vertieft das Thema mit Algorithmen, Laufzeitbetrachtungen und Anwendungsbeispielen wie Labyrinthen und Springerwegen. Dabei werden auch Heuristiken zur Optimierung der Suche, insbesondere die Warnsdorf-Heuristik, besprochen.
Schwierige Probleme in der Informatik: Graphentheorie mit GraphBench
Das Unterrichtsmaterial führt anhand des Plans für ein Stadtfest in Bern in komplexe graphentheoretische Probleme ein. Die Lernenden nutzen die Software GraphBench, um NP-schwere Probleme wie das Hamilton-Kreis-Problem oder Graphenfärbbarkeit zu untersuchen, zu experimentieren und ihre Erkenntnisse zu präsentieren.
Routing-Algorithmen und der Dijkstra-Algorithmus
Das Unterrichtsmaterial erklärt anhand von Grafen und dem Dijkstra-Algorithmus, wie Router im Internet den kürzesten Weg für Datenpakete finden. Es verbindet anschauliche Erklärungen mit interaktiven Aufgaben zur manuellen Durchführung und zur Analyse von Routing-Tabellen.
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.
Binary Search Algorithmus in verschiedenen Programmiersprachen
Das Material beschreibt den klassischen Suchalgorithmus der binären Suche anhand einer analogen Erklärung und präsentiert konkrete Implementierungen und Pseudocodes für verschiedene Programmiersprachen und Paradigmen.
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: 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: 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 - Oxygen System (Graphensuche und Robotersteuerung)
Eine Programmieraufgabe im Rahmen von Advent of Code, bei der ein Roboter durch einen unbekannten, labyrinthartigen Raum gesteuert werden muss, um das Sauerstoffsystem zu finden. Dabei müssen Suchalgorithmen zur kürzesten Wegfindung (wie Breitensuche) auf einer dynamisch entdeckten Karte implementiert werden.
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: 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.
Anwendung von Sortieralgorithmen auf komplexe Datensätze
Dieses Unterrichtsmaterial zeigt anhand von Python-Code, wie klassische Sortieralgorithmen wie Quicksort und Selectionsort so angepasst werden können, dass sie nicht nur einfache Zahlen, sondern komplexe Datensätze wie Adressdateien im CSV-Format sortieren. Die Lernenden erweitern bestehenden Programmcode, implementieren benutzerdefinierte Vergleichsfunktionen und bearbeiten praktische Programmieraufgaben.
Sortieren durch Einfügen (Insertionsort)
Das Unterrichtsmaterial führt in das klassische Sortierverfahren 'Insertionsort' ein. Anhand von Aufgaben analysieren, modellieren und implementieren die Lernenden den Algorithmus eigenständig.
Sortieren durch Auswählen / Selectionsort
Das Material führt anhand des Selection-Sort-Algorithmus schrittweise in die Grundidee des Sortierens ein, lässt Lernende den Algorithmus manuell nachvollziehen, in Struktogrammen modellieren und schliesslich implementieren.
Entwicklung von Sortieralgorithmen
Dieses Unterrichtsmaterial führt spielerisch und handelnd an die Entwicklung von Sortieralgorithmen heran. Die Lernenden erarbeiten sich Strategien zunächst mit physischen Objekten oder Simulationen und formalisieren diese anschliessend in Algorithmen und Struktogrammen.
Das Sortierproblem und Suchen in Datenbeständen
Dieses Unterrichtsmaterial führt in das Sortier- und Suchproblem anhand von praktischen Beispielen mit Adressdaten ein. Es vergleicht die Suche in sortierten und unsortierten Datenbeständen und erläutert die Grundlagen zur automatisierten Sortierung.
Einführung in Sortieralgorithmen
Dieses Unterrichtsmaterial führt in das Thema Sortieren von Daten ein. Die Lernenden befassen sich mit verschiedenen Sortierverfahren und vergleichen diese hinsichtlich ihrer Effizienz.
Anwendung der Suchalgorithmen
Dieses Unterrichtsmaterial führt anhand eines konkreten Beispiels mit Adressdaten in CSV-Form dazu, bestehende Suchalgorithmen wie die binäre und lineare Suche von Zahlen auf komplexe Datensätze in Python anzupassen. Die Lernenden transformieren Daten und erweitern bestehende Programme.
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.
Binäre Suche
Das Unterrichtsmaterial führt in das klassische Suchverfahren der binären Suche ein. Anhand von Aufgaben zur Erläuterung und Ablaufmodellierung sowie einer Programmieraufgabe wird das Prinzip der halbierenden Bereichssuche verstanden und umgesetzt.
Lineare Suche
Das Material führt in den Algorithmus der linearen Suche für sortierte und unsortierte Listen ein. Anhand von Aufgaben analysieren, modellieren und implementieren die Lernenden das Suchverfahren.
Entwicklung von Suchalgorithmen
Das Material bietet eine interaktive und problemorientierte Einführung in Suchalgorithmen. Schülerinnen und Schüler erkunden anhand eines digitalen Tools systematische Suchverfahren sowohl in unsortierten als auch in sortierten Datenbeständen.
Ein Suchproblem: Manuelle Suche in ungeordneten und geordneten Datenbeständen
Anhand einer Adressdatei erleben die Lernenden den Unterschied zwischen der Suche in ungeordneten und sortierten Datenbeständen. Sie erfahren spielerisch bzw. händisch, warum sortierte Daten die Suche erleichtern und begründen die Notwendigkeit von Sortieroperationen bei großen Datenmengen.
Algorithmen zur ggT-Berechnung
Dieses Arbeitsblatt behandelt den Euklidischen Algorithmus und den Wechselwegnahme-Algorithmus zur Bestimmung des größten gemeinsamen Teilers (ggT). Anhand konkreter Aufgaben vergleichen die Lernenden die Effizienz der beiden Verfahren und analysieren deren zugrundeliegende Strategien.
Korrektheitsbeweis für den euklidischen Algorithmus
Das Material behandelt den mathematischen Beweis der Korrektheit und der Schleifeninvariante für einen Algorithmus zur Bestimmung des grössten gemeinsamen Teilers (ggT) und enthält eine Übungsaufgabe dazu.
Das Wechselwegnahmeverfahren
Das Unterrichtsmaterial führt spielerisch und durch haptisches sowie schrittweises Ausführen in einen klassischen mathematischen Algorithmus ein. Die Schülerinnen und Schüler führen das Verfahren manuell mit Streichhölzern durch, analysieren einen gegebenen Algorithmus und untersuchen dessen Verhalten bei verschiedenen Eingaben.
Exkurs: Die Suchmaschine Google
Das Unterrichtsmaterial beleuchtet die Funktionsweise und Entwicklung der Google-Suche anhand von Videos und eigenen Recherchen. Die Lernenden setzen sich kritisch mit Algorithmen wie PageRank sowie mit der Unternehmensstruktur und Kritikpunkten an Alphabet Inc. auseinander.
Verlinkung von Webseiten und der PageRank-Algorithmus
Dieses Unterrichtsmaterial führt in die Funktionsweise von Hyperlinks und den historischen PageRank-Algorithmus von Google ein. Anhand von Aufgaben analysieren die Lernenden die Linkpopularität und die Relevanz von Webseitenstrukturen.
Das Ranking-Problem bei Suchmaschinen
Das Unterrichtsmaterial führt Lernende anhand von Alltagserfahrungen, konkreten Aufgaben und Diskussionsfragen an das grundlegende 'Ranking-Problem' von Suchmaschinen heran. Es beleuchtet Kriterien zur Relevanzbestimmung von Webseiten und diskutiert technische sowie ethische Aspekte.
StammbaumXML: Verarbeitung von Daten eines Stammbaumes
Das Unterrichtsmaterial behandelt die automatisierte Verarbeitung von Stammbaumdaten mithilfe von XML-Dokumenten und Python. Die Lernenden analysieren Datenstrukturen, entwickeln Programmierfunktionen zur Datenabfrage und -auswertung und untersuchen Suchalgorithmen wie die Breitensuche anhand konkreter Codebeispiele.
Sorting Networks - Variationen und Experimente
Dieses Unterrichtsmaterial baut auf den Grundlagen von Sortiernetzwerken auf und erforscht verschiedene Variationen wie identische Werte, umgekehrte Sortierung, Buchstaben, Wörter und musikalische Noten. Zudem wird experimentell untersucht, ob Sortiernetzwerke auch rückwärts funktionieren, wodurch Prinzipien des algoritmischen Denkens und der Abstraktion vertieft werden.
Sorting Networks - Variationen und Analysen
Dieses Unterrichtsmaterial baut auf den Grundlagen von Sortiernetzwerken auf und lässt Schülerinnen und Schüler verschiedene Variationen wie Duplikate, umgekehrte Sortierung und das Sortieren von Buchstaben ausprobieren. Zudem wird untersucht, ob sich das Netzwerk auch in umgekehrter Richtung betreiben lässt, was grundlegende Aspekte des algorithmischen Denkens und der Abstraktion vertieft.
Binäre Suche und Suchstrategien (CS Unplugged)
Dieses Unterrichtsmaterial führt spielerisch und ohne Computer (CS Unplugged) in den Algorithmus der binären Suche ein. Die Lernenden vergleichen Suchstrategien für sortierte und unsortierte Daten und reflektieren dabei algorithmisches Denken, Abstraktion und Effizienz.
Number Hunt - Sequential Search Activity
Dieses Unterrichtsmaterial führt spielerisch in die sequentielle Suche ein. Die Schülerinnen und Schüler erkunden anhand eines Suchspiels mit nummerierten Boxen die Funktionsweise und Ineffizienz der linearen Suche in unsortierten Daten und reflektieren dabei algorithmisches Denken.