> Home
> Algorithmen
> Datenstrukturen
> Probleme
> Maschinenmodelle
> Themen
> Mindmaps
> Aufgaben
> Programmierung
> Facharbeit
> Abitur
> Projekte
> Informatik-AG
> News
> Impressum
> email
|
|
Die Ackermann-Funktion
Eine schnell wachsende Funktion
Rekursion ist geeignet, Funktionen zu definieren, die besonders schnell wachsen.
Die sogenannte Ackermannfunktion (F.W. Ackermann, 1896-1962) ist ein Beispiel für eine solche, schnell wachsende, rekursive Funktion.
Als Funktion mit zwei Parametern n und m ist sie folgendermaßen definiert.
a(0,m)=m+1; a(n,0)=a(n-1,1); a(n,m)=a(n-1,(a(n,m-1))
Man beachte die Schachtelung im dritten Teil der Definition.
Die Ackermannfunktion ist ein Beispiel für eine Funktion, die nicht direkt durch Iteration ersetzt werden kann.
Die bemerkenswerte Eigenschaft der Ackermannfunktion ist, dass schneller wächst als jede
primitiv-rekursive Funktion. Der Wert von a(4,2) kann mit 19729 Dezimalziffern beschrieben werden.
Der Wert von a(4,4) ist größer als 10 10 19000.
Um die Größe dieser Zahl abschätzen zu können, kann berücksichtigt werden, dass nach Schätzungen, die
Anzahl der Elementarteilchen im bekannten Universum etwa bei 10 70 liegt.
Die folgende Funktion in Pseudocode beschreibt die Ackermannfunktion algorithmisch:
function a(n,m:integer):integer;
begin
if (n=0) then a:= m+1
else if (m=0) then a:=a(n-1,1)
else a:=a(n-1,a(n,m-1));
end;
Die angegebenen Ausführungen zur Ackermannfunktion sind im wesentlichen entnommen aus:
Solymosi, A., Grude, U.:Grundkurs Algorithmen und Datenstrukturen. Eine Einführung in die
praktische Informatik mit Java. Vieweg: Braunschweig/Wiebaden, 2000
|
|