Algorithmus

Was ist ein Algorithmus?

Ein Algorithmus ist eine präzise beschriebene Folge ausführbarer Schritte, mit der sich eine bestimmte Art von Aufgabe lösen lässt. In einer Liste mit 1.000 Bestellnummern kannst du jeden Eintrag der Reihe nach vergleichen. Sind die Nummern aufsteigend sortiert, kannst du auch in der Mitte beginnen und nach jedem Vergleich eine Hälfte ausschließen. Die erste Suche braucht im ungünstigsten Fall 1.000 Vergleiche mit einem Listeneintrag, die zweite nur zehn.

Beide Suchalgorithmen haben dieselbe Eingabe: eine Liste und eine gesuchte Bestellnummer. Die Ausgabe ist die Position des Treffers oder die Meldung „nicht gefunden“. Die Handlungsvorschrift gilt für wechselnde Eingaben. Du kannst dieselben Schritte morgen mit einer längeren Liste und einer anderen Bestellnummer ausführen.

Was ist der Unterschied zwischen einem Algorithmus und einem Programm?

Der Algorithmus beschreibt das Verfahren. Ein Programm setzt es in Anweisungen um, die ein Computer ausführen kann. Du kannst die binäre Suche in Python programmieren, in einer anderen Programmiersprache implementieren oder mit nummerierten Karten auf einem Tisch ausführen. Die Syntax wechselt, die Entscheidungsregel bleibt: Vergleiche den mittleren Eintrag und suche bei Bedarf in der passenden Hälfte weiter.

Eine Bestellverwaltung verbindet mehrere Algorithmen. Ein Sortierverfahren ordnet die Bestellungen, ein Suchalgorithmus findet einen Eintrag, eine Rechenvorschrift ermittelt die Rechnungssumme. Zur Software gehören auch Eingabemaske und Ergebnisanzeige. „Der Algorithmus“ ist deshalb genauer bezeichnet, wenn du seine Aufgabe nennst: Geht es um die Suche, die Sortierung oder die Berechnung?

Wie funktioniert ein Algorithmus?

Algorithmus-Beispiel: Eine Nummer in einer Liste finden

Die folgende Liste enthält acht verschiedene Bestellnummern. Gesucht ist zuerst die 175. Jede Position ist direkt zugänglich. Bei einer geraden Anzahl von Einträgen nimmst du die linke der beiden mittleren Positionen. So ist die Mitte eindeutig.

Der erste Vergleich prüft Position 4. Ihr Wert 138 ist kleiner als der Suchwert 175. Dank der Sortierung scheiden die Positionen 1 bis 4 aus. Im Suchbereich 5 bis 8 liegt die Mitte an Position 6. Dort steht 162, ebenfalls kleiner als 175. Die linke Grenze rückt auf Position 7. Beim dritten Vergleich stimmen Listenwert und Suchwert überein. Die Ausgabe lautet Position 7.

Für den Suchwert 170 führen dieselben Vergleiche mit 138 und 162 wieder zum Suchbereich 7 bis 8. An Position 7 ist der Listenwert 175 diesmal größer als der Suchwert. Die rechte Grenze rückt auf Position 6. Jetzt liegt die linke Grenze bei 7 und die rechte bei 6: Der Suchbereich ist leer. Der Algorithmus kann „nicht gefunden“ ausgeben, ohne Position 8 zu lesen.

Die Suchprotokolle unterscheiden sich erst in der letzten Verzweigung. Für den Suchwert 175 gilt Gleichheit, für 170 endet die Schleife mit leerem Suchbereich. Ein dritter Testfall wäre eine leere Liste. Dann lautet die Ausgabe ebenfalls „nicht gefunden“, diesmal ohne einen einzigen Zugriff auf einen Listeneintrag.

Was sind Sequenz, Verzweigung und Schleife?

Eine Sequenz legt die Reihenfolge von Anweisungen fest. Bei der binären Suche berechnest du erst die mittlere Position und liest dann den dort gespeicherten Wert. Eine Verzweigung wählt anhand einer Bedingung den nächsten Schritt. Ist die Bestellnummer kleiner als der Suchwert, verschiebt sich die linke Grenze. Ist sie größer, verschiebt sich die rechte.

Die Schleife wiederholt den Vergleich für den verkleinerten Suchbereich. Die bereits geprüfte Mitte muss dabei ausscheiden. Bliebe sie im Bereich, könnte die Schleife bei einem letzten Eintrag immer wieder dieselbe Nummer prüfen. An einem Detail wie „Mitte plus eins“ entscheidet sich also, ob das Verfahren bei einer fehlenden Nummer zuverlässig endet.

Wie stellt man einen Algorithmus dar?

