Verwendet von Ackermann-Funktion?

Question

In unserem diskreten Mathematik-Kurs in meiner Universität, der Lehrer zeigt seine Schüler der Ackermann Funktion und weisen Sie die Schüler die Funktion auf dem Papier zu entwickeln.

Neben ein Maßstab für Rekursion Optimierung zu sein, hat die Ackermann-Funktion keinen wirklichen Gebrauch hat?

Answer 1

Ja. Die (inverse) Ackermann-Funktion erscheint in Komplexität Analyse von Algorithmen. Wenn es der Fall ist, bedeutet dies, kann man fast diesen Begriff ignorieren, da es so langsam wächst (viel wie log (log ... log (n) ...)) d lg * (n). Zum Beispiel: Minimum Spanning Trees (auch hier ) und disjunktes Set Bau Wald.

Auch: Davenport-Scinzel Sequenzen

Answer 2

Die ursprüngliche „Nutzung“ der Ackermann-Funktion war es zu zeigen, dass es Funktionen, die nicht primitive rekursiv sind, das heißt, die nicht unter Verwendung von nur für Schleifen mit vorbestimmten oberen Grenzwerte berechnet werden kann.

Die Ackermann-Funktion ist eine solche Funktion, es zu schnell wächst primitiv-rekursiv zu sein.

Ich glaube nicht, es gibt wirklich praktischen Nutzen, es zu schnell wächst, nützlich zu sein. Sie können nicht einmal explizit die Zahlen über eine (4,3) in einem angemessenen Raum darstellen.

Answer 3

Ich bin mit der anderen Antwort (von wringt-wringt) "in der Theorie".

In der Praxis ist Ackerman nicht zu nützlich, weil in der Praxis die einzigen Algorithmus Komplexität Sie neigen dazu, beinhalten 1, N, N ^ 2, N ^ 3, und jeder von log N multipled denen zu begegnen. (Und da log N ist nie mehr als 64, es ist effektiv ein konstanter Term sowieso.)

Der Punkt ist, „in der Praxis“, es sei denn, Ihre Algorithmus Komplexität „N-mal zu groß“ ist, kümmern Sie sich nicht um die Komplexität, weil reale Faktoren dominieren werden. (Eine Funktion, die in O (Invers Ackermann) ausführt, ist theoretisch besser als eine Funktion, die in O (log N) Zeit ausgeführt wird, aber in der Praxis werden Sie die zwei tatsächlichen Implementierungen gegen reale Daten messen und wählen Sie je nachdem, was tatsächlich besser abschneidet . im Gegensatz dazu hat die Komplexitätstheorie für zB „Materie in der Praxis“ N gegen N ^ 2, wobei die algorithmischen Komplexität Effekte in der Tat überwältigen tun alle „reale Welt“ Effekte. ich finde, dass „N“ die kleinste Maßnahme ist, die in der Praxis zählt ).