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.)

   Réponse

   #define taille 8
   #define vrai 1
   #define faux 0
   
   int T[taille+1][taille+1];
   
   int bon(int i, int j)
   { /* peut-on mettre une dame a position [i][j] sans conflit avec celles
   dans les colonnes plus a gauche? */
      int ii,jj;
      for ((ii=i,jj=j-1);jj>0;jj--) if (T[ii][jj]) return faux;
      for ((ii=i-1,jj=j-1);ii>0&&jj>0;(ii--,jj--)) if (T[ii][jj]) return faux;
      for ((ii=i+1,jj=j-1);ii<=taille&&jj>0;(ii++,jj--)) if (T[ii][jj]) return faux;
      return vrai;
   }
   
   int nombre(int j)
   {
      int i,somme=0;
      if (j==taille) return 1; /*sinon chercher une case dans la colonne j+1*/
      for (i=1;i<=taille;i++) /*essayer de mettre la dame dans la ligne i */
         if (bon(i,j+1))
            {
            T[i][j+1]=vrai;
            somme+=nombre(j+1); /*et ajouter le nombre de facons de completer
                                les colonnes j+2..taille*/
            T[i][j+1]=faux;
            }
      return somme;
   }
   
   main()
   {
      int i,j;
      for (i=1;i<=taille;i++) for (j=1;j<=taille;j++) T[i][j]=faux;
      printf("%i solutions\n",nombre(0));
   }
   
   

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.

   Réponse On peut calculer dans un tableau, disons T, pour chaque entier n (jusqu'à une limite donnée) le nombre d'appels engendrés par un appel de f(n).

   T[1]=1;
   for (i=2;i<=limite;i++);
      {
      T[i]=1;
      for (j=1;j<i;j++)
         if (i%j==0)
            T[i]+=T[j];
      }
   
   

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 */
   
   

   Réponse i > =1 et j < =max et si n est dans T il est a une position [x][y] telle que x > =i et y < =j

   Pour démontrer que cette assertion reste vraie après une itération, il faut démontrer que ``assertion plus la condition du while" avant l'exécution du if (alors) else implique ``assertion" après;
   donc, il faut démontrer que l'assertion reste vraie après exécution de la branche (alors) ou de la branche else.
   Je prends l'exemple de la branche else:
   avant exécution du else les 3 assertions suivantes sont vraies:
   assertion invariant; la condition while; négation de la condition if.
   C'est-à-dire i > =1 et j < =max et si n est dans T il est a une position [x][y] telle que x > =i et y < =j;  et i < =max et j > =1 et T[i][j]!=n;  et T[i][j] < =n
   on conclut:
   T[i][j] < n
   si y < =j T[i][y] < n
   si n est dans T il est a une position [x][y] telle que x > =i+1 et y < =j
   i+1 > =1.
   Et des deux dernières conclusions (et le j < =max), on déduit que l'invariant reste vraie après le i=i+1 (application de la règle pour les affectations).

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;
      
      

      Réponse O(n²)

   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;
      
      

      Réponse O(n³)

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

      Réponse O(logn)

   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;
      
      

      Réponse O(nlogn)

   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;
      
      

      Réponse O(n²)
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.)

   Réponse

   struct noeud
   {
   	struct noeud *Succ, *Pred;
   };
   
   void liberer(struct noeud *P)
   {
      if (P==nul) return;
      while (P->Pred!=nul) P=P->Pred;
      /* P pointe au debut*/
      while (P!=nul)
         {
         struct noeud *temp=P->Succ;
         desallouer(P);
         P=temp;
         }
   }