Complexité, Récursivité

1. On cherche à former la liste des nombres premiers inférieurs ou égaux à n. (Voir exercice 1 du TP2 et son corrigé.) On suppose que l'on a un tableau crible de boolean de n+1 éléments ainsi que des varirables d'entiers i, j et k. Au départ, tous les termes de crible sont initialisés à true. On considère les boucles suivantes

   boucle 1:
     crible[0]=false;
     crible[1]=false;
     for(i = 2 ; i <= n ; i++) if(crible[i])
       for(j = 2*i ; j <= n ; j += i) crible[j]=false;
   
   boucle 2:
     crible[0]=false;
     crible[1]=false;
     for(i = 2 ; i <= n ; i++)
       for(j = 2*i ; j <= n ; j += i) crible[j]=false;
   
   boucle 3:
     crible[0]=false;
     crible[1]=false;
     for(i = 2 ; i <= n ; i++) if(crible[i])
       for(j = i+1 ; j <= n ; j++) if((j%i) == 0)
         crible[j]=false;
   
   boucle 4:
     crible[0]=false;
     crible[1]=false;
     for(i = 2 ; i <= n ; i++)
       for(j = 2 ; j < i; j++) if((i%j) == 0)
         crible[i]=false;
   
   boucle 5:
     crible[0]=false;
     crible[1]=false;
     for(i = 2 ; i <= n ; i++) {
       k = (int) Math.sqrt(i); // racine carree de i
       for(j = 2 ; j <= k ; j++)
         if((i%j) == 0) crible[i]=false;
     }
   

   A la fin de ces cinq boucles, crible[i] indique si i est premier ou nom. Quelle est la complexité de ces algorithmes?
   [corrigé]

2. Ecrire une méthode récursive

   static int pgcd(int a,int b)
   

   qui calcule le pgcd de deux entiers. Proposer une méthode récursive et une méthode itérative.
   [corrigé]

3. Calcul des coefficients binomiaux.
   • Ecrire une méthode

     static int binomial(int n,int p)
     

     qui calcule le nombre de sous-ensembles de p éléments dans un ensemble de n. Proposer une méthode récursive à partir de la relation de Pascal
     binomial(n,p) = binomial(n-1,p-1) + binomial(n-1,p).
     Quelle est sa complexité?
   • Proposer une méthode à partir de la relation
     binomial(n,p) = ( n(n-1)...(n-p+1) ) / ( p(p-1)...1 ).
   • Ecrire une méthode

     static int[][] tb_binomial(int n)
     

     qui retourne une table de tous les coefficients binomiaux jusqu'à n. Quelle est sa complexité?
   
   [corrigé]
   [solution originale d'un élève]

4. Ecrire une méthode

   static int surj(int n,int p)
   

   qui calcule le nombre de surjections d'un ensemble de n éléments dans un ensemble de p. On pourra se servir de la relation
   surj(n,p) = p.(surj(n-1,p) + surj(n-1,p-1)).
   
   [corrigé]

5. Ecrire une procédure qui compose deux permutations données. Ecrire une procédure qui itère m fois une permutation sur n éléments. Comment le faire avec une complexité de O(n log m)?
   On pourra se servir des méthodes de l'exercice 2 du TP1 (voir son corrigé).
   [Même exercice que l'exercice 5 du TP2, voir son corrigé]