Figure


    Année 2004-2005 Session de Juin 2005
   GU : Licence Sciences Technologies (semestre 5) UE : INF209
   Épreuve de : Algorithmique Avancée
   Date :

Durée : 3h
   Documents autorisés
   Épreuve de Monsieur Robson





1
[5 points]
Je veux calculer An, 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 An pour n > 1 est soit le produit de An/2 avec lui-même (quand n est pair), soit le produit de An-1 avec A (à utiliser quand n est impair.)

Ecrire une procédure récursive Puissance(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=0n-1Arb(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;
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(logn)
  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(n3)
  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

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;




File translated from TEX by TTH, version 3.05.
On 14 Dec 2005, 11:15.

symboles bricolés pour netscape par sed