Skip to content

Algorithmus

Algorithmus


Was ist ein Algorithmus?

  • zentraler Begriff der Informatik, aber keine Besonderheit der Informatik
  • Algorithmen im Alltag allgegenwärtig, oft ohne sie als solche zu erkennen
  • Wir führen ohne es zu merken ständig Algorithmen aus
  • Algorithmisches Denken ist eine allgemeine Methode um “Wissen zu organisieren” (D. Knuth)

Algorithmus = Problemlösungsvorschrift

  • Die Lösung einer Aufgabe bedarf einer eindeutigen Vorschrift, die genau festlegt, welche Aktionen (Handlungen) nacheinander oder nebeneinander auszuführen sind
  • Die Bezeichnung Algorithmus leitet sich von Al-Chowarizmi (persischer Mathematiker und Astronom) ab

Beispiel (Euklid)

Euklid


Showtime


Bestandteile eines Algorithmus

  • Aneinanderreihung von Aktionen
  • Datenobjekte (z.B. p, q, r)
  • Aktionen werden auf Datenobjekte angewandt (Wertzuweisungen, Division, …)
  • Es gibt einen Ausführenden, für den der Algorithmus bestimmt ist. Wir nennen ihn Prozessor
  • Algorithmus ermittelt gesuchte aus gegebenen Daten

Definition

Ein Algorithmus ist eine vollständige, präzise und in einer Notation oder Sprache mit exakter Definition abgefasste, endliche Beschreibung eines schrittweisen Problemlösungsverfahrens zur Ermittlung gesuchter Datenobjekte (ihrer Werte) aus gegebenen Werten von Datenobjekten, in dem jeder Schritt aus einer Anzahl ausführbarer, eindeutiger Aktionen und einer Angabe über den nächsten Schritt besteht.


Zerlegung in Schritte

  • Ein Algorithmus läuft in einzelnen Schritten ab S1, S2, S3, …
  • Jeder Schritt führt zu einem neuen Zustand

Eindeutigkeit

  • Keine Interpretationsmöglichkeit des Ausführenden oder Unklarheiten bezüglich
    • der Ausführung eines Schrittes (Was?)
    • der Wahl des nächsten Schrittes (Was als nächstes?)

Ausführbarkeit

  • Vom Ausführenden darf nichts Unmögliches verlangt werden
  • der Algorithmus darf nicht in einen undefinierten Zustand geraten z.B. bei Division durch 0

Endlichkeit

  • Algorithmus muss mit endlich vielen Zeichen beschrieben werden können
  • Algorithmus muss nicht notwendigerweise nach endlicher Zeit zu einem Ergebnis kommen, es gibt auch nicht abbrechende Algorithmen