Allgemein, Astronomie, Informatik, Mathematik, Physik

Die Millennium Probleme {Teil 2}

Die Millennium Probleme sind sieben mathematische Probleme, die 2000 in einer Liste zusammengefasst wurden. Vom Clay Mathematics Institute in Cambridge (USA) wurde diese Liste nicht nur veröffentlicht, sondern für jedes dieser Probleme wurden jeweils 1 Million Dollar als Prämie ausgelobt. Allerdings – seien wir ehrlich – wird niemand ernsthaft nur wegen dieses Preises eines der Probleme lösen. Denn es handelt sich nicht um Fragestellungen, die man mal eben mit ein bisschen Disziplin sofort lösen könnte – zumindest ist das wahrscheinlich so. Auf der anderen Seite: Wer weiß, vielleicht braucht man nur diese eine gute Idee, die noch niemand hatte und Zack: Das Problem ist gelöst.

Die ersten drei der Probleme habe ich euch bereits in einem Artikel vorgestellt, heute habe ich die restlichen vier für euch dabei. HIER findet ihr den anderen Artikel.

Das Logo des Clay Mathematics Institute

Werfen wir einen genaueren Blick auf den zweiten Teil der sieben Probleme:

Warte, hier geht es weiter! …

Advertisements
Allgemein, Informatik, Mathematik

Über den Hamiltonkreis und NP-Vollständigkeit

Im heutigen Artikel möchte ich euch noch einmal mit in die Welt der Graphentheorie nehmen.

Vor einem Weilchen hatte ich euch ja bereits über das Königsberger Brückenproblem berichtet. Dabei ging es darum, dass Leonhard Euler ein einfaches Kriterium angeben konnte, wie sich die Anzahl der Brücken (dargestellt durch Kanten) und der Landteile (dargestellt durch Punkte / Ecken) zueinander verhalten müsste, damit es in einem Graphen einen Eulerkreis geben kann. Dabei ist ein Eulerkreis ein Weg durch den Graphen, bei dem jede Kante genau einmal passiert wird. Wer den kompletten Artikel dazu noch einmal lesen möchte, klickt HIER.

Der Graph zum Königsberger Brückenproblem. Einen Eulerweg gibt es nicht, wie ist es mit einem Hamiltonweg?

Heute geht es um eine ganz leicht veränderte Fragestellung, die aber einen riesigen Unterschied in der Lösung machen wird!

Warte, hier geht es weiter! …