12 Algorithmen

Ein Algorithmus bezeichnet im Allgemeinen einen nach bestimmten Schema ablaufenden Rechenvorgang. Algorithemen werden in Computer-Programmen verwendet, um spezifische Aufgaben zu lösen. Als Beispiele können Iterationen (wiederholte Programmanweisungen), Suchalgorithmen oder Sortieralgorithmen gelten.

Algorithmen sind eng mit den verwendeten Datenstrukturen (vgl. Kapitel 8 und 9) verknüpft:

1. Wertzuweisungen - skalare Datentypen

Die Wertzuweisung ist unstrukturiert. Daher werden skalare Datentypen verwendet, die keine Struktur aufweisen. Diese Datenstruktur tritt in einfachen Berechnungen auf. 
var i:integer;
begin
i:=1;
...
end.

Werden mehrere Wertzuweisungen aneinander gereiht, so verwendet man als Datentyp den Record (Verbund). Dieser Record besteht im Allgemeinen aus verschiedenen Datentypen: 

type verbund = record
i:integer;
c:char;
end;
var v:verbund;
begin
v.i:=1;
v.c:='j';
...
end.

Die Datenstruktur des Verbundes tritt beispielsweise in Datensätzen auf - die Datenfelder ("Name", "Alter", etc.) haben dabei unterschiedliche Typen.

2. Schleifen - Arrays

Sind sämtliche (endlich viele) Komponenten einer Rechnung vom gleichen Typ, so kann auf sie in einer Schleife zugegriffen werden (vgl. Kapitel 8). 
type ergebnisse = array[1..30] of byte;
var e:ergebnisse;
i:byte;
begin
for i:=1 to 30 do
i:=StrToInt(Edit1.text);
end;

Mit einer solchen Datenstruktur kann beispielsweise ein Mittelwert einer Zahlenfolge berechnet werden.

3. While-/Repeat-Schleifen - Sequenz (Datei, Liste)

Ist die Zahl der Komponenten zum Zeitpunkt der Codierung eines Programmes nicht bekannt, so steht die Zahl der Durchläufe eines Programmabschnittes nicht fest. Man verwendet dann While- oder Repeat-Schleifen. Dazugehörige Datentypen sind Dateien oder Listen. 

Type tperson = record
vorname:string[30];
famname:string[30];
alter:byte;
end;
var person:tperson;
datei:file of tperson;
begin
assign(datei,'datei.nam');
rewrite(datei);
person.vorname:='x';
while length(person.vorname)<> 0 do begin
person.vorname:=edit1.text;
...
end;
close(datei);
...
end.

Dies ist die typische Datenstruktur für Datenbanken (Dateien oder Listen) und Speicherklassen (Listen, Stapel, Bäume, etc.). In der objektorientierten Programmiersprac wird die "Klasse" bzw. das "Objekt" ähnlich einem Verbund aufgebaut. Zu den verschiedenen Datenkomponenten werden zugehörige Prozeduren (Methoden) gebunden.

Beispiele für Algorithmen:

12.1 Die Langton-Ameise

Alan M. Turing, einer der Begründer der modernen Rechnertheorie, entdeckte die nach ihm benannte Turing-Maschine, eine universelle Rechenmaschine. Im Prinzip wird dabei ein Lesekopf über eine Datei gesteuert - steht der Lesekopf still, so liest er aus der Datei den nächsten Steuerbefehl, den er sogleich ausführt...

Chris Langton entdeckte dazu einen einfachen "Roboter", der nach ihm "Langton-Ameise" genannt wird. Dieses Tierchen sitzt zunächst in der Mitte eines Zeichenfeldes, das in lauter weiße Quadrate unterteilt ist, die entweder weiß oder schwarz umgefärbt werden können. Die Ameise bewegt sich nun nach folgendem Schema: Kommt sie auf ein weißes Feld zu stehen, so wendet sie sich um 90° nach rechts, färbt das Quadrat schwarz und wandert um ein Feld weiter. Ist dieses schwarz, so färbt sie es weiß, dreht sich um 90° nach links und wandert wieder ein Feld weiter. Durch diesen Algorithmus scheint die Ameise in einem heillosen Durcheinander über das Zeichenfeld zu wuseln - tatsächlich wird die Bewegung nach einer endlichen Zahl von Schritten regelmäßig:

Zusätzliche Informationen

Das angegebene Rechenverfahren (Algorithmus) kann in Delphi etwa wie folgt realisiert werden: 

...
procedure Tform1.Button1Click(Sender:TObject);
var x,y,i,j:integer;
richtung:byte;
begin
richtung:=1;
x:=320;
y:=240;
inc(x);
repeat
if Canvas.Pixels[x,y]=clRed then begin
richtung:=((richtung-1) mod 4);
Canvas.Pixels[x,y]:=clBackground;
end else begin
richtung:=((richtung+1) mod 4);
Canvas.Pixels[x,y]:=clRed;
end;
case richtung of
0:dec(y);
1:inc(x);
2:inc(y);
3:dec(x);
end;
if richtung=0 then richtung:=4;
until (x<50) or (y<1) or (x>638) or (y>478);
end;

Das angegebene Verfahren lässt sich noch verallgemeinern. Eine allgemeine Ameise hat nicht nur die beiden Farben weiß und schwarz (oder rot...) zur Verfügung, sondern insgesamt n Farben, die mit 0, 1, 2, ... n-1 nummeriert werden. Aus einem Feld der Farbe k macht sie ein Feld der Farbe k+1, aus der Farbe n-1 wird die Farbe 0. Was sie außerdem noch tut, wird durch eine sogenannte Regelkette festgelegt. Diese ist eine Folge von genau nSymbolen - wieder von 0 bis n-1 nummeriert. Jedes Symbol ist entweder ein L ("linksdrehen") oder ein R ("rechtsdrehen"). In dieser Verallgemeinerung bewegt sich also Langtons Ameise auf einem Zeichenfeld mit den 2 Farben "weiß" und "rot" und der Regelkette RL.

Die Ameise, die sich nach der Regelkette 1100 (RRLL) bei den Farben weiß, rot, blau und grün über das Zeichenfeld bewegt, kehrt interessanterweise immer wieder zu ihrem Ausgangspunkt in der Mitte des Feldes zurück. Dabei legt sie axialsymmetrische Wege zurück...

Ameisen, die sich nach dem obigen Verfahren bewegen, heißen auch Turmiten.

Beispiel: Realisiere ein Delphi-Programm, das die Bewegung von Turmiten realisiert!

Beispiel: Verallgemeinere auf noch mehr Farben und "beliebige" Regelketten wie RLLR, RRLL, RLLLLR, ....