Chapitre 2  Exemples d’algorithmes itératifs et récursifs

Dans ce chapitre on va mettre l’accent sur l’écriture des algorithmes et leur justification (l’algorithme se termine et produit le bon résultat).

2.1  Deux versions de l’algorithme d’Euclide

Proposition 1   Soient: a∈ℤ, b∈ℤ. On a pour tout m∈ ℤ:
PGCD(a,b)=PGCD(b,a−mb) .

On peut en particulier appliquer la proposition précédente au cas où m=q est le quotient dans la division euclidienne de a par b.

[H] Deux entiers relatifs: a,b  Un entier pgcd de a et b  Fonction PGCD(a, b);
r← a mod b (reste de la division euclidienne);
r est nul b  PGCD(b,r)  Euclide, forme récursive [H] Deux entiers relatifs: a,b  Un entier pgcd de a et b  Fonction PGCD(a, b);
b est non nulr← a mod b (reste de la division euclidienne);
a← b;b← r  a  Euclide, forme impérative ou itérative On dispose aussi d’une variante binaire de cet algorithme, qui permet d’éviter les divisions en les remplaçant par des opérations de décalage.

[H] Deux entiers: a,b avec b≥ 3 impair et a>0  Un entier pgcd de a et b  Fonction PGCD(a, b);
a≠ b a paira← a/2; (On pourra utiliser le décalage binaire)  a>ba← a−b/2  r ← b−a/2
b← a; a← r  a  Euclide, version binaire impérative
Exercice 2   Améliorer l’algorithme binaire au cas b>0 de parité quelconque.

2.2  Algorithme d’Euclide étendu aux coefficients de Bezout

Proposition 1   Soient: a∈ℤ, b∈ℤ, d=PGCD(a,b). Il existe deux entiers u et v tels que d=ua+vb.

[H] Euclide étendu : version impérative 2 entiers a et b Une liste de 3 entiers: (u,v,d) tels que a.u+v.b=d Fonction Bezout(a, b)  A← (1,0,a); //On notera Ai le iieme opérande de la liste A   B← (0,1,b); //On notera Bi le iieme opérande de la liste B   reste← b 

reste≠0 q← le quotient de A3 par reste  temp ← A−q× B  A← B  B← temp  reste← B3 

A

Exercice 2   Programmez cet algorithme en Python et sous Xcas, en utilisant des listes. Affichez le nombre de tours effectués.

La version récursive sous xcas avec la syntaxe de type algorithmique: 

fonction bezoutr(a,b)
  //renvoie la liste [u,v,d] telle que a*u+b*v=d=pgcd(a,b) (fct recursive)
  local lb,q,r;
  si (b!=0) alors
    // pour des polynomes il suffit de remplacer
    //  iquo par quo et irem par rem
    q:=iquo(a,b);
    r:=irem(a,b);
    lb:=bezoutr(b,r);
    retourne([lb[1],lb[0]+(-q)*lb[1],lb[2]]);
  sinon 
    retourne([1,0,a]);
  fsi;  
ffonction;


exemple:

ou avec la syntaxe traditionnelle (cf le menu exemples d’xcas): 

  bezoutr(a,b):={
  //renvoie la liste [u,v,d] telle que a*u+b*v=d=pgcd(a,b) (fct recursive)
  local lb,q,r;
  if (b!=0) {
    q:=iquo(a,b);
    r:=irem(a,b);
    lb:=bezoutr(b,r);
    return([lb[1],lb[0]+(-q)*lb[1],lb[2]]);
  }
  else 
    return([1,0,a]);// lorsqu'il n'y a qu'une ligne, pas besoin des {}
}:;//  le :; permet de ne pas afficher le programme apres l'avoir valid\'e


exemple:

Proposition 3   On considère deux entiers a,b et l’on pose: r0=a et r1=b. On définit par récurrence tant que ri est non nul: ri+1=ri−1−qi.ri où qi est le quotient de la division Euclidienne de ri−1 par ri. 0n pose u0=1, u1=0 et v0=0, v1=1. Alors les suites (ui,vi) définies par
ui+1=ui−1−qi.ui  et  vi+1=vi−1−qi.vi
tant que ri est non nul, vérifient la relation suivante:
ui.a+vi.b=ri 
pour toute les valeurs de i où elles sont définies.
Exercice 4   Notons N le nombre d’itérations de l’algorithme d’Euclide. Alors les suites (ui)N≥ i≥ 1 et (vi)N≥ i≥ 1 sont de signe alterné et (|ui|)N≥ i≥ 1 et (|vi|)N≥ i≥ 1 sont croissantes

2.3  Exemples de coûts

Division euclidienne pour les entiers positifs

Théorème 1   Pour a∈ ℕ, b∈ ℕ*, il existe un unique couple d’entiers (q,r) avec a=bq+r et 0≤ r<b.

2.3.1  Méthode naïve:

[H] a≥ 0 et b>0; q← 0; r← a  r>b r← r−b  q← q+1  q et r  Division euclidienne, méthode naïve Le nombre de boucle de cet algorithme est q; à chaque étape il y a une soustraction et une comparaison ; pour b fixé la complexité croît linéairement avec a.