Pseudocode beschreibt die Anweisungen so genau, dass sich der Algorithmus umsetzen lässt, ohne die Syntax einer Programmiersprache zu kennen. In diesem Beispiel beginnt die Nummerierung bei 1. Beide Grenzen gehören zum Suchbereich. Die Ausgabe beendet den Aufruf sofort.

links  ← 1
rechts ← Länge(Liste)

solange links ≤ rechts:
    mitte ← links + abrunden((rechts − links) / 2)
    wert  ← Liste[mitte]

    wenn wert = Suchwert:
        gib mitte zurück
    sonst wenn wert < Suchwert:
        links ← mitte + 1
    sonst:
        rechts ← mitte − 1

gib „nicht gefunden“ zurück

Im Flussdiagramm, auch Programmablaufplan genannt, markieren Rauten die Entscheidungen. Pfeile zeigen den nächsten Schritt. Verfolge den Suchwert 170: Nach dem letzten Vergleich führt der Pfad über die geänderte rechte Grenze zurück zur Prüfung „Bereich leer?“. Erst dort endet die Suche ohne Treffer.

Welche Eigenschaften hat ein Algorithmus?

„Suche, bis du die Bestellnummer findest“ beschreibt den Erfolgsfall. Für einen fehlenden Eintrag fehlt die Abbruchbedingung. Eine vollständige Suchvorschrift legt die zulässigen Eingaben, die ausführbaren Anweisungen und die Ausgabe für beide Fälle fest.

Endliche Beschreibung und Terminierung sind zwei verschiedene Eigenschaften. „Schreibe immer wieder die Zahl 1“ ist eine kurze, endliche Vorschrift. Ihre Ausführung endet von selbst jedoch nie. Bei der binären Suche folgt die Terminierung aus der Bereichsgröße: Der Suchbereich besteht zunächst aus endlich vielen Einträgen. Jeder Schleifendurchlauf liefert einen Treffer oder entfernt mindestens die geprüfte Position. Die Abbruchbedingung beendet die Schleife spätestens bei leerem Suchbereich.

Auch die Korrektheit lässt sich am Suchbereich prüfen. Die Vorbedingung lautet: Die Liste ist aufsteigend sortiert. Die Schleife erhält dann eine sogenannte Invariante: Wenn der Suchwert vorkommt und noch kein Treffer gemeldet wurde, liegt eine Fundstelle zwischen den aktuellen Grenzen. Jede Verzweigung schließt nur Positionen aus, deren Werte zu klein oder zu groß sind. Zusammen mit der Terminierung begründet das, warum die Ausgabe sowohl bei einem Treffer als auch bei einer erfolglosen Suche stimmt.

Quelle: datenbasiert.de

Muss ein Algorithmus immer denselben Weg nehmen?

Bei einem deterministischen Algorithmus steht für denselben Zustand und dieselbe Eingabe der nächste Schritt fest. Die binäre Suche mit festgelegter Mitte prüft den Suchwert 175 daher jedes Mal an denselben drei Positionen. Ein randomisierter Algorithmus darf eine Zufallsauswahl treffen. Seine Vorschrift kann dennoch genauso präzise sein. Sie legt zum Beispiel fest, dass jede Position im Suchbereich mit gleicher Wahrscheinlichkeit ausgewählt wird.

Ausführungsweg und Ergebnis lassen sich getrennt betrachten. Eine Variante von Quicksort wählt ihr Trennelement zufällig. Zwei Durchläufe können dann die Zahlen in anderer Reihenfolge vergleichen und trotzdem dieselbe aufsteigend sortierte Zahlenfolge ausgeben. Bei einem Random Forest dient der Zufall einem anderen Zweck: Unterschiedliche Trainingsstichproben und Merkmalsauswahlen lassen verschiedene Entscheidungsbäume entstehen. Ein erneutes Training kann dadurch auch das Ergebnis verändern.

Welche Arten von Algorithmen gibt es?

Suchalgorithmen und Sortieralgorithmen

Ein Suchalgorithmus beantwortet eine Frage zum Datenbestand, etwa „An welcher Position steht 175?“. Ein Sortieralgorithmus ordnet die Einträge anhand eines Schlüssels. In einer Bestellverwaltung kann dieser Sortierschlüssel die Bestellnummer, das Bestelldatum oder der Rechnungsbetrag sein. Eine nach Rechnungsbetrag sortierte Liste erfüllt die Voraussetzung für eine binäre Suche nach Bestellnummern nur dann, wenn auch die Nummern in der passenden Reihenfolge stehen.

