Discussion :

[valentin03]

Bonjour à tous,
Un algo, qui d'une expression quelconque (limitée) donne les expressions équivalentes de toutes les variables de l'expression.
Exemple: x=(a+b)*(c-d)/e
On fixe des valeurs arbitraires pour calculer x.
Puis par force brute on teste-calcule tous les arrangements
Si valeur arrangement = valeurs variables afficher: variable = arrangement (expression)
ça paraît jouabe mais je m'interroge sur le nombre d'arrangements en fonction de la longueur de l'expression (14 pour l'exemple).
Quelqu'un aurait un tuyau pour ce nombre ? Merci.

[wiwaxia]

Bonjour à tous,
Un algo, qui d'une expression quelconque (limitée) donne les expressions équivalentes de toutes les variables de l'expression ...

Il faut donc concevoir un programme de calcul formel, rien de moins !

... Puis par force brute on teste-calcule tous les arrangements ...

Le nombre de combinaisons (ici égal à 13!/(2!)²~1.56E⁹ pour 13 caractères, dont deux paires identiques) est trop élevé pour permettre un inventaire exhaustif.
Quant à l'opération de "test-calcul", c'est plus vite dit que fait: il faut mettre au point des règles syntaxiques, dont la quantité deviendra rapidement ingérable en fonction du nombre et de la diversité des caractères présents.
As-tu songé de plus au nombre démesuré de résultats intelligibles (donc grammaticalement corrects), mais tous faux à l'exception de l'un d'entre eux, pour chacune des variables ? Et au moyen d'identifier la bonne solution ?

Il suffit de reprendre la relation citée: x=(a+b)*(c-d)/e
pour imaginer ce que pourrait donner:
- la permutation des termes (a, b, c, d, e),
-celle des signes (+) et (-), ou le déplacement des parenthèses ...

De plus tu pars ingénument d'une expression très simple, limitée aux opérations arithmétiques et dans laquelle chacun des paramètres n'intervient qu'une seul fois.
Que se passerait-il dans les cas suivants ?

x=(a+b)*(c+2*b)*(d+3*b)*(e+4*b)*(e+5*b)
x=(a+b)*(c-d)/(e+b⁶)
x=(a+b)*(c-d)/(e+2^b)
y=x*exp(-5*x)
y = x^x
y=3*sin(x)+5*sin(x²)

Il n'y a pas de solution explicite b = G(x, a, c, d, e) - pour les trois premières - ou x = G(y) pour les 3 autres.

[valentin03]

@:wiwaxia: Aaargh... Je me doutais qu'il y avait un problème, j'avais vu poindre le "!" mais le: "TouS FauX sauf UN seul" que je ne soupçonnais pas, a de quoi glacer le sang.
A combien de variables et d'opérateurs faudrait-il se limiter pour que ça soit jouable avec 100 000 combinaisons par exemple ?
Sans tenir compte du : "Tous faux sauf un seul" (dont on pourrait bien reparler, une égalité étant une égalité).
Je ne suis pas ingénu, je n'ai mis que les quatre opérateurs.
Pour l'analyse syntaxique ça va, en mettant des espaces on peut faire du mot à mot, tester l'opérateur courant et traiter sur place, les parenthèses traitées à part et réintégrées en avançant.
Je vais me renseigner sur quézaquo que le calcul formel.

[bstjean]

De plus tu pars ingénument d'une expression très simple, limitée aux opérations arithmétiques et dans laquelle chacun des paramètres n'intervient qu'une seul fois.
Que se passerait-il dans les cas suivants ?

x=(a+b)*(c+2*b)*(d+3*b)*(e+4*b)*(e+5*b)
x=(a+b)*(c-d)/(e+b⁶)
x=(a+b)*(c-d)/(e+2^b)
y=x*exp(-5*x)
y = x^x
y=3*sin(x)+5*sin(x²)

Il n'y a pas de solution explicite b = G(x, a, c, d, e) - pour les trois premières - ou x = G(y) pour les 3 autres.

Un autre problème provient du fait que le domaine de chaque variable n'est pas défini. Est-ce qu'il s'agit d'équations diophantiennes ou tes variables et le résultat peuvent être des fractions? Les variables sont limitées à quels intervalles de valeur : [0 à 100] ou [-123456789, 123456789] ou plus?

[valentin03]

Oh purée... bstjean ne me rajoute pas des problèmes. "On ne connaît rien ou à peu près de la vie de Diophante, même l'époque à laquelle il a vécu reste très incertaine1. Son œuvre est en partie perdue".
Trois excellents motifs pour le passer sous silence; contentons nous de choses simples.

[bstjean]

