Algorithmus

Grundsätzliches

Ein Algorithmus ist eine Handlungsvorschrift, die aus mehreren, genau definierten Einzelschritten besteht; sie dient zur Lösung eines Problems, oft mathematischer Natur. Algorithmen können sowohl durch Sprache ausgedrückt werden als auch in Software implementiert werden. Aus einer bestimmten Eingabe ergibt sich eine bestimmte Ausgabe. Algorithmen kommen auch im Alltag vor: Kochrezepte, Gesetze und Verträge sind alles Beispiele für geregelte Prozeduren, die zur Problemlösung dienen.

Bedeutung

Algorithmen im engeren Sinne beschäftigen sowohl die Mathematik als auch der Informatik, z.B. im Bereich der Komplexitätstheorie und der Berechenbarkeitstheorie. Im Software-Bereich steuern Algorithmen Programme, Computer und Maschinen. Sie bilden hier die logische Regel, welche der Ausführung zugrunde liegt.

Eigenschaften von Algorithmen

Determiniertheit

Liefert ein Algorithmus bei gleichen Startbedingungen und Parametern immer das gleiche Ergebnis, so nennt man ihn determiniert.

Determinismus

Ein deterministischer Algorithmus liegt vor, wenn der nächste Handlungsschritt zu jedem Zeitpunkt der Ausführung eindeutig definiert ist. Besteht zu irgendeinem Zeitpunkt der Ausführung eine freie Wahlmöglichkeit, dann ist der Algorithmus nichtdeterministisch.

Determiniertheit vs. Determinismus

Jeder deterministische Algorithmus ist automatisch determiniert, d.h. kommt bei gleichen Startbedingungen immer zum selben Ergebnis. Umgekehrt ist aber nicht jeder determinierte Algorithmus auch deterministisch. Ein Beispiel dafür ist der Sortier-Algorithmus Quicksort : dieser gelangt immer zum gleichen Ergebnis, verwendet aber unterschiedliche Wege. Ein Beispiel wäre ein Irrgarten, der nur einen Ausgang hat, aber unterschiedliche Wege, die zum Ausgang führen. „Determinismus“ bezieht sich also auf den immer gleichbleibenden Ablauf, „Determiniertheit“ auf das immer gleichbleibende Resultat.

Finitheit

Statische Finitheit

Die Beschreibung eines Algorithmus verfügt über eine endliche Länge, d.h. er besteht aus einer begrenzten Anzahl von Zeichen.

Dynamische Finitheit

Ein Algorithmus benötigt zur Ausführung nur begrenzt viel Speicherplatz, um Zwischenresultate zu abzuspeichern.

Terminiertheit

Terminierender Algorithmus

Ein Algorithmus hält unabhängig von der Eingabe nach endlich vielen Schritten an.

Nichtterminierender Algorithmus

Ein Algorithmus mit Endlosschleife. Dies kann ein gewolltes Verhalten sein, z.B. bei Betriebssystemen. Diese Programme laufen unendlich weiter, außer der Benutzer gibt einen Befehl zum Abbruch.

Finitheit vs. Terminiertheit

„Finitheit“ betrifft die Beschreibungslänge oder den Speicherplatzbedarf eines Algorithmus, „Terminiertheit“ seine Ausführungsdauer. Z.B. gibt es finite Algorithmen, deren endliche Beschreibungslänge eine unendliche Ausführungsdauer zur Folge hat.

Effizienz

Laufzeiteffizienz

Die Laufzeiteffizient betrifft die Schnelligkeit der Ausführung eines Algorithmus.

Speichereffizienz

Die Speichereffizienz betrifft den Speicherplatz, den ein Algorithmus zur Ausführung benötigt. Die Effizienz eines Algorithmus kommt besonders dann zum Tragen, wenn für die Lösung eines Problems mehrere Algorithmen miteinander verglichen werden. Um solche Vergleiche anzustellen, werden die Algorithmen zunächst unabhängig von Implementation und verwendeter Hardware bewertet. Dafür werden anstelle der Zeitangaben in Sekunden die Rechenschritte angesetzt; und anstelle des Speicherbedarfs wird eine Anzahl Speicherplätze unbestimmter Größe für die Variablen berechnet.

Algorithmen und Suchmaschinen

Suchmaschinen wie Google, Bing oder Yahoo verwenden Algorithmen, um die Ergebnisse auf ihren Suchergebnisseiten (=SERPs) zu hierarchisieren. Das Ziel ist es, dass für den User relevanteste Ergebnis an erster Stelle anzuzeigen, das nächstrelevanteste Ergebnis an zweiter Stelle usw. Dafür kommt bei den meisten Suchmaschinenbetreibern eine Kombination aus verschiedenen Algorithmen zum Einsatz, von denen einige im Folgenden vorgestellt werden. Die genauen Formeln der Suchmaschinen-Algorithmen sind allerdings nicht bekannt; die Betreiber veröffentlichen diese nicht, um einer Manipulation der SERPs vorzubeugen. Außerdem werden die Algorithmen regelmäßig durch Updates seitens der Suchmaschinenbetreiber modifiziert.

Bekannte Suchmaschinen-Algorithmen

Page-Rank-Algorithmus

Ein von Google patentierter Algorithmus zur Bestimmung des Werts einer Webseite; entscheidend ist, wie viele Links von außen auf eine Webseite verweisen und wie hoch deren eigener Wert (=PageRank) ist.

Hilltop-Algorithmus

Ermöglicht die Sortierung einer großen Menge von verknüpften Dokumenten nach Suchbegriffen. Anders als beim PageRank-Algorithmus entscheidet nicht der Wert eines Dokuments, sondern die Entsprechung des Dokuments für einen Suchbegriff.

TrustRank-Algorithmus

Ein von Yahoo patentierter Algorithmus zur Qualitätsbestimmung einer Webseite. Zuerst wird manuell eine kleine Gruppe von Webseiten ausgewählt, die als sehr vertrauenswürdig eingestuft wurden. Dieses „Vertrauen“ (=Trust) vererben die ausgewählten Seiten durch Links auf andere Webseiten, ähnlich dem PageRank-Algorithmus. Nachdem die Quellen festgelegt wurden, berechnet der Algorithmus den Trust-Rank automatisch anhand der Linkstruktur.

HITS-Algorithmus

Der HITS-Algorithmus (=hyper-text induced topic selection) identifiziert herausragende Knotenpunkte im Internet anhand der Linkstruktur, und erlaubt so eine Bewertung von Webseiten ähnlich dem PageRank-Algorithmus.