Parametrisierung von Vertex Cover

In der Unterrichtseinheit geht es darum, mit den Schülerinnen und Schülern das anspruchsvolle Thema des Algorithmen-Entwurfs mit Parametrisierung am Leitfaden eines anschaulichen Beispiels zu erarbeiten. Gewählt wurde der Algorithmus VC-Para, der das NP-schwere Optimierungsproblem VCmin in ein Entscheidungsproblem umwandelt und das exponentielle Verhalten des vollständigen Durchrechnens durch die Einführung eines Parameters gewissermassen deckelt.

Der rote Faden durch die Unterrichtseinheit bildet eine Geschichte: Der Schüler/die Schülerin ist Teil eines Organisationskomitees für einen Stadtlauf. Dabei ist er/sie dafür verantwortlich, dass durch geschicktes Aufstellen von Streckenposten in Sackgassen, an Kreuzungen und auf Plätzen die gesamte Laufstrecke überwacht werden soll. Geschickt heisst in diesem Zusammenhang: Es sollen möglichst wenige Streckenposten aufgestellt werden.