Année 2004-2005 Session de Juin 2005

GU : Licence Sciences Technologies (semestre 5) UE : INF209 Épreuve de : Algorithmique Avancée Date : 15 juin 2005 Durée : 3h

Documents autorisés

Épreuve de Monsieur Robson

1 [5 points]

Je veux calculer A^{n}, c’est-à-dire la n-ème puissance d’une matrice (de taille m × m) A; je dispose d’une procédure Matmult(X, Y, Z) qui calcule en Z le produit des deux matrices X et Y. Au lieu de faire n − 1 multiplications, je veux utiliser le fait que A^{n} pour n > 1 est soit le produit de A^{n/2} avec lui-même (quand n est pair), soit le produit de A^{n−1} avec A (à utiliser quand n est impair.)

Ecrire une procédure récursive P uissance(A, n, B) qui effectue ce calcul.

réponse

procédure Puissance(val AA:matrice; val n:entier; ref B:matrice);
/* "AA" parce que "A" est un mot réservé d'Exalgo!*/
/* n>=1 */
var C:matrice;
debut
   si n=1 alors
      pour i allant de 1 à m par pas de 1 faire
         pour j allant de 1 à m par pas de 1 faire
            B[i][j]:=AA[i][j]
         finpour
      finpour
   sinon
      Puissance(AA,n/2,C); /*n/2 arrondi vers le bas*/
      Matmult(C,C,B);
      si n mod 2 > 0
         alors
         Matmult(AA,B,B)
      finsi
   finsi
finprocédure;

2 [4 points]

Je peux calculer le nombre de formes possibles d’un arbre binaire de n sommets, en utilisant la récurrence Arb(n) = ∑_{g=0}^{n−1} Arb(g) ∗ Arb(n − 1 − g) (où g est la taille du sous-arbre gauche et n − 1 − g celle de celui de droite) ; avec la condition Arb(0) = 1.

Expliquer comment la programmation dynamique permet de faire ce calcul de façon beaucoup plus efficace qu’une fonction récursive appliquant directement la récurrence.

Réponse En calculant une seule fois et stockant dans un tableau les valeurs de Arb(i) (en ordre croissant de i) :

Tab[0]:=1;
pour i allant de 1 à max par pas de 1 faire
   somme:=0;

1/3

   pour g allant de 0 à n-1 par pas de 1 faire
      somme:=somme+Tab[g]*Tab[n-1-g]
   finpour;
   Tab[i]:=somme
finpour;

le temps de calcul sera quadratique au lieu de (au moins) exponentiel.

3 [4 points]

le code qui suit est censé déterminer si le nombre positif n est premier (c’est-à-dire qu’il n’existe pas de facteur f de n tel que 2 ≤ f < n.)

Proposer un invariant qui pourrait être utilisé pour démontrer que la boucle est correcte.

f:=2;
tant que f < n et (n/f)*f < n faire // f n'est pas facteur de n
   f:=f+1
fintantque;
// n est premier si (et seulement si) f=n

Réponse (f ≥ 2 ou n = 1) et f ≤ n et n n’a pas de facteur en [2..f − 1]

4 [3 points]

Donner le temps de calcul des boucles qui suivent en termes de O(fonction de n) :

  1. i:=1;
     tant que i<n faire
        i:=i*10
     fintantque;

Réponse O(log n)

  2. pour i allant de 1 à n faire
        pour j allant de i à n faire
           pour k allant de i à j faire
              x:=x+1;
           finpour
        finpour
     finpour;

Réponse O(n^{3})

  3. j:=1;
     pour i allant de 1 à n faire
        tant que j<i faire
           j:=j*2
        fintantque
     finpour;

Réponse O(n) (j multiplié par 2 au plus une fois par itération de la boucle pour)

5 [4 points]

le type listep est un pointeur vers une structure qui contient un entier (premier) et un pointeur du même type vers le prochain elément (reste) ; la liste vide est représentée par le pointeur NULL. On suppose que deux variables de ce type A et B pointent, toutes les deux vers des listes où les entiers sont triés en ordre strictement croissant. Ecrire des instructions pour décider si c’est le cas que tous les entiers de A sont aussi présents en B. (Une solution correcte et efficace est souhaitée.) Réponse

2/3

tantque AA != NULL faire
selonque
cas B=NULL: retourne faux;
cas B^.premier<AA^.premier: B:=B^.prochain;
cas B^.premier=AA^.premier: AA:=AA^.prochain;B:=B^.prochain;
autrement: retourne faux
finselonque
fintantque;
retourne vrai;

3/3