In diesem Beitrag wird das Thema „NP-schwere Probleme" für die Schule aus didaktisch-methodischer Sicht aufbereitet. Stellvertretend geschieht dies am Knotenüberdeckungsproblem, das erhebliche praktische Relevanz besitzt. Im ersten Teil (siehe LOG IN, Heft 1 46/147, S.53 ff.) wurden Beispiele sowie Modellierungsaspekte zur Knotenüberdeckung in Graphen aufgezeigt. Ausgehend von unterschiedlichen Modellierungen wurden verschiedene Lösungsverfahren erläutert und bewertet. Darüber hinaus wurde die mit NPschweren Problemen verbundene, anscheinend unvermeidliche „kombinatorische Explosion" thematisiert. Ausgehend vom konkreten Problem werden im Folgenden Problemverwandtschaft, Determinismus und Nichtdeterminismus intuitiv erklärt. Dies mündet in Erläuterungen zur P=NP-Frage, einem der interessantesten Probleme der aktuellen Forschung in der Informatik.

In diesem Beitrag wird das Thema ,,NP-schwere Probleme“ für die Schule aus didaktisch-methodischer Sicht aufbereitet. Stellvertretend geschieht dies am Knotenüberdeckungsproblem, das erhebliche praktische Relevanz besitzt. Im ersten Teil (siehe LOG IN, Heft 146/147, S. 53 ff.) wurden Beispiele sowie Modellierungsaspekte zur Knotenüberdeckung in Graphen aufgezeigt. Ausgehend von unterschiedlichen Modellierungen wurden verschiedene Lösungsverfahren erläutert und bewertet. Darüber hinaus wurde die mit NPschweren Problemen verbundene, anscheinend unvermeidliche ,,kombinatorische Explosion“ thematisiert. Ausgehend vom konkreten Problem werden im Folgenden Problemverwandtschaft, Determinismus und Nichtdeterminismus intuitiv erklärt. Dies mündet in Erläuterungen zur P=NP-Frage, einem der interessantesten Probleme der aktuellen Forschung in der Informatik.