Forum für Wissenschaft, Industrie und Wirtschaft

Hauptsponsoren:     3M 
Datenbankrecherche:

 

Kurzsichtig durch ein Netz von Farben

09.02.2009
Wissenschaftler aus Göttingen entwickeln einen Computer-Algorithmus, um bisher unlösbare Abzählprobleme zu knacken.

Wie viele unterschiedliche Sudokus gibt es? Auf wie viele verschiedene Weisen lassen sich die Länder auf einer Landkarte einfärben? Und wie verhalten sich die Atome in einem Festkörper? Forscher vom Max-Planck-Institut für Dynamik und Selbstorganisation in Göttingen und der Cornell University (Ithaca, USA) haben nun eine neuartige Methode entwickelt, mit der sich diese Fragen schnell beantworten lassen. Prinzipiell war zwar bisher ein Lösungsweg bekannt.

Doch für die meisten Anwendungen konnten Computer die Lösung nicht bestimmen. Die nötige Rechenzeit war zu lang. In der neuen Methode schauen die Wissenschaftler nun nur einzelne Ausschnitte des Problems an und arbeiten diese nacheinander ab. Bislang hatten sie in jedem Rechenschritt etwa die gesamte Landkarte oder das gesamte Sudoku im Blick. Viele Fragestellungen aus Physik, Mathematik und Informatik lassen sich so erstmals beantworten. (New Journal of Physics, 4. Februar 2009)

Ob Sudoku, Deutschlandkarte oder Festkörper - in allen Fällen geht es darum, Möglichkeiten zu zählen. Beim Sudoku sind es die erlaubten Lösungen, beim Festkörper die möglichen Anordnungen der Atome. Und im Fall der Landkarte stellt sich die Frage, auf wie viele Weisen sich die Karte einfärben lässt, so dass benachbarte Länder stets verschiedene Farben tragen. Abzähl-Probleme dieser Art stellen Wissenschaftler als Netz aus Linien und Knoten dar. Beantworten müssen die Forscher dann nur eine Frage: Auf wie viele Weisen lassen sich die Knoten einfärben, wenn eine bestimmte Anzahl von Farben vorgegeben ist? Einzige Bedingung: Knoten, die durch eine Linie verbunden sind, dürfen nicht dieselbe Farbe haben. Je nach Anwendung kommt der "Farbe" eines Knotens dabei eine völlig andere Bedeutung zu. Im Fall der Landkarte ist mit "Farbe" tatsächlich die Farbe gemeint, beim Sudoku entsprechen den "Farben" verschiedene Ziffern.

"Der bisherige Algorithmus kopiert bei jedem Rechenschritt das gesamte Netz und ändert dabei jeweils nur einen Aspekt", erklärt Frank van Bussel vom Max-Planck-Institut für Dynamik und Selbstorganisation (MPIDS). Mit zunehmender Anzahl von Knoten nimmt die Rechenzeit deshalb dramatisch zu. Für ein quadratisches Gitter von der Größe eines Schachbretts etwa beträgt sie schätzungsweise viele Milliarden Jahre. Der neue Algorithmus, den die Wissenschaftler aus Göttingen entwickelt haben, ist deutlich schneller. "Unsere Rechnung für das Schachbrett-Gitter dauert nur sieben Sekunden", führt Denny Fliegner vom MPIDS aus.

Der Trick: Mit der neuen Methode hangeln sich die Forscher von Knoten zu Knoten durch das Netz. Als sei das Computerprogramm kurzsichtig, berücksichtigt es stets nur den nächsten Knotenpunkt. Das gesamte Netz hat es nicht im Blick. Am ersten Knotenpunkt etwa, kann es zwar noch keine Farbe endgültig auswählen. Denn dafür müsste es wissen, wie alle anderen Knoten miteinander verbunden sind. Doch anstatt diese Frage sofort zu klären, notiert das Programm für den ersten Gitterpunkt eine Formel, die diese Unwägbarkeit als unbekannte Größe enthält. Beim Fortschreiten durch das Netz werden nach und nach alle Verbindungen sichtbar und die Unbekannten entfallen. Am letzten Knotenpunkt angekommen, kennt das Programm dann das gesamte Netz.

Diese neue Methode ist auf deutlich komplizierte Fälle anwendbar als der bisherige Standard-Algorithmus. "Wir können nun viele Fragen aus Physik, Graphentheorie und Informatik beantworten, die bisher praktisch unlösbar waren", sagt Marc Timme vom MPIDS. "Unsere Methode lässt sich beispielsweise auch auf antiferromagnetische Festkörper anwenden", fügt er hinzu. In diesen Festkörpern besitzt jedes Atom einen inneren Drehimpuls, den so genannten Spin, der verschiedene Werte annehmen kann. Die atomaren Spins richten sich in der Regel so aus, dass benachbarte Atome verschiedene Spins aufweisen. Die Anzahl der möglichen Anordnungen ist nun auch in der Praxis berechenbar. Daraus können Physiker auf grundlegende Eigenschaften der Thermodynamik von Festkörpern schließen.

Dr. Birgit Krummheuer | idw
Weitere Informationen:
http://www.ds.mpg.de/
http://www.iop.org/EJ/abstract/1367-2630/11/2/023001/

