Kapitel 1: Einführung

Algorithmus, Programm, Prozess

Eine endlich lange Vorschrift, bestehend aus Einzelanweisungen, heißt Algorithmus.

Der Durchführende, in unserem Fall der Computer, muss die Bedeutung der Einzelanweisungen im Sinne der ihm vorgegebenen Regeln ausführen können. Die Anweisungen werden deterministisch, nicht zufällig, abgearbeitet.

Ein für einen Computer (Compiler oder Interpreter) formulierter Algorithmus wird als Programm bezeichnet. Ein Programm in Ausführung ist ein Prozess.

Achtung: Eine endlich lange Vorschrift ist nicht gleichbedeutend mit einer endlich langen Laufzeit eines Programms. Es ist nicht schwer, mit nur ganz wenigen Anweisungen ein Programm zu schreiben, dessen Prozess, wenn das Programm ausgeführt wird, eine (theoretisch) unendliche Laufzeit hat.

Anweisungen, Ablaufprotokoll

Anweisungen

Elementare Anweisungen

Elementare Anweisungen sind Anweisungen, die im Rahmen des betrachteten Modells nicht weiter zerlegt werden. Wir sprechen auch von atomaren Anweisungen.

teile x durch 2
erhöhe z um 1

Strukturierte Anweisungen

Strukturierte Anweisungen enthalten Kontrollstrukturen, Bedingungen und/oder Teilanweisungen.

WENN x > y, DANN:
  temp = x
  x = y
  y = temp

Wir haben im Beispiel eine Kontrollstruktur mit einer Bedingung. Wenn x > y zu wahr evaluiert, sollen die eingerückten Anweisungen ausgeführt werden, andernfalls nicht. In ihrer Gesamtheit bilden die gezeigten Anweisungen eine strukturierte Anweisung, die aus einer Fallunterscheidung und drei abhängigen Teilanweisungen besteht.

Solche Strukturen ermöglichen es, den Kontrollfluss eines Programms gezielt zu steuern.

Ablaufprotokoll

Im Englischen wird ein Ablaufprotokoll als Trace bezeichnet. Es handelt sich um eine Aufzeichnung der Zustände, insbesondere der Belegungen der verwendeten Variablen, die ein Programm während seiner Ausführung durchläuft.

Der folgende Algorithmus beschreibt umgangssprachlich die Bildung einer Collatz-Folge. Dabei wird die Anzahl der Transformationen gezählt, die notwendig sind, eine Eingabezahl auf den Wert \(1\) zu transformieren.

lies eine positive Ganzzahl x ein
setze z auf 0
SOLANGE x > 1:
  WENN x gerade, DANN:
    halbiere x
  SONST:
    verdreifache x und erhöhe um 1
  erhöhe z um 1
gib z aus

Lassen Sie uns für den oben skizzierten Collatz-Algorithmus ein Ablaufprotokoll für die Eingabe der Zahl \(3\) erstellen.

Vor der Ausführung der ersten Anweisung besitzen die Variablen noch keinen definierten Wert und sind daher als ?? (undefiniert) gekennzeichnet.

Schritt	Zeile	x	z	Schritt	Zeile	x	z
0		??	??	11	5	4	4
1	1	3	??	12	8	4	5
2	2	3	0	13	5	2	5
3	7	10	0	14	8	2	6
4	8	10	1	15	5	1	6
5	5	5	1	16	8	1	7
6	8	5	2	17	9	1	7
7	7	16	2
8	8	16	3
9	5	8	3
10	8	8	4

Wir haben, wenn Sie so wollen, Computer gespielt und die Anweisungen des Algorithmus ausgeführt. Dabei haben wir über den Zustand der Variablen Protokoll geführt. Das Ergebnis für eine initiale Eingabezahl \(3\) lautet \(7\).