GEHNIO
Gesamtschule Duisburg-Hamborn/Neumühl
Informatik in der Oberstufe

> 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

 

 

 
  © 2002 Gesamtschule Duisburg-Hamborn/Neumühl.  
Hosted by www.Geocities.ws

1