Geheimnis-des-kürzestens-Weges

Buchvorstellung:

Das Geheimnis des kürzesten Weges

AUTOREN:

Renè Brandenberg,
Peter Gritzmann

In diesem Buch gibt es 2 Hauptpersonen. Die eine ist Ruth. Sie ist Schülerin und 15 Jahre alt. Ihr Gegenspieler ist eigentlich keine Person, sondern das Computerprogramm "Vim", welches denkt und spricht. Beide setzen sich mit dem Problem der Routenplanung auseinander. Vim hat die Rolle des Lehrenden, derjenige der alles erklärt und beantwortet. Ruth ist die Neugierige, die alles wissen und begreifen möchte. Das eigentliche Leben wie Freunde, Schule, erste Liebschaften, das Elternhaus sind nur Randerscheinungen in diesem Buch. Es wird die beste Freundin Martina und auch ihr Freund Jan erwähnt, sowie über die Eltern die recht sympathisch erscheinen geschrieben. Doch letztendlich sind all diese Dinge nur wie ein schöner Rahmen um ein Bild. Der eigentliche Inhalt ist die Routenplanung oder das "Geheimnis des kürzesten Weges" Die Geschichte Beginnt damit, dass Rut einen Computer von ihrem Vater geschenkt bekommt. Sie freut sich riesig über dieses Geschenk. Als sie den Computer hochfährt macht sie Bekanntschaft mit Vim.
Vim: "Hallo Ruth."
Ruth: "Wie? Was heißt hier `Hallo Ruth`?"
Vim: "Bitte nicht so schnell. Ich muss,ich erst an deine Stimme gewöhnen."
Ruth: "Das gibt's doch gar nicht. Die Kiste spricht nicht nur, sie versteht mich auch noch"
Vim: "Kiste? Meinst Du damit mich?"
Ruth: "äh ja, also eigentlich schon."
Vim: "Mein Namen ist Vim."
Ruth: "Vim? Und du findest ganz normal, dass du hier mit mir sprichst? Wer äh, was bist du und woher kennst meinen Namen."
Der Computer will ihr mit der Routenplanung die "trockene Mathematik" wieder schmackhaft machen. Die Mathematiker bezeichnen das auch als das kürzeste Weg - Problem. Dazu benutzen sie ein "Rezept" den Algorithmus. Dieser findet Anwendungen unter anderem bei der:
· Stadt und Verkehrsplanung
· Telekommunikation, Internet, Mobilfunk, Satellitenübertragung
· Hausbau - Reihenfolge, Projektplanung
· Organisation eines Rockkonzertes
· Fertigung von Leiterplatten und Computer, Fernseher usw.
Für die Routenplanung braucht man ein Modell, dass in der Realität verwendbar ist. Das ist z.B. ein Schnell - oder U-Bahnnetzplan. Diesen bezeichnet man in der Mathematik als Graphen.

 

Graph G = (V,E)

G Besteht aus V, einer endlichen Menge Knoten (z.B. Haltestellen bei U-Bahnen), sowie aus E, einer Menge 2-ehemaliger Teilmengen von V, den Kanten (z.B. Verbindungen zwischen Haltestellen).
Graphen sollten immer Zusammenhängend sein. Das gilt zum Beispiel für die Ausfallsicherheit von Netzwerken.
Vim: "In allen Netzwerken geht es doch immer darum etwas zu verbinden. Bei der Untersuchung nach Ausfallsicherheit stellte sich die Frage, ob die Verbindung zwischen je 2 Knoten des Netzwerkes auch dann noch gewährleistet ist, wenn eine Leistung ausfällt. In der Nacht vom 9. auf den10. November 1965 kam es fast im gesamten Nordosten der USA zu einer dreizehnstündigen Stromausfall und das nur, weil eine einzige übertragungsleitung eines der großen Kraftwerke an den Niagarafällen ausgefallen war. Die überlastung der verbliebenen Leitungen bewirkte den Zusammenbruch des gesamten Kraftwerkes und danach eine Kettenreaktion im gesamten Stromnetz der Region."
Ruth: "Oh diese Schlagzeile hört sich ja dramatisch an. Wenn ich mir Vorstelle, stundenlang im Dunklen in einer vielleicht noch überfüllten U-Bahn zu stehen! Da spricht sicher Panik aus."
Vim: .......
Ruth: .......
Vim: "Besonders schlimm waren die nächtlichen Eindrücke und Plünderungen in New York."