Lohnt es sich, 1.000 unsortierte Bestellungen eigens für eine Suche zu sortieren? Bei einer einzelnen Abfrage kannst du die Liste direkt linear durchsuchen. Bei vielen Abfragen auf demselben Bestand verteilen sich die Kosten für die einmalige Sortierung auf alle Suchvorgänge. Ändert sich der Bestand laufend, entsteht neuer Aufwand: Nach dem Einfügen einer Bestellung muss die Reihenfolge für die nächste binäre Suche stimmen.

Quelle: datenbasiert.de

Eine Beispielrechnung macht die Entscheidung messbar. Angenommen, die Sortierung der Liste kostet 9.000 Schlüsselvergleiche. Jede anschließende erfolglose lineare Suche benötigt bei 1.000 Einträgen genau 1.000 Vergleiche, die binäre Suche höchstens zehn. Bei neun solchen Abfragen ist die lineare Suche mit 9.000 Vergleichen günstiger. Bei zehn Abfragen sind es 10.000 Vergleiche gegenüber höchstens 9.100 für Sortierung und binäre Suche zusammen. Die Schwelle gilt für diese Eingabe und diese Zähleinheit. Kopieraufwand oder eine geänderte Liste würden die Rechnung verändern.

Wie funktionieren Optimierungsalgorithmen?

Ein Routenplaner modelliert Kreuzungen als Knoten und Straßenabschnitte als Kanten eines Graphen. Die Kantengewichte bestimmen, was „am besten“ bedeutet. Die Landstraße misst zwölf Kilometer bei 25 Minuten Fahrzeit. Eine Umfahrung misst 17 Kilometer und dauert 19 Minuten. Minimiert die Zielfunktion die Strecke, gewinnt die Landstraße. Minimiert sie die Fahrzeit, gewinnt die Umfahrung.

Der Dijkstra-Algorithmus findet in einem Graphen mit nichtnegativen Kantengewichten kürzeste Wege von einem Startknoten. Dazu führt er vorläufige Entfernungen. Er wählt den noch nicht abgeschlossenen Knoten mit der kleinsten bekannten Entfernung und prüft, ob sich über dessen Kanten ein kürzerer Weg zu den Nachbarn ergibt. Eine gesperrte Straße lässt sich aus dem Graphen entfernen. Ein Optimierungsalgorithmus sucht also die beste zulässige Lösung unter den Bedingungen, die seine Eingabedaten abbilden.

Was sind lernende Algorithmen?

Beim maschinellen Lernen ist das Lernverfahren programmiert. Welche konkreten Regeln später für eine Vorhersage gelten, hängt von den Trainingsdaten ab. Ein Lernalgorithmus für einen Entscheidungsbaum prüft beispielsweise Merkmale und Schwellenwerte, um Trainingsfälle mit unterschiedlichen Zielklassen zu trennen. Der fertig trainierte Baum ist das Modell.

Training und Anwendung haben unterschiedliche Eingaben und Ausgaben. Beim Training sind es Beispieldaten mit bekannten Zielwerten als Eingabe und ein Modell als Ausgabe. Bei der Anwendung gelangt ein neuer Fall in den bereits gelernten Baum. Sein Pfad endet in einem Blatt, das die Vorhersage liefert. Diese zweite Phase heißt Inferenz. Solche gelernten Vorhersagemodelle kommen beispielsweise in der Predictive Analytics zum Einsatz. Der Baum kann tausend neue Fälle bewerten, ohne seine Regeln währenddessen zu ändern.

Was bedeutet die Laufzeit eines Algorithmus?

Lineare und binäre Suche im Vergleich

Um zwei Suchalgorithmen zu vergleichen, brauchst du eine klare Zähleinheit. Hier zählt jede geprüfte Listenposition als ein Vergleich: Der dort gespeicherte Wert ist kleiner, gleich oder größer als der Suchwert. Wir zählen weder einzelne Prozessorbefehle noch Millisekunden. Die Tabelle zeigt die maximale Zahl geprüfter Einträge bei direktem Zugriff auf jede Position.

Woher kommen die zehn Vergleiche bei 1.000 Einträgen? Nach dem ersten Vergleich bleiben höchstens 500 Kandidaten, dann 250, 125, 62, 31, 15, 7, 3 und schließlich einer. Der zehnte Vergleich prüft diese letzte Position. Bei der linearen Suche kann ausgerechnet der tausendste Eintrag der Treffer sein. Fehlt der Suchwert, muss sie in einer unsortierten Liste ebenfalls alle 1.000 Positionen prüfen.

Was bedeutet die O-Notation?

