`:
`;
`!
`?
 
    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):
  
  - 
    
i:=1;
tant que i<n faire
   i:=i*10
fintantque;
   
  
  
  - 
    
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;
   
  
  
  - 
    
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