Eine spezielle Aufgabe für die DNA... - scinexx | Das Wissensmagazin
Anzeige
Anzeige

Eine spezielle Aufgabe für die DNA…

Das Problem eines Handlungsreisenden

Spätestens seit seiner Lektüre von „Molecular Biology of the Gene“ war für Adleman eindeutig klar: Die DNA kann rechnen. Doch offensichtlich hatte die Natur in ihrer Milliarden Jahre dauernden Entwicklung zwar eine Fülle von natürlichen Informationsverarbeitungsmaschinen produziert, aber keine, die per se als Computerersatz taugte. Die DNA und RNA-Stränge und zahlreichen Enzyme machten ihren jeweiligen „Job“ perfekt, aber erschienen nicht gerade dazu geeignet, zwei Zahlen zu addieren oder als Schachcomputer Dienst zu tun.

Wenn Adleman also versuchen wollte, einen universell einsetzbaren DNA-Computer zu bauen, musste er die von der Natur vorgegebenen Werkzeuge zweckentfremden. Und um dabei die richtigen Strukturen und Techniken zu erproben, konnte dies nicht in einem großen Schritt geschehen, sondern nur Stück für Stück. Adleman: „Es galt klein anzufangen, mit einem DNA-Computer, der ein spezielles Problem löste – aber nicht zu speziell, damit das Potential der neuartigen Rechenmethode deutlich zutage trat.“

Auf der Suche nach einem geeigneten begrenzten Problem verfiel Adleman auf einen Klassiker unter den mathematischen Gedankenspielen – das Handlungsreisenden-Problem, auch „Hamiltonsche Wege“ genannt. Dieses vom irischen Hofastronom William Rowan Hamilton Mitte des 19. Jahrhunderts aufgestellte Denkspiel stellte die Aufgabe, von einem Startknoten ausgehend einen Weg zu einem Ziel zu finden und dabei auf dem Weg alle anderen vorgegebenen Stationen genau einmal zu berühren.

Oder weniger abstrakt ausgedrückt: Ein Handlungsreisender soll eine bestimmte Anzahl von Städten besuchen und dabei den kürzesten Weg zwischen ihnen finden. Die Schwierigkeit dabei: Nicht alle Städte sind über Direktflüge miteinander verbunden, es gibt auch „Einbahnstraßen“. Außerdem darf er jede Stadt nur einmal besuchen.

Während das Problem mit einer kleinen Anzahl von Städten noch leicht zu lösen ist, wächst die Schwierigkeit mit steigender Knotenzahl exponentiell an. Es gibt bereits Anordnungen mit 100 Knoten, bei denen selbst die schnellsten heutigen Supercomputer Millionen von Jahren bräuchten, um den Hamilton-Pfad herauszufinden. Unter Informatikern gilt dieses Problem daher als „NP-unvollständig“ – als nicht effizient mit einem Algorithmus zu lösen. Alle möglichen Algorithmen bestehen aus einer so großes Menge an Einzelschritten, dass Computer entweder extrem lange brauchen oder am Ende sogar ein falsches Ergebnis liefern würden.

Anzeige

Und genau dieses vertrackte Problem sollte nun die Rechenkünste der DNA beweisen…

  1. zurück
  2. |
  3. 1
  4. |
  5. 2
  6. |
  7. 3
  8. |
  9. 4
  10. |
  11. 5
  12. |
  13. 6
  14. |
  15. 7
  16. |
  17. 8
  18. |
  19. 9
  20. |
  21. weiter


Stand: 16.10.2001

Anzeige

In den Schlagzeilen

Inhalt des Dossiers

Computer der Zukunft
Rechnen mit Quanten, Licht und DNA

An zwei Orten zugleich...
Geheimnisse der Quantenwelt

Weder Null noch Eins oder beides zugleich...
Das Prinzip des Quantenbits

Messen ohne hinzuschauen...
Hindernisse auf dem Weg zum Quantencomputer

Aus dem Werkzeugkasten der Natur...
Rechnen mit Biomolekülen

Eine spezielle Aufgabe für die DNA...
Das Problem eines Handlungsreisenden

Man nehme einen Teelöffel voll DNA...
Adlemans DNA-Rechenexperiment

Sieben Städte in sieben Tagen...
Suche nach der Nadel im Heuhaufen

DNA so schwer wie die Erde...
Hindernisse auf dem Weg zum DNA-Computer

Diaschauen zum Thema

keine Diaschauen verknüpft

News zum Thema

keine News verknüpft

Dossiers zum Thema

Anzeige
Anzeige