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 Individualisierte Faserkomponenten für den Weltmarkt
22.06.2017 | Laser Zentrum Hannover e.V. (LZH)

nachricht Innovative High Power LED Light Engine für den UV Bereich
22.06.2017 | Omicron - Laserage Laserprodukte 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: Klima-Satellit: Mit robuster Lasertechnik Methan auf der Spur

Hitzewellen in der Arktis, längere Vegetationsperioden in Europa, schwere Überschwemmungen in Westafrika – mit Hilfe des deutsch-französischen Satelliten MERLIN wollen Wissenschaftler ab 2021 die Emissionen des Treibhausgases Methan auf der Erde erforschen. Möglich macht das ein neues robustes Lasersystem des Fraunhofer-Instituts für Lasertechnologie ILT in Aachen, das eine bisher unerreichte Messgenauigkeit erzielt.

Methan entsteht unter anderem bei Fäulnisprozessen. Es ist 25-mal wirksamer als das klimaschädliche Kohlendioxid, kommt in der Erdatmosphäre aber lange nicht...

Im Focus: Climate satellite: Tracking methane with robust laser technology

Heatwaves in the Arctic, longer periods of vegetation in Europe, severe floods in West Africa – starting in 2021, scientists want to explore the emissions of the greenhouse gas methane with the German-French satellite MERLIN. This is made possible by a new robust laser system of the Fraunhofer Institute for Laser Technology ILT in Aachen, which achieves unprecedented measurement accuracy.

Methane is primarily the result of the decomposition of organic matter. The gas has a 25 times greater warming potential than carbon dioxide, but is not as...

Im Focus: How protons move through a fuel cell

Hydrogen is regarded as the energy source of the future: It is produced with solar power and can be used to generate heat and electricity in fuel cells. Empa researchers have now succeeded in decoding the movement of hydrogen ions in crystals – a key step towards more efficient energy conversion in the hydrogen industry of tomorrow.

As charge carriers, electrons and ions play the leading role in electrochemical energy storage devices and converters such as batteries and fuel cells. Proton...

Im Focus: Die Schweiz in Pole-Position in der neuen ESA-Mission

Die Europäische Weltraumagentur ESA gab heute grünes Licht für die industrielle Produktion von PLATO, der grössten europäischen wissenschaftlichen Mission zu Exoplaneten. Partner dieser Mission sind die Universitäten Bern und Genf.

Die Europäische Weltraumagentur ESA lanciert heute PLATO (PLAnetary Transits and Oscillation of stars), die grösste europäische wissenschaftliche Mission zur...

Im Focus: Forscher entschlüsseln erstmals intaktes Virus atomgenau mit Röntgenlaser

Bahnbrechende Untersuchungsmethode beschleunigt Proteinanalyse um ein Vielfaches

Ein internationales Forscherteam hat erstmals mit einem Röntgenlaser die atomgenaue Struktur eines intakten Viruspartikels entschlüsselt. Die verwendete...

Alle Focus-News des Innovations-reports >>>

Anzeige

Anzeige

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

10. HDT-Tagung: Elektrische Antriebstechnologie für Hybrid- und Elektrofahrzeuge

22.06.2017 | Veranstaltungen

„Fit für die Industrie 4.0“ – Tagung von Hochschule Darmstadt und Schader-Stiftung am 27. Juni

22.06.2017 | Veranstaltungen

Forschung zu Stressbewältigung wird diskutiert

21.06.2017 | Veranstaltungen

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

Individualisierte Faserkomponenten für den Weltmarkt

22.06.2017 | Physik Astronomie

Evolutionsbiologie: Wie die Zellen zu ihren Kraftwerken kamen

22.06.2017 | Biowissenschaften Chemie

Spinflüssigkeiten – zurück zu den Anfängen

22.06.2017 | Physik Astronomie