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.
Entwurf und Anwendung von Backtracking-Algorithmen
Dieses Unterrichtsmaterial für die 11. Klasse führt Lernende über die Modellierung von Suchbäumen und deren Speicherprobleme schrittweise an Backtracking-Algorithmen heran. Die Schülerinnen und Schüler lernen, wie das rekursive Trial-and-Error-Verfahren das speicherintensive Erstellen ganzer Suchbäume umgeht.
Leitprogramm: Entwurfsmethoden für Algorithmen (Greedy & Teile-und-Herrsche)
Dieses Leitprogramm führt Schülerinnen und Schüler in zwei zentrale Entwurfsmethoden für Algorithmen ein: die Greedy-Methode sowie das Teile-und-Herrsche-Prinzip. Anhand von Beispielen lernen die Lernenden, diese Strategien anzuwenden und eigene algorithmische Lösungen für spezifische Probleme zu entwickeln.
Mentoriert Arbeit: Einführung in randomisierte Algorithmen
Diese mentoriert Arbeit führt Schülerinnen und Schüler in das Themengebiet der randomisierten Algorithmen ein. Anhand von Beispielen wie Quicksort, Gegnerüberlistung und Matrixverifikation wird die Stärke des Zufalls in der Informatik sowie die Anwendung der Wahrscheinlichkeitstheorie erarbeitet.
Leitprogramm zu Bäumen und Backtracking
Dieses Leitprogramm für das letzte Gymnasialjahr führt in die Graphentheorie, Baumstrukturen und den Backtracking-Algorithmus ein. Es baut auf Vorkenntnissen in Wahrscheinlichkeitsrechnung und rekursiver Programmierung auf.
Matchings in Graphen und algorithmische Lösungsstrategien
Dieses Unterrichtsmaterial führt Schülerinnen und Schüler in das Konzept von Matchings in Graphen ein. Es behandelt die Modellierung von Zuteilungsproblemen, Greedy-Algorithmen, Backtracking, verbessernde Pfade sowie die Ungarische Methode.
Schnelle Multiplikation – Verfahren von Karatsuba
Das Unterrichtsmaterial führt in das Karatsuba-Verfahren zur schnellen Multiplikation grosser Zahlen ein. Die Schülerinnen und Schüler lernen die algorithmische Entwurfsstrategie von 'Divide and Conquer' kennen, wenden das Verfahren manuell an und vergleichen experimentell die Effizienz mit der herkömmlichen Schulmethode.
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.
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.
Softwareentwicklungstechniken: Teile und herrsche sowie Top-down und Bottom-up
Der Text erklärt grundlegende Techniken des Softwareengineerings wie das Prinzip 'Teile und herrsche' zur Reduktion von Komplexität. Zudem werden die Ansätze Top-down und Bottom-up bei der funktionalen Dekomposition von Programmen erläutert.
GraphBench
GraphBench ist eine interaktive Lernsoftware zur Veranschaulichung von NP-vollständigen Problemen, Reduktionen und Graphenalgorithmen. Die Java-Anwendung bietet neben grafischen Visualisierungen auch eine integrierte Programmierumgebung für eigene Algorithmen.
Vortrag: Backtracking mit Heuristiken
Dieses Material bietet einen einführenden Vortrag über das Konzept des Backtrackings und den Einsatz von Heuristiken. Es enthält Folien, Texte und Beispielaufgaben wie das n-Damen-Problem oder Labyrinth-Aufgaben zur Veranschaulichung.