`: `; `! `?  


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.

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.

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

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;

  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;

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

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


File translated from TEX by TTH, version 3.05.
On 13 Dec 2005, 13:27.

symboles bricolés pour netscape par sed