Licence Informatique
Algorithmique Avancée

jeudi, 6 janvier 2005

1. Je veux calculer le nombre de façons de placer 8 dames sur un échiquier (un carré de taille 8 cases par 8) sans avoir jamais deux sur la même ligne, ou deux sur la même colonne, ou deux sur une même ligne diagonale. Je veux le faire en utilisant une fonction récursive avec deux paramètres, l'un un tableau représentant un échiquier avec quelques colonnes à gauche déjà contenant une dame (sans avoir deux dans des positions interdites) et l'autre le nombre de ces colonnes à gauche (entre 0 et 8); le résultat de la fonction devra être le nombre de façons de compléter ce remplissage partiel du tableau (éventuellement 0).
   Ecrire une version de cette fonction récursive.

   (Votre fonction pourrait très bien avoir d'autres paramètres si vous le jugez utile.)

2. J'ai une fonction définie pour les entiers n strictement positifs par le code suivant (plusieurs détails supprimés):

   int f(int n)
   {
   int somme=0, i;
   if (n==1) return 1;
   for (i=1;i<n;i++)
      if (n%i==0) /*si i est facteur de n*/
      somme+=g(f(i)); /*g une fonction definie ailleurs*/
   return somme;
   }
   
   

   Je veux savoir combien d'appels récursifs seront effectués quand f(n) est appelé pour des grandes valeurs de n.

   Décrire comment la programmation dynamique peut aider à faire ce calcul de façon efficace.

3. Le code suivant est censé trouver la position d'un entier n dans un tableau T[ ][ ] (indicé de 1 à max dans chaque dimension), sur la précondition que les lignes et colonnes de T sont triés en ordre croissant.
   Donnez un invariant de la boucle qui suffirait pour démontrer le code correct et décrivez comment on pourrait démontrer que l'invariant reste vrai après une itération étant donné qu'il est vrai avant.

   i=1;
   j=max;
   while (i<=max && j>=1 && T[i][j]!=n)
           if (T[i][j]>n)
                   j--;
           else
                   i++;
   /*postcondition: si n est dans T il est a la position [i][j];
    * sinon i>max ou j<1 */
   
   

4. Déterminer (en fonction de n à O( ) près) le temps de calcul de chaque boucle contenant un commentaire /**/ :
   (P() est une procédure dont le temps de calcul est constant.)

   1. pour i allant de 1 a n*n par pas de 1 faire P(); /**/ finpour;
      
      

   2. pour i allant de 1 a n par pas de 1 faire 
         pour j allant de 1 a i*i par pas de 1 faire P(); finpour; /**/
      finpour;
      
      

   3. i:=1;
      tant que i<n*n faire i:=i*2; /**/
      fintantque;
      
      

   4. pour i allant de 1 a n par pas de 1 faire 
         j:=1;
         tant que j<i faire j:=j*2;
         fintantque; /**/
      finpour;
      
      

   5. pour k allant de 1 a n par pas de 1 faire
         i:=1;
         tant que i<k faire
            i:=i*2;
            pour j allant de 1 a i par pas de 1 faire P(); finpour; /**/
         fintantque;
      finpour;
      
      

5. Ecrire une fonction qui libère l'espace utilisé par une structure composée de noeuds, reliés par deux pointeurs Succ et Pred dans chaque noeud. La structure complète est une liste où le Succ de chaque noeud pointe à son successeur, sauf dans le dernier noeud ou ce pointeur est nul; le Pred de chaque noeud pointe à son prédecesseur, sauf dans le premier noeud ou ce pointeur est nul; le paramètre de la fonction est un pointeur à un noeud de la structure, pas forcément le premier.

   (L'espace utilisé pour un noeud est libéré par un appel de desallouer() avec comme paramètre un pointeur au noeud.)