Structures de Contrôle et Complexité

1. Ecrire un programme qui affiche la liste des nombres premiers inférieurs à n.
   [corrigé]

2. Faire une méthode estPermutation(int[] perm) qui admet comme argument un tableau perm et qui vérifie qu'il définit une permutation des entiers entre 0 et n-1 où n=perm.length (autrement dit, que toutes les entrées sont comprises entre ces bornes et représentées une et une seule fois). Faire une méthode de complexité O(n). Faire une méthode qui engendre une permutation aléatoire de n éléments de complexité O(n).
   On pourra se servir des méthodes
   • public static int[] chaineVersEntier(String[] chaineTab)
   • public static void afficheEntierTab(int[] entierTab)
   • public static int[] copieEntierTab(int[] entierTab)
   de l'exercice 2 du TP1 (voir son corrigé).
   [Même exercice que l'exercice 4 du TP1, voir son corrigé]

3. Etant donnée une permutation, écrire une méthode qui donne la liste de ses cycles ainsi que sa parité.
   [Même exercice que l'exercice 5 du TP1, voir son corrigé]

4. Calculer l'ordre d'une permutation en temps (quasiment) linéaire.
   [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)?
   [corrigé]