Algorithmen

Algorithmus

Ein Algorithmus (algorithm) ist eine allgemeingültige endliche Folge von elementaren Operationen, die maschinell durchgeführt werden können. Die Folge enthält eine Beschreibung, wie diese elementaren Operationen nacheinander durchgeführt werden sollen. Insbesondere ist dabei eine Start- und Ende-Bedingung angegeben.
G. Büchel, Praktische Informatik

Ein Algorithmus ist eine präzise (d. h. in einer festgelegten Sprache abgefasste) endliche Beschreibung eines allgemeinen Verfahrens unter Verwendung ausführbarer elementarer (Verarbeitungs-)Schritte.
Saake, Sattler; Algorithmen und Datenstrukturen

Algorithmus (algorithm) – Arbeitsanleitung zum Lösen eines Problems bzw. einer Aufgabe, die so präzise formuliert ist, dass sie von einem Computer ausgeführt werden kann.
Dietrich Boles

• Formulierung von Algorithmen
• Umgangssprachlich
• Programmiersprache
• Aktivitätsdiagramme / Struktogramme etc.
• Ausführung von Algorithmen durch einen Prozessor (Mensch / Computer) → Prozess (process)

Algorithmus / Beispiel

Aufgabe: Berechne die Summe der Zahlen von 1 bis n

Umgangssprachliche Formulierung

Addiere für eine vorgegebene natürliche Zahl n
die Zahlen von 1 bis n. Dies ist das Resultat.

Programmiersprache

int n = readInt();
int erg = 0;
int aktZahl = 1;
while (aktZahl <= n) {
    erg = erg + aktZahl ;
    aktZahl = aktZahl + 1;
}
printInt(erg);

Terminierend / Deterministisch

Ein Algorithmus heißt

• terminierend, wenn er zu einem Ende kommt
• determiniert, wenn er immer zum selben Ergebnis kommt
• deterministisch, wenn er immer dieselben Schritte durchläuft

Jeder deterministische Algorithmus ist auch determiniert

Wichtigste Klasse: deterministische, terminierende Algorithmen

Terminierender Algorithmus

Ein terminierender Algorithmus ist ein Algorithmus, der immer ein Ende erreicht und ein Ergebnis liefert. Dies bedeutet, dass der Algorithmus unter allen möglichen Eingabebedingungen und Zuständen immer aufhört zu arbeiten und ein Ergebnis liefert, anstatt in eine Endlosschleife zu geraten oder in einen unerwarteten Zustand zu gelangen.

Ein anderes Beispiel wäre ein Algorithmus zum Suchen eines bestimmten Werts in einem Array. Der Algorithmus wird das Array elementweise durchlaufen und jeden Wert mit dem gesuchten Wert vergleichen. Sobald der gesuchte Wert gefunden wird, gibt der Algorithmus den Index des Werts im Array zurück und beendet seine Arbeit.

Ein Algorithmus, der nicht terminierend ist, wäre ein Algorithmus, der in einer Endlosschleife stecken bleibt und niemals aufhört zu arbeiten. Ein Beispiel wäre ein Algorithmus, der versucht, eine unendliche Summe von 1 zu berechnen, und niemals aufhört zu arbeiten.

Determinierter Algorithmus

Ein determinierter Algorithmus ist ein Algorithmus, dessen Ausführung immer zu dem gleichen Ergebnis führt, unabhängig von der spezifischen Implementierung oder der Hardware, auf der er ausgeführt wird. Dies bedeutet, dass der Algorithmus immer das gleiche Ergebnis liefert, wenn er mit den gleichen Eingabedaten aufgerufen wird.

Ein Beispiel für einen determinierten Algorithmus ist das Sortieren eines Arrays. Der Algorithmus wird das Array elementweise durchlaufen und die Elemente an ihre korrekten Positionen sortieren. Einmal sortiert, gibt der Algorithmus das sortierte Array zurück und beendet seine Arbeit. Wenn der Algorithmus mit den gleichen Eingabedaten aufgerufen wird, wird er immer das gleiche sortierte Array zurückgeben.

Es ist wichtig, dass ein Algorithmus determiniert ist, da dies bedeutet, dass das Ergebnis reproduzierbar und verlässlich ist.

Beispiel: determinierter, nicht deterministischer Algorithmus

1. Nehmen Sie eine Zahl x ungleich 0.
2. Entweder: Rechnen Sie (3x + x)/x
   Oder: Rechnen Sie x - (x - 4)
3. Schreiben Sie das Ergebnis auf

Beispiel: nichtdeterminierter Algorithmus:

1. Nehmen Sie eine beliebige Zahl x.
2. Addieren Sie 5 hinzu und multiplizieren Sie mit 3.
3. Schreiben Sie das Ergebnis auf.

Deterministischer Algorithmus

Ein deterministischer Algorithmus ist ein Algorithmus, bei dem nur definierte und reproduzierbare Zustände auftreten. Für die gleiche Eingabe folgt auch immer die gleiche Ausgabe und zusätzlich wird die gleiche Folge an Zuständen durchlaufen. Zu jedem Zeitpunkt ist der nachfolgende Abarbeitungsschritt des Algorithmus eindeutig festgelegt.[1] Das bedeutet auch, dass alle Zwischenergebnisse innerhalb des Algorithmus immer gleich sind.

Bausteine für Algorithmen

• Elementare Operationen
• Sequenzielle Ausführung
• Parallele Ausführung
• Bedingte Ausführung
• Schleife
• Unterprogramm
• Rekursion