Das Museumswächterproblem

Wie viele Wächter braucht man, um ein Museum zu überwachen? Was im Grünen Gewölbe vielleicht geholfen hätte, stellen wir hier „hands-on“ an einem Modell nach. So finden wir gemeinsam die minimale Anzahl von Wächtern (und deren Position), und begeben uns letztlich auf die Suche nach einer generellen Lösung für Museen, die beliebige Grundrisse haben.
   

Interaktiv am Modell zum Anfassen
45 min
in der Schule / an der IEF in Rostock
ab Klassenstufe 8

Mich fasziniert, dass jedem Problem ein Schwierigkeitsgrad zugeordnet werden kann, der angibt, wie schnell es von einem Computer gelöst werden kann; mehr noch, in der Welt aller Probleme gibt es regelrechte Hierarchien dieser Schwierigkeitsgrade. Da wir heutzutage mit immer größer werdenden Datenmassen kämpfen, gehen Algorithmiker hier auf die Jagd nach den jeweils schnellsten Problemlösungen in Theorie und Praxis.