Document ID: /fineweb-2-swissfilter-quality_10-filterrobots/filtered/03124.jsonl.gz/2704

Algorithmen-Entwurf mit Parametrisierung am Beispiel von Vertex Cover
Peter Greutmann
Unterrichtseinheit für Stufe Sek II 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.