Wissenschaftssommer 2008

Die Spiele und Exponate

Die schwersten Spiele ihrer Klasse (Komplexitätstheorie)

Die Informatik ist die Lehre von den Algorithmen, dabei löst jeder Algorithmus ein Problem. Die Komplexitätstheorie vergleicht die Schwierigkeit dieser Probleme mittels sogenannter Komplexitätsklassen. Eine interaktive Übersicht erklärt die Klassen und das jeweils schwerste Spiel daraus... versuch' doch mal diese Probleme zu Lösen!

Das Postsche Korrespondenzproblem (PCP)

Ergänze die Reihe! Obere und untere Farbfolge sollen übereinstimmen, die Spielfläche ist nicht begrenzt. Man kann keine Schranke für die Größe der Lösungskandidaten angeben.

Pentominos - Ein Klassiker neu entdeckt

Pentominos sind gewisse Spielsteine oder Figuren, ein kleiner Bruder der Pentomino-Steine ist der bekannte Domino-Stein - ein Spielstein, der aus 2 Quadraten zusammengeklebt ist. Ebenfalls bekannt sind die Tetromino-Steine aus dem Spiel Tetris. Ein Pentomino-Stein ist aus 5 Quadraten zusammengesetzt (griech.: «pento-» = fünf).

Knoten im Kopf

Knoten kennt jeder. Die meisten verknoten jeden morgen ihre Schnürsenkel, aber was hat das mit Mathematik zu tun? Lerne, Knoten zu vergleichen und Knoten zu multiplizieren!

Das Parkettierungsproblem

Kann man mit solchen Kacheln beliebig große Flächen füllen, so daß alle Kreisteile zusammenpassen?

Bin Packing (exakt und approximiert)

Passen die Gegenstände in die Behälter (englisch: bins)? Jeder Gegenstand hat ein bestimmtes Gewicht und jeder Behälter kann ein bestimmtes Gesamtgewicht aufnehmen. Die Gegenstände sind nicht teilbar.

Spiele mit Wasser

Es geht darum eine bestimmte Wassermenge abzumessen, wobei man nur Wasser zwischen vorgegebenen Gefäßen hin- und herschütten darf.

Hat jede Fläche eine Rückseite? - Das Möbiusband

Es handelt sich um eine endliche gekrümmte Fläche im dreidimensionalen Raum, die nur einen Rand und daher auch keine 'Oberseite' bzw. 'Unterseite' besitzt, also 'einseitig' ist. Möbius hat sie konstruiert, um eine Fläche zu erhalten, in der keine Orientierung möglich ist, man also nicht zwischen links und rechts unterscheiden kann.

Der Turm von Hanoi

Im Großen Tempel von Benares, unter dem Dom, der die Mitte der Welt markiert, ruht eine Platte, in der 3 Diamantnadeln befestigt sind, jede eine Elle hoch. Bei der Erschaffung der Welt hat Gott 64 Scheiben aus purem Gold auf eine der Nadeln gesteckt, wobei die größte Scheibe auf der Platte ruht, und die übrigen, immer kleiner werdend, eine auf der anderen...

Tetrominos - Tetris einmal anders

Wenn man vier gleichgroße Quadrate zusammengefügt, entstehen Spielsteine verschiedener Größe und Form. Damit kann man vorgegebene Flächen (meist Quadrate oder Rechtecke, auch mit Aussparungen) ausfüllen.

Lunar Lockout - Verschiebe-Puzzles

Ein Spielstein zieht nach Norden, Osten, Süden oder Westen solange, bis er direkt vor einem anderen Stein stehenbleibt. Finde eine Zugfolge, nach der einer der sechs Steine auf der markierten Position in der Mitte steht!

Ausflug in die vierte Dimension

Der vierdimensionale Würfel entsteht als Überdeckungsgebilde, wenn ein gewöhnlicher dreidimensionaler Würfel der Kantenlänge a in einer vierten Dimension senkrecht zum gesamten dreidimensionalen Raum um die Länge a bewegt wird.