Wie funktionieren eigentlich Algorithmen? Im OpenClassroom des Stanford Computer Science Department gibt Tim Roughgarden eine Einführung. Die Audioqualität tut eher weh. Ansonsten eine echt coole Sache. Die Vorlesung ist in kleine Stücke geteilt, unter 10 Minuten lang.
In Teil 2 und Teil 3 geht es um die Frage, wie eine Email ihren Weg durchs Netz findet. In Roughgardens Beispiel schicken wir eine Email aus dem internen Stanford-Netzwerk in Kalifornien, an die Cornell University in Ithaca, New York. Dabei ist das Internet der Raum, durch den die Email sich bewegt, das ganze System – Roughgarden nennt es den “Graph“. Die Knoten oder Eckpunkte (“vertices”) sind die Router und Server, die miteinander durch Kabel oder drahtlos verbunden sind.
Die Email soll möglichst schnell von A nach B kommen. Roughgarden nimmt an, dass die Email dafür über möglichst wenige Knotenpunkte hüpfen sollte – je weniger Hüpfer, desto schneller. Mit welchem Algorithmus lässt sich der schnellste Pfad berechnen?
Ein Student schlägt den Dijkstra-Algorithmus vor, einen Algorithmus aus den 50ern. Keine schlechte Idee, sagt Roughgarden, doch das Problem: Für diesen Algorithmus müsste die Uni Stanford Buch über das gesamte Netz führen. Nur mit Kenntnis des ganzen Systems und aller Knoten kann der Dijkstra-Algorithmus den kürzesten Pfad ermitteln.
Einfacher ist esm wenn das System der Stanford-Uni (der Gateway) nur wissen muss, mit welchen Knoten es lokal verbunden ist. Das ist beim Bellman-Ford-Algorithmus der Fall, den Roughgarden später genauer erklären will.
Erstmal hält er fest:
“The evolution of how routing has been done on the internet has been completely guided by the mathematical properties of these shortest-path algorithms that we are going to study. The algorithms are actually from the 50s, they even predate the open net, which is from the 60s, but noneoftheless these algorithms have shaped the evolution of how the internet works.”
Wikipedia: Kürzester Pfad