Année 2005-2006 Session de SECONDE SESSION 2005-6

GU : Licence Sciences Technologies (semestre 5) UE : INF209 Épreuve de : Algorithmique Avancée Date : 14 juin 2006 Durée : 3h

Documents autorisés

Épreuve de Monsieur Robson

1 [4 points]

Dans une ville dont les rues forment un quadrillage parfaitement rectiligne orienté Nord-Sud et Est-Ouest, les intersections sont numérotées de 0 à n du Sud au Nord et de 0 à m de l’Ouest à l’Est ; on veut calculer le plus court temps pour voyager de (m, n) à (0, 0) en ne faisant que des déplacements vers le Sud ou vers l’Ouest. Deux tableaux de deux dimensions S et O donnent pour chaque intersection le temps pour aller au voisin dans les directions Sud et Ouest respectivement. Donner deux méthodes de calculer ce plus court temps :

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

ii. [2 points] par programmation dynamique

2 [3 points]

Ecrire une procédure ou fonction qui construit une copie identique d’une liste passée en paramètre (et formée par des enregistrements contenant chacun un entier et un pointeur vers le prochain ou un pointeur nul.) Vous pouvez l’écrire en C (en utilisant malloc ou une fonction analogue) ou en Exalgo (en utilisant allouer.)

3 [5 points]

Quel est (en notation O()) le temps de calcul des 5 séquences suivantes :

   i. pour i allant de 1 à n par pas de 1 faire
        pour j allant de i à n par pas de i faire
           /* une opération de temps constant */
        finpour
     finpour;
  ii. i:=1;
     j:=0;
     tantque j<n faire
        i:=i*2;
        j:=j+i
     fintantque;
  iii. pour i allant de 1 à n par pas de 1 faire
        j:=i;
        tantque j>1 faire
           j:=j-1
        fintantque
     finpour;
  iv. j:=n;
     pour i allant de 1 à n par pas de 1 faire
        tantque j>1 faire
           j:=j/2
        fintantque;

1/2

     j:=i
     finpour;
  v. 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
              m:=1;
              tantque m<i*j*k faire
                 m:=m+1
              fintantque
           finpour
        finpour
     finpour;

4 [4 points]

Donner deux boucles imbriquées qui calculent le produit de tous les éléments d’une matrice carrée de nombres réels. Pour chacune des deux boucles (externe et interne), donner un invariant qui puisse démontrer sa correction. (On ne vous demande pas l’écriture de la démonstration.)

5 [4 points]

En utilisant la fonction rand() qui à chaque appel donne un entier pseudo-aléatoire dans l’intervalle [0, N] pour une grande constante N, écrire des instructions pour appliquer une permutation aléatoire aux éléments d’un tableau A de taille m. (Autant que possible, chaque permutation devrait être choisie avec la même probabilité.)

2/2