Definition

Ein Algorithmus ist eine eindeutige Handlungsvorschrift zur Lösung eines Problems oder einer Klasse von Problemen.

– Wikipedia

Beispiel Rezept

  1. Pfanne erhitzen
  2. Ei in die Pfanne schlagen
  3. Etwas Salz und nach Wunsch Kräuter hinzugeben
  4. Das Ei verrühren, bis es fest ist
  5. Den Herd ausschalten und die Pfanne von dem Herd nehmen

Dies ist eine Handlungsvorschrift, um ein Problem zu lösen, nämlich die Anfertigung eines Rühreis. Die Handlungsvorschrift ist jedoch nicht eindeutig! Es steht nicht dabei, wie warm der Herd sein soll, und es stehen keine eindeutigen Mengenangaben dabei.

Ein Kochrezept ist daher kein Algorithmus.

Verwendung

Algorithmen werden in der Mathematik verwendet, um Dinge zu berechnen. Da Algorithmen sich gut formalisieren lassen, können sie in ein Computerprogramm umgewandelt werden, das den Algorithmus automatisiert durchführt.

Wichtige Eigenschaften

Determiniertheit

Ein Algorithmus ist determiniert, wenn er bei gleichen Startbedingungen und der gleichen Eingabe immer das gleiche Ergebnis liefert.

Terminiertheit

Ein Algorithmus ist terminierend, wenn er immer nach endlich vielen Schritten anhält/abbricht.

Beispiel: Fibonacchi-Zahlen

Die Fibonacchi-Zahlen sind die Zahlenreihe 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, … Dabei kommt auf die nächste Zahl, indem man die beiden Zahlen davor addiert: Die 6. Zahl ist 3 + 5 = 8, die 7. Zahl ist 5 + 8 = 13, usw.

Der einfachste Algorithmus, um eine beliebige Fibonacchi-Zahl zu berechnen:

$$fib(x)\;=\left\{\begin{array}{lc}1&falls\;x=1\;oder\;x=2\\fib(x-2)+fib(x-1)&falls\;x>2\end{array}\right.$$

Der Algorithmus gibt 1 für die ersten beiden Fibonacchi-Zahlen zurück. Danach ergibt es immer die Summe der vorherigen Fibonacchi-Zahlen.

Der Algorithmus ist deterministisch, denn wenn man den Algorithmus 1000 Mal für das gleiche x anwendet, erhält man jedes Mal das gleiche Ergebnis.

Der Algorithmus ist terminierend. Zwar wendet sich der Algorithmus sich selbst an, was zuerst nach einer Endlosschleife klingt. Aber da dabei das x immer kleiner wird, gelangt man irgendwann am Anfang der Fibonacchi-Reihe, wo die Endlosschleife abgebrochen wird.

Hier ist die Ausführung für x = 5 als Baum dargestellt:

fib(5) = 5
 ├─ fib(4) = 3
 │   ├─ fib(3) = 2
 │   │   ├─ fib(2) = 1
 │   │   └─ fib(1) = 1
 │   └─ fib(2) = 1
 └─ fib(3) = 2
     ├─ fib(2) = 1
     └─ fib(1) = 1

Fibonacchi in Java

Der obige Algorithmus ließe sich in der Programmiersprache Java folgendermapen programmieren:

int fib(int x)
{
    if (x == 1 || x == 2) return 1;
    return fib(x - 2) + fib(x - 1);
}

Beispiel: Fakultät

Die Fakultät von x ist das Produkt aller Zahlen von 1 bis x. Die Fakultät von 5 ist zum Beispiel 1 × 2 × 3 × 4 × 5 = 120. Der Algorithmus lässt sich so formulieren:

  1. Setze y auf 1
  2. Falls x = 1, wird der Algorithmus beendet, das Ergebnis ist y
  3. Multipliziere y mit x.
  4. Verringere x um 1.
  5. Fahre mit Punkt 2 fort.

Das passiert für x = 5:

1.  y hat nun den Wert 1
2.  Dieser Schritt wird ignoriert, weil x ≠ 1
3.  y hat nun den Wert  1 × 5 =  5
4.  x hat nun den Wert  5 — 1 =  4
5.
2.  Dieser Schritt wird ignoriert, weil x ≠ 1
3.  y hat nun den Wert  5 × 4 =  20
4.  x hat nun den Wert  4 — 1 =  3
5.
2.  Dieser Schritt wird ignoriert, weil x ≠ 1
3.  y hat nun den Wert 20 × 3 =  60
4.  x hat nun den Wert  3 — 1 =  2
5.
2.  Dieser Schritt wird ignoriert, weil x ≠ 1
3.  y hat nun den Wert 60 × 2 =  120
4.  x hat nun den Wert  2 — 1 =  1
5.
2.  x = 1, also wird der Algorithmus beendet, das Ergebnis ist 120

Das passiert bei dem Algorithmus: Da nach Schritt 5 mit Schritt 2 fortgefahren wird, haben wir eine Endlosschleife. y wird am Anfang auf 1 gesetzt und mit 5, dann 4, dann 3, dann 2 multipliziert.

Da x so lange um 1 verringert wird, bis es den Wert 1 hat, wissen wir, dass der Algorithmus für alle positiven Zahlen irgendwann abbricht. Der Algorithmus ist also für positive Zahlen terminierend.

Außerdem ist der Algorithmus deterministisch, da bei gleichem x immer das gleiche Ergebnis herauskommt.

Fakultaet in Java

Der obige Algorithmus ließe sich in Java folgendermapen programmieren:

int fakultaet(int x)
{
    int y = 1;
    while (true)       // Endlosschleife
    {
        if (x == 1) return y;
        y = y * x;
        x = x - 1;
    }
}
Kommentieren Kommentare