Licence Informatique
Algorithmique Avancée

10 septembre 2004

1. Un tableau T numéroté de 0 à n contient des éléments qui sont ou blanc ou noir et je veux calculer efficacement le nombre de noir. Cette tâche est simplifiée par le fait qu'il existe probablement de grandes intervalles qui sont uniformément blancs ou noirs et par une fonction disponible couleur(g,d) qui donne la couleur de l'intervalle [g..d] comme blanc ou noir si tout l'intervalle est de la même couleur et comme gris sinon.
   Ecrire une fonction récursive nombre(g,d) qui calcule le nombre de noir pour l'intervalle [g..d] en utilisant couleur() et en divisant l'intervalle en deux parties tant qu'il est gris.

2. le nombre de chiffres 1 dans le développement binaire d'un entier positif n est le nombre pour n/2 plus (1 si n est impair).
   Ecrire une boucle qui calcule ce nombre pour tous les entiers entre 1 et 1000 par programmation dynamique et comparer l'efficacité de cette méthode avec la méthode naive qui calcule le nombre pour chaque entier indépendamment.

3. Le code donné est censé calculer combien de nombres premiers sont facteur de n. Donner des invariants des deux boucles (extérieure et intérieure) qui pourraient être utilisés pour démontrer que le code est correct.

   m=n;
   compteur=0;
   for (f=2;f<=m;f++)
      {
      if (m%f==0)
         {
         compteur++;
         do m=m/f; while (m%f==0);
         }
      }
   
   

4. L'algorithme de Strassen multiplie deux matrices (

   A11	A12
   A21	A22

   ) et (

   B11	B12
   B21	B22

   ) de la façon suivante:

   P1=(A12-A22)(B21+B22);
   P2=(A11+A22)(B11+B22);
   P3=(A11-A21)(B11+B12);
   P4=(A11+A12)B22;
   P5=A11(B12-B22);
   P6=A22(B21-B11);
   P7=(A21+A22)B11;
   C11=P1+P2-P4+P6;
   C12=P4+P5;
   C21=P6+P7;
   C22=P2-P3+P5-P7;
   
   

   pour obtenir le produit (

   C11	C12
   C21	C22

   )

   1. Démontrer que l'élément C11 est correctement calculé.
   2. Combien de multiplications d'éléments de base (par exemple des float) sont effectuées quand cet algorithme est utilisé récursivement pour multiplier deux matrices de taille

      1. 2 ×2
      2. 4 ×4
      3. 8 ×8

5. Une liste est construite de structures qui contiennent un champs prochain qui est un pointeur vers une structure du même type. On veut décider si une liste est ``normale'' (terminée par un pointeur nul) ou ``circulaire'' (une structure contient un pointeur vers une autre qui est déjà dans la liste). Pour faire ça on va utiliser la méthode de deux pointeurs qui parcourent la liste dans une boucle où l'un se déplace deux fois plus vite que l'autre. Si la liste est circulaire, après un certain temps, les deux pointeurs seront dans le cycle et forcément le plus vite va rattraper l'autre; sinon le plus vite va arriver au pointeur nul.

   Ecrire la fonction qui décide si une liste (donnée par un paramètre pointeur) est circulaire ou non.