Algorithme "Des chiffres et des lettres" - Page 2

Ben tu as toujours l'associativité (cf. ./27), ça réduit pas mal mine de rien

Je sais, mais quel coefficient k_|0<k<1 l’associativité va-t-elle faire gagner ?
D’une part, j’ai peur qu’il soit difficile à calculer, et d’autre part, intuitivement, je pense que ce coefficient tend vers 1 quand le nombre N de nombres (donc N-1 opérateurs) devient grand, donc asymptotiquement, on risque de retomber sur la « suite de Walters » (appelons-la comme ça dans ce topic ).
Et n’oublions pas que, n’ayant considéré que les soustractions et divisions donnant des résultats respectivement positifs et supérieurs à 1, on a déjà éliminé une partie des équivalences d’associativité.

Euh dire que la suite (appelle-la suite de Walters si tu veux, c'est pas une série ) a le bon comportement asymptotique et dire qu'elle est le meilleur majorant possible de la complexité (enfin la complexité c'est pas très précis, mais le sens pourrait être « nombre de possibilités à examiner dans le pire cas ») sont deux choses différentes... (quoique je pinaille, si tu veux un O(complexité dans le pire cas), c'est-à-dire que ta suite majore la complexité *à un facteur constant près*, alors seul le comportement asymptotique est important, c'est vrai)

Sinon l'associativité signifie que dès que dans ton arbre tu as deux nœuds + ou × en relation père-fils tu peux les permuter, donc je ne vois pas ce qui te permet de penser que ça a moins d'influence s'il y a plus d'opérateurs : plus tu as d'opérateurs plus tu peux rencontrer cette relation... alors on pourrait penser que ça réduit la cardinalité d'un facteur constant (auquel cas ça ne change rien au O) mais la réduire d'un facteur qui tend vers 1, ça ne me semble pas très réaliste.

pour les soustractions et les divisions on s'est contenté de dire qu'elles n'étaient définies que pour un seul ordre des nombres, donc on fait comme si ces opérateurs étaient commutatifs, ça n'a pas de rapport avec l'associativité ^^

Sally (./33) :
Euh dire que la suite (appelle-la suite de Walters si tu veux, c'est pas une série ) a le bon comportement asymptotique et dire qu'elle est le meilleur majorant possible de la complexité (autrement dit que c'est un O(complexité dans le pire cas)) sont deux choses différentes...

En fait, je crois que je n’ai toujours pas compris la nuance entre « majorer la complexité » et « majorer la cardinalité » dans le cas qui nous intéresse (cf ./27).
Moi je veux juste calculer « quel est le nombre maximum d’opérations à N nombres si l’on ne sait absolument rien sur ces nombres ? »

Sally (./33) :
Sinon l'associativité signifie que dès que dans ton arbre tu as deux nœuds + ou × en relation père-fils tu peux les permuter, donc je ne vois pas ce qui te permet de penser que ça a moins d'influence s'il y a plus d'opérateurs : plus tu as d'opérateurs plus tu peux rencontrer cette relation... alors on pourrait penser que ça réduit la cardinalité d'un facteur constant (auquel cas ça ne change rien au O) mais la réduire d'un facteur qui tend vers 1, ça ne me semble pas très réaliste.

À mon avis (j’ai bien souligné le mot « intuitivement »), je ne pense pas que ce facteur soit constant.
Certes, quand N augmente, le nombre de relation qui font doublon par associativité augmente, mais pas comme 4^(N-1)×(2N-2)!/((N-1)!×2^(N-1)), je dirais (toujours intuitivement) que c’est plutôt avec une « complexité » de 4^(N-1)×N².

Sally (./33) :
pour les soustractions et les divisions on s'est contenté de dire qu'elles n'étaient définies que pour un seul ordre des nombres, donc on fait comme si ces opérateurs étaient commutatifs, ça n'a pas de rapport avec l'associativité ^^

Il me semble que si :

Ethaniel (./16) :
Certes, on pourra argumenter du fait que l’on ait envie de calculer (4-9)+12, avec donc un nombre intermédiaire négatif, mais quand on va calculer (12-9)+4, on trouvera de toute façon le même résultat, donc autant éliminer immédiatement les cas dont on sait qu’ils réapparaîtront sous une autre forme lors de la recherche exhaustive des cas possibles.

On joue, il me semble, sur l’associativité, pour dire que le calcul avec valeur intermédiaire négative pourra de toute façon être retrouvé autrement sans valeur négative.

J'ai édité, en fait majorer la complexité c'est juste moins précis . Ici ce qu'on veut calculer c'est bien le nombre d'arbres différents dans le pire cas (ou dit autrement, le nombre de façons de faire les opérations pouvant donner des résultats a priori différents quand on ne connaît pas les nombres), et pour ce calcul (qui lui est précis) il y a bien une différence entre être le majorant le plus fin partout et avoir le même comportement asymptotique ^^

Sinon je ne sais pas comment tu fais pour avoir une intuition aussi précise mais, même si j'ai la flemme d'essayer de faire du dénombrement — il y a une flopée de classes d'équivalence avec des cardinaux différents... attention à la notion de « doublon » d'ailleurs, tu vas avoir des triplons ou des quadruplons etc. Par exemple *tous* les arbres qui ne contiennent que des + sont équivalents entre eux — il me semble que ça réduit beaucoup plus la cardinalité que tu ne le crois :

si par exemple (ceci n'est pas un raisonnement rigoureux, c'est pour donner une idée) tu regardes uniquement les deux premiers opérateurs (ie la racine de l'arbre et son fils qui n'est pas une feuille, ou son fils gauche si les deux sont des nœuds — j'oublie la commutativité de la racine, donc en fait tous les arbres sont comptés deux fois, mais bon ça change rien), dans un arbre sur huit ces deux opérateurs vont être deux fois + ou deux fois ×. À chaque fois que ça se produit, ça signifie qu'on peut pivoter et obtenir un autre arbre différent mais équivalent. Donc cet arbre peut être éliminé si on compte l'autre ; par contre c'est possible que l'autre soit encore dans mes 1/8 et dans ce cas il ne faut pas éliminer les deux, mais au total sur mes 1/8 je suis sûr de pouvoir en éliminer au moins la moitié¹. Ainsi rien qu'avec ce vague raisonnement simpliste je sais déjà qu'on peut éliminer au moins 1/16 des arbres.

¹Dit autrement, le vrai calcul est que dans chaque classe d'équivalence on peut éliminer tous les représentants sauf un. Dire qu'un arbre est équivalent à un autre arbre différent revient à dire qu'il appartient à une classe d'équivalence de cardinal au moins 2. Ensuite, d'une part le nombre de classes de cardinal au moins 2 est au maximum la moitié du nombre de leurs représentants, et d'autre part on peut éliminer au moins un représentant de chaque classe, donc le nombre d'arbres éliminables est bien minoré par la moitié du nombre d'arbres qui possèdent un équivalent différent. Ce dernier nombre étant au moins un huitième du total comme on le voit en regardant juste les deux premiers opérateurs (ça ne vaut donc que pour N > 2 )

Pollux (./19) :
Si tu appelles ta suite c[n] tu as la relation :
c[0] = 0
c[1] = 1
c[n] = 1/2 sum[k=0..n] C(n,k) c[k] c[n-k] pour n>1

Si tu poses c'[n] = c[n]*2^(n-1) ça te donne une relation un peu plus simple
c'[0] = 0
c'[1] = 1
c'[n] = sum[k=0..n] C(n,k) c'[k] c'[n-k] pour n>1
( http://www.research.att.com/~njas/sequences/A001813 )
C'est la version étiquetée des http://en.wikipedia.org/wiki/Catalan_number (on peut aussi faire le lien avec les nombres de Catalan directement : c'[n] = catalan[n-1]*n! puisque pour avoir une version étiquetée d'un arbre non étiqueté il suffit de rajouter une permutation quelconque des feuilles, et c[n]*2^(n-1) = c'[n] puisque pour avoir une version asymétrique d'un arbre symétrique il suffit de rajouter une information de direction à chaque noeud).

Rhââ Pollux, tout semble si simple avec toi  !
Je n’avais jamais entendu parler des nombres de Catalan jusqu’à ton post, et je ne vois pas comment j’aurais pu trouver tout seul.
Quant à ta relation c[n], j’ai dû batailler ferme sur mes arbres pour la retrouver et me convaincre que, oui, c’est bien ça …

Pollux (./19) :
Ou bien tu peux trouver l'expression de c' directement en notant tes arbres en RPN : si tu rajoutes à tes n nombres n-1 opérateurs distincts o1..on-1 (donc au total tu as un alphabet A à 2n-1 éléments), tu peux faire correspondre à chaque arbre son expression RPN, qui est une permutation de A. Mais si tu prends une permutation quelconque de A, ça ne correspond pas toujours à une expression RPN... Heureusement il existe une unique permutation circulaire de ta permutation qui correspond à une vraie expression RPN : si tu notes p[k] la profondeur de la pile (éventuellement négative) avant le k-ème symbole, tu prends le plus grand k tel que p[k] soit minimale et en faisant une rotation de k éléments tu obtiens une expression RPN (et c'est le seul k vérifiant cette propriété). Ca te donne une relation d'équivalence entre permutations de A, et chaque classe d'équivalence a 2n-1 éléments. Donc il y a (2n-1)!/(2n-1) = (2n-2)! arbres utilisant o1..on-1. Puisqu'on veut un seul opérateur, il faut diviser par le nombre de permutations de o1..on-1 : ça donne bien c'[n] = (2n-2)!/(n-1)!

J’ai aussi essayé de cette manière (tous mes arbres ont leur notation RPN équivalente), mais ça n’a vraiment rien donné.
Et je comprends pourquoi : dans ton explication, j’ai décroché dès la mention de p[k], donc dès le début, en fait.
Tu pourrais développer un peu si tu as le temps, STP  ?

Ethaniel (./18) - Posté : 30-09-2008 :

Pollux (./17) :
(ah tiens en fait elle y est aussi avec 4^(n-1), et même en double http://www.research.att.com/~njas/sequences/?q=4,48,960,26880&sort=0&fmt=0&language=english&go=Search )

Ne faudrait-il pas prévenir les admins du site que la seconde suite, qui date seulement du 21 septembre dernier, fait doublon avec la première ?

En fait, ce n’est pas un doublon, il y a un décalage :
¤ A052714 = 0, 1, 4, 48, …
¤ A144828 = 1, 4, 48, …J’avais parlé de doublon le 30/09, et que vois-je en contribution sur la seconde suite datée du lendemain ?

A144828a(n)=A052714(n+1). [From R. J. Mathar (mathar(AT)strw.leidenuniv.nl), Oct 01 2008]

Pollux, c’est toi, R. J. Mathar  ?

Sally (./36) :
attention à la notion de « doublon » d'ailleurs, tu vas avoir des triplons ou des quadruplons etc.

Je sais, mais #flemme# de répéter à chaque fois « (ou n-uplon) » …

Sally (./36) :
il me semble que ça réduit beaucoup plus la cardinalité que tu ne le crois

J’ai dénombré précisément, pour N=3, les équivalences des arbres ne contenant que des + et des - (idem pour ceux ne contenant que des * et des /), et on passe finalement de 48 calculs différents à 32  !
Pour N=4, je sens que ça va être beaucoup plus chaud, mais bon, j’aurai toute la soirée pour y bosser pendant que madame regarde la Star N’Ac’ (sauf si je me laisse tenter par la Trilogie martienne ).

Sally (./36) :
Ainsi rien qu'avec ce vague raisonnement simpliste je sais déjà qu'on peut éliminer au moins 1/16 des arbres.

Au temps pour mon « k tendant vers 1 », donc, puisqu’il est majoré par 15/16 pour N>2…
Y’a pas à dire, l’intuition mathématique, c’est vraiment pas la même chose que l’intuition physique  ! (ce qui ne m’empêche pas de raconter des conneries en physique aussi, mais quand même beaucoup beaucoup moins qu’en maths)

Ethaniel (./37) :

Pollux (./19) :
Ou bien tu peux trouver l'expression de c' directement en notant tes arbres en RPN : si tu rajoutes à tes n nombres n-1 opérateurs distincts o1..on-1 (donc au total tu as un alphabet A à 2n-1 éléments), tu peux faire correspondre à chaque arbre son expression RPN, qui est une permutation de A. Mais si tu prends une permutation quelconque de A, ça ne correspond pas toujours à une expression RPN... Heureusement il existe une unique permutation circulaire de ta permutation qui correspond à une vraie expression RPN : si tu notes p[k] la profondeur de la pile (éventuellement négative) avant le k-ème symbole, tu prends le plus grand k tel que p[k] soit minimale et en faisant une rotation de k éléments tu obtiens une expression RPN (et c'est le seul k vérifiant cette propriété). Ca te donne une relation d'équivalence entre permutations de A, et chaque classe d'équivalence a 2n-1 éléments. Donc il y a (2n-1)!/(2n-1) = (2n-2)! arbres utilisant o1..on-1. Puisqu'on veut un seul opérateur, il faut diviser par le nombre de permutations de o1..on-1 : ça donne bien c'[n] = (2n-2)!/(n-1)!

J’ai aussi essayé de cette manière (tous mes arbres ont leur notation RPN équivalente), mais ça n’a vraiment rien donné.
Et je comprends pourquoi : dans ton explication, j’ai décroché dès la mention de p[k], donc dès le début, en fait.
Tu pourrais développer un peu si tu as le temps, STP  ?

Par exemple tu pars de la suite de symboles "+ 2 / 1 5 2 racine_n-ème", qui n'est pas une expression RPN valide.
Tu fais comme si elle était valide (par exemple en supposant qu'il y a déjà plein de trucs sur la pile), et tu l'exécutes en boucle. Et tu regardes la hauteur de la pile p[k] à chaque symbole k :

Qu'est-ce qui se serait passé si on avait eu une expression RPN valide ? On part du point p[0] = 0, et on aurait eu p[1] = 1 et p[k] >= 1 pour tout k>0 (ce qui n'est pas du tout le cas ici). Si l'expression a N symboles, toujours en supposant l'expression valide on a p[N] = 1. Ca veut dire qu'on peut tracer la droite y = 1/N * x et elle sera toujours en-dessous du graphe en zig-zags. Mieux, ce sera la plus haute droite qui reste en-dessous du graphe en zig-zag, et elle touche le zig-zag précisément à l'endroit où commence l'expression RPN (k multiple de N). Et là on se rend compte que cette caractérisation ne change pas si on prend un autre point de départ, puisque c'est simplement une propriété de la courbe ! On regarde ce que ça donne avec notre chaîne de départ :

Les petites étoiles donnent le point de départ de l'expression RPN, donc en faisant une permutation circulaire ça donne l'expression "1 5 2 racine_n-ème + 2 /" qui décrit le nombre d'or

Pollux, c’est toi, R. J. Mathar  ?

Peut-être qu'il lit yN ?

OK, merci beaucoup, je pense avoir saisi le concept…
Cette histoire de permutation circulaire, c’est un truc que l’on est censé apprendre quand on étudie les RPN  ?
Oh et sinon, le graphe en zig-zag avec sa droite qui reste en dessous, ça me fait penser aux “monotonic paths” en lien avec les nombres de Catalan  !

Ethaniel (./39) :
OK, merci beaucoup, je pense avoir saisi le concept…
Cette histoire de permutation circulaire, c’est un truc que l’on est censé apprendre quand on étudie les RPN  ?

Je sais pas trop ce que tu appelles "étudier les RPN" (peut-être que j'avais déjà vu ça, mais j'en suis pas sûr)

Oh et sinon, le graphe en zig-zag avec sa droite qui reste en dessous, ça me fait penser aux “monotonic paths” en lien avec les nombres de Catalan  !

En fait on peut aussi dire que c'est :
- la donnée d'un premier symbole parmi les n+1
- la donnée d'une "structure en zig-zag" (= la façon de placer les parenthèses en notation infixe), il y en a Catalan[n]
- la donnée de permutations sur les n symboles restants et sur les n opérateurs
Donc ça fait (n+1)*C[n]*n!^2 = (2n)!, on retombe sur le résultat

(mais bon c'est prendre le problème à l'envers, c'est plutôt un moyen de trouver la formule des nombres de Catalan ^^)

Pollux (./40) :

Ethaniel (./39) :
OK, merci beaucoup, je pense avoir saisi le concept…
Cette histoire de permutation circulaire, c’est un truc que l’on est censé apprendre quand on étudie les RPN  ?

Je sais pas trop ce que tu appelles "étudier les RPN" (peut-être que j'avais déjà vu ça, mais j'en suis pas sûr)

Ben disons que je sais juste lire une expression écrite en RPN et que c’est informatiquement implanté par une pile dans laquelle on empile les nombres lus et dont on retire les 2 nombres au sommet quand on lit une opération, en empilant le résultat.
Mais par contre, jamais il ne me serait venu à l’idée d’exécuter en boucle une expression RPN aléatoire (de N nombres et N-1 opérations) et de dessiner la ligne en zig-zag pour en déduire qu’il existe une et une seule permutation circulaire de l’expression RPN qui soit valide (et en fait, jamais ce théorème ne me serait venu à l’esprit, donc je ne risquais pas d’en chercher la démo ).
Ce que j’appelle « étudier les RPN », c’est donc apprendre ce genre de théorème (ou le redécouvrir si on est fortiche ) au lieu de se contenter de savoir comment ça marche et point barre (ce qui est mon cas).

Ben en fait y a pas besoin de connaissances particulières, tu pars du résultat à trouver qui est (2n)!/n! expressions RPN valides, et tu vois que le nombre de chaînes pouvant potentiellement être du RPN est (2n+1)!/n!. Il y a juste un facteur 2n+1 entre les deux : avec un peu de chance on peut trouver pourquoi cette relation est si simple. Tu regardes quelles sont les chaînes qui sont ou ne sont pas des expressions RPN valides : pour chaque expression RPN valide e, e est valide (), alors que les 2n permutations circulaires non triviales de e ne le sont pas. Donc ça nous fait bien le facteur 2n+1 qu'on voulait (ça peut être utile de connaître les [url=http://fr.wikipedia.org/wiki/Relation_d'équivalence#Ensemble_quotient]ensembles quotient[/url]) : si on démontre que toutes les chaînes sont des permutations circulaires d'expressions RPN on aura démontré le résultat. Après, tracer la hauteur de la pile c'est la façon naturelle de caractériser les expressions bien parenthésées...

Bonjours,
Il y a une semaine je me suis proposé justement de créer ce type d'algorithme et ... J'AI RÉUSSI !!!
Mon algorithme trouve instantanément les solutions avec 6 nombres, 2 sec pour 7 nombres et 1 min pour 8 nombre.
Il passe par toute les possibilité mais sans RÉPÉTER.
Je l'ai écrit en PASCALE sous DELPHI (la seule langage que je connais).
La base est une procédure récursive qui fait appel à elle même.

Yorkie (./43) :
Je l'ai écrit en PASCALE sous DELPHI (la seule langage que je connais).

En effet, le langage français, c'est pas encore tout à fait ça