Forum für Wissenschaft, Industrie und Wirtschaft

Hauptsponsoren:     3M 
Datenbankrecherche:

 

Dominosteine auf der unendlichen Ebene

02.02.2001


Das Spiel mit den zweigeteilten Steinen, die an gleichwertigen Enden aneinandergefügt werden, ist ein Einwanderer aus Fernost: Dominos sind in China schon seit tausend Jahren bekannt. Erst Anfang des 18. Jahrhunderts fanden die gepunkteten Steine den Weg nach Europa, wo sie heute in der Spielesammlung kaum einer Familie fehlen. Triominos - nach demselben Prinzip anlegbare Dreiecke - machen ihnen neuerdings Konkurrenz, und Tüftler kennen Pentominos oder andere Polyominos als ausgefallene Art des Puzzlespiels. Dass Dominosteine mit wenigen einfachen Veränderungen ganz neue, spannende Spielvarianten ermöglichen könnten, ist dagegen ein Einfall, der bisher nicht realisiert wurde. Die Idee stammt von Horst Müller, Professor am Institut für Informatik der Universität Erlangen-Nürnberg, und die Anregung dazu hat er aus seinem Berufsfeld bezogen, der Theoretischen Informatik.

Bunte, flache Klötze, per Hand sorgfältig lackiert - und das auf dem Arbeitstisch eines Wissenschaftlers? Die Antwort auf die Frage, ob diese Holzteilchen zum Zeitvertreib und zur Ablenkung da sind oder vielleicht doch mit Informatik zu tun haben, lautet: beides. Es sind Dominos, wie sie in mathematisch formulierbaren Problemen auftauchen. Anders als bei den gewohnten länglichen Spielsteinen, die zwei Felder mit je einer Punktzahl tragen, wird ihnen für jede der vier Seiten eine bestimmte Eigenschaft zugewiesen.

Die einfachste Variante, die auf Professor Müllers Tisch liegt, trägt deshalb auf der quadratischen Oberfläche vier Farbfelder, wie durch ein Kreuz von Eck zu Eck unterteilt. So wird klar, welche Farbe welcher Seite zugeordnet ist. Wie beim üblichen Dominospiel gleiche Punktwerte zueinander passen, müssen hier gleiche Farben - blau, grün oder gelb - aufeinander treffen. Die Vierfarb-Dominos dürfen jedoch nicht gedreht werden: ein Teil, dem Gelb für den "Norden" zugewiesen wurde, muss immer mit der gelben Kante nach oben liegen.

Wenn Professor Müller in seiner Vorlesung über "Perlen der Theoretischen Informatik" über Varianten des Domino-Problems spricht, geht es allerdings nicht um ein Spiel, bei dem die Gegner versuchen, ihre Steine möglichst schnell anzusetzen, um als erster nichts mehr auf der Hand zu haben. Es geht um Entscheidbarkeit, um Berechenbarkeit. In die Anwendung übersetzt, bedeutet das: Kann ein Algorithmus - eine Rechenvorschrift - gefunden werden, mittels derer ein Computer eine bestimmte Aufgabe lösen kann, oder ist das für diese Aufgabe prinzipiell unmöglich? Für Computer, die nur eine begrenzte Anzahl von Rechenoperationen ausführen können, gibt es Probleme, vor denen sie unweigerlich versagen müssen.

Das beschränkte und das uneingeschränkte Domino-Problem sind Fachleuten als Beispiele für Entscheidbarkeit oder Unentscheidbarkeit bekannt. Die Frage lautet: Können derartige Domino-Teile, wenn sie in unbegrenzter Zahl, aber mit festgelegten Eigenschaften zur Verfügung stehen, eine unendliche Fläche völlig ausfüllen? Dass über die Möglichkeit, eine Ebene auf diese Art zu "parkettieren", nichts gesagt werden kann, wenn die Eigenschaften der Dominos nicht genauer beschrieben werden, lässt sich beweisen. Andernfalls kommt es darauf an, um welche Art von Domino-Steinen es sich handelt.

