1.2.3 Klassische algorithmische Strategien (z.B. Greedy, Teile-und-Herrsche, Backtracking) für den Entwurf eigener Lösungen einbeziehen
Unterrichtsmaterial zum Lernziel: Die Maturandinnen und Maturanden können klassische algorithmische Strategien (z.B. Greedy, Teile-und-Herrsche, Backtracking) für den Entwurf eigener Lösungen einbeziehen.
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.
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.
Computing Maximum Matchings in Bipartite Graphs
Der Text erklärt detailliert die theoretischen Grundlagen und Algorithmen für Matchings und das Minimum Vertex Cover in Graphen mit Fokus auf bipartite Graphen. Er enthält mathematische Herleitungen sowie eine vollständige Implementation in C++ zur Berechnung maximaler Matchings und minimaler Vertex Covers.
Swiss Olympiad in Informatics - Aufgaben und Archiv
Eine Sammlung von anspruchsvollen Programmier- und Algorithmenaufgaben der Schweizer Informatik-Olympiade mit verschiedenen Teilaufgaben und Kontexten. Die Aufgaben eignen sich zur Förderung von fortgeschrittenem algorithmischem Denken und Problemlösungskompetenzen.
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.
Treaps: Balanced Binary Search Trees and Ropes
Dieses fortgeschrittene Material von Johannes Kapfhammer erklärt das Konzept von Treaps (Kombination aus Binärsuchbaum und Heap) sowie impliziten Treaps (Ropes) für den Einsatz in der wettbewerbsorientierten Programmierung. Es behandelt Operationen wie Suchen, Einfügen, Bereichsanfragen (Range Queries) und Lazy Updates mit Code-Beispielen.
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++.
Smaller to Larger (DSU on Trees)
Dieses fortgeschrittene Dokument erklärt den Optimierungsalgorithmus Smaller to Larger (auch DSU on Trees genannt) für Baumstrukturen. Es enthält die theoretische Herleitung, einen formalen Beweis der logarithmischen Laufzeitkomplexität sowie konkrete Code-Beispiele und Anwendungsbeispiele wie BOI- und CEOI-Aufgaben.
Recursive Segment Trees mit Lazy Propagation in C++
Dieser Artikel von Timon Gehr erklärt die Implementierung und Optimierung von Segmentbäumen in C++. Es wird detailliert gezeigt, wie Bereichsaktualisierungen (range updates) mithilfe von Lazy Propagation effizient durchgeführt und verschiedene Arten von Operationen kombiniert werden können.
Fortgeschrittene Dynamische Programmierung: 2D-DP und Bitmask DP
Das Skript behandelt fortgeschrittene Konzepte der dynamischen Programmierung, darunter zweidimensionale DP-Ansätze (wie die längste palindromische oder gemeinsame Teilsequenz sowie Matrix-Kettenmultiplikation) und Bitmask-DP (am Beispiel des Traveling Salesperson Problems). Es enthält ausführliche algorithmische Erklärungen und C++-Codebeispiele für rekursive und iterative Implementierungen.
Greedy Algorithms and Correctness Reasoning
Dieses Unterrichtsmaterial erklärt das Konzept von Greedy-Algorithmen anhand von Optimierungsproblemen und zeigt Strategien zur Begründung von deren Korrektheit auf. Es enthält konkrete Fallbeispiele mit Pseudocode (Concierge, Binge, Stollencut) sowie Gegenbeispiele.
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.
Sammlung von Unterrichtsmaterialien zu fortgeschrittenen Datenstrukturen, Algorithmen und Java-Programmierung
Eine umfangreiche Sammlung von Materialien, Aufgaben und Programmierprojekten in Java und JavaScript für den Informatikunterricht. Sie deckt Themen wie Datenstrukturen (Listen, Bäume, Graphen), Sortieralgorithmen, objektorientierte Entwurfsmuster und fortgeschrittene Programmierkonzepte ab.
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.
Greedy und Teile und Herrsche
Dieses Leitprogramm für das Schwerpunktfach Informatik stellt zwei grundlegende Entwurfsmethoden für Algorithmen vor: Greedy-Algorithmen und das Teile-und-Herrsche-Prinzip. Anhand verschiedener Probleme lernen die Schülerinnen und Schüler, diese algorithmischen Strategien zu verstehen und anzuwenden.
Bäume und Backtracking
Dieses Leitprogramm für das Schwerpunktfach Informatik führt Schülerinnen und Schüler im letzten Jahr vor der Matur in die Themen Bäume und Backtracking ein. Es behandelt fortgeschrittene algorithmische Strategien und deren praktische Umsetzung.
The Alien Trick (WQS Binary Search)
Der Artikel erklärt eine fortgeschrittene algorithmische Technik, den sogenannten Alien-Trick oder WQS-Binärsuchalgorithmus, zur Optimierung von dynamischer Programmierung und Greedy-Problemen unter Konvexitätsannahmen. Es wird gezeigt, wie Parameterdimensionen unter Verwendung von Konvexität und Binärsuche eliminiert werden können, um die Laufzeitkomplexität zu verbessern.
Persistent Segment Trees und Datenstrukturen
Der Artikel erklärt das Konzept persistenter Datenstrukturen am Beispiel von Segment Trees und zeigt, wie effizient Versionen durch Zeigerstrukturen erhalten bleiben können. Es wird beschrieben, wie Änderungen nur O(log n) Knoten betreffen, wodurch das Kopieren des gesamten Baumes vermieden wird.
Matchings in Graphen und algorithmische Lösungsansätze
Diese Unterrichtsunterlagen behandeln die Modellierung von Paarbildungs- und Zuteilungsproblemen mittels Graphen und Matchings. Die Schülerinnen und Schüler lernen Greedy-Algorithmen, Backtracking, verbessernde Pfade und die Ungarische Methode kennen.
Median-Berechnung in verschiedenen Programmiersprachen
Eine Sammlung von Code-Beispielen in verschiedenen Programmiersprachen und Paradigmen (wie Ada, APL, Assembly, Algol-Derivate), um den Median einer Liste durch Sortieren oder Quickselect effizient zu bestimmen.
Effiziente Sortieralgorithmen: MergeSort und HeapSort
Diese Unterrichtseinheit stellt die effizienten Sortieralgorithmen MergeSort und HeapSort vor. Die Schülerinnen und Schüler lernen dabei Strategien wie 'Teile und Beherrsche' sowie die Nutzung von Heaps zur Problemlösung kennen.
Leitprogramm Bäume und Backtracking
Ein Leitprogramm für das Gymnasium, das in Bäume und Backtracking einführt. Es setzt Vorkenntnisse in Wahrscheinlichkeitsrechnung, Graphentheorie und rekursiver Programmierung in Processing voraus.
Leitprogramm Entwurfsmethoden für Algorithmen: Greedy und Teile-und-Herrsche
Dieses Leitprogramm führt in zwei grundlegende Entwurfsmethoden für Algorithmen ein: die Greedy-Methode sowie das Teile-und-Herrsche-Prinzip. Lernende erhalten eine Übersicht über die Methoden und deren Anwendung auf verschiedene Probleme, wobei der Text als Einleitung ohne konkrete Aufgaben oder Lösungen auskommt.