[PDF] Complexité de lalgorithme dEuclide

View - Download Complexité de lalgorithme dEuclide

Previous PDF

Next PDF

HST-2901 Histoire des mathematiques

Complexite de l'algorithme d'Euclide

M^eme si la complexite algorithmique est un domaine qui a connu un essor considerable principalement au cours des dernieres decennies, il est interessant d'observer que certains resultats dans ce domaine remontent au milieu duxixesiecle. On doit en eet au mathema- ticien francais Gabriel Lame (1795{1870) le theoreme suivant, paru dans lesComptes rendus de l'Academie des sciencesen 1844. TheoremeLe nombre de divisions a eectuer pour trouver lepgcdde deux entiers naturels a l'aide de l'algorithme d'Euclide ne depasse pas cinq fois le nombre de chires dans l'ecriture decimale du plus petit des deux nombres. Mais avant de plonger dans cette demonstration, on peut noter au passage un lien revelateur entre l'algorithme d'Euclide et la celebre suite desnombres de Fibonacci (1;1;2;3;5;8;13;:::), denie recursivement par F

1=F2= 1; Fn=Fn1+Fn2pourn= 3;4;:::

En appliquant cet algorithme a deux nombres de Fibonacci consecutifs,Fn+2etFn+1avec n1, on obtient : F n+2= 1Fn+1+Fn F n+1= 1Fn+Fn1... F

4= 1F3+F2

F

3= 2F2;

montrant ainsi quepgcd(Fn+2;Fn+1) =F2= 1, c'est-a-dire que ces deux nombres sont premiers entre eux. Or le point interessant, et c'est la le coeur de l'observation de Lame, 1 est qu'on se trouve ici en presence d'une longuesuite de divisions euclidiennes, en ce sens que les quotients, sauf le dernier, sont tous egaux a 1. Il s'agit donc en quelque sorte du pire caspour ce qui est de l'ecacite de la procedure d'Euclide et les nombres de Fibonacci serviront pour ainsi dire de barometresdans l'analyse de l'ecacite de cet algorithme. (On aura note que le calcul a ete eectue ici en precisementnetapes, c'est-a-dire qu'il a necessitendivisions euclidiennes.)

Voici donc la demonstration du theoreme de Lame.

D

emonstration :Soit deux naturelsaetb, aveca > b, dont lepgcdrja ete trouve1. Le texte de Lame ne parle pas de