En fait, s'il s'agit d'équations diophantiennes (https://fr.wikipedia.org/wiki/%C3%89..._diophantienne), ça facilite quelque peu les choses comme les variables et le résultat doivent TOUS être des entiers!

[wiwaxia]

Bonjour,

Je m'en tenais au strict énoncé du problème posé

... Un algo, qui d'une expression quelconque (limitée) donne les expressions équivalentes de toutes les variables de l'expression.
Exemple: x=(a+b)*(c-d)/e ...

c'est à dire à l'établissement de la fonction explicite (si elle existe !) de chacun des termes figurant dans une relation donnée.
J'ai déjà précisé en quoi l'exemple cité était trop simple, et donnait traîtreusement à penser que l'algorithme de résolution était à portée de main (ou plutôt de clavier ...) .

... Un autre problème provient du fait que le domaine de chaque variable n'est pas défini. Est-ce qu'il s'agit d'équations diophantiennes ou tes variables et le résultat peuvent être des fractions? Les variables sont limitées à quels intervalles de valeur : [0 à 100] ou [-123456789, 123456789] ou plus?

Compte tenu de la difficulté, je n'envisageais même pas la restriction de la recherche à un domaine donné, ou sur un ensemble donné (entiers ou rationnels) de variables.

En fait, s'il s'agit d'équations diophantiennes (https://fr.wikipedia.org/wiki/%C3%89..._diophantienne), ça facilite quelque peu les choses comme les variables et le résultat doivent TOUS être des entiers!

Hélas non ! L'article cité est malheureusement très clair sur ce point ...
Comment ferais-tu pour trouver les solutions entières non triviales (y = 0 impliquant x = 0 ou x = ± 1) de l'équation: y² = 5*x*(1 - x²) ?
Tuyau: il y a (x = -9 ; y = ± 60) et rien d'autre jusqu'à -2000 d'après ma calculette.
Tu remarqueras que le procédé n'a rien à voir avec la recherche d'une fonction réciproque, et qu'il pourrait à lui seul constituer le sujet d'un autre débat.

Je crois me rappeler qu'il a été question de calcul formel sur un forum récent, remontant peut-être à quelques semaines (?).

Petit sujet amusant, et beaucoup moins ambitieux: trouver par un procédé aléatoire des chaînes de 13 caractères résultant d'une permutation de la séquence '(a+b)*(c-d)/e' , et correspondant à une expression grammaticalement correcte de (x).

[valentin03]

Hormis le mur de la factorielle je ne vois pas où serait la difficulté (avec les 4 opérateurs)
Avec 200 000 combinaisons combien de termes peut-on faire tourner ?
Peut-on calculer la "racine" de factorielle ? (anti-factorielle ???)

[wiwaxia]

La fonction factorielle intervient dans le dénombrement des séquences, en non pas dans la relation étudiée.

Il s'agit au départ d'une fonction entière d'une variable entière; l'argument (k) correspondant à N = k! = Fact(k) se repère donc facilement par un algorithme d'encadrement du genre:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
k:= 0; f:= 1:
REPEAT
  Inc(k); f:= k * f
UNTIL (f>=N);

en réalité un peu plus compliqué du fait du dépassement rapide des limites du calcul (L_max = 10¹⁰⁰ pour les calculatrices), et que l'on a par exemple:
69! = 1.71E⁹⁸ < L_max < 70! = 1.20E¹⁰⁰ .

Il existe une fonction réelle d'une variable réelle qui s'identifie (à une translation près) à (k!); il s'agit de la fonction Gamma, définie à partir d'une intégrale et qui se prête à des calculs d'interpolation.

Il est cependant beaucoup plus facile, face à de très grands nombres, de partir de la formule de Stirling:
k! ~ (k/e)^k*Sqrt(2*Pi*k) .

[wiwaxia]

Après tous ces détours (auxquels je ne suis pas étranger ) il est temps d'en revenir à l'essentiel de la question posée.

1°) Tu cherches
[QUOTE]

... Un algo, qui d'une expression quelconque (limitée) donne les expressions équivalentes de toutes les variables de l'expression.

ce qui (cela a déjà été dit) relève du calcul formel; il ne saurait être question de réinventer la roue dans un tel domaine, et la seule option est de te tourner vers un logiciel approprié - il n'en manque pas sur Internet, et peut-être que quelques uns d'entre eux fonctionnent déjà sur ton ordinateur.

2°) Alors que s'imposait un traitement logique des équations, tu t'orientes vers l'énumération aveugle de toutes les chaînes de caractères utilisant les mêmes signes:

