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.
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.
Eingabe: Menge \(\sf A\) von \(\sf n\) Zahlen, hier durchnumerierte Werteliste \(\sf A=A_0, \dots A_{n-1}\).
Setzte Hilfswert (Variable) \(\sf m\) auf das erste Element der Liste, d.h. \(\sf m = A_0\).
Gehe alle Elemente von \(\sf A\) durch, wobei das aktuelle Element als \(\sf a\) bezeichnet wird:
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
Falls nicht: * mache weiter mit dem nächsten Element in Schritt 3
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.
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