[PDF] Chapitre 8 : Eléments dalgorithmique illustrations arithmétiques 1

View - Download Chapitre 8 : Eléments dalgorithmique illustrations arithmétiques 1

Previous PDF

Next PDF

Chapitre 8 : Elements d'algorithmique, illustrations arithmetiques

1 Terminaison et correction : exemples sur les algorithmes

arithmetiques

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

a)Remarque :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 la variablecomme a uncontenantet ala valeurcommeun contenu. Convention :Dans ces notes, on noteraxun nom de variable informatique etxlavaleur (ouxkles valeurs successives) stockee(s) dans la variable qui s'appellex. 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 commearguments d'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, ician'est pas modiee non plus, alors que la variable localerprend 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 deaparb. 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 se donne deux nombres (a;b)et on denit une suite nie strictement decroissante d'entiers naturels(rk)k?⟦0;N⟧par r

0=a,r1=bet pour toutk≥1, tant querk≠0, on denitrk+1comme le reste de la division

euclidienne derk-1parrk. 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 : 2 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. : 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;0)avecrNle dernier reste non nul.

Rappel :pour tout entier, pgcd(;0)=.

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 : cf. T.P

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. N.B.Le≪pourquoi≫de cette def. par rec. a ete vu en T.P. 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 enPython: cf. T.P.

2 Introduction aux problemes de co^ut d'algorithme : com-

plexite 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.

2.1 Sur l'exemple de l'algorithme d'Euclide

Exercice a faire :On considere deux entiers(a;b)?N2, aveca>b, on notea=bq+rla division euclidienne deaparb. On noter0=a,r1=bet on reecrit cette division euclidienne r

0=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)+1.

4

2.2 Exemple de l'exponentiation :

2.2.1 Le co^ut de l'exponentiation

≪usuelle≫ Ecrire une fonctionexpo(a,n)qui renvoie la valeur dea??nqui n'utilise que des multiplications.

Combien de multiplications necessite-t-elle?

2.2.2 Le co^ut de l'exponentiation rapide

Normalement≫, prendre un nombrexa la puissanceN, c'est faireN-1 multiplications. En T.P. on a etudie et implemente l'algorithme d'exponentiation rapide qui permet de reduire ce nombre de multiplications a au plus 2noun+1 est le nombre de chires de l'ecriture deNen base 2. Autrement ditce nombre de multiplications est majore parklog(N)oukest une constante.

2.3 Exemple de l'evaluation d'un polyn^ome :

On code un polyn^omePpar la liste[an;:::;a0]de ses coecients. Ecrire une fonctionevalpoly qui recoitPetxet renvoie la valeurP(x)=n i=0a ixi. Determiner le nombre d'additions et de multiplications faites, essayer d'optimiser!

2.4 Un langage mathematique pour l'etude asymptotique de la com-

plexite

2.4.1 NotationO: (standard en maths et en info.)

a)Denition (maths)Si(un)et(vn)sont deux suites reelles, on dit queun=O(vn)(sous- entendu quandn→+∞) ssi il existe un rangn0?Net une constanteA>0 tels que : Terminologie :Siun=O(vn), on dit que la suite(un)estdomineepar la suite(vn). Remarque :Siun=o(vn)alors a fortioriun=O(vn)mais la recip. est fausse.

D'une maniere generale,sivn≂wnetun=O(vn)alorsun=O(wn).Dans l'exemple precedente, 4n2+120n+14566≂4n2d'ou la conclusionun=O(n2).

b)Inter^et en informatique :Souvent (mais pas toujours!) en informatique, ces constantes (comme le4devant le4n2ci-dessus-) , n'ont pas beaucoup d'inter^et. En eet, comme on le verra deja ci-dessous au§3, une bonne evaluation du co^ut de l'algorithme depend d'autres facteurs (compter les autres instructions du programme par exemple) qui changent les constantes multiplicatives : Avec le langage precedent, on dira que la complexite de l'exponentiation rapide est en O(log(n))alors que l'exponentiation nave est enO(n).