Remarque 2   Si on mesure la taille de l’entier a par le nombre de chiffres de son développement en binaire: t=log2(a), alors la complexité croît exponentiellement avec la taille de a.

2.3.2  Recherche dichotomique

[H] a≥ 0 et b>0; Le quotient et le reste de la division de a par b n← 0;
2nb≤ a n← n+1  α← 2n−1;β← 2n;
k de 1 jusque n−1 γ=α+β/2  γ b≤ a α←γ; β ←γ; q=α et r=a−bq; Division euclidienne, recherche dichotomique

Exercice 3   Comparez avec la méthode que vous utilisez à la main.

2.3.3  Puissance rapide

Proposition 4   Soit (G,*) un groupe commutatif dont on note la loi multiplicativement. On peut calculer an en O(log(n)) opérations *.
Remarque 5   On distinguera deux situations assez différentes selon que le coût de x*y est indépendant des éléments x,y de G ou pas. Donnez 2 exemples de G dans chaque situation.

[H] Un élément g de G et un naturel n. Un élément de G: gn Fonction puiss(g, n);
u← 1; v ← g; //u,v: 2 variables locales   n>1 n pairv← v*v; n← n/2  u ← u*v; v← v*v; n ← (n−1)/2  u*v  Puissance rapide.

Exercice 6   Comparez cet algorithme avec un algorithme de recherche de l’écriture en base 2 de n.

2.3.4  Sujet 0: Première épreuve d’amissibilité

Pour n ∈ ℕ tel que n > 1, on note In l’ensemble des éléments inversibles de l’anneau (ℤ/nℤ, +, ×).

…

5. Pour les algorithmes demandés, on utilisera uniquement les opérations ×, +, ^ et la fonction de deux variables reste où reste(a,b) donne le reste de la division euclidienne de a par b pour a ∈ ℕ et b ∈ ℕ* . On pourra également utiliser des boucles de type

On précisera le logiciel de calcul formel ou le modèle de calculatrice utilisé.

5.1. Écrire une procédure Test( , ) ayant comme arguments deux entiers naturels k et n avec n > 1 affichant “1” si k ∈ In et “0” sinon.

5.2. Écrire une procédure Card( ) ayant comme argument un entier n avec n > 1 affichant le cardinal de In .

5.3. Écrire une procédure Ord( , ) ayant comme arguments deux entiers naturels k et n avec n > 1 affichant la valeur de ω(k) , l’ordre de k dans (In , ×), si k ∈ In et "Erreur" sinon.

TP02



Exercice I:

1) -11ex

a) Programmez l’algorithme du pgcd récursif en python. (on créera une fonction gcd en python.

b) Mettez aussi dans votre fichier des valeurs assez grandes d’entiers et testez votre fonction. Vérifiez vos résultats avec xcas. (Trouvez la bonne commande dans les menus déroulants)

2) -11ex

a) Créez en python une fonction bezout selon l’algorithme de bezout itératif.

b) Dans xcas, trouvez l’instruction correspondante déjà implémentée, et vérifiez votre programme.



Exercice II:

1) En étudiant/testant le corrigé de l’exercice VI du TP01 (tp01-QQ.py), créez une classe ZN dont les éléments seront initialisés et affichés comme dans l’exemple ci dessous:

(python)
>>> m=ZN(13,7) >>> m 'Classe de 13 modulo 7'

2) Ajoutez à votre classe une méthode __eq__ pour comparer ZN(a,b) et ZN(c,d) de la facon suivante: retour True si b=d et a et c sont congrus modulo b, sinon __eq__ doit retourner False

3) -11ex

a) Ajoutez a votre classe les méthodes __add__ et __mul__ pour définir la structure d’anneau de ℤ/nℤ. (On simplifiera le représentant)

4) Définir une méthode __truediv__ pour la division (__div__ si l’on est en Python2). On retournera None si cette division est impossible.

5) Vérifiez vos résultats avec xcas.



Exercice III:

Etudiez le sujet 0.

1) -11ex

a) Programmez rapidement les questions 5.1 et 5.2. méthode naive pour 5.2.

b) Si n est un produit de 2 nombres premiers, que vaut le cardinal de In? Quel est le nombre de tours de votre méthode?

c) Quel est le nom mathématique de cette fonction? Quelle est l’instruction xcas correspondant à cette fonction?

2) Programmez le 5.3 de manière naive.



Exercice IV:

1) Créez en Python une fonction puis(a,n) qui calcule an par puissances rapides.

2) On pose p=1021+117.

a) Vérifiez avec xcas que c’est un nombre premier.

b) Calculez dans ℤ/pℤ les nombres: 5p−1, 5p−1/2, 7p−1/2. Interprétation?



Exercice V:

Programmez en python une fonction qui retourne l’écriture en base 2 d’un entier. (Sous forme d’une liste d’entiers)

Ce document a été traduit de LATEX par HEVEA