[PDF] algorithme d'euclide python
[PDF] algorithme de dijkstra arduino
[PDF] algorithme de dijkstra c++
[PDF] algorithme de dijkstra en ligne
[PDF] algorithme de dijkstra java
[PDF] algorithme de dijkstra javascript
[PDF] algorithme dichotomie python
[PDF] algorithme factorielle boucle pour
[PDF] algorithme factorielle en c
[PDF] algorithme factorielle n
[PDF] algorithme factorielle pascal
[PDF] algorithme factorielle python
[PDF] algorithme fonction procedure exercice corrigé pdf
[PDF] algoritmo de dijkstra aplicaciones
[PDF] algoritmo de dijkstra c++
Université de BordeauxPréparation à l"agrégation
Mathématiques2021-2022
Algorithme d"Euclide
1.Rappels
SoitAun anneau euclidien. C"est donc queAest commutatif unitaire, intègre, et qu"il existe une application?:A→Nappelée stathme euclidien, telle que (1)?(a) = 0 si et seulement sia= 0 (2) Siaetbsont des éléments deA, avecb?= 0, il existe des éléments retqdeAtels quea=bq+ret?(r)< ?(b). Les élémentsret qsont respectivement appelés reste et quotient de la division dea parb; on n"impose pas qu"ils soient uniques. Par exemple, siA=Z, on peut prendre?(n) =|n|. Ici, il n"y a pas unicité de l"écriturea=bq+r, où?(r)< ?(b); on impose traditionnellement
0?r < bce qui garantit l"unicité, mais c"est un choix arbitraire : on pourait
tout aussi bien imposer-b/2< r?b/2 par exemple. SiA=K[X], oùK est un corps, on peut choisir?(P) = degP+ 1 siP?= 0 et?(0) = 0. Enfin, pourA=Z[i], on peut prendre comme stathme?(a+ib) =a2+b2. Tout anneau euclidien est principal, et tout anneau principal est factoriel (tout élément non nul se décompose en produit fini d"irréductibles et cette décomposition est unique, à multiplication des facteurs par des inversibles près). SiAest un anneau principal, soientaetbdeux éléments deAtels que (a,b)?= (0,0), il existeddansAtel que (1)d|aetd|b (2) Sie|aete|b, alorse|d. Cet élémentd, unique à multiplication près par un élément inversible de A, est appelé le pgcd deaetb, et noté pgcd(a,b), ou parfois (a,b) si le contexte ne permet pas d"ambiguïté avec l"élément (a,b) deA2. On a alors aA+bA=dA. En particulier, il existeuetvdansAtels queau+bv=d (identité de Bézout). Ceci donne une définition légèrement plus générale : on appelle pgcd de (a,b) tout générateur de l"idéalaA+bAdeAengendré paraetb; cette définition est équivalente à la précédente quand (a,b)?= 0 et définit pgcd(0,0) = 0. Une dernière définition, encore plus générale puisqu"elle est valable si l"anneauAest factoriel. SiAest factoriel,a?A\{0}, etpirréductible dans A, on définitvp(a) la plus grande puissance depqui divisea: siv=vp(a), on apv|amaispv+1?a. On définit pgcd(0,b) =bpuis, pour toutb?Aet poura,btous deux non nuls, on pose pgcd(a,b) =? ppmin(vp(a),vp(b)) 1
2oùpparcourt un système de représentants des éléments irréductibles deA
modulo les unités. Cette définition généralise les deux précédentes et permet de calculer le pgcddquand la factorisation dansAest effective. SiAest de plus euclidien, l"algorithme d"Euclide permet aussice calcul, en général à bien moindre coût que celui d"une factorisation. L"algorithme d"Euclide étendu calcule, en même temps qued, des élémentsuetvsatis- faisant l"identité de Bézout. Rappelons finalement que dans un anneau principalA, siaetbsont deux éléments deA, il existe un élémentcdansA, unique à multiplication près par un inversible deA, tel que (1)a|cetb|c (2) Sia|eetb|e, alorsc|e. C"est le ppcm deaetb, noté ppcm(a,b), ou encore [a,b]. On a aA+bA= (a,b)A, aA∩bA= [a,b]AetabA= (a,b)[a,b]A.
2.Algorithme d"Euclide
Algorithme 2.1(Algorithme d"Euclide)
Entrée:a,bdansA
Sortie:pgcd(a,b)
(1) Sib= 0, retournera. (2) Soitrle reste de de la division euclidienne deaparb. Posera←b, b←ret revenir à l"étape(1). Preuve.Le cas (a,b) = (0,0) est clair puisque l"algorithme retourne direc- tement 0 à l"étape (1). Le cas général vient du fait que (a,b) = (a+bk,b) pour toutk?A(exercice). L"algorithme se termine car la valeur de?(b) décroit strictement tant queb?= 0. Comme?prend ses valeur dansN, on finit par arriver à?(b) = 0, doncb= 0.?
3.Algorithme d"Euclide étendu
Algorithme 3.1(Algorithme d"Euclide étendu)
Entrée:aetbdansA,(a,b)?= (0,0).
Sortie: Le pgcdddeaetb, et un couple(u,v)deA2tel queau+bv=d. (1) Sia= 0, sortird=b,u= 0,v= 1. (3) Tant quey?= 0 (4) Calculer le quotientqet le resterde la division euclidienne de xpary. (5)(ux,uy)←(uy,ux-quy). (6)(vx,vy)←(vy,vx-qvy). (7)(x,y)←(y,r). (8) Sortird=x,u=ux,v=vx. 3 Preuve.Comme dans l"algorithme précédent, l"algorithme se termine, et l"on calcule biendun pgcd deaetb. On posex0=a,v0= 0,u0= 1,x1=b,v1= 1 etu1= 0. Pouri?1, on écrit la division euclidiennexi-1=qixi+xi+1, où?(xi+1)< ?(xi), et on posevi+1=vi-1-qivietui+1=ui-1-qiui. C"est donc que ?uivi u i+1vi+1? =?0 11-qi?? ui-1vi-1 u ivi?
Donc si
?uivi u i+1vi+1?? a b? =?xi-1 x i? ce qui est vrai pouri= 1, alors ?uivi u i+1vi+1?? a b? =?0 11-qi?? xi-1 x i? =?xi x i+1? Soitll"entier tel quexl+1= 0. On a bien alorsula+vlb=xl=d.?
4.Complexité dansK[X]
SoitKun corps. AlorsK[X] est un anneau euclidien. On veut majorer le nombre d"opérations dansKnécessaire à l"exécution des algorithmes d"Eu- clide en fonction du degré des polynômes concernés. On gardeles notations du paragraphe précédent.
4.1.Algorithme d"Euclide.Soientaetbdeux polynômes deK[x], de
degrés respectifsnetm. On suppose quem?n. Le nombre d"itérationsl est borné par?(b), donc icim+ 1. Pour touti, on noteni= degxi. On peut diviser le polynômexi-1parxi en utilisant au plus (2ni+ 1)(ni-1-ni+ 1) additions et multiplications, et une inversion dansK. Donc le coût total est inférieur à C=l? i=1(2ni+ 1)(ni-1-ni+ 1) additions et multiplications, pluslinversions dansK. On voit alors que
C?(2m+1)l?
On a donc prouvé le résultat suivant.
Théorème 4.1.SoitN?1. On peut exécuter l"algorithme d"Euclide pour deux polynômes de degré inférieur ou égal àNenO(N2)opérations sur le corps de base. On peut donner une majoration plus précise deC. Pour cela, on évalueC dans le cas où le degré décroît exactement de 1 à chaque pas, eton montre ensuite que c"est le cas le pire. 4 Dans ce cas,l=m+ 1,n0=n,n1=met pouridans{2...,m+ 1}, n i=m-i+ 1. On trouve alors que
C= (2m+ 1)(n-m+ 1) + 2m+1?
i=2?
2(m-i+ 1) + 1?
= 2mn+n+m+ 1. Pour montrer que c"est le cas le pire, on pose, pourn0?n1> n2>···> n l?0,
σ(n0,...,nl) =l?
i=1(2ni+ 1)(ni-1-ni+ 1). Montrons queσcroît, si l"on insère un entierkentrenj-1et unnj, ou bien si l"on ajoutekaprèsnl. Soit donckun entier tel quenj-1> k > nj. = (2k+ 1)(nj-1-k+ 1) + (2nj+ 1)(k-nj+ 1)-(2nj+ 1)(nj-1-nj+ 1) = (2k+ 1)(nj-1-k+ 1) + (2nj+ 1)(k-nj-1) = 2(nj-1-k)(k-nj) + 2k+ 1>0 On montrerait le méme résultat, en ajoutant un entierkaprèsnl. On en déduit par récurrence queσ(n0,...,nl)?σ(n0,n1,n1-1,n1-2,...,1), et donc que le cas où le degré baisse de 1 à chaque pas est le cas le pire. Théorème 4.2.L"algorithme d"Euclide, appliqué à des polynômesaetbde degrés respectifsnetm(n?m), utilise au plus2mn+m+n+1additions et multiplications, plusm+ 1inversions dansK.
4.2.Algorithme d"Euclide étendu.Pour évaluer la complexité de l"al-
gorithme d"Euclide étendu, il nous faut majorer le degré despolynômesui etvi.
Proposition 4.3.On a
degvi=?
1?j degui=? 2?j Preuve.Par récurrence. On av0= 0,v1= 1,v2=v0-q1v1=-q1. Ainsi, degv2= degq1=n-m=n0-n1. Soiti?1. On suppose que pour tout j? {1,...,i}, on a degvj=?j-1 k=1degqk. Ainsi, degvj-11?k?idegqi.
L"égalité pour le degré deuise prouve de la même façon.? 5 Le calcul devi+1=vi-1-qividemande au plus 2degqidegvi+ degqi+ degvi+1 opérations dansKpour le produit et au plus degvi+1+1 opérations pour la soustraction, c"est-à-dire en tout 2(ni-1-ni)(n0-ni-1+n0-ni+1), sauf pouri= 1 : le calcul dev2=-q1demanden-m+ 1 changements de signe. On obtient que le nombre d"opérations dansKpour calculer lesvi est majoré par C v=n-m+ 1 + 2l? i=2((ni-1-ni)(n0-ni-1) +n0-ni+ 1) ?n-m+ 1 + 2nl? i=2(ni-1-ni) + 2(l-1)(n+ 1) ?n-m+ 1 + 2n(n1-nl) + 2(l-1)(n+ 1) ?n-m+ 1 + 2mn+ 2m(n+ 1) ?4mn+n+m+ 1. On montrerait de même que le nombre d"opérations dansKnécessaires au calcul desuiest inférieur ou égal à 4m2+m. On peut améliorer ces majorations, en calculant le nombre d"opérations nécessaires au calcul desuiet desvidans le cas où le degré du reste baisse de 1 à chaque étape, puis en montrant que c"est le cas le pire. On obtient alors C v=n-m+ 1 + 2m+1? i=2((n-(m-i+ 2)) +n-(m-i+ 1) + 1)) = 4mn-2m2+n+m+ 1 C u= 2 + 2m+1? i=3((m-(m-i+ 2)) +m-(m-i+ 1) + 1) = 2(m2+m). On peut aussi noter que l"algorithme d"Euclide étendu calcule inutilement la suite desvi: on peut entièrement supprimer ces calculs, sans affecter le calcul deuetd. Sib?= 0, on peut alors poserv= (d-au)/b. Théorème 4.4.L"algorithme d"Euclide étendu, appliqué à des polynômes aetbde degrés respectifsnetm(n?m), utilise6mn+O(n)additions et multiplications, plusm+ 1inversions dansK. 5.Complexité dansZ
5.1.Algorithme d"Euclide.On applique l"algorithme d"Euclide à deux
entiersaetbpositifs. Le nombre d"itérations est inférieur ou égal àb, mais on peut trouver une bien meilleure majoration : Théorème 5.1.Soitnun entier naturel non nul, et soientaetbdeux entiers tels quea > bet tels que l"algorithme d"Euclide appliqué àaet 6bnécessite exactementndivisions, et tels queasoit minimal pour cette
propriété. Alorsa=Fn+1etb=Fn, où(Fn)est la suite de Fibonacci définie parF0= 0,F1= 1,Fi+2=Fi+1+Fipouri?0. Preuve.Si on applique l"algorithme d"Euclide àFn+1etFn, on obtient (Fn+1,Fn) = (Fn,Fn-1) =···= (F1,F0) = 1. On a donc exactementndivisions.
Réciproquement, on suppose queaetbsatisfont les conditions de l"énoncé. Soientxn+1=a,xn=b, et pouri < n, soitxile reste de la division dexi+2 parxi+1, jusqu"àx0= 0. Alors pour touti,xi+1> xi. On noteqila partie entière dexi+1/xi. Commexi+1=xi-1+qixi?xi-1+xipour toutiet commex0=F0= 0 etx1?F1= 1, on obtient par récurrence quexi?Fi pour touti. Donca?Fn+1. La minimalité deamontre alors quea=Fn+1. De plus,xn-1?Fn-1=Fn+1-Fn?a-b, puisqueFn?b. Comme en outrexn-1?xn+1-xn=a-b, les inégalités ci-dessus sont des égalités et F n=b.? Le cas le pire est donc atteint pour deux éléments consécutifs de la suite de Fibonacci. On peut écrireFnde façon explicite. Soient ?=1 +⎷ 5 2etψ=1-⎷
5 2 les racines dex2-x-1, alorsFn⎷ 5 =?n-ψn. Ainsi, si l"algorithme
d"Euclide appliqué àaetbdemanden-1 divisions, alorsa⎷ 5??n-ψn.
Donca⎷
5> ?n-1 et
n < log(1 +a⎷ 5) log?. On en déduit que le nombre de divisions est majoré par log ?(1 +a⎷ 5)? -2. Donc, siaetbsont inférieurs àN, alors le nombre d"opérations élémentaires dans l"algorithme d"Euclide est enO((logN)3+1). Mais on peut faire mieux : Théorème 5.2.Siaetbsont inférieurs àN, le coût du calcul de(a,b)par l"algorithme d"Euclide est enO((logN)2+ 1). Preuve.On suppose quea > b >0, et que l"algorithme d"Euclide pouraet bdemande exactementndivisions. On notex0=a,x1=b,x2,...xn+1= 0 la suite des restes successifs, et pouridans{1,...,n}, on noteqile quotient dexi-1parxi. Doncxi-1=qixi+xi+1. Le coût des divisions est inférieur à une constante multipliée par
n? i=1(logxi+ 1)(logqi+ 1)?(loga+ 1)n? i=1(logqi+ 1) ?(logN+ 1)(n+ logn? i=1q i). 7 Comme n? i=1q i?n? i=1x i-1 xi=a(a,b)?N, le coût est bien enO((logN)2+ 1).? 5.2.Coût de l"algorithme d"Euclide étendu.On reprend les notations
du §3. Doncx0=a,v0= 0,u0= 1,x1=b,v1= 1 etu1= 0. Pouri?1, x i-1=qixi+xi+1, où?(xi+1)< ?(xi), et on pose?uivi u i+1vi+1? =?0 11-qi?? ui-1vi-1 u ivi? Proposition 5.3.Pour touti, on a les inégalités|ui|?b/xi-1et|vi|? a/x i-1. Preuve.On a?uivi
u i+1vi+1? =?0 11-qi? ···?0 11-q1?
ainsi det?uivi u i+1vi+1? = (-1)i et ?uivi u i+1vi+1? -1 = (-1)i?vi+1-vi -ui+1ui? Or tous les
?0 11-qi? -1 =?qi1 1 0? sont à coefficients positifs, donc leur produit aussi! Donc ?uivi u i+1vi+1? -1 =?|vi+1| |vi| |ui+1| |ui|? Or ?uivi u i+1vi+1?? a b? =?xi x i+1? donc ?|vi+1| |vi| |ui+1| |ui|?? xi x i+1? =?a b? D"où l"on tire les inégalités annoncées.? Un calcul similaire à celui du paragraphe précédent permet alors de montrer le résultat suivant. Théorème 5.4.Siaetbsont inférieurs àN, l"algorithme d"Euclide étendu appliqué àaetbutiliseO((logN)2+ 1)opérations élémentaires.quotesdbs_dbs17.pdfusesText_23
[PDF] Algorithme dEuclide - Département de Mathématiques dOrsay