2.4.2 Notation: (standard en info)

a)Des maths encore :La notationO(f(n))ne donne qu'unemajorationa partir d'un certain rang. Par exemple si on prendun=netvn=n2, on a dans les deux casun=O(n3) etvn=O(n3). Pourtant on voit vient que(un)et(vn)ne vont pas a la m^eme vitesse. b)Si on veut ^etre plus precis, avec unencadrement: on suppose que(un)et(vn)sont

des suites positives (A.P.C.R. eventuellement).Denition :Siun=O(vn)etvn=O(un)autrement dit, si on a des constantes

u n=(vn).5 c) Les deux algorithmes vus ci-dessus (Euclide et exponentiation rapide) sont en (log(n)).

3 Tests de primalite, diviseurs : comparaisons, complexite

3.1 Le test le plus basique pour la primalite :

a) La fonction suivante permet certainement de savoir si un nombrenest premier, en testant le reste de la division euclidienne denpar tous les entiersiinferieurs an, jusqu'au premier diviseur den. def premier(n): if (n<=1): return False else : i=2 while (iadopterons le modele suivant :Modele a co^ut constant(valable sauf si les nombres deviennent trop grands) : les

aectations, comparaisons, et les operations arithmetiques seront toutes considerees

commeune unite.aa. Oui cela peut para^tre etrange qu'une multiplication ne soit pas comptee plus cher qu'une

addition : cela ne sera plus vrai sur des entiers de typelong(iv) Avec ce modele du (iii), le resultat du (ii) devient :pourkiterations de

l'algorithme le co^ut est de 4k+3. Le probleme est de savoir, pour un entiern, combien l'algorithme fait d'iterations. Claire- ment, le nombre d'iterations de l'algorithme est majore parn. D'ou : c)L'evaluation de la complexite de la fonctionpremier:

Par ce qui precede le co^ut de la fonctionpremierest inferieur ou egal a 4n+3.Donc il est correct de dire que le co^ut est depremierest enO(n).d) La complexitedans le pire casi.e. dans le cas ounest premier sera exactement de 4n+2.

e) Cependant, pour tous les nombresnon premiers, l'algorithme s'arr^etera sur le plus petit diviseur premier den, dont on a vu qu'il est inferieur ou egal a⎷n. Donc la complexitemoyennede l'algorithme sera bien inferieure.... (pour bien l'evaluer, il faudrait conna^tre la proportion de nombres premiers parmi les entiers jusqu'a un certain nombre, nous y reviendrons peut-^etre ...)

Surtout cette remarque permet de penser au :

6

3.2 Test juste un peu moins basique de primalite :

Il sut de penser a s'arr^eter a

⎷n def premier_mieux(n): if (n<=1): return False else : from math import sqrt i=2 while (i<=sqrt(n)) and (n%i!=0): i+=1 if i<=sqrt(n) : return False else : return Truedef premier_mieux(n): if (n<=1): return False else : i=2 while (i*i<=n) and (n%i!=0): i+=1 if i*i<=n : return False

else : return TrueLe raisonnement precedent montre qu'on a un algorithme en (⎷n).En eet, dans le pire

cas, sin=p2avecppremier le nombre de divisions est en eet exactement⎷n.

Sauf qu'on doit se demander ce que co^ute le calcul de⎷n: on verra plus tard qu'il peut se faire

tres rapidement.

3.3 Obtention de tous les diviseurs d'un entiern

a) Considerons la premiere fonction suivante : def diviseurs(n): l=[] for i in range(1,n+1): if n%i==0: l.append(i) return l Quelle est la complexite de cet algorithme en nombre d'operations arithmetiques? b)Exercice :En ranant l'idee du§3.2, on peut fabriquer un algorithme enO(⎷n)donnant le m^eme resultat. Comment? 7 Complements de preuves et solutions pour le chap. 8