Zwischendurch sei erwähnt, dass Ruth versucht Vim vor ihren Eltern geheim zu halten. Sie möchte nicht, dass ihre Eltern bemerken wie viel Zeit sie vor dem Computer verbringt. Denn Ruth befürchtet ihr Vater würde sonst das Programm vom Computer nehmen. übrigens führt sie später auch ihren Freund Jan in das Routenproblem ein. Beide erforschen gemeinsam mit Vim neue Probleme und Theorien. Ganz am Ende des Buches stellt sich heraus, dass Vim ein Prototyp war, von Ruths Vater entwickelt und auf ihren Computer installiert. Seine Tochter sollte die 1. Testperson sein. Das Programm wurde mit Erfolg abgeschlossen. Aber nun weiter im Text. Es geht jetzt über Begriffe wie: Multigraphen, Bogen, Schleifen, Kantengewichte, Bogengewichte und Diagraph bis zu dem Kapitel "Eine ungefährliche Explosion". Diesen Abschnitt fand ich ziemlich beeindruckend. Deshalb möchte ich darauf etwas näher eingehen. Um den kürzesten Weg zu finden, so erklärt Vim, müsste jeder mögliche Weg ausprobiert werden. Bei vielen Knoten und Schichten würde der Rechner Monate bis Milliarden Jahre dazu brauchen. Hier eine Tabelle zur Explosion der Rechenzeit.

Bild 1
--> vergrößern

Abbildung 1:

Au - steht für Milliarden Jahre
Es musste eine bessere Idee gefunden werden, als alles durchzuchecken.
Bild 2
--> vergrößern

Vim und Ruth wollen die beste Verbindung vom Marinenplatz zum Harras bestimmen. Jetzt geht man ganz systematisch vor. In diesem Fall gibt es genau 4 Möglichkeiten (auch entgegngesetzte Richtungen werden beachtet) die eine Entfernung 1 vom Marineplatz haben. Dann schaut man sich alle an, die Abstand 2 haben usw. und wertet sie aus.

Vim: "... Immer dann, wenn wir eine Haltestelle erreichen, die wir schon zuvor mit weniger Schritten erreicht haben, brauchen wir diesen Weg nicht weiterzuverfolgen. Diese Art des Ausschließens bestimmter Wege ist eine Grundlage des Algorithmus, den ich dir beschreiben möchte. Machen wir weiter wie bisher, so können wir im nächsten schritt alle Knoten mit abstand 3 zum Marinenplatz auflisten und danach alle mit Abstand 4. Da wir den Harras dann immer noch nicht erreicht haben..."
Ruth: "... wissen wir, dass die Verbindung der Länge 5 mit der U6 am kürzesten ist. Wie ich's gesagt habe"

Man stellt jetzt immer die kürzeste Verbindung von einem Knoten zum anderen fest und nicht für den ganzen Graphen. So bleiben die Möglichkeiten in einem übersichtlichen Rahmen. Nun wird von Vim der Dijkstra - Algorithmus durchgearbeitet und Ruth kann es kaum erwarten alles zu verstehen und zu begreifen. Doch für mich wird die "Geschichte" immer abstrakter und kaum noch nachvollziehbar. Der interessierte Leser kann nun noch viel mehr erfahren über den Dijkstra - Algorithmus, die While - Schleife, die Näherungslösung, das Preprocessing, Paarungs - und Zuordnungsprobleme, die Warnsdroff´`s Regel, NP - Probleme, Hamiltonweg und Hamiltonkreis und vieles mehr.

Für mich war diese Buch "schwere Lektüre", fast wie eine Fremdsprache, von der ich einige Vokabeln und die Grammatik nur teilweise beherrsche. Doch für Mathefreaks oder Mathegenies könnte es ein interessanter Lesestoff sein.

Lukas Maibier

 

You have no rights to post comments.
Zum Kommentieren muss man angemeldet sein.