Algorithmus

Endliche, präzise definierte Schrittfolge zur Lösung einer Klasse von Problemen, Grundbaustein klassischer Informatik und moderner KI-Verfahren.

Definition

Ein Algorithmus ist eine endliche und präzise definierte Schrittfolge, die ein bestimmtes Problem oder eine Klasse von Problemen löst. Er beschreibt das Was und das Wie der Berechnung, ohne sich auf eine konkrete Programmiersprache festzulegen. Algorithmen sind die theoretischen Bausteine der Informatik und damit auch der Künstlichen Intelligenz.

Donald Knuth beschreibt Algorithmen in The Art of Computer Programming durch fünf wesentliche Merkmale: Endlichkeit, Bestimmtheit, Eingabe, Ausgabe und Effektivität. Diese Definition gilt bis heute als Standard.

In Praxis und Lehre werden Algorithmen meist in Pseudocode oder als Flussdiagramm beschrieben, um Implementierungsdetails von der Lösungsidee zu trennen.

Geschichte und Theorie

Der Begriff geht auf den persischen Gelehrten al-Chwarizmi zurück, dessen Name in der lateinischen Übersetzung Algoritmi überliefert ist. Sein Werk über das Rechnen mit Stellenwertsystemen prägte die mittelalterliche europäische Mathematik nachhaltig.

Im 20. Jahrhundert formalisierten Alan Turing mit der Turingmaschine und Alonzo Church mit dem Lambda-Kalkül den Begriff der Berechenbarkeit. Die Church-Turing-These postuliert, dass jede intuitiv berechenbare Funktion durch eine Turingmaschine berechnet werden kann. Damit entstand die theoretische Grundlage moderner Algorithmik.

Klassische Algorithmen-Themen sind Sortieren (Quicksort, Mergesort), Suchen (Binäre Suche), Graphen (Dijkstra, A-Stern), Datenstrukturen (Bäume, Hashtabellen) und Optimierung (Dynamische Programmierung, Gierige Algorithmen).

Praxis und Anwendung

Algorithmen sind allgegenwärtig, weit über klassische Informatik hinaus:

Suchmaschinen: PageRank und Nachfolger ordnen Webseiten nach Relevanz.
Empfehlungssysteme: Collaborative Filtering, Content-Based Filtering, hybride Verfahren.
Routing: Dijkstra und Varianten in Navigationssystemen.
Verschlüsselung: RSA, AES, elliptische Kurven, Hash-Funktionen.
KI und ML: Backpropagation, Gradient Descent, Beam Search, Monte Carlo Tree Search.
Datenbanken: B-Bäume, Hash-Indizes, Query-Optimierung.

In modernen Anwendungen kombinieren sich klassische Algorithmen mit gelernten Komponenten. Ein typisches Beispiel ist eine Suchmaschine, die klassische Indexierung mit gelerntem Ranking kombiniert.

Häufige Fehler

Algorithmus und Heuristik verwechseln: Eine Heuristik liefert oft gute, aber nicht garantiert optimale Lösungen. Algorithmen mit Korrektheitsgarantie sind nicht immer praktikabel.
Worst-Case und Average-Case vermengen: Quicksort hat im Worst-Case O(n hoch 2), im Average-Case O(n log n). Die Wahl der Analyse hängt vom Anwendungsfall ab.
Konstante Faktoren ignorieren: Asymptotisch schnellere Algorithmen können in der Praxis langsamer sein, wenn die konstanten Faktoren oder Cache-Effekte ungünstig sind.
Bias unterschätzen: Algorithmen sind nicht neutral, ihre Resultate hängen von Daten, Annahmen und Zielfunktion ab.
Pseudo-Code als ausführbar betrachten: Pseudo-Code dient der Klarheit, nicht der Ausführung. Implementierungsdetails (Datentypen, Edge Cases) müssen separat geklärt werden.

Abgrenzung

Programm: Konkrete Umsetzung eines Algorithmus in einer Sprache. Ein Algorithmus kann viele Programme erzeugen.
Heuristik: Lösungsverfahren ohne Garantie auf Optimalität, oft schneller oder einfacher.
Modell: In der KI ein gelernter Parametersatz, der zusammen mit einem Inferenz-Algorithmus eine Aufgabe löst.
Protokoll: Regelwerk für Kommunikation zwischen Systemen, oft mehrere Algorithmen kombinierend.
Datenstruktur: Organisation von Daten, die viele Algorithmen erst effizient ermöglicht.