2.1 Retour sur l'exemple de l'algorithme d'Euclide

abet que pour toutk, abi.e. queab≥2bri.e. quea≥2r bon, au travail! Par def. de la division euclidienne, on aa=bq+ravecr2(a)+log2(b)Remarque :Au brouillon : que veut-on montrer? SiNest le nombre d'etapes de l'algorithme, Avec la notation(rk)introduite ci-dessus pour les restes successifs de l'algo. d'Euclide, on a par a) : r r1r0. kr1r0=ab2 k. N-1 Ensuite, il est tres utile de penser qu'un entier positif non nul m veriem≥1 N-1. est inferieur a 2log

2(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.

2.2.2 Theoreme de Lame et consequences

b) Preuve des prop. de la suite de Fibonacci :

(iii)Montrons que?n≥2,C(Fn+1;Fn)=n-1.Preuve par recurrence :?Pourn=2, l'algo. d'Euclide applique aF3etF2a une seule etape :

F

3=2=2F2+0.?H.R. on supposeC(Fn+1;Fn)=n-1. On considere l'algo. d'Euclide applique a

F n+2;Fn+1. Sa premiere etape estFn+2=Fn+1+Fn. Les etapes suivantes consistent exactement a

faire l'algo. d'Euclide pourFn+1;Fn: donc par H.R. il y en an-1.c) (i) Preuve du theoreme de Lame :Soit(a;b)comme dans l'enonce.

?On met a part le cas trivial ouk=1:sik=1 cela signie queb?a. Mais alors l'enonce

arme seulement quea≥F3etb≥F2i.ea≥2 etb≥1, ce qui est evident avec l'hyp.a>b≥1.

8 ?On suppose desormaisk≥2. On considere la suite des restes dans l'algorithme d'Euclide applique aaetb:r0=a;r1=b>r2>???>rN>rN+1=0. Cette suite est strictement decroissante et?i?⟦1;N⟧,ri-1=qiri+ri+1(1)egalite dansN.

On en deduit :?i?⟦1;N⟧,qi≥1(2).

En eet,pour touti,qiest un entier positif, et sipar l'absurdeqi=0 pour uni?⟦1;N⟧alors (1)devientri-1=ri+1ce qui est unecontradictionavec la stricte decroissance. D'ou (2).

Avec(2)et(1), on obtient?i?⟦1;N⟧; ri-1≥ri+ri+1(3).Idee :Ainsi, la suite(ri)verie une relation de typeFibonacci(la relation(3)) a part qu'on

a une inegalite au lieu d'une egalite, et que la relation va dans le sens desidecroissants. On part

donc derN≥1et on va comparer successivement les indicesrN-iauxFi.Notons maintenantP(i)?rN-i≥Fi+2.

Montrons, gr^ace a(3), par recurrence nie queP(i)est vraie pour touti?⟦0;N⟧.Il s'agit en fait d'une recurrence d'ordre deux :

?Initialisation (double) : pouri=0,rNetant le dernier reste non nul, on arN≥1=F2. Pour i=1,rN-1>rNdoncrN-1≥2=F3. DoncP(0)etP(1)sont vraies. ?H.R. : on suppose queP(i-1)etP(i)sont vraies pour uni?⟦1;N-1⟧. Montrons queP(i+1) est vraie.

On a doncrN-i≥Fi+2etrN-(i-1)≥Fi+1. Et par l'ineg. (3) on sait querN-(i+1)≥rN-i+rN-(i-1)

La recurrence est etablie.Solution de l'exercice du§3.3 a) L'algorithme est bien s^ur enO(n): il fait exactementndivisions, etn+1 aectations.

b) L'idee est que si on conna^t tous les diviseurskdendans⟦1;⌊⎷n⌋⟧, on peut trouver tous

les autres sous la formen?k. def diviseurbis(n): l=[]quotesdbs_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