[PDF] Chapitre 8 : algorithmes et arithmétique 1 Autour de la division

View - Download Chapitre 8 : algorithmes et arithmétique 1 Autour de la division

Previous PDF

Next PDF

Chapitre 8 : algorithmes et arithmetique

1 Autour de la division euclidienne

1.1 Apprentissage de l'analyse d'un algorithme : division euclidienne

a)Une remarque vue depuis le chap. 2, mais revue notamment lors du C.R. du T.P. 6 sur la dichotomie :une des dicultes de lecture d'un algorithme en informatique par rapport aux mathematiques est qu'au cours du deroulement d'un algorithme, une variable peut ^etre reaectee et prendre successivement dierentes valeurs. En info., on peut penser a lavariablecomme a uncontenantet ala valeurcommeun contenu. Cette diculte est aussi un avantage en terme de concision... quand on a bien compris... comme on espere le montrer ci-dessous. b)Un algorithme pour obtenir le reste de la division euclidienneOn se donne deux entiersaetbavecb>0. Le resultat de la division euclidienne est le couple(q;r)tel que seulementdeux variables informatiquesaetb. Au depart dansaetb, il y a les valeursaet bpour lesquelles on veut calculer la division euclidienne, mais l'algorithme modie la valeur de la variable informatiqueaet on va montrer qu'a la n, dansail y a le resterque l'on cherche. Voici l'algo. ecrit enPythonou les valeurs deaetbseront donc rentrees comme argumentsd'une fonction appeleereste,volontairement non documentee: def reste(a,b): while (a<0) or (a>=b): if a<0: a=a+b if a>=b: a=a-b return a Comment juger de la validite de cet algorithme? Deux problemes bien distincts : ?terminaison: on doit ^etre s^ur que l'algorithme s'arr^ete au bout d'un nombre ni d'etapes, ?correction de l'algo.: on doit ^etre s^ur que l'algorithme fait ce qu'on veut, donc ici que la valeur renvoyee est bien celle du reste. c)Le probleme de la terminaison : Pour etudier l'algorithme on notea0=a, etakla valeur de la variable informatiqueaapres lak-ieme etape. (M1) ici :on se place dans chacun des deux cas desifet on fait une analyse semblable a celle de la dem. mathematique. ?Sia0=a≥b, alorsa1=a0-bet si on prendkle maximum des entiers tels quea0-kb≥b alorsa0-(k+1)b=b): if r<0: r=r+b q=q-1 if r>=b: r=r-b q=q+1 return q,r Comme dans l'algo. precedent, la var.bn'est pas modiee, et garde toujours la valeur initiale b,anon plus, alors querprend comme valeur nale la valeur du reste comme on l' a montre plus haut. La variable localeqest initialisee a 0 et a la n la fonction retourne la valeur nale deqdont on va montrer que c'est la valeurqdu quotient de la division euclidienne deapar b. Ici la valeur debq+rest un invariant de la bouclewhile En eet : a chaque etape on transformebq+renb(q-1)+(r+b)ou bien enb(q+1)+(r-b). Quel inter^et d'un tel invariant?A l'initialisation l'egalitebq+r==aest vraie avec les valeurs :b×0+a=a. Donc a l'arr^et de l'algorithme, commeaetbn'ont pas change de valeur et comme on a deja vu qu'a la n de l'algo.rcontenait bien la valeur voulue pour le reste de la div. euclidienne, la variableqcontient bien la valeurqtelle quea=bq+r.

1.2 L'algorithme d'Euclide pour le p.g.c.d.

