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 Matrix-Theorie als Ursprung von Raumzeit und Kosmologie
23.05.2018 | Universität Wien

nachricht Rotierende Rugbybälle unter den massereichsten Galaxien
23.05.2018 | Leibniz-Institut für Astrophysik Potsdam

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: Molecular switch will facilitate the development of pioneering electro-optical devices

A research team led by physicists at the Technical University of Munich (TUM) has developed molecular nanoswitches that can be toggled between two structurally different states using an applied voltage. They can serve as the basis for a pioneering class of devices that could replace silicon-based components with organic molecules.

The development of new electronic technologies drives the incessant reduction of functional component sizes. In the context of an international collaborative...

Im Focus: GRACE Follow-On erfolgreich gestartet: Das Satelliten-Tandem dokumentiert den globalen Wandel

Die Satellitenmission GRACE-FO ist gestartet. Am 22. Mai um 21.47 Uhr (MESZ) hoben die beiden Satelliten des GFZ und der NASA an Bord einer Falcon-9-Rakete von der Vandenberg Air Force Base (Kalifornien) ab und wurden in eine polare Umlaufbahn gebracht. Dort nehmen sie in den kommenden Monaten ihre endgültige Position ein. Die NASA meldete 30 Minuten später, dass der Kontakt zu den Satelliten in ihrem Zielorbit erfolgreich hergestellt wurde. GRACE Follow-On wird das Erdschwerefeld und dessen räumliche und zeitliche Variationen sehr genau vermessen. Sie ermöglicht damit präzise Aussagen zum globalen Wandel, insbesondere zu Änderungen im Wasserhaushalt, etwa dem Verlust von Eismassen.

Potsdam, 22. Mai 2018: Die deutsch-amerikanische Satellitenmission GRACE-FO (Gravity Recovery And Climate Experiment Follow On) ist erfolgreich gestartet. Am...

Im Focus: Faserlaser mit einstellbarer Wellenlänge

Faserlaser sind ein effizientes und robustes Werkzeug zum Schweißen und Schneiden von Metallen beispielsweise in der Automobilindustrie. Systeme bei denen die Wellenlänge des Laserlichts flexibel einstellbar ist, sind für spektroskopische Anwendungen und die Medizintechnik interessant. Wissenschaftlerinnen und Wissenschaftler des Leibniz-Instituts für Photonische Technologien (Leibniz-IPHT) haben, im Rahmen des vom Bundesministerium für Bildung und Forschung (BMBF) geförderten Projekts „FlexTune“, ein neues Abstimmkonzept realisiert, das erstmals verschiedene Emissionswellenlängen voneinander unabhängig und zeitlich synchron erzeugt.

Faserlaser bieten im Vergleich zu herkömmlichen Lasern eine höhere Strahlqualität und Energieeffizienz. Integriert in einen vollständig faserbasierten...

Im Focus: LZH zeigt Lasermaterialbearbeitung von morgen auf der LASYS 2018

Auf der LASYS 2018 zeigt das Laser Zentrum Hannover e.V. (LZH) vom 5. bis zum 7. Juni Prozesse für die Lasermaterialbearbeitung von morgen in Halle 4 an Stand 4E75. Mit gesprengten Bombenhüllen präsentiert das LZH in Stuttgart zudem erste Ergebnisse aus einem Forschungsprojekt zur zivilen Sicherheit.

Auf der diesjährigen LASYS stellt das LZH lichtbasierte Prozesse wie Schneiden, Schweißen, Abtragen und Strukturieren sowie die additive Fertigung für Metalle,...

Im Focus: Achema 2018: Neues Kamerasystem überwacht Destillation und hilft beim Energiesparen

Um chemische Gemische in ihre Einzelbestandteile aufzutrennen, ist in der Industrie die energieaufwendige Destillation gängig, etwa bei der Raffinerie von Rohöl. Forscher der Technischen Universität Kaiserslautern (TUK) entwickeln ein Kamerasystem, das diesen Prozess überwacht. Dabei misst es, ob es zu einer starken Tropfenbildung kommt, was sich negativ auf die Trennung der Komponenten auswirken kann. Die Technik könnte hier künftig automatisch gegensteuern, wenn sich Messwerte ändern. So ließe sich auch Energie einsparen. Auf der Prozesstechnik-Messe Achema in Frankfurt stellen sie die Technik vom 11. bis 15. Juni am Forschungsstand des Landes Rheinland-Pfalz (Halle 9.2, Stand A86a) vor.

Bei der Destillation werden Flüssigkeiten durch Verdampfen und darauffolgende Kondensation des Dampfes in ihre Bestandteile getrennt. Ein bekanntes Beispiel...

Alle Focus-News des Innovations-reports >>>

Anzeige

Anzeige

VideoLinks
Industrie & Wirtschaft
Veranstaltungen

Größter Astronomie-Kongress kommt nach Wien

24.05.2018 | Veranstaltungen

22. Business Forum Qualität: Vom Smart Device bis zum Digital Twin

22.05.2018 | Veranstaltungen

48V im Fokus!

21.05.2018 | Veranstaltungen

VideoLinks
Wissenschaft & Forschung
Weitere VideoLinks im Überblick >>>
 
Aktuelle Beiträge

Vom Stroh zum Energieträger: Eintopf-Rezept für Wasserstoffgewinnung

24.05.2018 | Biowissenschaften Chemie

Steuern und Künstliche Intelligenz: WTS und DFKI auf der CEBIT

24.05.2018 | Messenachrichten

Größter Astronomie-Kongress kommt nach Wien

24.05.2018 | Veranstaltungsnachrichten

Weitere B2B-VideoLinks
IHR
JOB & KARRIERE
SERVICE
im innovations-report
in Kooperation mit academics