Paare und Zuweisungen mit Matchings finden

In diesen Unterlagen erarbeiten Schüler:innen Grundkonzepte von Matchings. Sie modellieren Paarbildungs- und Zuteilungsprobleme als Graphen und identifizieren deren Lösungen als Matchings in diesen Graphen. Den Kern bildet der Entwurf eines Algorithmus, mit dem man ein grösstmögliches Matching findet. Dabei lernen die Schüler:innen Folgendes kennen: einen Greedy-Algorithmus, Bäume zur Auflistung von Lösungen, Backtracking, verbessernde Pfade (augmenting paths), bipartite und gewichtete Graphen sowie die Ungarische Methode.

Didaktisch interessant für die Informatik sind Matchings aus mehreren Gründen. Die Problemstellungen und Lösungen sind klar visualisierbar. Die Anwendungen sind zahlreich und nah am Alltag der Schüler:innen. Aus algorithmischer Sichtweise illustriert die Suche eines grösstmöglichen Matchings die Macht eines systematischen Verfahrens: Die Anzahl Matchings in einem allgemeinen Graphen wächst exponentiell in der Anzahl Knoten, trotzdem gibt es einen simplen und eleganten Lösungsalgorithmus mit polynomieller Laufzeit. Insbesondere die Ungarische Methode eignet sich besonders für den Unterricht, denn sie kann vollständig in der Tabellenform eines Graphen ausgeführt werden, was auch das Lösen grosser Probleminstanzen von Hand ermöglicht. Diese Unterlagen sollen eine Alternative zur Weiterführung der Graphen oder einen Einstieg in die Algorithmik bieten. Im Informatikunterricht werden häufig Themen rund ums Thema Wege, Pfade, Kreise etc. diskutiert. Daraus werden dann Tiefen-, Breitensuche, Dijkstras Algorithmus oder Ähnliches erarbeitet. Dabei bietet die Welt der Graphen und Algorithmen so viel mehr.