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 : 12 janvier 2006 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

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

ii. [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 :

   i. 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;
  ii. i:=1;
     j:=0;
     tantque j<n faire
        i:=i+1;
        j:=j+i
     fintantque;
  iii. pour i allant de 1 à n par pas de 1 faire
        j:=i;
        tantque j>1 faire
           j:=j/2
        fintantque
     finpour;
  iv. j:=n;
     pour i allant de 1 à n par pas de 1 faire
        tantque j>1 faire
           j:=j/2
        fintantque
     finpour;

1/2

  v. 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 2^{i} sous-ensembles d’un ensemble de taille i (i > 0), exactement la moitié (2^{i−1}) sont pairs.

2/2