Algorithmus – Spezialwissen

Diese Seite vertieft den Begriff Algorithmus fachlich und dient zugleich als Einstieg in das gleichnamige Kapitel. Sie richtet sich an fortgeschrittene Lernende, Prüfungsvorbereitung und berufliche Vertiefung. Grundbegriffe wie Variablen, Bedingungen, Schleifen, Funktionen und einfache Datenstrukturen werden vorausgesetzt.

Niveau	Fortgeschritten bis professionell
Fachgebiet	Grundlagen der Informatik und theoretische Informatik
Prüfungsrelevanz	Definition, Ablaufanalyse, Korrektheit, Terminierung und Komplexität
BookStack-Struktur	Grundlagen der Informatik → Algorithmus → Algorithmus – Spezialwissen

Die anschauliche Einführung zum Begriff befindet sich auf Algorithmus – anschaulich erklärt. Diese Spezialwissen-Seite setzt das dort vermittelte Grundverständnis voraus und konzentriert sich auf präzise Definitionen, fachliche Abgrenzungen und Prüfungswissen.

Fachliche Einordnung

Algorithmen gehören zu den Grundkonzepten der Mathematik und Informatik. In der Mathematik beschreiben sie unter anderem Rechen-, Konstruktions- und Entscheidungsverfahren. In der Informatik bilden sie die abstrakte Grundlage für die systematische Verarbeitung von Daten und für die Implementierung von Programmen.

Ein Algorithmus löst normalerweise nicht nur eine einzelne konkrete Aufgabe. Er beschreibt ein allgemeines Verfahren für eine ganze Klasse zulässiger Problemfälle. Ein Sortieralgorithmus ist beispielsweise nicht nur für eine bestimmte Liste vorgesehen, sondern kann auf viele Listen angewendet werden, sofern seine Voraussetzungen erfüllt sind.

Ein Problem beschreibt, was gelöst werden soll. Ein Algorithmus beschreibt, wie eine Klasse solcher Problemfälle systematisch gelöst werden kann.

Präzise Definition

Arbeitsdefinition: Ein Algorithmus ist eine endlich beschriebene Folge ausführbarer und eindeutig festgelegter Regeln, die zulässige Eingaben verarbeitet und daraus eine Ausgabe, eine Entscheidung oder eine Zustandsänderung erzeugt.

Bestandteil	Bedeutung
Eingabe	Daten oder Zustände, die zu Beginn vorliegen.
Verarbeitung	Regeln, Operationen, Vergleiche und Zustandsänderungen.
Kontrollfluss	Reihenfolge, Bedingungen, Schleifen, Rekursion oder Nebenläufigkeit.
Ausgabe	Berechneter Wert, Entscheidung, veränderte Datenstruktur oder Fehlermeldung.
Abbruchbedingung	Festlegung, wann die Verarbeitung beendet wird.

Ein Algorithmus muss nicht jede denkbare Eingabe akzeptieren. Stattdessen wird ein Definitionsbereich festgelegt. Eingaben außerhalb dieses Bereichs müssen abgelehnt oder durch eine definierte Fehlerbehandlung aufgefangen werden.

FUNKTION Dividiere(a, b)
    WENN b = 0
        GIB FEHLER "Division durch null" ZURÜCK
    ENDE WENN

    GIB a / b ZURÜCK
ENDE FUNKTION

Eine unzulässige Eingabe oder eine mathematisch nicht definierte Operation ist nicht automatisch ein unberechenbares Problem. Die Division durch null kann erkannt und als definierter Fehlerfall behandelt werden.

Kerneigenschaften von Algorithmen

Eigenschaft	Fachliche Bedeutung
Endliche Beschreibbarkeit	Das vollständige Verfahren muss sich durch einen endlichen Text, ein Diagramm oder ein anderes endliches Modell beschreiben lassen.
Ausführbarkeit	Jeder einzelne Schritt muss im zugrunde gelegten Berechnungsmodell tatsächlich ausführbar sein.
Eindeutigkeit	Für jede Situation muss festgelegt sein, welche Aktionen oder Fortsetzungen zulässig sind.
Determinismus	Bei gleicher Eingabe und gleichem Anfangszustand entsteht derselbe Ablauf und dasselbe Ergebnis.
Terminierung	Ein klassischer terminierender Algorithmus endet für jede zulässige Eingabe nach endlich vielen Schritten.
Korrektheit	Für alle zulässigen Eingaben wird das verlangte Ergebnis erzeugt.

