Ein Ranking-Algorithmus

Automatisierung des Surf-Simulationsverfahrens

Wir betrachten weiterhin die folgende Webseitenwelt:

Das entwickelte Surf-Simulationsverfahren lässt sich wie folgt beschreiben:

ALGORITHMUS erzeugeRankingwerte:
    Lege den Surf- und Sprunganteil fest.
    Lege die Ausgangsbesucherzahlen fest.
    Lege die Anzahl der Simulationsschritte fest.
    Setze einen Zähler auf 0.
    SOLANGE der Zähler kleiner als die Anzahl der Simulationsschritte ist:
        Berechne die neuen Besucherzahlen.
        Erhöhe den Zähler um 1.
    Gib die Besucherzahlen (ggf. als Anteile) aus.

Aufgabe 1

Bei einer Suche nach einem Stichwort wird man auf den Webseiten A, B und E fündig. In welcher Reihenfolge werden die Webseiten von einer Suchmaschine angezeigt, die den oben gezeigten Ranking-Algorithmus benutzt?

Aufgabe 2

Die mit der Simulation berechneten Besucherzahlen stabilisieren sich mit zunehmender Anzahl von Schritten.

Ändere den Algorithmus und seine Implementierung so ab, dass die wiederholte Berechnung der Besucherzahlen erst dann abgebrochen wird, wenn sich die Zahlen hinreichend gut stabilisiert haben. Du musst hierzu festlegen, was „hinreichend gut stabilisiert“ bedeuten soll.

Was ist ein Algorithmus?

Wir haben nun einen Algorithmus für das Ranking-Problem gefunden. Allgemein nutzt man Algorithmen zur automatisierten Datenverarbeitung. Wichtig ist dabei, dass die Vorgänge exakt beschrieben werden. So mussten wir das Surf-Verhalten präzise festlegen, um Zahlen-Werte zu berechnen.

Algorithmen lassen sich auf unterschiedliche Weise formulieren: Hier hast du sowohl Pseudocode (siehe oben) als auch Programmcode in der Programmiersprache Python gesehen.

Anforderungen an Algorithmen

An Algorithmen werden vier Anforderungen gestellt:

• Ausführbarkeit bedeutet, dass der Prozessor (das ist die Maschine oder die Person, die den Algorithmus ausführen soll) jeden Einzelschritt des Algorithmus ausführen kann.
• Eindeutigkeit bedeutet, dass die Abfolge der einzelnen Schritte genau festgelegt ist.
• Endlichkeit bedeutet, dass die Beschreibung aus einem Text endlicher Länge besteht.
• Allgemeinheit bedeutet, dass nicht nur ein singuläres Problem, sondern eine ganze Klasse von Problemen gelöst werden soll.

Aufgabe 4

Diskutiere, inwieweit die vier Anforderungen an Algorithmen bei unserem Verfahren für das Ranking-Problem erfüllt sind.

Zur Herkunft des Algorithmusbegriffs

Die Bezeichnung „Algorithmus“ leitet sich aus dem Namen Al-Khwarizmi ab. Abu Abd Allah Mohammed Ibn Musa Al-Khwarizmi – so der vollständige Name – war ein choresmischer Universalgelehrter und Mathematiker, der etwa von 780 bis 850 n. Chr. lebte. Al-Khwarizmi stammte aus Choresm (arab. Khwarizmi) – das ist eine Gegend, die heute Teil von Usbekistan und Turkmenistan ist – und lebte und arbeitete in Bagdad. Al-Khwarizmi beschäftigte sich u. a. mit Verfahren zur Lösung von Gleichungen. Diese Verfahren können aus heutiger Sicht als Algorithmen bezeichnet werden. Das ist wohl der Grund, weshalb Al-Khwarizmi Pate für maschinell verarbeitbare Verfahren geworden ist.

Manipulationen

Ziel ist es zu verstehen, wie bei realen Suchmaschinen Rankingreihenfolgen manipuliert werden.

Aufgabe 5

Betrachte wieder die oben gezeigte sehr einfache Webseitenwelt. Die Seite A wird beim Ranking weit hinten aufgelistet. Die Rankingreihenfolge kann man manipulieren, indem man (viele) neue Webseiten erzeugt, die alle auf die Seite A verweisen.

(a) Erkläre, welche Entscheidungen im Random Surfer Modell dazu führen, dass diese Manipulation funktioniert.

(b) Probiere das selbst mit einer Simulation aus.