1.2.1 Gegebene Algorithmen analysieren und beurteilen
Unterrichtsmaterial zum Lernziel: Die Maturandinnen und Maturanden können gegebene Algorithmen analysieren und beurteilen.
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.
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.
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.
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.
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.
Korrektheit von Algorithmen testen
Dieses Unterrichtsmaterial führt in das systematische Testen von Algorithmen anhand konkreter Testfälle am Beispiel des euklidischen Algorithmus zur ggT-Berechnung ein. Lernende spielen Testfälle durch und reflektieren Fragen zur Vollständigkeit und zum Nachweis der Korrektheit.
Das Verhalten eines Algorithmus präzise beschreiben
Das Unterrichtsmaterial führt anhand konkreter Beispiele und des Euklidischen Algorithmus (Wechselwegnahme) in die präzise Beschreibung des Verhaltens von Algorithmen mittels Vor- und Nachbedingungen (Spezifikation) ein. Es zeigt, wie Vermutungen durch Tests überprüft und Randbedingungen wie Endlosschleifen identifiziert werden müssen.
Binary Search Trees (Unplugged)
Dieses Unterrichtsmaterial erklärt das Konzept von binären Suchbäumen (BST) auf spielerische und physische Art (Unplugged-Methode). Die Schülerinnen und Schüler lernen anhand von praktischen Übungen auf dem Pausenplatz oder im Klassenzimmer, wie Daten in Bäumen strukturiert, gesucht und effizient eingefügt werden.
Schweizer Informatik-Olympiade (SOI) Aufgaben und Archiv
Eine Sammlung von fortgeschrittenen algorithmischen Programmieraufgaben und theoretischen Fragestellungen aus der Schweizer Informatik-Olympiade (SOI), einschliesslich detaillierter Aufgabenstellungen zu Graphen, Datenstrukturen und Spieltheorie.
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.
Das Eulerproblem und der Hierholzer- sowie Fleury-Algorithmus
Das Skript beleuchtet die historische Entwicklung des Königsberger Brückenproblems und leitet daraus Graphen und das Konzept von Eulerpfaden ab. Anschliessend werden zwei klassische Algorithmen zur Bestimmung von Eulerpfaden (Hierholzer und Fleury) mit theoretischen Erklärungen und Code-Beispielen in C++ vorgestellt.
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.
How to Prove Correctness of Algorithms
Dieses Material erklärt theoretische Grundlagen und Techniken zum Nachweisen der Korrektheit von Algorithmen. Es behandelt strukturierte Begründungen, Widerspruchsbeweise, vollständige Induktion und mathematische Notation im Kontext von Informatik-Wettbewerben.
Topological Sorting with Depth First Search
Dieses Tutorial erklärt das Konzept der topologischen Sortierung und wie es mithilfe einer modifizierten Tiefensuche (DFS) auf gerichtete Graphen angewendet werden kann. Es enthält neben einer anschaulichen Schritt-für-Schritt-Erklärung und einem Beispiel auch eine vollständige Implementierung in C++ inklusive Zyklenerkennung.
Die Breitensuche (BFS) in Graphen
Dieses Lehrmaterial erklärt die Breitensuche (BFS) als klassischen Algorithmus zur Graphentraversierung und Bestimmung kürzester Wege in ungewichteten Graphen. Die Funktionsweise wird detailliert erläutert und anhand von Code-Beispielen in C++ und Python praktisch veranschaulicht.
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.
Day 21: Chronal Conversion (Advent of Code Puzzle)
Dieses Programmier- und Logikrätsel aus dem Advent of Code fordert Lernende auf, ein gegebenes virtuelles Maschinenprogramm zu analysieren und den Zustand eines Registers so zu manipulieren, dass das Programm nach möglichst wenigen Schritten terminiert. Es fördert das Verständnis von Kontrollstrukturen, Assembler-ähnlichen Befehlen und algorithmischer Problemlösung.
Control Flow as Graph
Das Material beschreibt ein Notional Machine Konzept, um den Kontrollfluss von Methoden und Funktionen als Graphen darzustellen. Es visualisiert Ausführungspfade und hilft dabei, zusammengesetzte Anweisungen sowie typische Programmverstehensfehler zu analysieren.
Korrektheit als Problem bei Algorithmen
Das Unterrichtsmaterial führt in die theoretische Frage ein, ob ein entwickelter Algorithmus das gewünschte Verhalten zeigt. Anhand eines Beispiels zur Bestimmung des grössten gemeinsamen Teilers (ggT) wird der Begriff der Korrektheit bezüglich einer Spezifikation thematisiert und durch eine Aufgabe zur Überprüfung vertieft.
Rekursion und Algorithmen in Python
Ein praxisorientiertes Unterrichtsmaterial zur Vertiefung von Rekursion anhand von Fakultät, Ackermann-Funktion und Code-Analysen. Die Schüler:innen programmieren in Python, analysieren Laufzeiten und untersuchen den Call-Stack im Debug-Modus.
Lineare und binäre Suche im Vergleich
Das Material erklärt und vergleicht die lineare und die binäre Suche anhand von Python-Codebeispielen. Es wird auf die Algorithmik, die O-Notation für das Wachstumsverhalten und einen praktischen Experimentvergleich mit matplotlib eingegangen.
GraphBench: Interaktive Lernumgebung für NP-Vollständigkeit und Graphenalgorithmen
GraphBench ist eine interaktive Java-Lernumgebung für NP-vollständige Probleme, Reduktionen und Graphenalgorithmen. Die Software bietet grafische Visualisierungen, verschiedene Lösungsansätze von Heuristiken bis zur erschöpfenden Suche sowie eine Programmierumgebung für eigene Algorithmen.
The Magic of $/ in Raku: Regexes and Race Conditions
Ein weihnachtlich angehauchtes Programmierbeispiel in der Programmiersprache Raku zeigt, wie reguläre Ausdrücke und parallele Verarbeitung (race) zu unerwarteten Fehlern führen können. Anhand dieses Beispiels wird erklärt, wie implizite Variablen wie die Match-Variable $/ in verschachtelten Scopes und Multithreading-Umgebungen funktionieren.
Parallele Verarbeitung in Raku: Hyper und Race
Der Artikel erklärt anhand von Beispielen in der Programmiersprache Raku, wie sich durch den Einsatz von Multi-Threading mittels `.hyper` und `.race` sowie durch das Anpassen von Batch-Grössen die Ausführungszeit von Programmen optimieren lässt. Dabei werden auch Themen wie Overhead, CPU-Auslastung und Performance-Messungen behandelt.
Matching Maps with Raku
Der Text beschreibt in einer erzählerischen Adventskalender-Geschichte, wie in der Programmiersprache Raku eine In-Memory-Datenstruktur (Hash/Map) effizient nach Regulären Ausdrücken durchsucht werden kann. Dabei werden verschiedene Optimierungsansätze wie Methodenoptimierung, Parallelisierung (.hyper) und spezialisierte Module verglichen.