nombres de Fibonacci, tournure qui n'est devenue l'expression consacree que plus tard auxixesiecle, sous l'in uence d'Edouard Lucas (1842{1891). via l'algorithme d'Euclide a l'aide dej+ 1 divisions euclidiennes : a=q1b+r10< r1< b b=q2r1+r20< r2< r1 r

1=q3r2+r30< r3< r2...

r j2=qjrj1+rj0< rj< rj1 r j1=qj+1rj: Observons tout d'abord que tous les nombres intervenant dans ce calcul sont des naturels non nuls. On a donc en particulier que tous les quotients satisfontqi1. De plusqj+1>1, car sinon on auraitrj1=rj, ce qui contredirait la derniere condition 0< rj< rj1. En remontant la cha^ne de divisions euclidiennes, de bas en haut, on trouve alors r j1 = 1 =F2 r j1=qj+1rj21 = 2 =F3 r j2=qjrj1+rj12 + 1 = 3 =F4 r j3=qj1rj2+rj113 + 2 = 5 =F5 r j4=qj2rj3+rj215 + 3 = 8 =F6... b=q2r1+r21Fj+1+Fj=Fj+2: Autrement dit, pour qu'il y ait euj+1 divisions dans l'application de l'algorithme euclidien, il faut que bFj+2;() oubest le plus petit des deux nombres dont on cherche lepgcd. (C'est par le biais de cette inegalite que les nombres de Fibonacci jouent ici le r^ole de barometres dont je parlais plus haut.) Nous proposons maintenant deux facons (en soi essentiellement equivalentes) de conclure la demonstration du theoreme de Lame a partir de cette derniere inegalite. Variante 1 :Cette premiere preuve repose sur le resultat preliminaire suivant : F n+5>10Fnpourn2:() On verie facilement que cette inegalite est veriee pourn= 2. Par ailleurs, pourn3, on a F n+5=Fn+4+Fn+3 = 2Fn+3+Fn+2 = 3Fn+2+ 2Fn+1 = 5Fn+1+ 3Fn = 8Fn+ 5Fn1: De plus, la suite de Fibonacci n'etant pas decroissante, on aFn=Fn1+Fn22Fn1, d'ou l'on tire 2Fn4Fn1. Il s'ensuit alorsFn+5= 8Fn+ 5Fn1>8Fn+ 4Fn110Fn, et doncFn+5>10Fn, tel que demande. 2 L'inegalite () nous dit donc que pourn2,Fn+5a au moins un chire de plus que F ndans sa representation decimale. On peut alors en degager une borne sur le nombre de chires des nombres de Fibonacci, lorsqu'ecrits en base dix, en egrenant ceux-ci par tranches de cinq. Partant du fait que pour 2n6,Fnest un nombre a un chire, on en tire que pour 5 + 1< n25 + 1,Fns'ecrit avec au moins 2 chires pour 25 + 1< n35 + 1,Fns'ecrit avec au moins 3 chires pour 35 + 1< n45 + 1,Fns'ecrit avec au moins 4 chires... pourk5 + 1< n(k+ 1)5 + 1,Fns'ecrit avec au moins (k+ 1) chires. Soit maintenantk, le nombre de chires dans le developpement decimal deb. On a donc b <10k, et il faut montrer, pour conclure la preuve du theoreme de Lame, quej+ 15k, ou, rappelons-le,j+ 1 est le nombre d'etapes dans l'application de l'algorithme d'Euclide a aetb(aveca > b). Supposons au contraire quej+1>5k. On a doncj+2>5k+1, d'ou il suit, par les considerations precedentes sur le nombre de chires des nombres de Fibonacci ecrits en base dix, queFj+2s'ecrit avec au moins (k+ 1) chires. Or par l'inegalite (), il en serait de m^eme pourb, ce qui contredit le fait queba precisementkchires dans son

ecriture decimale.Variante 2 :Voici une autre facon de conclure la demonstration du theoreme de Lame.

Elle utilise le fait bien connu que lenenombre de Fibonacci satisfait l'inegalite F nn2;() ou=1+p5 2 designe lenombre d'or, solution de l'equation2=+ 1.2 Combinant les inegalites () et (), on en tire quebFj+2j. Comme on s'interesse au nombre de chires decimaux deb, il est naturel de passer au logarithme base dix. On a donc log

10bjlog10. Or on peut se convaincre facilement du fait3que log10 >15

, de sorte que log

10b >j5

Soit maintenantk, le nombre de chires dans le developpement decimal deb. On a alors b <10k, donc log10b < k. On en conclut quej5 < k, donc quej <5ket enn,jetketant

des entiers,j+ 15k, ce qu'il fallait demontrer.Le theoreme de Lame arme donc que l'algorithme d'Euclide applique a des entiersaet

b(a > b) arr^ete apresO(log10b) divisions euclidiennes. Pas mal ecace, somme toute!2. L'inegalite () se verie aisement par recurrence. Elle est immediatement vraie pourn= 1 et 2.

SupposantFk1k3etFk2k4, on a alorsFk=Fk1+Fk2k3+k4= (+ 1)k4=

2k4=k2.

3. L'inegalite log

10 >15

peut se verier par une simple evaluation numerique, car log100,208987. On peut aussi justier cette inegalite en bornant log

10de la maniere suivante :

1 +p5 2 5

5 +p125

10 5 >5 + 1110 5 =16510

5=1024210

5>1000210

5= 10:

Le resultat suit en prenant le log

10des expressions extr^emes. Je remercie mon collegue Jeremie Rostand de

m'avoir propose cette astucieuse minoration. 3quotesdbs_dbs33.pdfusesText_39

[PDF] leviers de mobilisation

[PDF] différence entre motivation et mobilisation

[PDF] plan daction mobilisation du personnel

[PDF] mobilisation du personnel définition

[PDF] suite fibonacci

[PDF] mobilisation des employés définition

[PDF] trouver les racines d'un polynome de degré 2

[PDF] polynome degré n

[PDF] définition de la mobilisation

[PDF] factoriser un polynome de degré n

[PDF] polynome degré 2

[PDF] phyllotaxie spiralée

[PDF] définition société civile organisée

[PDF] comment expliquer l'abstention électorale

[PDF] mobilisation des civils première guerre mondiale