Für die vierfarbigen Plättchen beispielsweise lässt sich allein durch Ausprobieren relativ schnell eine Anordnung aus wenigen Teilen finden, die - wie eine Wandkachel oder ein Tapetenmuster - in jeder Richtung immer wieder aneinandergesetzt werden könnte und deshalb auch bis ins Unendliche reicht. Sehr viel schwieriger wird es, wenn die Domino-Seiten keine Farbeigenschaft haben, sondern etwa schräg aufgesetzte, herausragende oder eingekerbte Dreiecke darüber bestimmen, ob zwei Seiten aneinandergefügt werden können. Auch wenn sich für konkrete Dominosteine das Problem als nicht berechenbar erweist, bleibt das Ausprobieren noch offen - mit viel Geduld und Glück könnte ja ein Parkett zustandekommen. Nur dann ist tatsächlich die Entscheidung gefallen. "Wenn es nicht funktioniert, kann man nichts darüber sagen, ob es nicht grundsätzlich möglich wäre", erklärt Professor Müller.

Tiefer in die theoretische Informatik einzudringen, ist jedoch nicht nötig, um deren Definition von Dominosteinen für den Entwurf neuer Spiele zu nutzen. Mathematische Regeln liegen vielen gebräuchlichen Spielen zugrunde, und Spielbegeisterte wenden sie an, ohne dass ihnen dies überhaupt bewusst wird. Professor Müller, der sich auch mit Labyrinthen auskennt, hat mehrere, sowohl einfache wie komplexe Domino-Varianten vorrätig, die zu Puzzles für Denksportler oder zu Legespielen mit Wettbewerbsregeln tauglich wären. Informatik und Mathematik als Quellen für Spiel-Ideen zu benutzen, ist keineswegs ein abwegiger Gedanke. M.C. Escher, als Grafiker für seine Einfälle berühmt, schrieb vor fast dreißig Jahren über die Mathematiker seines Bekanntenkreises: "Wie verspielt die gelehrten Damen und Herren doch sein können!"

Kontakt:
Prof. Dr. Horst Müller, Professur für Theoretische Informatik

... mehr zu:
»Domino »Dominostein »Dominosteine

Martensstraße 3, 91058 Erlangen
Tel.: 09131/85 -27911, Fax: 09131/85 -27239
E-Mail: mueller@informatik.uni-erlangen.de

Weitere Informationen finden Sie im WWW:


Gertraud Pickel | idw

Weitere Berichte zu: Domino Dominostein Dominosteine

Weitere Nachrichten aus der Kategorie Interdisziplinäre Forschung:

nachricht Neues Verbundprojekt erforscht die neurodegenerative Erkrankung Morbus Alzheimer
12.09.2017 | Universitätsklinikum Würzburg

nachricht Damit sich Mensch und Maschine besser verstehen
04.09.2017 | Technische Universität Chemnitz

Alle Nachrichten aus der Kategorie: Interdisziplinäre Forschung >>>

Die aktuellsten Pressemeldungen zum Suchbegriff Innovation >>>

Die letzten 5 Focus-News des innovations-reports im Überblick:

Im Focus: Tiny lasers from a gallery of whispers

New technique promises tunable laser devices

Whispering gallery mode (WGM) resonators are used to make tiny micro-lasers, sensors, switches, routers and other devices. These tiny structures rely on a...

Im Focus: Wundermaterial Graphen: Gewölbt wie das Polster eines Chesterfield-Sofas

Graphen besitzt extreme Eigenschaften und ist vielseitig verwendbar. Mit einem Trick lassen sich sogar die Spins im Graphen kontrollieren. Dies gelang einem HZB-Team schon vor einiger Zeit: Die Physiker haben dafür eine Lage Graphen auf einem Nickelsubstrat aufgebracht und Goldatome dazwischen eingeschleust. Im Fachblatt 2D Materials zeigen sie nun, warum dies sich derartig stark auf die Spins auswirkt. Graphen kommt so auch als Material für künftige Informationstechnologien infrage, die auf der Verarbeitung von Spins als Informationseinheiten basieren.

