Skip to main content

Algorithmus – Spezialwissen

Diese Seite vertieft den Begriff Algorithmus fachlich und dient zugleich als Einstieg in das gleichnamige Kapitel. Sie richtet sich an fortgeschrittene Lernende, an die Prüfungsvorbereitung und an die berufliche Vertiefung.

Grundbegriffe wie Variablen, Bedingungen, Schleifen, Funktionen und einfache Datenstrukturen werden vorausgesetzt.

Niveau Fortgeschritten bis professionell
Fachgebiet Grundlagen der Informatik und theoretische Informatik
Voraussetzungen Grundverständnis von Algorithmen sowie Grundlagen zu Variablen, Bedingungen, Schleifen, Funktionen und einfachen Datenstrukturen
Prüfungsrelevanz Definition, Ablaufanalyse, Korrektheit, Terminierung und Komplexität
BookStack-Struktur Grundlagen der Informatik → Algorithmus → Algorithmus – Spezialwissen

Du möchtest den Begriff zunächst anschaulich und Schritt für Schritt verstehen? Dann beginne mit dem Lernartikel Algorithmus auf lernen.drachenbrut-larp.de.

Diese Spezialwissen-Seite setzt das dort vermittelte Grundverständnis voraus und konzentriert sich auf präzise Definitionen, fachliche Zusammenhänge, formale Betrachtungen 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

Fachliche 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.

Fachliche Vertiefung

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.

Partielle und totale Korrektheit

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.

Zusammenhänge und Abgrenzungen

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.

Technische und formale Details

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.

Eine eigene Vertiefungsseite „Korrektheit und Terminierung“ ist geplant und soll diese Themen später ausführlicher behandeln.

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

Dieser Abschnitt fasst die Punkte zusammen, die für Prüfungen, Ausbildung oder fachliche Wiederholung besonders sicher beherrscht werden sollten.

Begriffe sicher definieren

Diese Begriffe sollten sicher definiert werden können:

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

Unterschiede sicher erklären

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

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

Typische Prüfungsfehler:

Algorithmus und Programm werden gleichgesetzt.

Eine Endlosschleife wird mit dem allgemeinen Halteproblem verwechselt.

Die Division durch null wird fälschlich als Nichtberechenbarkeit eingeordnet.

Big O wird als konkrete Laufzeit in Sekunden interpretiert.

Weiterlernen und Verknüpfungen

Lernartikel

Die verständliche Einsteigerseite findest du hier:

Algorithmus – Lernartikel

Begriff im Glossar

Die kurze Begriffserklärung findest du hier:

Algorithmus – Glossar

Verwandte Wissensartikel

  • Korrektheit und Terminierung (geplant)

Quellen und Literatur

Die fachlichen Quellen, Lehrbücher und weiterführenden Lernangebote zu diesem Themengebiet werden zentral gepflegt:

Quellen und Literatur zu Algorithmen und Datenstrukturen

Die vollständigen bibliografischen Angaben werden bewusst nicht auf dieser Seite wiederholt.

Fachlich geprüft: 5. August 2026
Strukturell an die Wissensarchitektur angepasst: 23. August 2026

Back to top