Bei der Korrektheit wird zwischen partieller Korrektheit und totaler Korrektheit unterschieden. Partielle Korrektheit bedeutet: Falls das Verfahren endet, ist sein Ergebnis richtig. Totale Korrektheit verlangt zusätzlich den Nachweis, dass das Verfahren für jede zulässige Eingabe tatsächlich endet.

Totale Korrektheit besteht aus zwei Teilen: Das Ergebnis ist richtig und der Algorithmus terminiert für jede zulässige Eingabe.

Algorithmus, Programm und Datenstruktur

Begriff	Bedeutung
Problem	Die zu lösende Aufgabenstellung mit zulässigen Eingaben und verlangten Ergebnissen.
Algorithmus	Der abstrakte und grundsätzlich sprachunabhängige Lösungsweg.
Implementierung	Die konkrete Umsetzung eines Algorithmus in einer Programmiersprache und technischen Umgebung.
Programm	Ein ausführbares oder interpretierbares Softwaregebilde, das meist mehrere Algorithmen und zusätzliche Infrastruktur enthält.
Prozess	Eine laufende Instanz eines Programms mit eigenem Ausführungszustand und zugeordneten Ressourcen.
Datenstruktur	Eine konkrete Organisation von Daten, die bestimmte Zugriffe und Operationen ermöglicht.

Derselbe Algorithmus kann in verschiedenen Programmiersprachen implementiert werden. Die tatsächliche Laufzeit kann sich trotzdem unterscheiden, etwa durch Compiler, Interpreter, Hardware, Speicherverwaltung, Bibliotheken und die verwendete Datenstruktur.

Algorithmus und Datenstruktur müssen deshalb gemeinsam betrachtet werden. Eine lineare Suche benötigt keine sortierten Daten, muss im ungünstigsten Fall aber alle Elemente prüfen. Eine binäre Suche reduziert den Suchbereich schrittweise, setzt jedoch passend sortierte Daten und einen geeigneten Zugriff auf das mittlere Element voraus.

Bei der Beurteilung eines Verfahrens immer prüfen, ob die gewählte Datenstruktur zu den benötigten Operationen passt. Nicht nur der Algorithmus allein bestimmt die Effizienz.

Darstellung und formale Analyse

Algorithmen können in präziser Alltagssprache, als Pseudocode, in Programmablaufplänen, Struktogrammen, UML-Aktivitätsdiagrammen oder mithilfe mathematischer und formaler Notationen dargestellt werden. Die geeignete Form hängt von Zielgruppe, Umfang und erforderlichem Präzisionsgrad ab.

Darstellungsform	Stärke	Grenze
Alltagssprache	Leicht zugänglich	Kann mehrdeutig sein
Pseudocode	Strukturiert und sprachunabhängig	Keine vollständig einheitliche Syntax
Programmablaufplan	Abläufe und Entscheidungen visuell erkennbar	Bei großen Abläufen schnell unübersichtlich
Struktogramm	Kontrollstrukturen klar als Blöcke	Für stark nebenläufige Abläufe weniger geeignet
UML-Aktivitätsdiagramm	Aktivitäten, Entscheidungen und Parallelität darstellbar	UML modelliert weit mehr als einzelne Algorithmen
Formale Beschreibung	Hohe mathematische Präzision	Hohe fachliche Einstiegshürde

FUNKTION LineareSuche(liste, suchwert)
    FÜR position VON 0 BIS Länge(liste) - 1
        WENN liste[position] = suchwert
            GIB position ZURÜCK
        ENDE WENN
    ENDE FÜR

    GIB NICHT_GEFUNDEN ZURÜCK
ENDE FUNKTION