a)Description mathematique(donnee dans le cours de maths, on change legerement l'in- dexation pour plus de commodite) : on se donne deux nombres(a;b)et on denit une suite nie strictement decroissante d'entiers naturels(rk)k?⟦0;N⟧parr0=a,r1=bet pour tout k≥1, tant querk≠0, on denitrk+1comme le reste de la division euclidienne derk-1par r k. La terminaison de l'algorithme est claire :la suite(rk)est une suite d'entiers naturels strictement decroissante jusqu'a 0. Par def.rNest ledernier reste non nul b)Algorithme informatique : Maths :La suite(rk)est une suite rec. d'ordre 2 :rk+1est deni a partir derketrk-1. Traduction en info. :on a besoin d'une boucle qui modiedeux variables. EnPythonen utilisant l'operateur%pour le reste de la div. eucl. : 2 def Euclide(a,b): b=abs(b)# pour se ramener a un b positif, ce qui ne change pas le pgcd while b>0: a,b=b,a%b return a Remarque :Dans un langage qui ne permet pas l'aectation en couple, on aura besoin d'une variable locale tampon pour faire l'echange. c)La correction de l'algorithme :pourquoi l'algo. renvoie-t-il pgcd(a,b)? La justication a ete donnee en cours de maths, et en fait, sans le dire, on a introduit un : Invariant de boucle : a chaque etape de la boucle le pgcd(a,b)est inchange. Au depart il vaut pgcd(a;b)et a la n, en notation maths, il vaut pgcd(rN-1;rN)avecrN=0 doncrN-1. Rappel :pour tout entier, pgcd(;0)=. Dans le cours de maths, ceci est donne par la def. du pgcd. avec des sous-groupesZ+0Z=Z.

1.3 La version soustractive de l'algorithme d'Euclide

Considerons l'algorithme implemente dans la fonctionPythonsuivante : def EuclideS(a,b): """calcul du pgcd par la methode des soustractions successives""" a=abs(a) b=abs(b) while (a!=0) and (b!=0): if a<=b: b=b-a if b1.4 L'algorithme d'Euclide etendu : obtention d'une relation de Bezout

On se donne encore(a;b)?(N?)2.

a) On a vu en cours comment obtenir des coecients d'une identiteau+bv=doud=a?b, en remontantles egalites de l'algorithme d'Euclide. L'algorithme suivant permetsimultanement de calculer le pgcdd=a?betun couple(u;v)tel queau+bv=d. b)Mathematiquement :On denit des suites qui vont toutes ^etre nies(rk),(qk),(uk)et (vk)recurrentes d'ordre deux, (saufqk) comme suit : ?Initialisation (double sauf pourqk) :⎧⎪⎪⎨⎪⎪⎩r

0=a; q0=0; u0=1; v0=0;

r

1=b;u1=0;v1=1:

?Formule de recurrence :pour toutk≥1,tant querk≠0 i)(qk;rk+1)est le couple quotient-reste de la division euclidienne derk-1parrk, ii)uk+1=uk-1-ukqk, etvk+1=vk-1-vkqk. c)Terminaison de l'algorithme :L'algorithme precedent≪contient≫l'algo. d'Euclide du

1.2 et a la m^eme condition d'arr^et donc il s'arr^ete.

d)Correction :Puisque pour les(qk)et(rk)on a la m^eme def. qu'au 1.2 on sait qu'a l'arr^et de l'algorithme pourrN=0,rN-1=a?b. Examinons les(uk;vk):

Propriete :Pour chaquek,auk+bvk=rk.Demonstration :notonsPk?auk+bvk=rk. Preuve par recurrence double :

?Par l'initialisation au b)P0etP1sont vraies. ?H.R. Supposons que pour unk≥1,PketPk-1sont vraies. Donc par l'H.R.,auk+1+bvk+1=rk-1-qkrketrk-1-qkrk=rk+1par def. derk+1. Ceci prouve P k+1. La rec. est etablie.e)Algorithme informatique et implementation enPython: cf. T.P. 8

1.5 Troisieme facteur d'analyse d'un algorithme : le co^ut

Une fois qu'on a etudie laterminaisonet lacorrectiond'un algorithme, on peut aussi etudier sonco^uti.e. en combien d'etapes il se termine et le nombre d'operationselementairesqu'il necessite. 4

Chapitre 8 : algorithmes et arithmetique (suite)

1.5.1 Premiere approche pour l'algorithme d'Euclide ( notations harmonisees)

Ex. pl. 16 (notations modiees)On considere deux entiers(a;b)?N2, aveca>b, on note a=bq+rla division euclidienne deaparb. On noter0=a,r1=bet on reecrit cette division euclidienner0=r1q1+r2: etape 1 de l'algo. d'Euclide. Pour toutk≥1, tant querk≠0, on noterk+1le reste de la division euclidienne derk-1parrk, qu'on ecritrk-1=qkrk+rk+1. On note, comme dans le cours,rNle dernier reste non nul, de sorte que la derniere etape de l'algorithme d'Euclide s'ecrit :rN-1=qNrN+0. Avec ces notations l'algorithme a exactementNetapes (numerotees par lesqi). abet que pour toutk, r rkrk-1. Autrement dit, le produit \dividende-diviseur" est au moins divise par2a chaque etape de l'algo. d'Euclide b) En deduire que le nombreNd'etapes de l'algorithme d'Euclide applique aaetbest majore par log

2(a)+log2(b).

Solution de l'exercice

