Algorithme d'Euclide étendu
Bonjour,
Je ne comprends pas le programme, et surtout les passages encadrés.
Pour le cas $B=0$, on a $AU+BV=PGCD(A,B)$ d'après Bezout.
Si $B=0$, $PGCD(A,B)=\dfrac{A}{\lambda}$ donc le premier coefficient de Bezout vaut $1$ non ?
Je ne comprends pas le $(D,U,V) \longleftarrow PGCD(B,R)$
A quoi sert le $(Q,R)$ il n'est pas utilisé dans la suite ?
Je ne comprends pas le programme, et surtout les passages encadrés.
Pour le cas $B=0$, on a $AU+BV=PGCD(A,B)$ d'après Bezout.
Si $B=0$, $PGCD(A,B)=\dfrac{A}{\lambda}$ donc le premier coefficient de Bezout vaut $1$ non ?
Je ne comprends pas le $(D,U,V) \longleftarrow PGCD(B,R)$
A quoi sert le $(Q,R)$ il n'est pas utilisé dans la suite ?
Connectez-vous ou Inscrivez-vous pour répondre.
Réponses
Mais je ne comprends pas ce programme. Je veux bien essayer de l'appliquer sur un exemple mais je n'ai pas compris le programme.
@Boole et Bill
En effet, désolé.
Le principe est de réappliquer le même programme avec d'autres paramètres, en s'assurant que l'on va s'arrêter à un moment donné...
Bon, comme a dit @Philou je teste sur un exemple.
$A=X^3-2$ et $B=2X^2-3$.
$(Q,R)=(\dfrac{X}{2},\dfrac{3X}{2}-2)$
Je ne comprends pas la commande $(D,U,V) \longleftarrow PGCD(B,R)$
C'est qui $D$ ? On stocke où le pgcd de B et R ?
-- Schnoebelen, Philippe
Une traduction en Matlab: Et un test: Cordialement,
Rescassol
@Rescassol
Je n'ai plus utilisé Matlab depuis 10 ans !
Si je reprends mon exemple :
$A=X^3-2$ et $B=2X^2-3$.
$(Q,R)=(\dfrac{X}{2},\dfrac{3X}{2}-2)$
On a $A=B \dfrac{X}{2}+(\dfrac{3X}{2}-2)$
Ici $D=\dfrac{3X}{2}-2$ ?
Comment trouver $U$ et $V$ ?
Pourquoi dans l'algorithme $V_{k+1}=U_k$ ?
Jusqu'à ce que tu te retrouves dans le cas de base où l'on te donne les valeurs de U et V... puis tu termines les calculs dans l'ordre.
Je ne vois pas comment déterminer $U_0$ et $V_0$.
-- Schnoebelen, Philippe
Je n'arrive pas à appliquer l'algorithme sur un exemple.
Avant de te dire "je dois mieux maitriser la récursivité", il te faut avoir "le gout de la magie". Et pour ça, pas besoin d'ordinateur.
Sur les entiers, une écriture comme
$f(a,b):=[$
if CasSimple then
ReponseSimple else
$a<b$ then $f(b,a)$ else $f(a,a-b)]$
qui, par snobisme culturel récent dû aux avancées technologiques, est qualifié de "programme informatique"
mérite tout à fait ton respect comme hypothèse mathématique ad hoc
La seule chose que tu ne feras pas, c'est de dire:
"Définition: blabla"
Tu diras plutôt:
"Hypothèse: soit $f$ une fonction telle que blabla"
Par exemple, pour les entiers (je ne spoile pas ton fil en parlant des polynômes et en même temps ça m'évite des efforts), ça prend la forme:
Hypothèse: soit $f: \N^2\to \Z^3$ telle que pour tous entiers $a,b$ :
si $a=b$ alors $f(a,b)=(a,1,0)$ sinon,
si $a=0$ alors $f(a,b)=(b,0,1)$ sinon,
si $a<b$ et $f(b,a) =(d,u,v)$ alors $f(a,b) = (d,v,u)$ sinon,
si $f(a-b,b) = (d,u,v)$ alors $f(a,b) = (d,u,v-u) $
Nous allons démontrer que blabla
Et franchement, la traduction en paradigme informatique, est non seulement "assez triviale", mais surtout UNE TOUTE AUTRE AFFAIRE.
Si tu n'adoptes pas cette "positive attitude", ton cerveau sera sans cesse à hésiter. Faire des maths, ce n'est pas s'interdire des choses, c'est recenser des choses. C'est faire formellement les hypothèses qu'on utilisera ensuite.
Il se trouve que la fonction que je t'ai décrite existe pour des raisons "accidentelles" qui sont que les calculs terminent toujours au bout d'un temps fini à partir de l'application de l'hypothèse faite, ce qui non seulement assure l'unicité de la fonction, mais aussi pour des raisons plus raffinées de fondements, son existence. Or ces derniers points sont systématiquement occultés au point même que tes enseignants, pour une grande part, ne seraient même pas capables de réécrire (pas au cas par cas, mais le principe général).
Brouillon:
[small]$d = u(a-b) + vb = ua + (v-u)b$[/small]
A noter que l'exo est bancal, en théorie (je reprends mon analogie avec les entiers) c'est $\N^2\to \Z^5$ et non dans $\Z^3$. C'est du gachis de perdre les attestations que $d$ divise a et b.
Ayant récupéré $d = u(a-b) + vb$ et $a-b = Kd$ et $b = Ld$, tu renvoies pour $(a,b)$ (et non plus $(a-b,b)$)
new(u) := u
new(v) := (v-u)
new(K):= K+L
new(L):=L
Je veux juste comprendre comment fonctionne l'algorithme sur un exemple avec 2 polynômes simples concrets $A$ et $B$.
Je sais faire une division euclidienne de polynôme et calculer des coefficients de Bezout pour des entiers en remontant la division euclidienne de deux entiers.
Il me reste la question suivante. C'est qui le premier triplet $(d,u,v)$ ? Comment le trouver ?
-- Schnoebelen, Philippe
Quand on a $A=X^3-2$ et $B=2X^2-3$.
$(Q,R)=(\dfrac{X}{2},\dfrac{3X}{2}-2)$
Quelle est l'étape suivante ?
On peut quand même expliquer le principe dans ce cas-ci en numérotant la profondeur de récursion. C'est le résultat final.
On peut vérifier à la main que \[U_0A_0+V_0B_0=\left(\frac{4X}{9}+\frac{16}{27}\right) \left(X^3-2\right)+\left(-\frac{2X^2}{9}-\frac{8X}{27}-\frac{1}{3}\right)\left(2X^2-3\right)=1=D_0\]
De mon téléphone
"Bizam merci mais je ne comprends rien à ce que vous faites c'est du chinois pour moi :-( "
si $x\notin \N$ alors $f(x)=0$
si $x\in \N$ alors $f(x)=1+f(x+1)$
De même avec tes fonctions PGCD : arrête de chercher à comprendre en même temps
- pourquoi ça marche
- ce qu'elles font.
Suppose qu'elles marchent sans te préoccuper de pourquoi (ie suppose qu'elles renvoient un résultat pour toute entrée) et rêve un peu. La question de savoir pourquoi les exécuter aboutit est TOUTE AUTRE.
Je suis convaincu que tu comprends très bien que :
si
$P = BQ + R$ et $D = UQ + VR$
alors
$D = UQ + V(P-BQ) = UQ + VP - VBQ = VP + (U-VB)Q$
Autrement dit que si le père noel te fournit $D,U,V$ pour $(Q,R)$, tu comprends que toi-même, tu récupères $D,V,(U-VB)$ pour $(P,Q)$
@MathCoss
Oui je ferai ça à l'avenir, c'est lourd de manipuler les polynômes.
@Bisam
@Christophe
Merci beaucoup j'ai compris la logique, mais je n'aurais jamais réussi tout seul.
J'avais réussi à comprendre des programmes récursifs très simples comme calculer factorielle n, mais là c'était plus compliqué.
@Noobey
Quand même pas, l'explication est très claire et très détaillée.
Ca viendra t'inquiète, si tu prends le gout de rêver (faire des hypothèses (d'existence) s'appelle rêver).