Algorithmen

1.2. Algorithmen#

Definition

Ein Algorithmus ist eine formale Vorschrift wie die Lösung einer Fragestellung gefunden werden kann. Dabei handelt es sich meist um eine Folge von einfachen Anweisungen, welche zur Lösung komplexer Probleme führen können.

../../../_images/algorithmus.svg

Fig. 1.15 Algorithmus#

Algorithmen sollten so formuliert sein, dass sie nicht nur für einzelne explizite Fragestellungen, sondern auch im Allgemeinen anwendbar sind. Das wird am Beispiel des schriftliche Dividierens und einem Kuchenrezept deutlich. Beide bestehen aus einfachen Anweisungen und lösen ein komplexeres Problem. Allerdings kann die Rechenvorschrift für beliebige Divisionsaufgaben eingesetzt werden, während das Kuchenrezept nur zur Herstellung eines speziellen Kuchens führt.

Das obige Beispiel für einen Algorithmus ist eines von vielen, welche von Menschen eingesetzt werden (können):

  • Schriftliches Rechnen

  • Lösen von linearen Gleichungssystemen

  • Bestimmung des Durchschnitts

  • Lösen eines Zauberwürfels

Viele Algorithmen aus unserem Alltag sind aus sehr elementaren Anweisungen aufgebaut. Trotz der Einfachheit der Anweisungen, können Sie von Menschen nicht eingesetzt werden, da die erforderliche Anzahl von Operationen sehr hoch sein kann. An dieser Stelle kommen Computer zum Einsatz. Wie in diesem Kapitel gezeigt wird, können mit den Grundrechenarten und Logischen Verknüpfungen komplexe Probleme gelöst werden.

Beispiele

Beispiele für Algorithmen aus dem Alltag bzw. Ingenieurwesen, welche auf Computer zurückgreifen:

  • Numerische Lösung von Differentialgleichungen (z.B. Strukturmechanik, Wärmetransport)

  • Suchmachinen im Internet

  • Vorschläge beim online Einkaufen oder Medienkonsum

  • Autonavigation

Beispiel – Maximum einer Zahlenliste

Ein einfacher Algorithmus zur Bestimmung des maximalen Werts einer beliebig großen Menge von Zahlen ist wie folgt definiert.

  1. Eingabe: Menge \(\sf A\) von \(\sf n\) Zahlen, hier durchnumerierte Werteliste \(\sf A=A_0, \dots A_{n-1}\).

  2. Setzte Hilfswert (Variable) \(\sf m\) auf das erste Element der Liste, d.h. \(\sf m = A_0\).

  3. Gehe alle Elemente von \(\sf A\) durch, wobei das aktuelle Element als \(\sf a\) bezeichnet wird:

  4. Falls das aktuelle Element \(\sf a\) größer ist als \(\sf m\): * setzte \(\sf m = a\) * mache weiter mit dem nächsten Element in Schritt 3

  5. Falls nicht: * mache weiter mit dem nächsten Element in Schritt 3

  6. Nachdem alle Elemente aus \(\sf A\) in Schritt 3 durchlaufen wurden, enthält \(\sf m\) den maximalen Wert der Liste \(\sf A\).

Folgende Abbildung visualisiert den obigen Ablauf als Flussdiagramm.

../../../_images/alg_findmax.svg

Fig. 1.16 Algorithmus zur Bestimmung des Maximums einer Zahlenliste#

Im obigen Flussdiagramm sind drei Grundelemente verwendet worden:

  • Anweisungen (grün): Hier finden Zuweisungen, z.B. Setzen von Variablenwerten, hier \(\sf m\), statt

  • Schleifen (orange): Wiederholungen bzw. Iterationen über eine Menge, dabei wird bei jedem Durchlauf der Wert der Laufvariable, hier \(\sf a\), neu gesetzt

  • Verzweigung (blau): Abfrage einer Bedingung, welche entscheidet welche folgenden Elemente ausgeführt werden, hier wird geprüft ob \(\sf a > m\)

Aus diesen Elementen können alle Algorithmen aufgebaut werden.

Ein Beispiel für den Ablauf des Algoritmus für eine Liste von 20 Zahlen ist:

Schritt 1:
==========
A = [203, 433, 504, 602, 567, 762, 183, 482, 471, 741,
 854, 486, 350, 550, 885, 395, 203, 288, 909, 644]

Schritt 2:
==========
m = A[0] = 203

Schritt 3:
==========
a = 203, m = 203
a = 433, m = 203, da a > m ist, setzte m auf m= 433
a = 504, m = 433, da a > m ist, setzte m auf m= 504
a = 602, m = 504, da a > m ist, setzte m auf m= 602
a = 567, m = 602
a = 762, m = 602, da a > m ist, setzte m auf m= 762
a = 183, m = 762
a = 482, m = 762
a = 471, m = 762
a = 741, m = 762
a = 854, m = 762, da a > m ist, setzte m auf m= 854
a = 486, m = 854
a = 350, m = 854
a = 550, m = 854
a = 885, m = 854, da a > m ist, setzte m auf m= 885
a = 395, m = 885
a = 203, m = 885
a = 288, m = 885
a = 909, m = 885, da a > m ist, setzte m auf m= 909
a = 644, m = 909

Schritt 4:
==========
Maximaler Wert in A: m = 909

Kapitelübersicht

In diesem Kapitel werden folgende Themen behandelt:

  • Sortieralgorithmen

  • Eigenschaften von Algorithmen

  • Numerische Algorithmen