... Exemple: x=(a+b)*(c-d)/e
On fixe des valeurs arbitraires pour calculer x.
Puis par force brute on teste-calcule tous les arrangements
Si valeur arrangement = valeurs variables afficher: variable = arrangement (expression)
ça paraît jouable mais je m'interroge sur le nombre d'arrangements en fonction de la longueur de l'expression (14 pour l'exemple) ...

... ce qui revient à chercher l'aiguille dans une botte de foin, après l'y avoir délibérément jetée !
a) Oubliant la présélection des séquences conformes aux règles de syntaxe - dont tu ne souffles mot - tu ne proposes comme seul test que
b) la vérification de la relation en cause pour une (ou plusieurs ?) liste(s) de valeurs connues (x₁, a₁, b₁, c₁, d₁, e₁);

... On fixe des valeurs arbitraires pour calculer x ...
... Si valeur arrangement = valeurs variables afficher: variable = arrangement (expression) ...

et rien ne permet d'exclure l'existence de plusieurs expressions, dans le vaste ensemble sélectionné, vérifiant la (ou les) égalité(s) numériques.

Question essentielle: as-tu rédigé un programme, ou une ébauche de programme ? Ou au moins le début de l'apparence d'un commencement d'un vague plan d'algorithme ? Il serait intéressant pour toi de t'y mettre ...

Voici deux projets envisageables, partant de l'expression proposée: x=(a+b)*(c-d)/e

1°) L'énumération aléatoire des chaînes de caractères grammaticalement correctes, sans même contrôler les doublons résultant de la commutativité des opérations (+, *), à partir de la liste suivante:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

ListeC: ARRAY[1..14] OF Char = ('a', 'b', 'c', 'd', 'e', '+', '-', '*', '/', '(', '(', ')', ')', ' ')

dont le dernier terme est neutre, et à laquelle tu adjoindras une matrice de compatibilité

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

MatC: ARRAY[1,,13, 1..13] OF Boolean = ...

(que je te laisse le soin de remplir).