Weiter im KI-Lexikon

← Zurück zum Lexikon

Häufige Fragen

Was ist ein Algorithmus?+

Ein Algorithmus ist eine endliche, präzise und eindeutig formulierte Folge von Anweisungen, die eine Klasse von Problemen löst. Er nimmt eine Eingabe entgegen, verarbeitet sie nach festen Regeln und liefert nach endlich vielen Schritten eine Ausgabe. Das Konzept ist sprach- und maschinenunabhängig und wird in Pseudocode, mathematischer Notation oder konkreter Programmiersprache beschrieben.

Woher stammt der Begriff Algorithmus?+

Der Begriff geht auf den persischen Mathematiker al-Chwarizmi (ca. 780 bis 850) zurück, dessen Name in der lateinischen Form Algoritmi überliefert ist. Sein Werk über das Rechnen mit indisch-arabischen Ziffern prägte die mittelalterliche Mathematik. Im 20. Jahrhundert formalisierten Alan Turing und Alonzo Church den Begriff der Berechenbarkeit, der dem modernen Algorithmusverständnis zugrunde liegt.

Welche Eigenschaften muss ein Algorithmus haben?+

Klassisch gefordert sind Endlichkeit (terminiert nach endlich vielen Schritten), Determiniertheit oder zumindest klare Spezifikation, Eindeutigkeit der Einzelschritte, Allgemeinheit (löst eine ganze Problemklasse) und Effektivität (jeder Schritt ist mechanisch ausführbar). Bei randomisierten Algorithmen wird die strenge Determiniertheit zugunsten kontrollierter Zufälligkeit aufgegeben.

Was ist der Unterschied zwischen Algorithmus und Programm?+

Ein Algorithmus ist die abstrakte Lösungsidee, ein Programm ist die konkrete Implementierung in einer Programmiersprache. Derselbe Algorithmus kann in vielen Sprachen umgesetzt werden. Beispielsweise existiert Quicksort als Algorithmus, und es gibt Implementierungen in Python, C, Rust und vielen weiteren Sprachen.

Welche Rolle spielen Algorithmen in der Künstlichen Intelligenz?+

KI-Systeme bestehen aus Lern- und Inferenz-Algorithmen, etwa Backpropagation für das Training neuronaler Netze, Beam Search für die Textgenerierung oder Reinforcement Learning für Spielagenten. Während klassische Algorithmen Regeln direkt kodieren, lernen ML-Algorithmen Parameter aus Daten. Die unterliegende Theorie ist jedoch dieselbe.

Wie misst man die Effizienz eines Algorithmus?+

Üblich sind die O-Notation für Laufzeit (Time Complexity) und Speicher (Space Complexity), die das Wachstum in Abhängigkeit von der Eingabegrösse beschreiben. Ein Algorithmus mit O(n log n) skaliert besser als einer mit O(n hoch 2). Daneben spielen praktische Faktoren wie Cache-Lokalität, Parallelisierbarkeit und konstante Faktoren eine Rolle.

Was sind algorithmische Verzerrungen?+

Algorithmic Bias beschreibt systematische Verzerrungen, die durch Datenauswahl, Modellannahmen oder Optimierungsziele entstehen und bestimmte Gruppen benachteiligen. Klassische Beispiele sind Gesichtserkennung mit unterschiedlicher Genauigkeit pro Hauttyp oder Kreditscoring, das historische Ungleichheiten verstärkt. Faire Algorithmen sind ein eigenes Forschungsfeld.

Sind alle KI-Verfahren Algorithmen?+

Im weiten Sinn ja, jedes berechenbare KI-Verfahren lässt sich als Algorithmus beschreiben. Im engeren Sinn unterscheidet man jedoch klassische Algorithmen (regelbasiert, deterministisch) von ML-Modellen (parametrisch, datengetrieben). Trainings- und Inferenzschritte eines neuronalen Netzes sind weiterhin Algorithmen, aber das gelernte Modell selbst ist ein Parametersatz und kein klassischer Algorithmus.

Quellen

Cormen, Leiserson, Rivest, Stein (2022), Introduction to Algorithms
Donald Knuth (1968 ff.), The Art of Computer Programming
Sedgewick und Wayne (2011), Algorithms

Wikidata: Q8366 · Zuletzt geprüft: 2026-06-07