Zur formalen Analyse gehören insbesondere Vorbedingungen, Nachbedingungen, Schleifeninvarianten und der Terminierungsnachweis. Diese Themen werden auf der späteren Vertiefungsseite „Korrektheit und Terminierung“ ausführlich behandelt.

UML ist keine besondere Form des Flussdiagramms. UML ist eine umfassende Modellierungssprache. Für Abläufe eignen sich vor allem UML-Aktivitätsdiagramme.

Komplexität und Berechenbarkeit

Die Komplexitätsanalyse untersucht, wie der Ressourcenbedarf eines Algorithmus mit der Größe seiner Eingabe wächst. Im Mittelpunkt stehen meist Zeit- und Speicherkomplexität. Die Eingabegröße wird häufig mit n bezeichnet; ihre konkrete Bedeutung hängt vom Problem ab.

Notation	Bedeutung
`O(g(n))`	Asymptotische obere Schranke
`Ω(g(n))`	Asymptotische untere Schranke
`Θ(g(n))`	Asymptotisch enge Schranke

Typische Größenordnungen sind O(1), O(log n), O(n), O(n log n), O(n²), O(cⁿ) und O(n!). Sie beschreiben das Wachstum des Aufwands, nicht die konkrete Laufzeit in Sekunden.

Der Average Case darf nicht ohne Annahmen über die Verteilung der Eingaben angegeben werden. Auch Big O ist keine exakte Laufzeitangabe, sondern beschreibt eine asymptotische obere Schranke.

Die Berechenbarkeitstheorie stellt eine andere Frage: Kann ein Problem grundsätzlich durch ein mechanisches Verfahren gelöst werden? Ein Problem kann theoretisch berechenbar, aber praktisch sehr aufwendig sein. Ein unentscheidbares Problem besitzt dagegen keinen allgemeinen Algorithmus, der sämtliche zulässigen Fälle korrekt entscheidet.

Das Halteproblem fragt, ob ein allgemeiner Algorithmus für jedes beliebige Programm und jede beliebige Eingabe zuverlässig entscheiden kann, ob die Ausführung irgendwann endet. Ein solcher allgemeiner Entscheidungsalgorithmus existiert nicht.

Unentscheidbar bedeutet nicht „sehr langsam“. Es bedeutet, dass kein allgemeiner Algorithmus existiert, der alle zulässigen Fälle korrekt entscheidet.

Prüfungswissen

Diese Begriffe sollten sicher definiert werden können:

Algorithmus
Determinismus
Terminierung
partielle und totale Korrektheit
Zeit- und Speicherkomplexität
Berechenbarkeit und Entscheidbarkeit

Diese Unterschiede sollten erklärt werden können:

Algorithmus und Programm
Vorbedingung und Nachbedingung
Best Case, Average Case und Worst Case
Big O, Big Omega und Big Theta
Heuristik und Näherungsalgorithmus
unentscheidbar und praktisch zu aufwendig
endlicher Automat und Turing-Maschine

Schema für eine vollständige Algorithmusanalyse:

Zweck und Problemklasse benennen.
Eingaben, Ausgaben und Definitionsbereich bestimmen.
Ablauf und Kontrollstrukturen erläutern.
Vor- und Nachbedingungen angeben.
Korrektheit und Terminierung begründen.
Zeit- und Speicherkomplexität bestimmen.
Grenzfälle, Fehlerfälle und praktische Einschränkungen nennen.

Typische Prüfungsfehler sind die Gleichsetzung von Algorithmus und Programm, die Verwechslung einer Endlosschleife mit dem allgemeinen Halteproblem, die Einordnung der Division durch null als Nichtberechenbarkeit sowie Big O als konkrete Sekundenangabe.

Weiterlernen und Nachschlagen

Quellen und Literatur zu Algorithmen und Datenstrukturen

Dort findest du die zentral gepflegten Fachquellen, Lehrbücher und Lernangebote zu diesem Themengebiet. Die vollständigen bibliografischen Angaben werden bewusst nicht auf dieser Seite wiederholt.

Fachlich geprüft: 5. August 2026