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 Die Sonne: Motor des Erdklimas
23.08.2017 | Generalverwaltung der Max-Planck-Gesellschaft, München

nachricht Entfesselte Magnetkraft
23.08.2017 | Generalverwaltung der Max-Planck-Gesellschaft, München

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: Platz 2 für Helikopter-Designstudie aus Stade - Carbontechnologie-Studenten der PFH erfolgreich

Bereits lange vor dem Studienabschluss haben vier Studenten des PFH Hansecampus Stade ihr ingenieurwissenschaftliches Können eindrucksvoll unter Beweis gestellt: Malte Blask, Hagen Hagens, Nick Neubert und Rouven Weg haben bei einem internationalen Wettbewerb der American Helicopter Society (AHS International) den zweiten Platz belegt. Ihre Aufgabe war es, eine Designstudie für ein helikopterähnliches Fluggerät zu entwickeln, das 24 Stunden an einem Punkt in der Luft fliegen kann.

Die vier Kommilitonen sind im Studiengang Verbundwerkstoffe/Composites am Hansecampus Stade der PFH Private Hochschule Göttingen eingeschrieben. Seit elf...

Im Focus: Wissenschaftler entdecken seltene Ordnung von Elektronen in einem supraleitenden Kristall

In einem Artikel der aktuellen Ausgabe des Forschungsmagazins „Nature“ berichten Wissenschaftler vom Max-Planck-Institut für Chemische Physik fester Stoffe in Dresden von der Entdeckung eines seltenen Materiezustandes, bei dem sich die Elektronen in einem Kristall gemeinsam in einer Richtung bewegen. Diese Entdeckung berührt eine der offenen Fragestellungen im Bereich der Festkörperphysik: Was passiert, wenn sich Elektronen gemeinsam im Kollektiv verhalten, in sogenannten „stark korrelierten Elektronensystemen“, und wie „einigen sich“ die Elektronen auf ein gemeinsames Verhalten?

In den meisten Metallen beeinflussen sich Elektronen gegenseitig nur wenig und leiten Wärme und elektrischen Strom weitgehend unabhängig voneinander durch das...

Im Focus: Wie ein Bakterium von Methanol leben kann

Bei einem Bakterium, das Methanol als Nährstoff nutzen kann, identifizierten ETH-Forscher alle dafür benötigten Gene. Die Erkenntnis hilft, diesen Rohstoff für die Biotechnologie besser nutzbar zu machen.

Viele Chemiker erforschen derzeit, wie man aus den kleinen Kohlenstoffverbindungen Methan und Methanol grössere Moleküle herstellt. Denn Methan kommt auf der...

Im Focus: Topologische Quantenzustände einfach aufspüren

Durch gezieltes Aufheizen von Quantenmaterie können exotische Materiezustände aufgespürt werden. Zu diesem überraschenden Ergebnis kommen Theoretische Physiker um Nathan Goldman (Brüssel) und Peter Zoller (Innsbruck) in einer aktuellen Arbeit im Fachmagazin Science Advances. Sie liefern damit ein universell einsetzbares Werkzeug für die Suche nach topologischen Quantenzuständen.

In der Physik existieren gewisse Größen nur als ganzzahlige Vielfache elementarer und unteilbarer Bestandteile. Wie das antike Konzept des Atoms bezeugt, ist...

Im Focus: Unterwasserroboter soll nach einem Jahr in der arktischen Tiefsee auftauchen

Am Dienstag, den 22. August wird das Forschungsschiff Polarstern im norwegischen Tromsø zu einer besonderen Expedition in die Arktis starten: Der autonome Unterwasserroboter TRAMPER soll nach einem Jahr Einsatzzeit am arktischen Tiefseeboden auftauchen. Dieses Gerät und weitere robotische Systeme, die Tiefsee- und Weltraumforscher im Rahmen der Helmholtz-Allianz ROBEX gemeinsam entwickelt haben, werden nun knapp drei Wochen lang unter Realbedingungen getestet. ROBEX hat das Ziel, neue Technologien für die Erkundung schwer erreichbarer Gebiete mit extremen Umweltbedingungen zu entwickeln.

„Auftauchen wird der TRAMPER“, sagt Dr. Frank Wenzhöfer vom Alfred-Wegener-Institut, Helmholtz-Zentrum für Polar- und Meeresforschung (AWI) selbstbewusst. Der...

Alle Focus-News des Innovations-reports >>>

Anzeige

Anzeige

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

Die Zukunft des Leichtbaus: Mehr als nur Material einsparen

23.08.2017 | Veranstaltungen

Logistikmanagement-Konferenz 2017

23.08.2017 | Veranstaltungen

DFG unterstützt Kongresse und Tagungen - Oktober 2017

23.08.2017 | Veranstaltungen

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

Spot auf die Maschinerie des Lebens

23.08.2017 | Biowissenschaften Chemie

Die Sonne: Motor des Erdklimas

23.08.2017 | Physik Astronomie

Entfesselte Magnetkraft

23.08.2017 | Physik Astronomie