2°) Le dénombrement systématique des expressions viables du paramètre (e) à partir des combinaisons des 4 parenthèses qui structurent la relation, en éliminant les cas où l'on ne trouve qu'un seul terme à l'intérieur d'une paire:
[ ... (v) ... ] ou rien à l'extérieur [ x = ( ... ) ] - ce parce qu'elles deviennent alors inutiles.
Il faut d'abord classer manuellement les expressions, en envisageant tous les arrangements possibles avec les variables (v = a, b, c, d, e) et les opérateurs (# = +, -, *, /):
((v#v)#v)#v#v
((v#v)#v#v)#v
((v#v#v)#v)#v
(v#(v#v)#v)#v
+ arrangements rétrogrades ...
v#(v#v)#(v#v)
(v#v)#v#(v#v)
(v#v)#(v#v)#v
(v#v)#(v#v#v)
(v#v#v)#(v#v)

[valentin03]

@: wiwaxia: Oui j'ai commencé un truc qui analyse l'expression, fixe des valeurs et calcule "x"; j'ai fait la combinatoire; mais le hic, c'est que dans ma grande naïveté je n'ai pas fait gaffe au: "Tous faux sauf un", qui rend le projet totalement utopique.
Je comprends à ton éclairage pourquoi je ne trouvais pas cette fonctionnalité (la rotation des variables qui serait bien pratique) dans les softs de calcul formel.
Mais ils auraient quand même pu mettre les différentes écritures possibles et équivalentes des expressions (qui sont dans les bouquins).
Avec tes formules j'ai trouvé qu'avec 100 000 combinaisons on pouvait faire tourner 9 termes, c'était déjà pas mal; mais ton: "Tous faux sauf un" m'a définitivement cassée la baraque; car parfois variable varie.

[valentin03]

Si je trouve la liste des illégalités et que j'élimine les combinaisons illégales, ce qui reste devrait être bon, non ?

[wiwaxia]

Il faudrait dire plus exactement ""Tous faux sauf quatre", compte tenu des permutations autorisées qui conduisent à 4 expressions équivalentes de (x):

x = (a+b)*(c-d)/e = (b+a)*(c-d)/e = (c-d)*(a+b)/e = (c-d)*(b+a)/e

toutes les autres, bien que de syntaxe correcte, sont fausses.
Exemples: x = (a-b/c)*(d+e) ou (d*e-c/(b+a)) ... etc

Si je trouve la liste des illégalités et que j'élimine les combinaisons illégales, ce qui reste devrait être bon, non ?

C'est précisément ce que contient la matrice de booléens que je te proposais d'écrire, une fois posée la liste des caractères:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

ListeC: ARRAY[1..14] OF Char = ('a', 'b', 'c', 'd', 'e', '+', '-', '*', '/', '(', '(', ')', ')', ' ')

et étant convenu qu'on repère en colonne le dernier caractère écrit, et en ligne le nouveau qui devrait être ajouté.
Ainsi la première colonne de la matrice aurait pour contenu:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
 
MatC[i, 1] = < False,
               False,
               False,
               False,
               False,
               True,
               True,
               True,
               True,
               False,
               False,
               False,
               False >

parce qu'aucun caractère ne peut succéder à un autre (lui-même compris), ni être directement suivi d'une parenthèse, mais qu'il vient toujours après lui l'un des 4 opérateurs.

[valentin03]

@ wiwaxia: Cite: "aucun caractère ne peut succéder à un autre, il vient toujours après lui l'un des 4 opérateurs"
Dans ces cas on parlera plutôt d'incohérence.
Mais pour les illégalités cohérentes telles que:
"Exemples: x = (a-b/c)*(d+e) ou (d*e-c/(b+a)) ... etc"; y a pas quelque part des listes de cas, ça permettrait de poser les interdictions en fonction de l'expression.
Parce que ce que je veux c'est faire tourner les variables autour du signe "=" (en restant dans la légalité)
Et comme on ne peut pas demander au pc de réfléchir, il faut bien trouver un moyen.

[wiwaxia]

OK je me suis mal exprimé:

parce qu'aucune variable ne peut succéder à une autre (elle-même comprise), ni être directement suivie d'une parenthèse, mais qu'il vient toujours après elle l'un des 4 opérateurs.

... Parce que ce que je veux c'est faire tourner les variables autour du signe "=" (en restant dans la légalité) ...

Il s'agit au départ de toutes les expressions cohérentes de de la variable (x):

... projets envisageables, partant de l'expression proposée: x=(a+b)*(c-d)/e ...

qui commence donc systématiquemet par: 'x = '.
Passer à un autre terme ne change strictement rien au problème; pour (a) par exemple, il suffirait de remplacer ce terme par 'x' dans la liste initiale, et de commencer par 'a = '.
Le programme proposé a pour objet la chaîne qui suit, de 13 caractères, et de la programmer aléatoirement.

[valentin03]

Il s'agit au départ de toutes les expressions cohérentes de de la variable (x):

Il s'agit de trouver (d'écrire) "a" en fonction de x et du reste
Pareil pour b et les autres. x ne sert qu'en tant que terme à échanger.
Et le passage par les valeurs numériques, qu'à valider (mais ça valide des trucs faux, car violant des règles; où trouver une liste exhaustive de ces fameuses règles quel est l'ordre de grandeur de leur nombre ? Pour les quatre opérateurs, restons modeste.
Le "Beaucoup de faux et peu de justes" est fort ennuyeux.

[anadoncamille]

Bonjour,

Si tu souhaites explorer l'espace des valeurs possibles de ton équation en vue d'en trouver la solution, tu peux utiliser un algorithme génétique. Chaque gène porte les valeurs des variables et la fonction de fitness est la proximité entre le résultat de l'équation et x, nul si l'équation est résolue. Je ne suis pas sûr d'avoir bien compris ton problème mais la solution me semble jouable et elle te donnera des résultats en un temps fini.

[Flodelarab]

Bonjour

Je n'ai toujours pas compris l'énoncé.

Je m'étonne que personne n'ait parlé de la notation polonaise inversée, plus pratique, probablement pour ce genre de dénombrement.

Enfin, si le but est de faire un programme qui gagne aux chiffres de Des chiffres et des lettres, c'est largement faisable.

[valentin03]

Bonjour

Je n'ai toujours pas compris l'énoncé.

Le but est d'obtenir à partir d'une expression x=variables et opérateurs
Les expressions variable=variables et opérateurs pour toutes les variables
Je pensais fixer des valeurs à l'expression initiale pour calculer x
Puis faire toutes les combinaisons variable=variables et opérateurs
Eliminer les incohérences du genre: a=x+/b*(-)
Calculer les expressions cohérentes
Les valeurs de chaque variable restant fixes tout au long des calculs
Il me semble que quand il y a égalité l'expression est valide
Et ainsi avoir l'expression de chaque variable en fonction des autres
Il semble que je me plante dans le raisonnement mais où ?

[Flodelarab]

Je maintiens ma réponse.

Va voir sur Wikipedia, Notation polonaise inversée. Déjà, plus de problème de parenthèses.

Et quand au fait de partir de valeurs fixes qu'on combine avec les 4 opérations élémentaires, c'est le jeu des chiffres et des lettres que de nombreux informaticiens ont résolus. Renseigne-toi.