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.