badger71
Messages postés17Date d'inscriptiondimanche 22 décembre 2002StatutMembreDernière intervention17 janvier 2006
-
23 sept. 2004 à 20:55
jourgun
Messages postés19Date d'inscriptionvendredi 21 février 2003StatutMembreDernière intervention27 août 2007
-
31 août 2007 à 12:45
Cette discussion concerne un article du site. Pour la consulter dans son contexte d'origine, cliquez sur le lien ci-dessous.
jourgun
Messages postés19Date d'inscriptionvendredi 21 février 2003StatutMembreDernière intervention27 août 2007 31 août 2007 à 12:45
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é.
cs_Forman
Messages postés600Date d'inscriptionsamedi 8 juin 2002StatutMembreDernière intervention 6 avril 20101 30 août 2007 à 19:31
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
jourgun
Messages postés19Date d'inscriptionvendredi 21 février 2003StatutMembreDernière intervention27 août 2007 30 août 2007 à 17:23
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.
TeBeCo
Messages postés467Date d'inscriptionlundi 24 juin 2002StatutMembreDernière intervention 9 mars 2011 4 janv. 2007 à 17:16
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#)
cs_Forman
Messages postés600Date d'inscriptionsamedi 8 juin 2002StatutMembreDernière intervention 6 avril 20101 5 août 2006 à 03:46
"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
cs_Alain Proviste
Messages postés908Date d'inscriptionjeudi 26 juillet 2001StatutModérateurDernière intervention 1 février 20152 5 août 2006 à 02:50
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 ?
cs_Alain Proviste
Messages postés908Date d'inscriptionjeudi 26 juillet 2001StatutModérateurDernière intervention 1 février 20152 5 août 2006 à 02:47
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...
cs_Forman
Messages postés600Date d'inscriptionsamedi 8 juin 2002StatutMembreDernière intervention 6 avril 20101 4 août 2006 à 20: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 ;-)
cs_Alain Proviste
Messages postés908Date d'inscriptionjeudi 26 juillet 2001StatutModérateurDernière intervention 1 février 20152 4 août 2006 à 14:38
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"
cs_Forman
Messages postés600Date d'inscriptionsamedi 8 juin 2002StatutMembreDernière intervention 6 avril 20101 4 août 2006 à 11:35
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
cs_Forman
Messages postés600Date d'inscriptionsamedi 8 juin 2002StatutMembreDernière intervention 6 avril 20101 4 août 2006 à 11:32
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 :)
cs_Alain Proviste
Messages postés908Date d'inscriptionjeudi 26 juillet 2001StatutModérateurDernière intervention 1 février 20152 3 août 2006 à 08:32
faut croire que non
cs_Forman
Messages postés600Date d'inscriptionsamedi 8 juin 2002StatutMembreDernière intervention 6 avril 20101 3 août 2006 à 02:09
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 ;-)
cs_Alain Proviste
Messages postés908Date d'inscriptionjeudi 26 juillet 2001StatutModérateurDernière intervention 1 février 20152 28 juil. 2005 à 21:35
effectivement on dépasse très la capacité actuelle des variables :)
Cacophrene
Messages postés251Date d'inscriptionlundi 29 mars 2004StatutMembreDernière intervention 4 mars 20081 28 juil. 2005 à 20:23
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
cs_Alain Proviste
Messages postés908Date d'inscriptionjeudi 26 juillet 2001StatutModérateurDernière intervention 1 février 20152 3 juin 2005 à 17:27
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à )
cs_yoman64
Messages postés592Date d'inscriptionsamedi 19 janvier 2002StatutMembreDernière intervention 4 décembre 2008 2 juin 2005 à 14:58
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 :)
cs_Alain Proviste
Messages postés908Date d'inscriptionjeudi 26 juillet 2001StatutModérateurDernière intervention 1 février 20152 2 juin 2005 à 13:49
tu as choisis des nombres m et n trop grand
ackerman(4,4) > 10^80, imagine le nombre de recurrence, imagine ta pauvre pile :)
cs_yoman64
Messages postés592Date d'inscriptionsamedi 19 janvier 2002StatutMembreDernière intervention 4 décembre 2008 1 juin 2005 à 18:47
Sa me fait une erreur "Out of stack Space" ... c'est quoi sa ? lol
cs_Alain Proviste
Messages postés908Date d'inscriptionjeudi 26 juillet 2001StatutModérateurDernière intervention 1 février 20152 24 sept. 2004 à 07:19
'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
cs_PaTaTe
Messages postés2126Date d'inscriptionmercredi 21 août 2002StatutContributeurDernière intervention19 février 20212 23 sept. 2004 à 23:04
y a des erreurs de syntaxe dans ce code ou je me trompe ?
cs_EBArtSoft
Messages postés4525Date d'inscriptiondimanche 29 septembre 2002StatutModérateurDernière intervention22 avril 20199 23 sept. 2004 à 22:17
Il faut preciser que c'est une syntaxe vb.net
@+
badger71
Messages postés17Date d'inscriptiondimanche 22 décembre 2002StatutMembreDernière intervention17 janvier 2006 23 sept. 2004 à 21:02
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
cs_Alain Proviste
Messages postés908Date d'inscriptionjeudi 26 juillet 2001StatutModérateurDernière intervention 1 février 20152 23 sept. 2004 à 20:59
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é.
badger71
Messages postés17Date d'inscriptiondimanche 22 décembre 2002StatutMembreDernière intervention17 janvier 2006 23 sept. 2004 à 20:55
Hum, tu aurais un exemple d'utilisation d'une telle fonction ?
31 août 2007 à 12:45
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é.
30 août 2007 à 19:31
"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
30 août 2007 à 17:23
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.
4 janv. 2007 à 17:16
5 août 2006 à 03:46
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
5 août 2006 à 02:50
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
5 août 2006 à 02:47
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...
4 août 2006 à 20:15
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 ;-)
4 août 2006 à 14:38
4 août 2006 à 11:35
Le nombre estimé d'atomes dans l'univers est de l'ordre de 10^80
4 août 2006 à 11:32
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 :)
3 août 2006 à 08:32
3 août 2006 à 02:09
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 ;-)
28 juil. 2005 à 21:35
28 juil. 2005 à 20:23
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
3 juin 2005 à 17:27
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à )
2 juin 2005 à 14:58
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 :)
2 juin 2005 à 13:49
ackerman(4,4) > 10^80, imagine le nombre de recurrence, imagine ta pauvre pile :)
1 juin 2005 à 18:47
24 sept. 2004 à 07:19
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
23 sept. 2004 à 23:04
23 sept. 2004 à 22:17
@+
23 sept. 2004 à 21:02
Juste le plaisir d'avoir un grand nombre ? Ok :p
Et si, jsuis bôôôô :p
23 sept. 2004 à 20:59
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é.
23 sept. 2004 à 20:55