Die O-Notation beschreibt eine obere Schranke für das Wachstum des Aufwands in Abhängigkeit von der Eingabegröße. Bei der linearen Suche wächst die maximale Vergleichszahl proportional zur Listenlänge n. Ihre Worst-Case-Laufzeit beträgt O(n). Bei der binären Suche halbiert sich der Suchbereich nach jedem erfolglosen Vergleich. Ihre Worst-Case-Laufzeit im Array beträgt O(log n). Selbst bei doppelter Listenlänge genügt höchstens ein zusätzlicher Vergleich.

Im günstigsten Fall treffen beide Suchalgorithmen beim ersten Vergleich. Neben der Eingabegröße zählt die Datenstruktur: In einem Array kostet der Zugriff auf die Mitte konstanten Aufwand. In einer einfach verketteten Liste folgt das Programm den Verweisen von einem Element zum nächsten. Dort kann die Suche trotz logarithmischer Vergleichszahl linearen Zeitaufwand benötigen.

Neben der Zeit zählt der Speicherbedarf. Der Pseudocode oben führt für die binäre Suche nur wenige Variablen, unabhängig von der Zahl der Bestellungen. Sein zusätzlicher Speicherbedarf beträgt O(1). Wenn eine Implementierung bei jeder Halbierung eine neue Teilliste kopiert, kostet das zusätzliche Zeit und Speicher. Zwei Programme mit derselben Suchidee können sich deshalb in einer Laufzeitmessung deutlich unterscheiden.

Algorithmen: Beispiele

Wie funktioniert der Algorithmus einer Suchmaschine?

Wer „Fahrradwerkstatt“ sucht, erwartet passende Werkstätten und möchte einen brauchbaren Treffer möglichst weit oben sehen. Dafür sind zwei Aufgaben zu lösen. Beim Retrieval ermittelt die Suchmaschine aus ihrem Index eine Auswahl möglicher Treffer. Beim Ranking ordnet sie diese Kandidaten nach geschätzter Relevanz. Eine für diese Anfrage nicht ausgewählte Seite kann auch ein hervorragendes Rankingverfahren nicht an die erste Position setzen.

Mit „Fahrradwerkstatt heute geöffnet“ ändert sich die Aufgabe. Die Öffnungszeit erhält mehr Bedeutung, während eine reine Reparaturanleitung weniger gut zur Suchabsicht passt. Ein Sortieralgorithmus könnte Seiten nach einem berechneten Relevanzwert ordnen. Wie dieser Wert entsteht, ist eine vorgelagerte Entscheidung des Suchsystems. Eine alphabetische Sortierung ergibt eine eindeutige Reihenfolge. Ein Relevanzranking löst eine andere Suchaufgabe.

Wie funktionieren Social-Media-Algorithmen?

Auch ein Feed beginnt mit einer Kandidatenauswahl. Aus möglichen Beiträgen erstellt das Empfehlungssystem eine persönliche Rangfolge. Ein vereinfachtes Modell könnte schätzen, mit welchem Video du dich länger beschäftigen wirst. Ein weiteres Signal könnte sein, ob du Beiträge desselben Kontos regelmäßig überspringst. Welche Signale verfügbar sind und wie sie gewichtet werden, hängt von der Plattform und der jeweiligen Oberfläche ab.

Stell dir vor, du hast eine Reparaturanleitung bis zum Ende angesehen. Der nächste Feed könnte dir weitere Fahrradthemen empfehlen. Das beobachtete Signal ist die Wiedergabe des Videos. Ob du grundsätzlich Fahrräder magst oder nur einmal einen Reifen flicken musstest, bleibt eine Schlussfolgerung. Wie Auswahl und Gewichtung bei einzelnen Plattformen funktionieren, beschreibt unser Beitrag über Social-Media-Algorithmen.

Was ist der Unterschied zwischen Algorithmus und KI?

Ein Algorithmus ist ein Verfahren. Künstliche Intelligenz bezeichnet ein Forschungs- und Anwendungsgebiet, das unter anderem mit Algorithmen für Suche, Planung und maschinelles Lernen arbeitet. Die binäre Suche nach deiner Bestellnummer folgt einer festen Vergleichsregel. Auch eine Million erfolgreiche Suchvorgänge verändern ihre Entscheidungsregel nicht.

Ein Empfehlungssystem kann aus neuen Trainingsdaten ein anderes Modell ableiten. Ein Algorithmus bereitet die Eingabedaten auf, ein Lernalgorithmus bestimmt Modellparameter, ein Rankingverfahren ordnet die Beiträge. Bei einer Bestellnummer kannst du die richtige Fundstelle eindeutig prüfen. Bei einem Feed hängt schon die Definition eines guten Ergebnisses von der Zielgröße ab: Ein Ranking nach erwarteter Wiedergabedauer kann dieselben Beiträge anders sortieren als ein Ranking nach Aktualität.