abi.e. queab≥2bri.e. que a≥2rbon, au travail! Par def. de la division euclidienne, on aa=bq+ravecr2(10300)=600log2(10)<2000.

Remarquons aussi que log

2(a)est moins que le nombre de chires deadans l'ecriture en base

2, donc que l'algo. d'Euclide ne prend pas plus d'iterations que le nombre de bits necessaires pour

ecrireaetben base deux.

1.5.2 Etude plus ne du nombre maximum d'operations dans l'algorithme d'Euclide :

a)Notation :Soit(a;b)?N2, on noteraC(a;b)le nombre d'operations i.e. de divisions euclidiennes, dans l'algorithme d'Euclide applique aaetb. En langage algorithmique,

le nombreC(a;b)s'appelle leco^utou lacomplexitede l'algorithme d'Euclide.Exemple :Sib?aalors l'algorithme d'Euclide nit en une division euclidienne etC(a;b)=1.

5 b)Le cas de la suite de Fibonacci :On denit une suite recurrente d'ordre 2 notee(Fn)n?N comme suit :F0=0,F1=1 et?n?N≥1,Fn+1=Fn+Fn-1.

Calculons d'abord les premieres valeurs desFn:

La suite de Fibonacci a les proprietes suivantes : i)F0=0,F1=1,F2=1, mais(Fn)n≥2eststrictement croissante ii) on en deduit que pour toutn≥3, l'egaliteFn+1=Fn+Fn-1est l'egalite de division euclidienne deFn+1parFnavec quotient 1 et resteFn-1. iii) On en deduit aussi que pourn≥2, le co^utC(Fn+1;Fn)de l'algorithme d'Euclide applique aFn+1;Fnverie :

C(Fn+1;Fn)=n-1

c)La suite de Fibonacci est≪le pire cas≫pour le co^ut de l'algo. d'Euclide :(i) Theoreme (Lame, 1847)Soit(a;b)?(N?)2aveca>bet notonsC(a;b)le co^ut de

l'algorithme d'Euclide applique aaetb. Alors siC(a;b)=k?N?, on aa≥Fk+2etb≥Fk+1.(ii) En renversant le point de vue : Le co^utC(a;b)de l'algorithme d'Euclide applique a deux

Dans le cas ouaetbsont donc deux termes successifs de la suite de Fibonacci, cette majo- ration est bien s^ur uneegalite.

C'est en ce sens que l'on peut dire que

≪le pire cas≫de l'algorithme d'Euclide est celui applique a deux termes successifsa=Fk+2etb=Fk+1de la suite de Fibonacci. d)Une formule explicite pour lesFn: On va montrer (gr^ace au cours sur les espaces vectoriels) que si on note'=1+⎷5 2 (appele nombre d'or) et =1-⎷5 2 =-1' , on a la formule explicite suivante :?n?N;Fn='n- n⎷5 n≥1 : n⎷5 -12 +12 Parfois on se contente d'exprimer ce resultat(†)sous la formemoins precised'un equivalent : F n≂n→+∞' n⎷5

Question :Pourquoi est-ce moins precis?

Remarque :En fait, ici,Fnest exactementl'entier le plus prochede'n⎷5 des quen≥2. e)Application au co^ut dans le pire cas de l'algorithme d'Euclide : Soient(a;b)?(N?)2aveca>b. Soitk=C(a;b)le co^ut de l'algorithme d'Euclide applique a aetb. (i) Avec le c) et le d), on obtient une majoration (a peu pres optimale) dek: Ceci donne, en n'utilisant que(1)une inegalite un peu compliquee, certes precises, mais qu'on n'utilisera pas beaucoup! 6 (ii) Exercice : verier qu'on a par exemple l'inegalite plus simple : ln(b)+1 (iii)Remarque :par rapport au travail du 1.5.1, on a une majoration indep. dea, seulementquotesdbs_dbs35.pdfusesText_40

[PDF] quel est le plus grand multiple de 46 inferieur a 300

[PDF] divisibilité par 25

[PDF] un nombre entier est divisible par 5 si

[PDF] soustraction a trou

[PDF] multiplication a trou ce2

[PDF] division a trou methode

[PDF] additions ? trous cm1

[PDF] addition a trou ce2

[PDF] division avec diviseur ? virgule

[PDF] division dun nombre décimal par un nombre entier

[PDF] regle division a virgule

[PDF] division nombres décimaux cm2 exercices

[PDF] division a virgule exercice

[PDF] multiplication et division de fraction 4eme controle

[PDF] 9-3÷1/3+1 reponse