Reduktion NP-schwerer Probleme

Interaktive Simulationen:

Auf der rechten Seite finden Sie Verlinkungen zu Simulationen zur Lösung von Instanzen der Probleme: Subset-Sum, Binpacking, Knapsack und 3-Partition.

Materialien:

In diesem Abschnitt finden Sie Materialien zu einem Lernszenario zur Reduktion von NP-schweren Problemen mithilfe enaktiver Materialien und interaktiver Simulationen. Für die Einbettung im Unterricht werden die Ideen und Materialien in dem verlinkten Artikel in der MNU-Zeitschrift vorgestellt. Die Materialien ohne Lösungen sind frei zugänglich. Die Materialpakete inklusive Lösungen sowie der Artikel sind passwortgeschützt, da sie nur für Lehrer*innen gedacht sind. Bei Interesse senden Sie uns bitte eine E-Mail unter Angabe Ihres Namens und Ihrer Schule.

Diese Materialien basieren auf der Masterarbeit "NP-schwere Probleme - Aufbereitung ausgewählter Aspekte für den Informatikunterricht" von JAN WALTER (2025).

Allgemeine Hinweise zu den Simulationen:

Eingaben sind eingeschränkt
Lösungsalgorithmen brechen nach 40 Sekunden ab