Utilisations de la fonction Ackermann?

Question

Dans notre cours de mathématiques discret dispensé dans mon université, l'enseignant montre à ses étudiants la fonction Ackermann . et demandez à l’élève de développer la fonction sur papier.

En plus d’être une référence pour l’optimisation de la récursivité, la fonction Ackermann a-t-elle de véritables utilisations?

Answer 1

Oui. La fonction Ackermann (inverse) apparaît dans l'analyse de complexité des algorithmes. Lorsque cela se produit, cela signifie que vous pouvez presque ignorer ce terme car il croît si lentement (un peu comme log (log ... log ... log (n) ...)), c'est-à-dire lg * (n). Par exemple, Arbres de recouvrement minimaux (également here ) et Ensemble disjoint de construction de forêt.

Aussi: Séquences Davenport-Scinzel

Answer 2

L'original " use " de la fonction Ackermann était de montrer qu’il existe des fonctions qui ne sont pas récursives primitives, c’est-à-dire qui ne peuvent pas être calculées en utilisant uniquement des boucles avec des limites supérieures prédéterminées.

La fonction Ackermann est une telle fonction, elle se développe trop rapidement pour être récursive primitive.

Je ne pense pas qu'il y ait des utilisations vraiment pratiques, cela pousse trop vite pour être utile. Vous ne pouvez même pas représenter explicitement les nombres au-delà de (4,3) dans un espace raisonnable.

Answer 3

Je suis d'accord avec l'autre réponse (par wrang-wrang) "en théorie".

En pratique, Ackerman n’est pas très utile car, en pratique, les seules complexités d’algorithmes que vous avez tendance à rencontrer concernent 1, N, N ^ 2, N ^ 3, et chacune de celles-ci multipliées par logN. (Et puisque logN n’excède jamais 64, c’est quand même un terme constant.)

Le point important étant "en pratique", à moins que la complexité de votre algorithme ne soit "N fois trop grande", vous ne vous souciez pas de la complexité, car les facteurs réels domineront. (Une fonction qui s'exécute en O (inverse-Ackermann) est théoriquement meilleure qu'une fonction qui s'exécute en temps O (logN), mais dans la pratique, vous mesurerez les deux implémentations réelles par rapport à des données réelles et sélectionnerez celle qui fonctionnera le mieux. En revanche, la théorie de la complexité importe "dans la pratique", par exemple pour N contre N ^ 2, où les effets de complexité algorithmique l'emportent sur tous les effets du "monde réel". Je trouve que "N" est la plus petite mesure qui en pratique.)