Algorithmen
Im Software-Bereich steuern Algorithmen Programme, Computer und Maschinen. Sie bilden hier die logische Regel, welche der Ausführung zugrunde liegt.
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.
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.
Liefert ein Algorithmus bei gleichen Startbedingungen und Parametern immer das gleiche Ergebnis, so nennt man ihn determiniert.
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.
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.
Die Beschreibung eines Algorithmus verfügt über eine endliche Länge, d.h. er besteht aus einer begrenzten Anzahl von Zeichen.
Ein Algorithmus benötigt zur Ausführung nur begrenzt viel Speicherplatz, um Zwischenresultate zu abzuspeichern.
Ein Algorithmus hält unabhängig von der Eingabe nach endlich vielen Schritten an.
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“ 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.
Die Laufzeiteffizient betrifft die Schnelligkeit der Ausführung eines Algorithmus.
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.
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.
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.
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.
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.
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.