FONCTION D'ACKERMAN

Information sur la source

Catégorie :Maths

Classé sous : ackerman, ackermann, algo, recursivité, math Niveau : Débutant Date de création : 23/09/2004 Date de mise à jour : 24/09/2004 07:20:06 Vu : 10 817

Auteur : Alain Proviste

Site perso

Ecrire un message privé

Ce membre participe au partage de revenus publicitaires

Note :
Aucune note

Commentaire sur cette source (25)

Ajouter un commentaire et/ou une note

Description

La fonction d'ackerman est une fonction mathématique.
C'est la fonction qui croit le plus rapidement, bien plus rapidement qu'une expontielle.
Par exemple : ackerman(4,4) > 10^80
pourtant l'algo fait simplement quelques lignes :

la fonction A : (m, n) |--> A(m, n) d'Ackerman est définie sur N × N par :
        Si m = 0, alors A(0, n) = n+1,
        sinon si n=0, A(m, 0) = A(m-1, 1)
        sinon(A(m, n) = A(m - 1, A(m, n - 1)))

Source

Version C# de ce code disponible !

Private Function ackerman(ByVal m As Long, ByVal n As Long)
If m = 0 Then
Return n + 1
ElseIf n = 0 Then
Return ackerman(m - 1, 1)
Else
Return ackerman(m - 1, ackerman(m, n - 1))
End If
End Function

    Private Function ackerman(ByVal m As Long, ByVal n As Long)
        If m = 0 Then
            Return n + 1
        ElseIf n = 0 Then
            Return ackerman(m - 1, 1)
        Else
            Return ackerman(m - 1, ackerman(m, n - 1))
        End If
    End Function

Historique

24 septembre 2004 07:20:06 :: Quelques fautes de frappes dans la description.

Sources du même auteur

Toutes les sources de Alain Proviste

Sources de la même categorie

Toutes les sources de la catégorie Maths

Sources en rapport avec celle ci

Commentaires

Commentaire de badger71 le 23/09/2004 20:55:14

Hum, tu aurais un exemple d'utilisation d'une telle fonction ?
Commentaire de Alain Proviste le 23/09/2004 20:59:55 administrateur CS

non et toi ?
T PA BOOOOOOO :)
En fait si.
Un jour une société américaine a mis en jeu un gros paquet de dollars. Le but était d'écrire un chiffre, le plus grand possible, sur une carte postale et de l'envoyer à la société, ou alors de décrire une méthode qui permettrait de décrire comment trouver le plus grand nombre.
Le gars qui a envoyé la fonction d'ackerman a gagné.
Commentaire de badger71 le 23/09/2004 21:02:46

On se demande pourquoi un gars aurait inventé cette fonction s'il n'avait pas à s'en servir...

Juste le plaisir d'avoir un grand nombre ? Ok :p

Et si, jsuis bôôôô :p
Commentaire de EBArtSoft le 23/09/2004 22:17:07 administrateur CS

Il faut preciser que c'est une syntaxe vb.net

@+
Commentaire de PaTaTe le 23/09/2004 23:04:47

y a des erreurs de syntaxe dans ce code ou je me trompe ?
Commentaire de Alain Proviste le 24/09/2004 07:19:10 administrateur CS

    'version vb pas .net
    Private Function ackerman(ByVal m As Long, ByVal n As Long)
        If m = 0 Then
            ackerman = n + 1
        ElseIf n = 0 Then
            ackerman = ackerman(m - 1, 1)
        Else
            ackerman = ackerman(m - 1, ackerman(m, n - 1))
        End If
    End Function
Commentaire de yoman64 le 01/06/2005 18:47:27

Sa me fait une erreur "Out of stack Space" ... c'est quoi sa ? lol
Commentaire de Alain Proviste le 02/06/2005 13:49:14 administrateur CS

tu as choisis des nombres m et n trop grand
ackerman(4,4) > 10^80, imagine le nombre de recurrence, imagine ta pauvre pile :)
Commentaire de yoman64 le 02/06/2005 14:58:12

En faite , 4 et 4 me donne àla meme erreur... Je vois pas trop l'interet si on peut meme pas calculer de méga nombre...
Le plus haut j'ai été c'est 4093...avec 3 et 9 .... en tout cas lol je me demandais justre si y'avais moyen d'optimisé pour que sa face pas sa ... merci :)
Commentaire de Alain Proviste le 03/06/2005 17:27:06 administrateur CS

4 4 > 10^80
c une question de capacité de variables.
c pour le principe que c algo existe, pas pour s'amuser à compter ( et il est en rapport avec un exercie connu aussi, dans les bouquins de prog, c'est pkoi je l'ai mis là )
Commentaire de Cacophrene le 28/07/2005 20:23:14

Salut à tous !

Ackermann, oui, c'est une divergence qui donne le vertige. Même la bonne vieille factorielle ne lui arrive pas à la cheville. Certaines valeurs particulières suivent des récurrences moins pentues, si me je souviens de mes cours de CAML... mais en tout cas même en essayant d'utiliser des "grands entiers", je crois qu'on sera vite coincés. Ackermann c'est l'ère post-informatique :-)