Weitere Nachrichten aus der Kategorie Physik Astronomie:

nachricht Topologische Isolatoren: Neuer Phasenübergang entdeckt
17.10.2017 | Helmholtz-Zentrum Berlin für Materialien und Energie GmbH

nachricht Vorhersagen bestätigt: Schwere Elemente bei Neutronensternverschmelzungen nachgewiesen
17.10.2017 | GSI Helmholtzzentrum für Schwerionenforschung GmbH

Alle Nachrichten aus der Kategorie: Physik Astronomie >>>

Die aktuellsten Pressemeldungen zum Suchbegriff Innovation >>>

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

Im Focus: Sicheres Bezahlen ohne Datenspur

Ob als Smartphone-App für die Fahrkarte im Nahverkehr, als Geldwertkarten für das Schwimmbad oder in Form einer Bonuskarte für den Supermarkt: Für viele gehören „elektronische Geldbörsen“ längst zum Alltag. Doch vielen Kunden ist nicht klar, dass sie mit der Nutzung dieser Angebote weitestgehend auf ihre Privatsphäre verzichten. Am Karlsruher Institut für Technologie (KIT) entsteht ein sicheres und anonymes System, das gleichzeitig Alltagstauglichkeit verspricht. Es wird nun auf der Konferenz ACM CCS 2017 in den USA vorgestellt.

Es ist vor allem das fehlende Problembewusstsein, das den Informatiker Andy Rupp von der Arbeitsgruppe „Kryptographie und Sicherheit“ am KIT immer wieder...

Im Focus: Neutron star merger directly observed for the first time

University of Maryland researchers contribute to historic detection of gravitational waves and light created by event

On August 17, 2017, at 12:41:04 UTC, scientists made the first direct observation of a merger between two neutron stars--the dense, collapsed cores that remain...

Im Focus: Breaking: the first light from two neutron stars merging

Seven new papers describe the first-ever detection of light from a gravitational wave source. The event, caused by two neutron stars colliding and merging together, was dubbed GW170817 because it sent ripples through space-time that reached Earth on 2017 August 17. Around the world, hundreds of excited astronomers mobilized quickly and were able to observe the event using numerous telescopes, providing a wealth of new data.

Previous detections of gravitational waves have all involved the merger of two black holes, a feat that won the 2017 Nobel Prize in Physics earlier this month....

Im Focus: Topologische Isolatoren: Neuer Phasenübergang entdeckt

Physiker des HZB haben an BESSY II Materialien untersucht, die zu den topologischen Isolatoren gehören. Dabei entdeckten sie einen neuen Phasenübergang zwischen zwei unterschiedlichen topologischen Phasen. Eine dieser Phasen ist ferroelektrisch: das bedeutet, dass sich im Material spontan eine elektrische Polarisation ausbildet, die sich durch ein äußeres elektrisches Feld umschalten lässt. Dieses Ergebnis könnte neue Anwendungen wie das Schalten zwischen unterschiedlichen Leitfähigkeiten ermöglichen.

Topologische Isolatoren zeichnen sich dadurch aus, dass sie an ihren Oberflächen Strom sehr gut leiten, während sie im Innern Isolatoren sind. Zu dieser neuen...

Im Focus: Smarte Sensoren für effiziente Prozesse

Materialfehler im Endprodukt können in vielen Industriebereichen zu frühzeitigem Versagen führen und den sicheren Gebrauch der Erzeugnisse massiv beeinträchtigen. Eine Schlüsselrolle im Rahmen der Qualitätssicherung kommt daher intelligenten, zerstörungsfreien Sensorsystemen zu, die es erlauben, Bauteile schnell und kostengünstig zu prüfen, ohne das Material selbst zu beschädigen oder die Oberfläche zu verändern. Experten des Fraunhofer IZFP in Saarbrücken präsentieren vom 7. bis 10. November 2017 auf der Blechexpo in Stuttgart zwei Exponate, die eine schnelle, zuverlässige und automatisierte Materialcharakterisierung und Fehlerbestimmung ermöglichen (Halle 5, Stand 5306).

Bei Verwendung zeitaufwändiger zerstörender Prüfverfahren zieht die Qualitätsprüfung durch die Beschädigung oder Zerstörung der Produkte enorme Kosten nach...

Alle Focus-News des Innovations-reports >>>

Anzeige

Anzeige

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

DFG unterstützt Kongresse und Tagungen - Dezember 2017

17.10.2017 | Veranstaltungen

Intelligente Messmethoden für die Bauwerkssicherheit: Fachtagung „Messen im Bauwesen“ am 14.11.2017

17.10.2017 | Veranstaltungen

Meeresbiologe Mark E. Hay zu Gast bei den "Noblen Gesprächen" am Beutenberg Campus in Jena

16.10.2017 | Veranstaltungen

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

Sicheres Bezahlen ohne Datenspur

17.10.2017 | Informationstechnologie

Pflanzen gegen Staunässe schützen

17.10.2017 | Biowissenschaften Chemie

Den Trends der Umweltbranche auf der Spur

17.10.2017 | Ökologie Umwelt- Naturschutz