Figure

    Année 2005-2006 Session de PREMI∪RE SESSION 2005-6
   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
[4 points]
Au rugby, on peut gagner 3 points ou 5 points ou 7 points dans un coup. On veut calculer le nombre de façons de gagner 50 points (l'ordre des coups étant important; 3, 5, 7, ... est différent de 7, 5, 3, ...); donner du code (C ou Exalgo) de faire ce calcul

  1. [2 points] par une fonction récursive

  2. [2 points] par programmation dynamique

2
[3 points]
Une liste d'entiers est implémentée par des enregistrements de 2 champs valeur, l'entier et prochain, un pointeur vers le prochain enregistrement (ou NUL dans le dernier); écrire une fonction avec paramètre un pointeur vers le premier enregistrement d'une liste et qui retourne le nombre d'éléments dans la liste qui sont strictement inférieurs à leur prédécesseur immédiat.

3
[5 points]
Quel est (en notation O()) le temps de calcul des boucles: 

  1. pour i allant de 1 à n par pas de 1 faire
   pour j allant de i à n par pas de 1 faire
      /* une opération de temps constante*/
   finpour
finpour;



  2. i:=1;
j:=0;
tantque j<n faire
   i:=i+1;
   j:=j+i
fintantque;



  3. pour i allant de 1 à n par pas de 1 faire
   j:=i;
   tantque j>1 faire
      j:=j/2
   fintantque
finpour;



  4. j:=n;
pour i allant de 1 à n par pas de 1 faire
   tantque j>1 faire
      j:=j/2
   fintantque
finpour;



  5. m:=1;
pour i allant de 1 à n par pas de 1 faire
   pour j allant de i à n par pas de 1 faire
      pour k allant de i à j par pas de 1 faire
         tantque m<i*j*k faire
            m:=m+1
         fintantque
      finpour
   finpour
finpour;

4
[4 points]
Le fragment d'Exalgo donné calcule en p le i-ème nombre premier; proposer des invariants de chaque boucle qui pourraient servir à démontrer qu'il est correct: 
p:=2;
c:=3;
pour i allant de 2 à n par pas de 1 faire
   repeter
      f:=2;
      tantque f*f <= c ET c mod f > 0 faire
         f:=f+1
      fintantque;
      prem:=(c mod f > 0);
      si prem alors p:=c finsi;
      c:=c+1
   jusqu'à prem
   finrepeter;
finpour;

5
[4 points]
En utilisant la fonction pseudo-aléatoire rand() qui retourne un entier entre 0 et N-1 avec distribution uniforme, écrire une procédure qui construit (dans un tableau sousensemble[]) un sous-ensemble de taille paire de l'ensemble des entiers 1, 2,…, n ; chaque sous-ensemble pair doit être produit avec la même probabilité.

Vous pouvez utiliser sans preuve le fait que parmi les 2i sous-ensembles d'un ensemble de taille i (i > 0), exactement la moitié (2i-1) sont pairs.



File translated from TEX by TTH, version 3.05.
On 27 Nov 2006, 17:33.