Cordialement,
Cacophrène
Commentaire de Alain Proviste le 28/07/2005 21:35:55 administrateur CS

effectivement on dépasse très la capacité actuelle des variables :)
Commentaire de Forman le 03/08/2006 02:09:39

Et celle-ci:
u(n)=n^n^n^n^n^n...n^n
<----- n fois ----->

Je crois que ça diverge encore plus vite, et pas besoin de relation de récurrence ;-)
Commentaire de Alain Proviste le 03/08/2006 08:32:53 administrateur CS

faut croire que non
Commentaire de Forman le 04/08/2006 11:32:07

Je ne l'ai pas démontré, mais si on calcule les termes on obtient:
u(1)=1
u(2)=4
u(3)=7625597484987 (7.6E12)
u(4)=Exp(1.8E154) (capacité des flottants pas assez élevée, mais c'est un nombre qui a au moins 10^153 chiffres, c'est encore une autre échelle que Ackerman(4,4)=10^80 qui n'en a que 80)

Ca me parait un bon candidat pour battre Ackerman! Pour comparer, u(4) est déjà l'exponentielle de l'ordre de grandeur du nombre théorique d'atomes dans l'univers. Alors que Ackerman(4,4) est seulement l'ordre de grandeur du nombre d'atomes dans une petite étoile :)
Commentaire de Forman le 04/08/2006 11:35:37

Petite correction: il faut remplacer "atomes" par "particules élémentaires" dans ce que je viens d'écrire ;)

Le nombre estimé d'atomes dans l'univers est de l'ordre de 10^80
Commentaire de Alain Proviste le 04/08/2006 14:38:16 administrateur CS

c'est la croissance de la fonction d'ackerman qui est fulgurante, alors que la croissance de n'importe quelle série de puissances restera toujours "controlable"
Commentaire de Forman le 04/08/2006 20:15:15

qu'est-ce que tu entends par "contrôlable"?
La fonction d'Ackerman n'est, en dernière analyse, qu'une série d'additions. En effet, si tu développes Ackerman(4,4) par exemple (en utilisant la relation de récurrence) tu t'apercevras que ce n'est qu'une gigantesque suite d'additions des termes du bord de NxN (le carré cartésien de l'ensemble des entiers positifs).

La suite que je définis est une série de multiplications, ce n'est pas une "suite de puissances" car le nombre de puissances successives n'est pas constant. Et je crois même être en mesure de te faire la démonstration que Ackerman(n,n) est négligeable devant ma suite lorsque n tend vers l'infini (mais ça risque d'être des calculs assez lourds et rébarbatifs). Ce qui est une façon plus "rigoureuse" de dire que la croissance de ma suite est plus "fulgurante" que celle d'Ackerman.

Et sans vouloir faire le boulet, tu ne peux pas écrire que tu as trouvé une suite qui a la croissance la plus fulgurante possible (comme tu l'as fait plus haut). En effet, un boulet te répondrait que l'on peut encore faire mieux: il suffit de prendre le carré de ta suite par exemple...

Dans tous les cas, je tiens à préciser que je ne cherche à aggresser personne, et que je suis plutôt content quand ça parle de maths sur ce site ;-)
Commentaire de Alain Proviste le 05/08/2006 02:47:56 administrateur CS

ce que je voulais dire par "controlable" ou "non controlable" c'est la même difference que "uniformément continue" ou "non uniformement continue"

pas la peine de faire le boulet en disant que ta fonction n'est pas "uniformement continue", ça je le sais, mais c pour donner une idée de "controle" sur l'évolution d'une fonction...
Commentaire de Alain Proviste le 05/08/2006 02:50:45 administrateur CS

evidement on peut toujours +1 pour avoir une fonction que va plus "vite"

je pense que si le gagnat a utilisé ackerman pour gagner son million de dollar, il y a une raison derriere non ?

http://en.wikipedia.org/wiki/Ackermann_function
Commentaire de Forman le 05/08/2006 03:46:45

"we have a function of one variable that dwarfs every primitive recursive function"
C'est ça que tu voulais dire par "non contrôlable" (c'est juste que je n'ai jamais entendu le terme "contrôlable" avant que tu le mentionnes)?