Graphen ist wohl die exotischste Form von Kohlenstoff: Alle Atome sind untereinander nur in der Ebene verbunden und bilden ein Netz mit sechseckigen Maschen,...

Im Focus: Hochautomatisiertes Fahren bei Schnee und Regen: Robuste Warnehmung dank intelligentem Sensormix

Schlechte Sichtverhältnisse bei Regen oder Schnellfall sind für Menschen und hochautomatisierte Fahrzeuge eine große Herausforderung. Im europäischen Projekt RobustSENSE haben die Forscher von Fraunhofer FOKUS mit 14 Partnern, darunter die Daimler AG und die Robert Bosch GmbH, in den vergangenen zwei Jahren eine Softwareplattform entwickelt, auf der verschiedene Sensordaten von Kamera, Laser, Radar und weitere Informationen wie Wetterdaten kombiniert werden. Ziel ist, eine robuste und zuverlässige Wahrnehmung der Straßensituation unabhängig von der Komplexität und der Sichtverhältnisse zu gewährleisten. Nach der virtuellen Erprobung des Systems erfolgt nun der Praxistest, unter anderem auf dem Berliner Testfeld für hochautomatisiertes Fahren.

Starker Schneefall, ein Ball rollt auf die Fahrbahn: Selbst ein Mensch kann mitunter nicht schnell genug erkennen, ob dies ein gefährlicher Gegenstand oder...

Im Focus: Ultrakurze Momentaufnahmen der Dynamik von Elektronen in Festkörpern

Mit Hilfe ultrakurzer Laser- und Röntgenblitze haben Wissenschaftler am Max-Planck-Institut für Quantenoptik (Garching bei München) Schnappschüsse der bislang kürzesten Bewegung von Elektronen in Festkörpern gemacht. Die Bewegung hielt 750 Attosekunden lang an, bevor sie abklang. Damit stellten die Wissenschaftler einen neuen Rekord auf, ultrakurze Prozesse innerhalb von Festkörpern aufzuzeichnen.

Wenn Röntgenstrahlen auf Festkörpermaterialien oder große Moleküle treffen, wird ein Elektron von seinem angestammten Platz in der Nähe des Atomkerns...

Im Focus: Ultrafast snapshots of relaxing electrons in solids

Using ultrafast flashes of laser and x-ray radiation, scientists at the Max Planck Institute of Quantum Optics (Garching, Germany) took snapshots of the briefest electron motion inside a solid material to date. The electron motion lasted only 750 billionths of the billionth of a second before it fainted, setting a new record of human capability to capture ultrafast processes inside solids!

When x-rays shine onto solid materials or large molecules, an electron is pushed away from its original place near the nucleus of the atom, leaving a hole...

Alle Focus-News des Innovations-reports >>>

Anzeige

Anzeige

IHR
JOB & KARRIERE
SERVICE
im innovations-report
in Kooperation mit academics
Veranstaltungen

Höher - schneller - weiter: Der Faktor Mensch in der Luftfahrt

20.09.2017 | Veranstaltungen

Wälder unter Druck: Internationale Tagung zur Rolle von Wäldern in der Landschaft an der Uni Halle

20.09.2017 | Veranstaltungen

7000 Teilnehmer erwartet: 69. Urologen-Kongress startet heute in Dresden

20.09.2017 | Veranstaltungen

 
VideoLinks
B2B-VideoLinks
Weitere VideoLinks >>>
Aktuelle Beiträge

Drohnen sehen auch im Dunkeln

20.09.2017 | Informationstechnologie

Pfeilgiftfrösche machen auf „Kommando“ Brutpflege für fremde Kaulquappen

20.09.2017 | Biowissenschaften Chemie

Frühwarnsystem für gefährliche Gase: TUHH-Forscher erreichen Meilenstein

20.09.2017 | Energie und Elektrotechnik