J'aimerais savoir comment trouver les solutions du système, ou tout du moins savoir s'il y en a au moins une.
Le système suivant n'est qu'un exemple, mais j'aimerais pouvoir appliquer la méthode de résolution à un algorithme et résoudre des systèmes plus grands.
L'information ESSENTIELLE, c'est celle que tu donnes en dernier : a,b,c,d,e,f prennent leurs valeurs dans {0,1}
Du coup, le pivot de Gauss, il ne sert à rien. Le pivot de Gauss, il va nous emmener vers des solutions réelles quelconques.
Y a-t-il au moins une solution. On va être bourrin, on a 2^6=64 combinaisons à regarder, ça va aller vite.
Si a =0, ça donne quoi ? La 1ère équation donne d=f=1 ; la 4ème équation donne c=e=1, la dernière équation donne b=0. Et on voit que ce sextuplet (0,0,1,1,1,1) est solution.
Y-a-t-il d'autres soutions ? Si a=1, alors la 1ère équation nous dit : (f=1,d=0) ou bien (f=0,d=1)
La 4ème équation nous dit (c=1,e=0) ou bien (c=0, e=1)
Si b=0, on n'aura pas de solution, mais si b=1, alors on trouve vite 2 nouvelles solutions (1,1,1,1,0,0) et (1,1,0,0,1,1).
Et ce sont bien évidemment les 3 seules solutions, puisqu'on a exploré COMPLETEMENT les cas a=0 et a=1
Mais il y avait aussi une information importante en 2e: Je ne cherchais pas spécifiquement la solution de ce système, mais j'aurais aimé savoir s'il y avait un moyen de le résoudre sans passer par la case "bourrin"
Comme je l'ai écrit, ce n'est qu'un exemple et j'utiliserai normalement beaucoup plus de variables, et pour peu que je passe à 100 variables, 2^100 je n'y arriverais jamais en recherche exhaustive....
Est-ce qu'il n'existe pas un moyen élégant, à l'image du pivot de Gauss pour savoir s'il y a une solution ? (ou encore mieux: les trouver )
J'aimerais avoir un algo qui résoud ça en temps polynomiale...
Avec 100 variables, en théorie, tu as 2^100 cas à explorer. Mais dans la pratique, tu en as beaucoup moins. Il y a plein de branches qu'on peut couper très vite. Dans l'exemple précédent, si on se limite aux variables (a,c,e), on a en théorie 8 combinaisons, et avec l'équation a+c+e=2, on tombe à 3 combinaisons. Chaque équation est l'équation d'un 'hyperplan',elle réduit énormément la taille de l'arbre.
Si par exemple j'ai 100 variables , si j'ai une équation qui me dit que la somme des 50 premières variables donne 25, alors, on avait 2^50 combinaisons possibles pour ces 50 variables, et on tombe à 50!/25!25!. On a divisé par 10 le nombre de combinaisons, avec une seule équation.
C'est un cas peu favorable. Si on a une équation qui dit que la somme de 50 variables donne 10, avec cette seule équation, on divise la taille de l'arbre par 100000.
Je ne suis pas du tout un spécialiste des théories, mais ici, si tu dois rechercher dans les outils 'modernes', je chercherais du côté 'Parcours d'arbre binaire'.
× Après avoir cliqué sur "Répondre" vous serez invité à vous connecter pour que votre message soit publié.
× Attention, ce sujet est très ancien. Le déterrer n'est pas forcément approprié. Nous te conseillons de créer un nouveau sujet pour poser ta question.
Mon portfolio photo : https://www.instagram.com/charlievanaret_photo/