Definition Algorithmus

Aus Informatik
Wechseln zu: Navigation, Suche
Definition: Algorithmus

Ein Algorithmus ist eine eindeutige, ausführbare Folge von Anweisungen endlicher Länge zur Lösung eines Problems. Ein Algorithmus besteht aus einem Deklarationsteil (Was wird benötigt?) und einem Anweisungsteil (Wie wird das Problem gelöst?).

Eigenschaften von Algorithmen

Allgemeinheit
Ein Algorithmus ist allgemeingültig, d. h. er löst eine Vielzahl von Problemen (der gleichen Art). Die Auswahl eines einzelnen konkreten Problems erfolgt über Eingabedaten oder Parameter.
Eindeutigkeit
An jeder Stelle des Algorithmus muss eindeutig festgelegt sein, was zu tun ist und welcher Schritt der nächste ist. Dafür muss jede Anweisung unmissverständlich formuliert sein.
Ausführbarkeit
Jede einzelne Anweisung eines Algorithmus muss vom Computer (vom Mensch) ausführbar sein.
Endlichkeit (Finitheit)
Die Beschreibung eines Algorithmus besitzt eine endliche Länge, d. h. er besteht aus einer begrenzten Anzahl von Anweisungen mit begrenzter Länge. Zudem darf ein Algorithmus zu jedem Zeitpunkt für seine Daten nur endlich viel Platz belegen.

Für die Praxis werden Algorithmen häufig auf die folgenden Eigenschaften eingeschränkt:

Determiniertheit
Wird ein Algorithmus mit den gleichen Eingabewerten und Startbedingungen wiederholt, so liefert er stets das gleiche Ergebnis.
Terminierung
Der Algorithmus ist nach endlich vielen Schritten beendet, d. h. er liefert ein Ergebnis oder hält an.

Beispiele für Algorithmen

  • Vorschriften zum Addieren, Subtrahieren oder Multiplizieren von Zahlen
  • euklidischer Algorithmus zur Berechnung des ggT zweier Zahlen
  • (gute) Bastelanleitungen
  • Spielregeln und alltägliche Vorschriften (sind aber leider nur selten exakt ausformuliert und enthalten Teile, die unterschiedlich interpretiert werden können)
  • Spielen einer Melodie
  • Bedienung eines Handys

Genauigkeit der Definition

Die obige Definition für den Begriff des Algorithmus ist zwar verständlich, aber mathematisch ungenau. In der kürzeren Geschichte der Mathematik (zu Beginn des 20. Jahrhunderts) wurden eine Reihe von Ansätzen entwickelt, die zu einer genauen Definition führen sollten. Die gefundenen Methoden waren letztlich alle gleich leistungsfähig. So kann man z. B. mit Hilfe der Turing-Maschine den Begriff des Algorithmus wesentlich präziser formulieren.