Dans notre cours de mathématiques discrètes de mon université, l'enseignant montre ses élèves le fonction Ackermann et Attribuez à l'élève de développer la fonction sur papier.
à côté d'être une référence pour l'optimisation de la récursivité, la fonction Ackermann a-t-elle des utilisations réelles?
3 Réponses :
Oui. La fonction (inverse) Ackermann apparaît dans l'analyse de la complexité des algorithmes. Quand cela fait, cela signifie que vous pouvez presque ignorer ce terme puisqu'il grandit si lentement (beaucoup comme le journal (journal ... Log (n) ...)) I.e. LG * (N). Par exemple: Minimum étendue des arbres (également Aussi: Séquences Davenport-Scinzel
Plus précisément, l'Union trouve l'algorithme si vous voulez un exemple. Yucs.org/~gnivasch/alpha/index.html
Mais c'est l'inverse de la fonction, qu'en est-il de la vraie fonction?
Je suis d'accord avec l'autre réponse (par Wrang-Wrang) "en théorie".
En pratique Ackerman n'est pas trop utile, car dans la pratique, les seules complexités d'algorithmes que vous avez tendance à rencontrer impliquent 1, n, n ^ 2, n ^ 3, et chacun de ceux multiples par logn. (Et comme Logn n'est jamais plus de 64 ans, c'est de toute façon un terme constant.)
Le point étant, "dans la pratique", à moins que votre complexité d'algorithme ne soit "N fois trop gros", vous ne vous souciez pas de la complexité, car les facteurs du monde réel domineront. (Une fonction qui s'exécute dans O (inverse-ackermann) est théoriquement meilleure qu'une fonction exécutée dans O (logn), mais dans la pratique, vous mesurerez les deux implémentations réelles contre les données du monde réel et sélectionner les performances actuelles. . En revanche, la théorie de la complexité "matière dans la pratique" est "importante" pour n versus n ^ 2, où les effets de la complexité algorithmique surviennent dans tous les effets "du monde réel". Je trouve que "n" est la plus petite mesure qui compte dans la pratique .)
En effet, l'analyse théorique vous donne uniquement la base de l'analyse de la performance.
Pouvez-vous expliquer combien de temps n'est jamais plus de 64 ans?
Habituellement, le "journal" est la base 2.IF Log (N) est 64, cela signifie que vous avez 2 ^ 64 éléments de données. C'est bien plus que ce que vous auriez dans la pratique; En effet, sur un ordinateur 64 bits, vous avez des pointeurs de 64 bits afin que vous ne puissiez même pas représenter facilement plus de 2 ^ 64 octets.
@Andrey Votre explication doit être ajoutée à cette réponse. Dans les architectures plus bit, cela compte toujours à un point. La différence compte dans quelque chose comme des shaders sur un GPU où chaque seconde compte.
L'original "Utilisation" de la fonction Ackermann était de montrer qu'il existe des fonctions qui ne sont pas primitives récursives, 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 pousse trop vite à être primitive récursif.
Je ne pense pas qu'il y ait des utilisations vraiment pratiques, elle pousse trop vite pour être utile. Vous ne pouvez même pas explicitement représenter les chiffres au-delà d'un (4,3) dans un espace raisonnable.
en.wikipedia.org/wiki/hyperopération