[ Inhalt ] [ Index ]

Algorithmen

Das Wort Algorithmus   leitet sich vom Namen des mittelalterlichen persischen Mathematikers

Abu Jaf'ar Mohammed ibn Mûsâ al-Khowârizm  

her; er schrieb um das Jahr 825 ein mathematisches Lehrbuch mit dem Titel

Kitab al-jabr w'al-muqabala   [7].

Das wohl bekannteste Beispiel für einen Algorithmus ist der Euklidische Algorithmus   zur Bestimmung des größten gemeinsamen Teilers   zweier Zahlen:

1. Wähle a > 0, b >= 0, o.B.d.A a >= b
2. b = 0 ==> ggt = a
3. Berechne r = a MOD b
4. r = 0 ==> ggt = b, STOP
5. Setze a = b, b = r, gehe nach 3

Bei der Formulierung haben wir angenommen, daß bekannt ist, wie a MOD b berechnet wird!

Für diese Berechnung kann man ebenfalls einen Algorithmus angeben, der bei geeigneter Darstellung von a und b sehr einfach wird:

1. a = n, b = m, a >= b, a >= 0, b > 0
2. a = 0 ==> a MOD b = 0
3. Stelle a durch n, b durch m Striche dar
4. Nimm solange m Striche von a weg, bis weniger als m
   Striche übrig bleiben.
5. Der verbleibende Rest ist das Ergebnis a MOD b