FONCTION D'ACKERMAN

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 EBArtSoft le 23/09/2004 22:17:07 administrateur CS

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

@+

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 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 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 Alain Proviste le 28/07/2005 21:35:55 administrateur CS

effectivement on dépasse très la capacité actuelle des variables :)

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: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 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: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 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 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