C'est marrant je n'avais jamais entendu parler de Ackermann avant de lire ton source, et dans l'article que tu mentionnes, la suite dont je parle juste avant est, à peu de choses près, la suite qu'Ackermann a défini au début de ses recherches avant de passer à l'autre (zut, je me suis encore fait plagier par anticipation mdr). Et dans l'article ils expliquent qu'elle a des propriétés semblables (en particulier qu'elle n'est pas une "primitive recursive function"), et qu'elle a un taux de croissance comparable (en ce sens qu'elle dépasse toutes les fonctions récursives primitives).

Ceci dit, ça ne répond pas à la question de savoir laquelle des 2 est la plus fortement croissante, et je persiste à croire que c'est la suite d'exposants emboités (même si elle a moins d'intérêt mathématiquement parlant). Peut-être que le gagnant du concours dont tu parles n'en avait pas entendu parler, ni les autres concurrents lol
Commentaire de TeBeCo le 04/01/2007 17:16:17

c'est pas parceque la valeur pour "4" est plus grande que sa limite en l'infini le sera pour autant si la croissance d'ackerman la surpasse au final yaura un moment ou elle le depassera cela dit si tu t'ennui vraiment Forman tu code une classe qui encapusle un INT64 avec un Catch sur le depassement de capacité et tu gere les INT64 dans des collection ou autre et tu pourra stocker des chiffre de taille limiter sois a la pile systeme avant qu'il crack sois parce que la collection d'INT64 sera plus quoi faire du prochain (il me semble que qqun a mit une source dernierement sur ce site ou peut etre en C#)
Commentaire de jourgun le 30/08/2007 17:23:10

Forman, ta fonction n'est pas la fonction définie la première fois par ackerman. Elle n'est d'ailleur même pas récursive primitive.
Elle est égale, si tu veux, à phi(n, n, 3), en gardant les notations de http://fr.wikipedia.org/wiki/Fonction_d%27Ackermann

L'interêt d'un telle fonction n'est pas, au départ de gagner de l'argent mais de donner un exemple de fonction qui n'est pas récursive primitive. Cependant, elle a une autre utilité, notement celle de donner une borne pour la complexité de certains algorithme, comme celui des ensembles disjoints.

Enfin, on ne peut pas construire de "faonction ayant la croissance la plus rapide". En effet, si une telle fonction existe, son carré croit plus vite, ce qui est absurde.

Merci de s'informer avant de dire des aneries sur ce site.
Commentaire de Forman le 30/08/2007 19:31:55

Hahem...
"Elle n'est d'ailleur même pas récursive primitive."
Eh bien si, justement, ma fonction est récursive primitive, comme l'indique l'algorithme itératif suivant (on n'utilise que des boucles itératives simples, des additions et des multiplications. Voir par exemple à ce sujet:
http://fr.wikipedia.org/wiki/Fonction_r%C3%A9cursive_primitive) :
> int forman(int n){
>   int i,j,t,s=1;
>   for (i=1;i<=n;i++){
>     t=s;
>     s=1;
>     for (j=1;j<=t;j++)
>       s*=n;
>   }
>   return s;
> }

Ackerman a d'abord travaillé sur des suites de la forme "a flècheverslehaut b" qui signifie "mettre b fois a à la puissance a" (voir http://fr.wikipedia.org/wiki/Notation_des_puissances_it%C3%A9r%C3%A9es_de_Knuth), avant d'itérer cette mise en puissance aux ordres supérieurs. Ce que plus tard Knuth a repris. Et d'ailleurs la suite qu'on appelle aujourd'hui "suite d'Ackerman" n'est pas la suite originale définie par Ackerman (qui elle dépend de 3 variables), mais une écriture simplifiée à 2 variables comme le précise l'article wikipedia que tu signales obligemment.

L'intérêt mathématique de la fonction d'Ackermann n'est pas seulement de venir faire le troll sur ce site, mais aussi de donner un exemple de fonction qui est récursive, mais pas récursive primitive.

Et merci de rappeler, comme je l'avais déjà indiqué dans mon commentaire plus haut (le 18° en partant du début si j'ai bien compté), <<[qu'il n'existe pas de] "fonction ayant la croissance la plus rapide". En effet, si une telle fonction existe, son carré croit plus vite, ce qui est absurde.>>. C'est utile au cas où quelqu'un l'aurait manqué.

Si moi aussi j'avais une vocation de troll, je citerais ici ta dernière phrase, celle à propos des âneries, tu vois de laquelle je parle? Mais non, je n'en ferai rien.

Bien cordialement,
Forman
Commentaire de jourgun le 31/08/2007 12:45:32

Veuillez excuser mon labsus : en effet, je ne voulait pas dire "Elle n'est d'ailleur même pas récursive primitive.", mais plutôt que cette fonction n'est pas non récursive primitive. Dans le contexte, cela prend tout son sens, car c'est sa croissance extraordinaire qui permet de prouver le caractère non récursif primitif de la fonction d'ackermann. Ainsi, la fonction dont tu parlait était récursive primitive, et sa croissance était donc plus faible que la fonction d'ackermann.

Forman excuse-moi, pour cette dernière phrase un peu violente, je ne te visait pas toi particulièrement : il est vrai que de voir que "C'est la fonction qui croit le plus rapidement" ou qu'il existe une démonstration que la fonction d'ackermann est négliqeable devant phi(n,n,3), m'avait un peu énervé.

Ajouter un commentaire

Discussions en rapport avec ce code source

??? Ch Algo. de colli. 3d avec 3DRM ???? par DllKiller

Algo des zip par villissina

Algo de Recherche Texte ... newbie en panne par Rosbif

geometrie math par alien

Recherche d?un bouquin de math.. par Marc

moteur de recherche et algo de Boyer-Moore et Knuth-Morris-Pratt par guirec

Algo pour convertir un nombre DECIMAL en HEXA par Rurouni

Fraction sur RichTextBox pour Math. par Benji86

ALGORITHME par Tom

ALGORITHME par Tom